検索方法、検索装置、索引生成方法、索引生成装置
【課題】 索引を生成する方法と装置、検索方法と検索装置を提供する。
【解決手段】 索引エントリは、少なくとも検索項目に対応する検索項目識別子、１又は複数の検索情報から生成された１又は複数の索引項目、検索情報についての累積情報を有する。累積情報は、検索情報を含む情報の暗号文を累積し、あるいは検索情報を含む情報からマッピングすることにより取得されたデータを累積することにより生成される。検索時、索引項目と累積情報が検索者に提供される。検索者は索引項目から検索情報を抽出し、累積情報を使用して抽出された検索情報が完全かどうかを検証する。一例として、累積情報は暗号化された逆索引に組み込まれる。
【解決手段】 索引エントリは、少なくとも検索項目に対応する検索項目識別子、１又は複数の検索情報から生成された１又は複数の索引項目、検索情報についての累積情報を有する。累積情報は、検索情報を含む情報の暗号文を累積し、あるいは検索情報を含む情報からマッピングすることにより取得されたデータを累積することにより生成される。検索時、索引項目と累積情報が検索者に提供される。検索者は索引項目から検索情報を抽出し、累積情報を使用して抽出された検索情報が完全かどうかを検証する。一例として、累積情報は暗号化された逆索引に組み込まれる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に情報処理技術に関し、特に、検索方法、検索装置及び検索結果についての十分検証を可能にする索引の生成方法と装置に関する。
【背景技術】
【０００２】
様々なアプリケーションプログラムにおいて、大量の情報についての検索が、特別条件を満たす情報を取得するために必要である。一般に、索引は、もとの情報について予め構築されている。その後、検索要求に応じて一致する項目を見つけ出すために索引内で検索が実行され、その結果、関連情報が取り出される。様々な理由から、検索者は、検索から完全な結果情報、すなわち、検索条件を満たす全ての情報を得たいと希望する。しかしながら、索引作業と検索についての既存の手法は、検索の完全性を保証しない。
【０００３】
コンピュータネットワークと通信技術の幅広い利用に伴い、データ所有者は、多くの場合、第三者機関によって維持されるサーバ上にデータファイルを格納する。そのような状況では、サーバ上に格納されたデータファイルを検索するサービスも、第三者機関によって提供されている。すなわち、検索サービスを提供する第三者機関は、検索者からの要求に応じて索引を使用することによりサーバ上に格納されたデータファイルを調べ、検索者に検索結果を提供する。検索における実質的な作業が第三者によって実行されるがため、検索の正確さおよび完全性が検証されかつ保証されるような状況がさらに一層要望されている。
【０００４】
さらに、プライバシーと安全性の懸念により、データファイルは、多くの場合暗号化された後に格納される。特に、ストレージサービスの上記のケースにおいては、ファイルの内容が無許可のユーザ（場合によっては、ストレージサービスと検索サービスを提供する第三者を含む）に露呈するのを防ぐために、ファイルはしばしば暗号化テキスト形式でサーバ上に格納される。しかしながら、ファイルが暗号化されたストレージは、ファイルの検索を困難にし、検索結果の正確さおよび完全性を検証することを特に難しくする。
【０００５】
本発明は、検索方法と検索装置及び索引生成方法と索引生成装置を提供する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように、索引作業と検索についての既存の手法は、検索結果の完全性を保証しない。また、検索における実質的な作業が第三者によって実行されるがために、検索の正確さおよび完全性が検証されかつ保証されることが望まれている。さらに、ファイルを暗号化してサーバに格納する場合、ファイルの検索を困難にし、検索結果の正確さおよび完全性を検証することを難しくするという問題がある。
【課題を解決するための手段】
【０００７】
本発明による索引生成方法は、検索項目に対応する検索項目識別子を生成するステップと、検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成するステップと、１以上の検索情報について累積情報を生成するステップと、索引を形成するために少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成するステップとを含む。
【０００８】
本発明による索引生成装置は、検索項目に対応する検索項目識別子を生成する検索項目識別子生成ユニットと、検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成する索引項目生成ユニットと、１以上の検索情報について累積情報を生成する累積情報生成ユニットと、少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成して、索引を形成する索引形成ユニットとを備える。
【０００９】
本発明による検索方法は、検索要求を生成するステップと、１以上の索引項目および１つの累積情報を受信するステップと、受信した１以上の索引項目から１以上の検索情報を抽出するステップと、受信した累積情報によって抽出した検索情報を検証するステップとを含む。
【００１０】
本発明による検索装置は、検索要求を生成する検索要求ユニットと、１以上の受信した索引項目から１以上の検索情報を抽出する検索情報抽出ユニットと、受信した累積情報によって抽出した検索情報を検証する検証ユニットとを備える。
【発明の効果】
【００１１】
本発明の方法によれば、累積情報を使用することにより、検索結果の完全性および正確さを証明することが可能となる。本発明は、逆索引、特に暗号化された逆索引に適用することができる。プライバシー・レベルに設定された暗号化逆索引により、良好なプライバシー管理及び機密性が検索結果の検証に基づいて提供される。
【図面の簡単な説明】
【００１２】
本発明の前述した特徴及び他の特徴は、以下の説明と添付図面とを参照することにより、さらに明らかになるであろう。
【図１】検索システムの一例を示すブロック図である。
【図２】本発明の実施の形態によるデータ所有者端末の構成例の概略を示すブロック図である。
【図３】本発明の実施の形態による索引を生成する処理を説明するフローチャートである。
【図４】本発明の実施の形態による検索者端末の構成例の概略を示すブロック図である。
【図５】本発明の実施の形態による検索処理を説明するフローチャートである。
【発明を実施するための形態】
【００１３】
本発明の種々の特徴および典型的な実施の形態については、図面を参照して以下にその詳細を説明する。以下の詳細な説明においては、多くの具体的な詳細が本発明を十分に理解するために提供される。しかしながら、これらの具体的詳細のうちのいくつかがなくとも本発明を実現できることは、当業者にとって明白である。実施の形態の以下の説明は、本発明の一例を示すことにより、本発明をよりよく理解するためになされている。本発明は、以下に説明されたどんな特定の構成およびアルゴリズムにも限定されない。本発明の範囲から外れない限り、構成要素、構成部品およびアルゴリズムのいかなる変形、代替案および改良も包含する。図面および以下の説明において、周知の構成および技術については、本発明を不必要に不明瞭にしないために詳細には説明しない。
【００１４】
図１は、本発明を適用した典型的な検索システムを概略的に示すブロック図である。
図１に示すように、データ所有者の装置或いは端末、サービスプロバイダによって管理されるサーバおよび１以上の検索者の装置或いは端末が、通信ネットワークによって接続され、互いに通信することができる。データ所有者は、ファイルおよびそれらのファイルの索引をサーバに格納する。サーバは、検索者端末からの検索要求に応じて索引を使用することによりファイルの検索を実行し、検索者に検索結果を提供する。
【００１５】
ここで使用される用語「サーバ」は、ストレージサービスと検索サービスの両方を提供する単一の装置、あるいはストレージサービス、データ検索、ユーザー管理などの種々のサービスを負担し、又はそれらのサービスを分担する互いに隣接し又は遠隔に位置する複数の装置の集合を意味する。
例えば、データ所有者端末は、ストレージサーバ上にファイルを格納し、ストレージサーバと通信し合うファイル検索サーバ上に索引を格納する。説明を簡単にするために、説明と図面においてサービスを提供するそのような全ての装置を「サーバ」と呼ぶことにする。
データ所有者端末とサーバは、図において個別の装置として示されている。しかしながら、以下に説明するように、本発明におけるデータ所有者端末とサーバの両機能は、単一の装置によって実現できることを十分に理解できるであろう。
【００１６】
データ所有者と検索者の装置或いは端末は、それぞれ、情報を処理することができかつ情報を通信することができる装置として実現される。例えば、パーソナルコンピュータ（ＰＣ）、携帯情報端末（ＰＤＡ）、スマートフォン（smart mobile phone）或いはその他のデータ処理装置等である。
一般に、サーバは、データを格納し維持することが可能であり、また、端末によるデータの条件付きアクセスを可能にする、サービスプロバイダによって管理される単一の装置或いは装置の集合として実現される。
【００１７】
図示のシステムにおいて、データ所有者は、自身のファイルに索引を付け、サーバ上にファイルと索引を格納する。検索時、検索者は、検索項目の情報（例えば、検索項目識別情報）を含む要求を送信する。サーバは、検索項目の情報に従って一致する索引エントリについて索引を調べ、関連情報の検索のために、索引エントリ中の索引項目（検索項目に関連する）を検索者に提供する。
特に、本発明による解決方法においては、累積情報も、検索結果の完全性の証明のために索引エントリに含まれている。サーバは、また検索者に索引エントリ中の累積情報（Ａｃｃｕｍｕｌａｔｏｒ）を提供する。検索者は、累積情報の利用により検索結果が完全で正確かどうかを検証する。
【００１８】
一般的な用途において、キーワードに基づいてそのキーワードを含んでいるファイルを検索する場合、逆索引がしばしば利用される。
以下の説明において、逆索引の利用を例として挙げる。しかしながら、本発明が、同様の方法で非逆索引に適用可能であることも言うまでもない。
【００１９】
図２は、本発明の実施の形態によるデータ所有者端末１００の構成例を示している。
図２に示すように、データ所有者端末１００は主に検索項目識別情報生成ユニット１０１、索引項目生成ユニット１０２、累積情報生成ユニット１０３および索引形成ユニット１０４を含む。
【００２０】
図３は、本実施の形態によるデータ所有者端末１００によって索引を生成する処理の概略を示す。
【００２１】
まず、ステップＳ２０１で、データ所有者のファイルに関する検索項目がセットされ、検索項目識別子生成ユニット１０１は検索項目に従ってそれぞれの検索項目識別情報を生成する。逆索引の利用において、検索項目はキーワードである。
例えば、データ所有者端末は、各ファイル内のキーワードを抽出し、検索項目としてそれらを採用する。あるいは、データ所有者が、端末への入力によって検索項目を手作業でセットする。
互いに異なるキーワードが、検索項目としてセットされれば、各検索項目(keyword) KWについて、検索項目識別子生成ユニット１０１が検索項目の対応する一意の識別子ＫＬを生成する。
【００２２】
検索項目識別子ＫＬは、例えば、検索項目ｋＷそのもの、あるいは検索項目ｋＷにマッピングされるデータである。暗号化された索引の利用において、検索項目識別子ＫＬは、ｋＷの暗号化テキスト、あるいはｋＷの情報を含んでいるデータである。
例えば、ＫＬは次のように計算される。
KL = Hash(MEK||KW) （式１）
ここで、Hash()はハッシュ関数を表わす。MEKは特定のパラメータ（例えば、データ所有者の親鍵（マスターキー））である。
「||」は、事前に設定された順序の文字列あるいは数字の組合せを表わす。
あるいは、KL = E(EKey, KW)
ここで、EKeyは特定の鍵である。E(EKey, KW)は、EKeyによるKWの暗号化を表す。
【００２３】
ステップＳ２０２で、各検索項目に関する検索情報がセットされ、索引項目生成ユニット１０２は、各検索情報に対応する索引項目を生成する。検索項目はそれぞれ１つあるいは複数の検索情報に対応する。検索情報は、その検索項目と一致する検索結果を提供するための何らかの情報である。
例えば、逆索引においては、検索項目（キーワード）ｋＷについて、キーワードｋＷを含む各ファイルのファイル名あるいは場所（あるいは、そのファイルに関する他の情報）が、検索項目に関する１つの検索情報としてセットされる。
例えば、検索項目ｋＷについて、キーワードｋＷを含んでいるｎ個のファイルのファイル名は、検索項目ｋＷに関するｎ個の検索情報I1, I2, …Inのようにセットされる。
【００２４】
暗号化ストレージの利用において、データ所有者がサーバ上にファイルの平文ではなく暗号化テキストを格納することに留意する必要がある。その場合、上述のファイル名は暗号化されたファイルの暗号文ファイル名かもしれない。
【００２５】
各検索情報について、索引項目生成ユニット１０２は、検索情報を含む、あるいは検索情報が導き出される索引項目を生成する。
１個の検索情報Ij (j＝1, 2,…, n)について、索引項目生成ユニット１０２は索引項目FLjを生成する。
索引項目FLjは、例えば、検索情報Ijそのもの、あるいはある変換によって検索情報Ijが取得される何らかの値である。暗号化索引の利用において、索引項目FLjは情報Ijを含む暗号文データかもしれない。
例えば、索引項目FLjは以下のように計算される。
FLj = E(EKey, Ij||Key) （式２）
ここで、EKeyは特定の鍵である。Keyは、特定のパラメータ（例えば、ファイルを暗号化するのにデータ所有者によって使用される鍵）である。E(EKey, Ij||Key)は、EKeyによるIjとKeyの組合せの暗号化を表わす。
【００２６】
次に、ステップＳ２０３で、累積情報生成ユニット１０３は、検索結果の完全性の検証のために、検索項目に関するすべての検索情報を累積する累積情報を生成する。
各検索情報を含む検索結果が完全かどうかを検索者端末が検証することができさえすれば、累積情報は様々な方法で生成することが可能である。
累積情報の演算は、排他的ＯＲ（ＸＯＲ）演算、剰余演算(modular operation)および累積シグネチャ（Accumulation
signature）の具体例を用いて以下に説明する。
当業者は、累積情報を生成するために他のアルゴリズムを利用可能であることは十分に理解するであろう。
具体例１−ＸＯＲ演算
【００２７】
検索項目KWに関するすべての検索情報I1, I2,
…Inについて、累積情報生成ユニット１０３は、ＸＯＲ演算により完全性累積情報ICを以下のように生成する。
【数１】
ここで、
【数２】
はＸＯＲ演算を表わす。
【００２８】
式３は、反復演算によって以下のように計算される。
set IC = 0
for j=1 to n
【数３】
next j
具体例２−剰余（Mod）演算
【００２９】
剰余演算により、累積情報生成ユニット１０３は完全性累積情報ＩＣを以下のように生成する。
【数４】
あるいは
【数５】
ここで、pは、大きな素数である。
【００３０】
式４は、反復演算によって以下のように計算される。
set IC = 1
for j=1 to n
IC = (IC * Ij)
mod p
next j
【００３１】
式５は、反復演算によって以下のように計算される。
set IC = 0
for j=1 to n
IC = (IC + Ij)
mod p
next j
具体例３−累積シグネチャ（Accumulation
signature）
【００３２】
以下のセキュリティパラメータ（security
parameter）があらかじめセットされると想定する。
大きな素数p、位数ｐの２つのグループG1とG2、G1とG2のジェネレータであるg1およびg2、p未満でpと互いに素であるすべての正整数の集合であるZp*、G1×G2→GTと定義される双線型写像（bilinear mapping）e
双線型写像は以下の特徴を有する。
（１）双線型性 (bilinearity)
全てのg1およびg2及びZp*に属する全てのaとbについて、
e(g1a,
g2b) = e(g1, g2)abの関係がある。
（２）非縮退（nondegeneracy）
g1=0 if e(g1, g2)
= 1 g2はG2に属する。
Gに対して{0,1}*をマッピングするハッシュ関数がセットされ、乱数KがZp*から選択される。秘密キーskがセットされる。
ここで、g2と乱数Kは検索者に公開される。そうでなければ、g2Kが検索者に公開される。
【００３３】
次に、累積情報生成ユニット１０３は累積情報ICを以下のように生成する。
【数６】
【００３４】
式６は、反復演算によって以下のように計算される。
set IC = 1
for j = 1 to n
IC = (IC * H(Ij)1/(sk+K))
mod p
next j
【００３５】
累積情報が生成された後、索引形成ユニット１０４は、各検索項目について索引エントリを生成する。索引エントリはそれぞれ、少なくとも、検索項目の検索項目識別子と、検索項目に関する全ての索引項目と、検索項目に関する全ての検索情報を累積することにより取得された累積情報を含んでいる。
次に、索引形成ユニット１０４は、各索引エントリを含む索引を形成する。それぞれ異なる索引項目の累積が各累積情報を生成するため、乱数Ｋはそれぞれ別に選択される場合があることに留意すべきである。
【００３６】
このように、累積情報を含む索引が、データ所有者端末１００で生成される。その後、データ所有者端末は、ファイルと生成された索引を将来の利用のためにサーバに格納することが可能である。
【００３７】
累積情報の利用について、図４及び図５を参照して以下に説明する。
【００３８】
図４は、本発明の実施の形態による検索者端末３００の構成例を示している。図４に示すように、検索者端末３００は、主に、検索要求ユニット３０１と、検索情報抽出ユニット３０２と、検証ユニット３０３を含む。
【００３９】
図５は、本実施の形態による検索を実行する検索者端末３００の処理の概略を示す図である。
【００４０】
まず、ステップＳ４０１で、検索要求ユニット３０１は、少なくとも１つの検索項目識別子を含む検索要求を生成し、サーバに検索要求を送信する。
検索者端末は、データ所有者から検索項目識別子を取得し、あるいは、データ所有者から検索項目識別子の計算に必要なデータを取得し、データ所有者端末で索引を形成する時に検索項目識別子を生成する方法に相当する方法によって検索項目識別子を計算する。
【００４１】
検索要求を受け取った後に、サーバは、受信した検索項目識別子と一致する検索項目識別子を有する索引エントリのために索引を調べる、検索者端末にその索引エントリ内の累積情報だけでなく索引項目もすべてを返却する。
認証が必要である場合、サーバは、上述のルックアップを実行する前に検索者を認証することも可能である。サーバが一致する索引エントリを発見できず、あるいは検索者の認証に失敗すると、サーバは、否定的な結果を返却するか、あるいはエラー処理に移行し、検索者端末に通知を送信する。そのような状態において、検索者端末は、エラー手順を実行し、例えば、手順を再試行しあるいは終了する。
【００４２】
サーバが検索結果を返却すれば、ステップＳ４０２で、検索者端末は、対応する累積情報だけでなく１つ或いは複数の索引項目も受け取る。
【００４３】
次に、ステップＳ４０３で、検索者端末の検索情報抽出ユニット３０２が、受信した各索引項目から検索情報を抽出する。上述したように、索引項目が検索情報そのものかもしれない。その場合、検索情報が直ちに取得される。
索引項目が検索情報の暗号文の形式であるか、あるいは変換によって検索情報が取得される値である場合、検索情報抽出ユニット３０２は対応する暗号解読あるいは変換によって検索情報を抽出する。暗号解読あるいは変換用に必要なパラメータは、データ所有者から取得することが可能である。
【００４４】
各索引項目に含まれる検索情報を取得した後、検索者端末の検証ユニット３０３は、受信した累積情報を使用することにより検索結果が完全でかつ正確かどうかを検証する（ステップＳ４０４）。
【００４５】
正確であると確認されれば、処理手続きはステップＳ４０５に移行し、取得した検索情報が、例えば、検索情報に従って対応するファイルを引き出すことあるいは追加の情報の処理に使用される。
検索情報の利用については、本発明と直接関係しないので、対応するユニットあるいはモジュールは、図面に示しておらず、かつその詳細な説明も省略している。
しかしながら、特定の用途に応じて必要とする処理を実行するために、他の必要なユニットあるいはモジュールが追加されるであろうことは十分に理解されるべきである。
【００４６】
検証が否定的であれば、不完全あるいは不正確であるとの検索結果が示される。多くの場合、それはデータの改ざんあるいはデータ通信におけるエラーに起因する。そのような状態において、処理手続きは、エラー処理のためにステップＳ４０６に移行し、例えば、検索要求の再送、再送信の要求、あるいは処理の終了を行う。
【００４７】
累積情報を用いた検証方法については、累積情報の生成においてデータ所有者端末で使用された方法に応じて決定される。
【００４８】
例えば、検証ユニット３０３は、データ所有者端末によって使用された方法と同じ方法によって抽出した検索情報に基づいて累積情報を計算し、その累積情報をサーバから受信した累積情報と比較する。
それらが一致すれば、検証が肯定的となり、そうでなければ、検証は否定的となる。幾つかの具体例を以下に示す。
【００４９】
ここで、検索情報抽出ユニットが受信した全ての索引項目から検索情報I'1, I'2,
…I'mを抽出すると仮定する。
累積情報が上記の式３に従って計算される場合、検証ユニット３０３は、
【数７】
,を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
【００５０】
同様に、累積情報が上記の式４に従って計算される場合、検証ユニット３０３は、
【数８】
を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
あるいは、累積情報が上記の式５に従って計算される場合、検証ユニット３０３は、
【数９】
を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
【００５１】
上記の式６に従って累積シグネチャ（Accumulation signature）の形式で累積情報が生成される場合、検証は累積シグネチャを検証することにより実行される。
特に、検証ユニット３０３は、
【数１０】
を計算し、関係e(IC', g2) = e(IC, g2sk * g2K)が成り立つかどうかを検証する。
関係が成り立てば、正確であると検証され、そうでなければ、検証は否定的となる。
【００５２】
累積情報を生成するために他の方法が使用される場合、検証ユニット３０３は、対応する方法を用いることにより検索情報が累積情報により完全かどうか検証する。
【００５３】
ある状況では、索引を更新する必要が発生する。例えば、新たなファイルが追加され、あるいは、既存ファイルが削除されと、検索情報が変換する。その結果、索引は正確な検索を保証するために更新される。索引項目はファイルの追加あるいは削除に応じて更新され、同時に、関連する索引エントリ内の累積情報もそれに応じて更新される。
【００５４】
例えば、一つの新たな検索情報Iaを検索項目KWに対応する索引エントリに追加する必要があるならば、上記の式３に従って計算された累積情報ICは、式７のように更新される。
【数１１】
上記の式４に従って計算された累積情報ICは、式８のように更新される。
ICupdated = (IC * Ia) mod p （式８）
上記の式５に従って計算された累積情報ICは、式９のように更新される。
ICupdated = (IC＋Ia)
mod p （式９）
また、上記の式６に従って計算された累積情報ICは、式１０のように更新される。
ICupdated = [IC * H(Ia)1/(sk+K)] mod p （式１０）
【００５５】
上記の式６に従って計算された累積情報ICについては、以下に示すように別の方法を用いて更新することが可能である。
まず、新たな公開乱数K'を選択し、次に、更新累積情報ICupdatedを以下のように計算する。
IC updated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’) （式１１）
【００５６】
他方、一つの既存の検索情報が検索項目KWに対応する索引エントリから削除されるならば、
上記の式３に従って計算された累積情報ICは、式１２のように更新される。
【数１２】
上記の式４に従って計算された累積情報ICは、式１３のように更新される。
ICupdated = (IC * Ib-1) mod p （式１３）
上記の式５に従って計算された累積情報ICは、式１４のように更新される。
ICupdated = (IC - Ib) mod p （式１４）
また、上記の式６に従って計算された累積情報ICは、式１５のように更新される。
ICupdated = [IC * H(Ib)-1/(sk+K)] mod p （式１５）
【００５７】
上記の式６に従って計算された累積情報ICについては、以下に示すように別の方法を用いて更新することが可能である。
まず、新たな公開乱数K'を選択し、次に、次に、更新累積情報ICupdatedを以下のように計算する。
IC updated = [IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’) （式１６）
【００５８】
索引エントリの更新はデータ所有者端末によって実行することが可能であり、更新された索引エントリは、以前のものと置き換えるためにサーバに送信される。あるいは、サーバによって更新を実行することが可能である。従って、索引更新のための更新ユニット（図示せず）は、データ所有者端末あるいはサーバに設けられる。
【００５９】
本発明による索引における累積は様々な索引に適用することが可能である。例えば、累積情報は暗号化索引に同様に適用することが可能である。例えば、索引エントリ内の索引項目は検索情報を含む情報を暗号化することにより取得された暗号文であり、また、累積情報は、検索情報が暗号化ファイルの暗号化されたファイル名である検索情報を累積することによって取得される。
そのような暗号化索引においては、データ所有者および権限を与えられた検索者を除いて、サーバを含む他の当事者は、索引項目を暗号化して検索情報を得ることができないし、暗号化処理のシミュレーションによって正確に解読することができる索引項目を取得することもできない。その結果、索引項目および累積情報の改ざんが防止される。
【００６０】
高速検索可能な暗号化方法を以下に示す。改良した暗号化逆索引が使用され、累積情報が検索結果の完全性の検証を与えるために使用される。
【００６１】
この方法において、データ所有者端末は、同じあるいは異なる鍵で各ファイルを暗号化し、サーバにファイルの暗号文を格納する。この例において、上記検索情報Ijは、ファイルFILEjの暗号化されたファイル名CFNjである。
暗号化されたファイル名に基づいて、サーバは、格納された暗号化ファイルの中で一致するファイルを即座に発見し、要求者にそのファイルを提供する。
【００６２】
指標付けの段階では、検索項目のように挙げられたキーワードKWについて、データ所有者端末は、キーワードKWを含む情報を暗号化することにより、あるいは値にキーワードKWを含む情報をマッピングすることにより、検索項目識別子を計算する。
例えば、MEKがデータ所有者のマスターキーである場合、検索項目識別子はKL = Hash(MEK||KW)のように計算される。
【００６３】
ファイルFILEj (j = 1, 2, … n)がキーワードKWを含むと仮定すると、データ所有者端末は、KWに関連するFILEjの索引項目FLJを以下のように計算する。
FLj = E(EKey, Ij||Kfilej) （式１７）
ここで、KfilejはファイルFILEjのための解読キーである。IjはファイルFILEjの暗号化されたファイル名である。EKeyは、索引項目を生成するための暗号鍵（データ所有者によってセットされる）である。また、E(EKey, Ij||Kfilej)は、IjとKfilejの組合せのEKeyによる暗号化を表わす。
【００６４】
その後、Ij (j = 1, 2, … n)が、検索項目KWの累積情報ICを生成するために累積される。例えば、それは、上述した式３から式６の何れかあるいは他の方法に従って計算される。
【００６５】
その後、少なくともKL、FLj (j = 1, 2, … n)及びICを含む索引エントリが、キーワードKWについて生成される。この索引エントリによって形成された暗号化された逆索引が、サーバに格納される。
【００６６】
データ所有者が検索者にキーワードによる検索を実行させる場合、データ所有者は安全な方法で、検索者に対してキーワードの検索項目識別子KLを公開し、索引項目の解読のための解読キーDKeyを検索者に公開する。
【００６７】
検索の段階では、検索者端末は、サーバに対して検索項目識別子KLを含む検索要求を送信する。
サーバは、受信した検索項目識別子KLに従って、一致する索引エントリについて格納した暗号化索引を調べ、一致する索引エントリに含まれる累積情報ICだけでなく全ての索引項目FLjを検索者端末に返却する。
【００６８】
サーバから各索引項目FLjを受け取った後、検索者端末は、索引項目の解読のためにデータ所有者によって公開された解読キーDKeyにより各索引項目FLjを解読し、暗号化されたファイル名およびファイル、すなわちIj とKfilejの対応する解読キーを取得する。
【００６９】
その後、データ所有者端末は、受信した累積情報ICを使用し、取得した暗号化ファイル名Ijがすべて完全かどうかを検証する。
正確であると認定されれば、検索者端末は、それらの暗号化ファイル名Ijを利用する。例えば、対応する暗号化ファイル名を有する暗号化ファイルを引き出すためにサーバに対して暗号化ファイル名Ijを送信し、その後、対応するファイル解読鍵Kfilejで暗号化されたファイルを解読し、ファイルのプレーンテキストを取得する。検証が否定的であれば、上述したエラー処理を実行する。
【００７０】
上記の説明において、ファイルと検索情報はサーバ上に暗号化された形式で格納される。このため、サーバに対してファイル情報が漏洩することが防止される。
【００７１】
上記の例の改良した形態においては、検索情報Ijから直接累積情報を計算する代わりに、検索情報Ijを含む情報の暗号文あるいは検索情報Ijを含む情報からマッピングされたデータが、累積情報ICを計算し、検証し及び更新するのに、Ijの代わりに使用される。
例えば、Ij' = Ij||Xが、累積情報を計算するのに前述のＩｊの代わりに使用される。ここで、Xは予め設定された情報、例えば、上記の例におけるDKeyである。
また、Ij' = Ij||Xは、上記したＸＯＲ演算、剰余演算等によって累積情報を計算する式のIjの代わりに使用することが可能である。ここで、Xは予め設定された情報、例えば、上記の例におけるDKeyである。
【００７２】
上述したように、索引項目が検索情報を含む情報の暗号文であり、かつ、累積情報が検索情報の累積によって形成されるので、権限外の第三者は索引項目あるいは累積情報を改ざんすることができない。
【００７３】
他の改良した形態において、データ所有者は、異なるプライバシー・レベル（privacy level）を設定し、その異なるプライバシー・レベル毎に別々に索引項目の暗号化キーEKeyと解読キーDKeyを設定することが可能である。
索引を生成する場合、あるプライバシー・レベルで開示することが可能なファイルに関して、そのプライバシー・レベルの索引項目暗号鍵がそのファイルについて索引項目を生成するのに使用される。
このように、検索項目（キーワード）と関連する索引エントリに、異なるプライバシー・レベルの索引項目が存在することになる。このような場面においては、各プライバシー・レベルの索引項目について、累積情報が生成される。
すなわち、１つの検索項目に対応する索引エントリにおいて、ある１つのプライバシー・レベルの累積情報が、そのプライバシー・レベルの全ての索引項目に含まれる検索情報を累積することによって生成される。このようにして、異なるプライバシー・レベルの複数の累積情報が生成される。
【００７４】
上述した改良した方法においては、データ所有者はプライバシー・レベルに応じて検索者に権限を与える。すなわち、検索者のプライバシー・レベルに適した索引項目解読キーDKeyが検索者に公開される。
検索時、検索者は、公開された索引項目解読キーDKeyで、サーバから受信したすべての索引項目のうち、同じプライバシー・レベルの索引項目暗号鍵EKeyを使用してもともと生成された検索項目を解読する。これにより、検索者は、そのプライバシー・レベルの検索項目に関する検索情報を取得することができる。
暗号解読の正確さの検証のために索引項目に所定のフラグを設定することもできる。例えば、索引項目を以下のように生成する。
FLj = E(EKey, FLAG||Ij||Kfilej) (式１８)
ここで、FLAGは検索者に認識されているパラメータである。
これによって、解読された情報内における正しいFLAGの存在を検証することによって、検索者は、暗号解読が正確に実行されているかどうかを判定することができる。
【００７５】
また、暗号解読によって対応するプライバシー・レベルの検索情報を取得した後、検索者は、そのプライバシー・レベルに対応する受信した累積情報を使用することで、そのプライバシー・レベルの検索情報が完全かどうかを検証する。
検索者は、受信した索引エントリに含まれる複数累積情報を使用して検証を実行してもよい。そして、累積情報のいずれかの１つが正しいと確認されれば、検証は肯定的となる。
それは、計算された累積情報が異なるプライバシー・レベルの受信した累積情報と等しくなるという確率が非常に低いためである。
あるいは、索引エントリはセクションに分けられる。すなわち、同じプライバシー・レベルの索引項目は同じセクションに加えられる。その結果として、検索者は、どのセクションで索引項目が正確に解読されているかを判定することで、検証においてどの累積情報を使用するかを決定することができる。
あるいは、検索者が使用すべき正しい累積情報を決定するのを支援するために、各累積情報に付加情報（例えば、プライバシー・レベルを示すパラメータ）を付与することも可能である。
あるいは、サーバは、検索時に、検索者のプライバシー・レベルを判定する処理を実行し、次に、検索者のプライバシー・レベルに応じて対応するプライバシー・レベルの累積情報を検索者に返却する。そのような場合、受信した累積情報から累積情報を選択する処理は検索者にとって不要となる。
【００７６】
本発明によるいくつかの実施の形態について図面を参照して上記のように説明した。しかしながら、本発明は、上記実施の形態で説明した特定の構成および処理に何ら限定されるものではない。上述した構成、アルゴリズム、動作及び処理について、本発明の精神の範囲内で、種々の代替案、変更あるいは変形が可能であることは、当業者によって十分に理解できるであろう。
例えば、上記の説明では、逆索引の具体例について詳細に説明した。しかし、本発明を非可逆索引（non-inverted index）に適用することも可能である。さらに、例えば、上述した例における検索項目は、ファイル名あるいは暗号化されたファイル名でもよいし、また、検索情報は、ファイルに含まれるキーワードあるいは暗号化されたキーワード等でもよい。
非可逆索引において、累積情報は同様の方法で適用することが可能である。
さらに、上述した例では、索引エントリが少なくとも１つの検索項目識別子、索引項目および累積情報を含んでいる。しかしながら、特定のアプリケーションの要求によって他の必要な情報およびデータを索引エントリに追加することも可能である。
【００７７】
本明細書で使用される、いわゆる「ファイル」は、幅の広い概念として解釈されるべきである。それは、例えば、テキストファイル、ビデオ／オーディオ・ファイル、写真／図、および他のデータあるいは情報を含むが、これらに限定されない。
【００７８】
データ所有者端末、検索者端末およびサーバの構成として、相互に接続された幾つかのユニットを図面に示した。
これらのユニットは、それらの間で信号を転送するために、バスあるいは他の信号ライン、あるいは無線によって接続することができる。しかしながら、各装置に含まれる構成要素は、上述したユニットに限定されないし、特定の構成については変更しあるいは差し替えることが可能である。各装置は、装置の操作者に対して情報を表示するための表示ユニット、操作者の入力を受け付ける入力ユニット、各ユニットの演算を制御する制御装置、他の記憶装置等のような、他のユニットを含むことも考えられる。それらの構成要素については、当業界において公知であるので詳細は説明しない。また、当業者であれば、上述した装置にそれらの構成要素を追加することは容易に理解するであろう。
さらに、上述したユニットは、図面において個別のブロックとして示しているけれども、どのユニットも１つの構成要素として他のものと組み合わせることが可能あるし、さらにいくつかの構成要素に分けることも可能である。
【００７９】
さらに、データ所有者端末、検索者端末およびサーバは、上述した例において別個の装置として説明しかつ示したが、それらは通信ネットワークで互いに遠隔に設置される可能性もある。しかしながら、それらは、機能の強化に伴って１つの装置として組み合わせることも可能である。
例えば、ある場合には、データ所有者端末として動作する新たな装置を作成する際にデータ所有者端末と検索者端末を組み合わせることも可能であるし、一方、他の場合には、検索者端末として検索を実行することができる新たな装置を作成する際にデータ所有者端末と検索者端末を組み合わせることも可能である。他の例としては、サーバとデータ所有者端末あるいは検索者端末を、それがアプリケーションでそれらの機能を代行すれば、互いに組み合わせることが可能である。また、異なる処理においてデータ所有者端末、検索者端末およびサーバとして機能する装置を作成することも可能である。
【００８０】
上述した通信ネットワークは、あらゆる種類の電気通信ネットワークあるいはコンピュータネットワークを含むあらゆる種類のネットワークである。また、通信ネットワークは、例えば、データ所有者端末、検索者端末およびサーバが、単一の装置のパーツとして実施される場合、データバスあるいはハブ等の内部データ転送機構を含む。
【００８１】
本発明に要素は、ハードウェア、ソフトウェア、ファームウェアあるいはそれの組み合わせにおいて実現され、それのシステム、サブシステム、構成部品あるいはサブコンポーネントにおいて利用することができる。ソフトウェア中で実現された時、本発明に要素は、必要なタスクを実行するためのプログラム、あるいはコードセグメントである。プログラムまたはコードセグメントは、コンピュータ読み取り可能な媒体に格納するか、あるいは伝送ケーブルか通信リンク上の搬送波に包含されたデータ信号によって送信することが可能である。コンピュータ読み取り可能な媒体には、情報を格納するか転送することが可能であるすべての媒体を含む。コンピュータ読み取り可能な媒の具体例は、電子回路、半導体記憶装置、ＲＯＭ、フラッシュ・メモリー、消去可能ＲＯＭ（ＥＲＯＭ）、フロッピー・ディスク、ＣＤ−ＲＯＭ光ディスク、ハードディスク、光ファイバー媒体、無線周波数（ＲＦ）リンクなどを含む。コードセグメントは、インターネット、イントラネットなどのようなコンピュータネットワークを経由してダウンロードすることも可能である。
【００８２】
本発明は、本発明の精神および本質的な機能から外れずに、他の特定の形態で実装可能である。例えば、特徴が本発明に基本的な範囲から外れない限り、特定の実施の形態で述べられたアルゴリズムは修正することが可能である。従って、現在の実施の形態は、全ての点において例示でありかつ限定的でないとして考慮されるべきである。本発明の範囲は、前述の説明によってではなく添付された請求項によって示される。また、したがって、請求項と同等の意味と範囲の内で生ずる変更は全て本発明の範囲に包含される。
【符号の説明】
【００８３】
１０１：検索項目識別情報生成ユニット
１０２：索引項目生成ユニット
１０３：累積情報生成ユニット
１０４：索引形成ユニット
３０１：検索要求ユニット
３０２：検索情報抽出ユニット
３０３：検証ユニット
【技術分野】
【０００１】
本発明は、一般に情報処理技術に関し、特に、検索方法、検索装置及び検索結果についての十分検証を可能にする索引の生成方法と装置に関する。
【背景技術】
【０００２】
様々なアプリケーションプログラムにおいて、大量の情報についての検索が、特別条件を満たす情報を取得するために必要である。一般に、索引は、もとの情報について予め構築されている。その後、検索要求に応じて一致する項目を見つけ出すために索引内で検索が実行され、その結果、関連情報が取り出される。様々な理由から、検索者は、検索から完全な結果情報、すなわち、検索条件を満たす全ての情報を得たいと希望する。しかしながら、索引作業と検索についての既存の手法は、検索の完全性を保証しない。
【０００３】
コンピュータネットワークと通信技術の幅広い利用に伴い、データ所有者は、多くの場合、第三者機関によって維持されるサーバ上にデータファイルを格納する。そのような状況では、サーバ上に格納されたデータファイルを検索するサービスも、第三者機関によって提供されている。すなわち、検索サービスを提供する第三者機関は、検索者からの要求に応じて索引を使用することによりサーバ上に格納されたデータファイルを調べ、検索者に検索結果を提供する。検索における実質的な作業が第三者によって実行されるがため、検索の正確さおよび完全性が検証されかつ保証されるような状況がさらに一層要望されている。
【０００４】
さらに、プライバシーと安全性の懸念により、データファイルは、多くの場合暗号化された後に格納される。特に、ストレージサービスの上記のケースにおいては、ファイルの内容が無許可のユーザ（場合によっては、ストレージサービスと検索サービスを提供する第三者を含む）に露呈するのを防ぐために、ファイルはしばしば暗号化テキスト形式でサーバ上に格納される。しかしながら、ファイルが暗号化されたストレージは、ファイルの検索を困難にし、検索結果の正確さおよび完全性を検証することを特に難しくする。
【０００５】
本発明は、検索方法と検索装置及び索引生成方法と索引生成装置を提供する。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
上述したように、索引作業と検索についての既存の手法は、検索結果の完全性を保証しない。また、検索における実質的な作業が第三者によって実行されるがために、検索の正確さおよび完全性が検証されかつ保証されることが望まれている。さらに、ファイルを暗号化してサーバに格納する場合、ファイルの検索を困難にし、検索結果の正確さおよび完全性を検証することを難しくするという問題がある。
【課題を解決するための手段】
【０００７】
本発明による索引生成方法は、検索項目に対応する検索項目識別子を生成するステップと、検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成するステップと、１以上の検索情報について累積情報を生成するステップと、索引を形成するために少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成するステップとを含む。
【０００８】
本発明による索引生成装置は、検索項目に対応する検索項目識別子を生成する検索項目識別子生成ユニットと、検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成する索引項目生成ユニットと、１以上の検索情報について累積情報を生成する累積情報生成ユニットと、少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成して、索引を形成する索引形成ユニットとを備える。
【０００９】
本発明による検索方法は、検索要求を生成するステップと、１以上の索引項目および１つの累積情報を受信するステップと、受信した１以上の索引項目から１以上の検索情報を抽出するステップと、受信した累積情報によって抽出した検索情報を検証するステップとを含む。
【００１０】
本発明による検索装置は、検索要求を生成する検索要求ユニットと、１以上の受信した索引項目から１以上の検索情報を抽出する検索情報抽出ユニットと、受信した累積情報によって抽出した検索情報を検証する検証ユニットとを備える。
【発明の効果】
【００１１】
本発明の方法によれば、累積情報を使用することにより、検索結果の完全性および正確さを証明することが可能となる。本発明は、逆索引、特に暗号化された逆索引に適用することができる。プライバシー・レベルに設定された暗号化逆索引により、良好なプライバシー管理及び機密性が検索結果の検証に基づいて提供される。
【図面の簡単な説明】
【００１２】
本発明の前述した特徴及び他の特徴は、以下の説明と添付図面とを参照することにより、さらに明らかになるであろう。
【図１】検索システムの一例を示すブロック図である。
【図２】本発明の実施の形態によるデータ所有者端末の構成例の概略を示すブロック図である。
【図３】本発明の実施の形態による索引を生成する処理を説明するフローチャートである。
【図４】本発明の実施の形態による検索者端末の構成例の概略を示すブロック図である。
【図５】本発明の実施の形態による検索処理を説明するフローチャートである。
【発明を実施するための形態】
【００１３】
本発明の種々の特徴および典型的な実施の形態については、図面を参照して以下にその詳細を説明する。以下の詳細な説明においては、多くの具体的な詳細が本発明を十分に理解するために提供される。しかしながら、これらの具体的詳細のうちのいくつかがなくとも本発明を実現できることは、当業者にとって明白である。実施の形態の以下の説明は、本発明の一例を示すことにより、本発明をよりよく理解するためになされている。本発明は、以下に説明されたどんな特定の構成およびアルゴリズムにも限定されない。本発明の範囲から外れない限り、構成要素、構成部品およびアルゴリズムのいかなる変形、代替案および改良も包含する。図面および以下の説明において、周知の構成および技術については、本発明を不必要に不明瞭にしないために詳細には説明しない。
【００１４】
図１は、本発明を適用した典型的な検索システムを概略的に示すブロック図である。
図１に示すように、データ所有者の装置或いは端末、サービスプロバイダによって管理されるサーバおよび１以上の検索者の装置或いは端末が、通信ネットワークによって接続され、互いに通信することができる。データ所有者は、ファイルおよびそれらのファイルの索引をサーバに格納する。サーバは、検索者端末からの検索要求に応じて索引を使用することによりファイルの検索を実行し、検索者に検索結果を提供する。
【００１５】
ここで使用される用語「サーバ」は、ストレージサービスと検索サービスの両方を提供する単一の装置、あるいはストレージサービス、データ検索、ユーザー管理などの種々のサービスを負担し、又はそれらのサービスを分担する互いに隣接し又は遠隔に位置する複数の装置の集合を意味する。
例えば、データ所有者端末は、ストレージサーバ上にファイルを格納し、ストレージサーバと通信し合うファイル検索サーバ上に索引を格納する。説明を簡単にするために、説明と図面においてサービスを提供するそのような全ての装置を「サーバ」と呼ぶことにする。
データ所有者端末とサーバは、図において個別の装置として示されている。しかしながら、以下に説明するように、本発明におけるデータ所有者端末とサーバの両機能は、単一の装置によって実現できることを十分に理解できるであろう。
【００１６】
データ所有者と検索者の装置或いは端末は、それぞれ、情報を処理することができかつ情報を通信することができる装置として実現される。例えば、パーソナルコンピュータ（ＰＣ）、携帯情報端末（ＰＤＡ）、スマートフォン（smart mobile phone）或いはその他のデータ処理装置等である。
一般に、サーバは、データを格納し維持することが可能であり、また、端末によるデータの条件付きアクセスを可能にする、サービスプロバイダによって管理される単一の装置或いは装置の集合として実現される。
【００１７】
図示のシステムにおいて、データ所有者は、自身のファイルに索引を付け、サーバ上にファイルと索引を格納する。検索時、検索者は、検索項目の情報（例えば、検索項目識別情報）を含む要求を送信する。サーバは、検索項目の情報に従って一致する索引エントリについて索引を調べ、関連情報の検索のために、索引エントリ中の索引項目（検索項目に関連する）を検索者に提供する。
特に、本発明による解決方法においては、累積情報も、検索結果の完全性の証明のために索引エントリに含まれている。サーバは、また検索者に索引エントリ中の累積情報（Ａｃｃｕｍｕｌａｔｏｒ）を提供する。検索者は、累積情報の利用により検索結果が完全で正確かどうかを検証する。
【００１８】
一般的な用途において、キーワードに基づいてそのキーワードを含んでいるファイルを検索する場合、逆索引がしばしば利用される。
以下の説明において、逆索引の利用を例として挙げる。しかしながら、本発明が、同様の方法で非逆索引に適用可能であることも言うまでもない。
【００１９】
図２は、本発明の実施の形態によるデータ所有者端末１００の構成例を示している。
図２に示すように、データ所有者端末１００は主に検索項目識別情報生成ユニット１０１、索引項目生成ユニット１０２、累積情報生成ユニット１０３および索引形成ユニット１０４を含む。
【００２０】
図３は、本実施の形態によるデータ所有者端末１００によって索引を生成する処理の概略を示す。
【００２１】
まず、ステップＳ２０１で、データ所有者のファイルに関する検索項目がセットされ、検索項目識別子生成ユニット１０１は検索項目に従ってそれぞれの検索項目識別情報を生成する。逆索引の利用において、検索項目はキーワードである。
例えば、データ所有者端末は、各ファイル内のキーワードを抽出し、検索項目としてそれらを採用する。あるいは、データ所有者が、端末への入力によって検索項目を手作業でセットする。
互いに異なるキーワードが、検索項目としてセットされれば、各検索項目(keyword) KWについて、検索項目識別子生成ユニット１０１が検索項目の対応する一意の識別子ＫＬを生成する。
【００２２】
検索項目識別子ＫＬは、例えば、検索項目ｋＷそのもの、あるいは検索項目ｋＷにマッピングされるデータである。暗号化された索引の利用において、検索項目識別子ＫＬは、ｋＷの暗号化テキスト、あるいはｋＷの情報を含んでいるデータである。
例えば、ＫＬは次のように計算される。
KL = Hash(MEK||KW) （式１）
ここで、Hash()はハッシュ関数を表わす。MEKは特定のパラメータ（例えば、データ所有者の親鍵（マスターキー））である。
「||」は、事前に設定された順序の文字列あるいは数字の組合せを表わす。
あるいは、KL = E(EKey, KW)
ここで、EKeyは特定の鍵である。E(EKey, KW)は、EKeyによるKWの暗号化を表す。
【００２３】
ステップＳ２０２で、各検索項目に関する検索情報がセットされ、索引項目生成ユニット１０２は、各検索情報に対応する索引項目を生成する。検索項目はそれぞれ１つあるいは複数の検索情報に対応する。検索情報は、その検索項目と一致する検索結果を提供するための何らかの情報である。
例えば、逆索引においては、検索項目（キーワード）ｋＷについて、キーワードｋＷを含む各ファイルのファイル名あるいは場所（あるいは、そのファイルに関する他の情報）が、検索項目に関する１つの検索情報としてセットされる。
例えば、検索項目ｋＷについて、キーワードｋＷを含んでいるｎ個のファイルのファイル名は、検索項目ｋＷに関するｎ個の検索情報I1, I2, …Inのようにセットされる。
【００２４】
暗号化ストレージの利用において、データ所有者がサーバ上にファイルの平文ではなく暗号化テキストを格納することに留意する必要がある。その場合、上述のファイル名は暗号化されたファイルの暗号文ファイル名かもしれない。
【００２５】
各検索情報について、索引項目生成ユニット１０２は、検索情報を含む、あるいは検索情報が導き出される索引項目を生成する。
１個の検索情報Ij (j＝1, 2,…, n)について、索引項目生成ユニット１０２は索引項目FLjを生成する。
索引項目FLjは、例えば、検索情報Ijそのもの、あるいはある変換によって検索情報Ijが取得される何らかの値である。暗号化索引の利用において、索引項目FLjは情報Ijを含む暗号文データかもしれない。
例えば、索引項目FLjは以下のように計算される。
FLj = E(EKey, Ij||Key) （式２）
ここで、EKeyは特定の鍵である。Keyは、特定のパラメータ（例えば、ファイルを暗号化するのにデータ所有者によって使用される鍵）である。E(EKey, Ij||Key)は、EKeyによるIjとKeyの組合せの暗号化を表わす。
【００２６】
次に、ステップＳ２０３で、累積情報生成ユニット１０３は、検索結果の完全性の検証のために、検索項目に関するすべての検索情報を累積する累積情報を生成する。
各検索情報を含む検索結果が完全かどうかを検索者端末が検証することができさえすれば、累積情報は様々な方法で生成することが可能である。
累積情報の演算は、排他的ＯＲ（ＸＯＲ）演算、剰余演算(modular operation)および累積シグネチャ（Accumulation
signature）の具体例を用いて以下に説明する。
当業者は、累積情報を生成するために他のアルゴリズムを利用可能であることは十分に理解するであろう。
具体例１−ＸＯＲ演算
【００２７】
検索項目KWに関するすべての検索情報I1, I2,
…Inについて、累積情報生成ユニット１０３は、ＸＯＲ演算により完全性累積情報ICを以下のように生成する。
【数１】
ここで、
【数２】
はＸＯＲ演算を表わす。
【００２８】
式３は、反復演算によって以下のように計算される。
set IC = 0
for j=1 to n
【数３】
next j
具体例２−剰余（Mod）演算
【００２９】
剰余演算により、累積情報生成ユニット１０３は完全性累積情報ＩＣを以下のように生成する。
【数４】
あるいは
【数５】
ここで、pは、大きな素数である。
【００３０】
式４は、反復演算によって以下のように計算される。
set IC = 1
for j=1 to n
IC = (IC * Ij)
mod p
next j
【００３１】
式５は、反復演算によって以下のように計算される。
set IC = 0
for j=1 to n
IC = (IC + Ij)
mod p
next j
具体例３−累積シグネチャ（Accumulation
signature）
【００３２】
以下のセキュリティパラメータ（security
parameter）があらかじめセットされると想定する。
大きな素数p、位数ｐの２つのグループG1とG2、G1とG2のジェネレータであるg1およびg2、p未満でpと互いに素であるすべての正整数の集合であるZp*、G1×G2→GTと定義される双線型写像（bilinear mapping）e
双線型写像は以下の特徴を有する。
（１）双線型性 (bilinearity)
全てのg1およびg2及びZp*に属する全てのaとbについて、
e(g1a,
g2b) = e(g1, g2)abの関係がある。
（２）非縮退（nondegeneracy）
g1=0 if e(g1, g2)
= 1 g2はG2に属する。
Gに対して{0,1}*をマッピングするハッシュ関数がセットされ、乱数KがZp*から選択される。秘密キーskがセットされる。
ここで、g2と乱数Kは検索者に公開される。そうでなければ、g2Kが検索者に公開される。
【００３３】
次に、累積情報生成ユニット１０３は累積情報ICを以下のように生成する。
【数６】
【００３４】
式６は、反復演算によって以下のように計算される。
set IC = 1
for j = 1 to n
IC = (IC * H(Ij)1/(sk+K))
mod p
next j
【００３５】
累積情報が生成された後、索引形成ユニット１０４は、各検索項目について索引エントリを生成する。索引エントリはそれぞれ、少なくとも、検索項目の検索項目識別子と、検索項目に関する全ての索引項目と、検索項目に関する全ての検索情報を累積することにより取得された累積情報を含んでいる。
次に、索引形成ユニット１０４は、各索引エントリを含む索引を形成する。それぞれ異なる索引項目の累積が各累積情報を生成するため、乱数Ｋはそれぞれ別に選択される場合があることに留意すべきである。
【００３６】
このように、累積情報を含む索引が、データ所有者端末１００で生成される。その後、データ所有者端末は、ファイルと生成された索引を将来の利用のためにサーバに格納することが可能である。
【００３７】
累積情報の利用について、図４及び図５を参照して以下に説明する。
【００３８】
図４は、本発明の実施の形態による検索者端末３００の構成例を示している。図４に示すように、検索者端末３００は、主に、検索要求ユニット３０１と、検索情報抽出ユニット３０２と、検証ユニット３０３を含む。
【００３９】
図５は、本実施の形態による検索を実行する検索者端末３００の処理の概略を示す図である。
【００４０】
まず、ステップＳ４０１で、検索要求ユニット３０１は、少なくとも１つの検索項目識別子を含む検索要求を生成し、サーバに検索要求を送信する。
検索者端末は、データ所有者から検索項目識別子を取得し、あるいは、データ所有者から検索項目識別子の計算に必要なデータを取得し、データ所有者端末で索引を形成する時に検索項目識別子を生成する方法に相当する方法によって検索項目識別子を計算する。
【００４１】
検索要求を受け取った後に、サーバは、受信した検索項目識別子と一致する検索項目識別子を有する索引エントリのために索引を調べる、検索者端末にその索引エントリ内の累積情報だけでなく索引項目もすべてを返却する。
認証が必要である場合、サーバは、上述のルックアップを実行する前に検索者を認証することも可能である。サーバが一致する索引エントリを発見できず、あるいは検索者の認証に失敗すると、サーバは、否定的な結果を返却するか、あるいはエラー処理に移行し、検索者端末に通知を送信する。そのような状態において、検索者端末は、エラー手順を実行し、例えば、手順を再試行しあるいは終了する。
【００４２】
サーバが検索結果を返却すれば、ステップＳ４０２で、検索者端末は、対応する累積情報だけでなく１つ或いは複数の索引項目も受け取る。
【００４３】
次に、ステップＳ４０３で、検索者端末の検索情報抽出ユニット３０２が、受信した各索引項目から検索情報を抽出する。上述したように、索引項目が検索情報そのものかもしれない。その場合、検索情報が直ちに取得される。
索引項目が検索情報の暗号文の形式であるか、あるいは変換によって検索情報が取得される値である場合、検索情報抽出ユニット３０２は対応する暗号解読あるいは変換によって検索情報を抽出する。暗号解読あるいは変換用に必要なパラメータは、データ所有者から取得することが可能である。
【００４４】
各索引項目に含まれる検索情報を取得した後、検索者端末の検証ユニット３０３は、受信した累積情報を使用することにより検索結果が完全でかつ正確かどうかを検証する（ステップＳ４０４）。
【００４５】
正確であると確認されれば、処理手続きはステップＳ４０５に移行し、取得した検索情報が、例えば、検索情報に従って対応するファイルを引き出すことあるいは追加の情報の処理に使用される。
検索情報の利用については、本発明と直接関係しないので、対応するユニットあるいはモジュールは、図面に示しておらず、かつその詳細な説明も省略している。
しかしながら、特定の用途に応じて必要とする処理を実行するために、他の必要なユニットあるいはモジュールが追加されるであろうことは十分に理解されるべきである。
【００４６】
検証が否定的であれば、不完全あるいは不正確であるとの検索結果が示される。多くの場合、それはデータの改ざんあるいはデータ通信におけるエラーに起因する。そのような状態において、処理手続きは、エラー処理のためにステップＳ４０６に移行し、例えば、検索要求の再送、再送信の要求、あるいは処理の終了を行う。
【００４７】
累積情報を用いた検証方法については、累積情報の生成においてデータ所有者端末で使用された方法に応じて決定される。
【００４８】
例えば、検証ユニット３０３は、データ所有者端末によって使用された方法と同じ方法によって抽出した検索情報に基づいて累積情報を計算し、その累積情報をサーバから受信した累積情報と比較する。
それらが一致すれば、検証が肯定的となり、そうでなければ、検証は否定的となる。幾つかの具体例を以下に示す。
【００４９】
ここで、検索情報抽出ユニットが受信した全ての索引項目から検索情報I'1, I'2,
…I'mを抽出すると仮定する。
累積情報が上記の式３に従って計算される場合、検証ユニット３０３は、
【数７】
,を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
【００５０】
同様に、累積情報が上記の式４に従って計算される場合、検証ユニット３０３は、
【数８】
を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
あるいは、累積情報が上記の式５に従って計算される場合、検証ユニット３０３は、
【数９】
を計算し、そのIC'をサーバから受信した累積情報ICと比較する。
【００５１】
上記の式６に従って累積シグネチャ（Accumulation signature）の形式で累積情報が生成される場合、検証は累積シグネチャを検証することにより実行される。
特に、検証ユニット３０３は、
【数１０】
を計算し、関係e(IC', g2) = e(IC, g2sk * g2K)が成り立つかどうかを検証する。
関係が成り立てば、正確であると検証され、そうでなければ、検証は否定的となる。
【００５２】
累積情報を生成するために他の方法が使用される場合、検証ユニット３０３は、対応する方法を用いることにより検索情報が累積情報により完全かどうか検証する。
【００５３】
ある状況では、索引を更新する必要が発生する。例えば、新たなファイルが追加され、あるいは、既存ファイルが削除されと、検索情報が変換する。その結果、索引は正確な検索を保証するために更新される。索引項目はファイルの追加あるいは削除に応じて更新され、同時に、関連する索引エントリ内の累積情報もそれに応じて更新される。
【００５４】
例えば、一つの新たな検索情報Iaを検索項目KWに対応する索引エントリに追加する必要があるならば、上記の式３に従って計算された累積情報ICは、式７のように更新される。
【数１１】
上記の式４に従って計算された累積情報ICは、式８のように更新される。
ICupdated = (IC * Ia) mod p （式８）
上記の式５に従って計算された累積情報ICは、式９のように更新される。
ICupdated = (IC＋Ia)
mod p （式９）
また、上記の式６に従って計算された累積情報ICは、式１０のように更新される。
ICupdated = [IC * H(Ia)1/(sk+K)] mod p （式１０）
【００５５】
上記の式６に従って計算された累積情報ICについては、以下に示すように別の方法を用いて更新することが可能である。
まず、新たな公開乱数K'を選択し、次に、更新累積情報ICupdatedを以下のように計算する。
IC updated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’) （式１１）
【００５６】
他方、一つの既存の検索情報が検索項目KWに対応する索引エントリから削除されるならば、
上記の式３に従って計算された累積情報ICは、式１２のように更新される。
【数１２】
上記の式４に従って計算された累積情報ICは、式１３のように更新される。
ICupdated = (IC * Ib-1) mod p （式１３）
上記の式５に従って計算された累積情報ICは、式１４のように更新される。
ICupdated = (IC - Ib) mod p （式１４）
また、上記の式６に従って計算された累積情報ICは、式１５のように更新される。
ICupdated = [IC * H(Ib)-1/(sk+K)] mod p （式１５）
【００５７】
上記の式６に従って計算された累積情報ICについては、以下に示すように別の方法を用いて更新することが可能である。
まず、新たな公開乱数K'を選択し、次に、次に、更新累積情報ICupdatedを以下のように計算する。
IC updated = [IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’) （式１６）
【００５８】
索引エントリの更新はデータ所有者端末によって実行することが可能であり、更新された索引エントリは、以前のものと置き換えるためにサーバに送信される。あるいは、サーバによって更新を実行することが可能である。従って、索引更新のための更新ユニット（図示せず）は、データ所有者端末あるいはサーバに設けられる。
【００５９】
本発明による索引における累積は様々な索引に適用することが可能である。例えば、累積情報は暗号化索引に同様に適用することが可能である。例えば、索引エントリ内の索引項目は検索情報を含む情報を暗号化することにより取得された暗号文であり、また、累積情報は、検索情報が暗号化ファイルの暗号化されたファイル名である検索情報を累積することによって取得される。
そのような暗号化索引においては、データ所有者および権限を与えられた検索者を除いて、サーバを含む他の当事者は、索引項目を暗号化して検索情報を得ることができないし、暗号化処理のシミュレーションによって正確に解読することができる索引項目を取得することもできない。その結果、索引項目および累積情報の改ざんが防止される。
【００６０】
高速検索可能な暗号化方法を以下に示す。改良した暗号化逆索引が使用され、累積情報が検索結果の完全性の検証を与えるために使用される。
【００６１】
この方法において、データ所有者端末は、同じあるいは異なる鍵で各ファイルを暗号化し、サーバにファイルの暗号文を格納する。この例において、上記検索情報Ijは、ファイルFILEjの暗号化されたファイル名CFNjである。
暗号化されたファイル名に基づいて、サーバは、格納された暗号化ファイルの中で一致するファイルを即座に発見し、要求者にそのファイルを提供する。
【００６２】
指標付けの段階では、検索項目のように挙げられたキーワードKWについて、データ所有者端末は、キーワードKWを含む情報を暗号化することにより、あるいは値にキーワードKWを含む情報をマッピングすることにより、検索項目識別子を計算する。
例えば、MEKがデータ所有者のマスターキーである場合、検索項目識別子はKL = Hash(MEK||KW)のように計算される。
【００６３】
ファイルFILEj (j = 1, 2, … n)がキーワードKWを含むと仮定すると、データ所有者端末は、KWに関連するFILEjの索引項目FLJを以下のように計算する。
FLj = E(EKey, Ij||Kfilej) （式１７）
ここで、KfilejはファイルFILEjのための解読キーである。IjはファイルFILEjの暗号化されたファイル名である。EKeyは、索引項目を生成するための暗号鍵（データ所有者によってセットされる）である。また、E(EKey, Ij||Kfilej)は、IjとKfilejの組合せのEKeyによる暗号化を表わす。
【００６４】
その後、Ij (j = 1, 2, … n)が、検索項目KWの累積情報ICを生成するために累積される。例えば、それは、上述した式３から式６の何れかあるいは他の方法に従って計算される。
【００６５】
その後、少なくともKL、FLj (j = 1, 2, … n)及びICを含む索引エントリが、キーワードKWについて生成される。この索引エントリによって形成された暗号化された逆索引が、サーバに格納される。
【００６６】
データ所有者が検索者にキーワードによる検索を実行させる場合、データ所有者は安全な方法で、検索者に対してキーワードの検索項目識別子KLを公開し、索引項目の解読のための解読キーDKeyを検索者に公開する。
【００６７】
検索の段階では、検索者端末は、サーバに対して検索項目識別子KLを含む検索要求を送信する。
サーバは、受信した検索項目識別子KLに従って、一致する索引エントリについて格納した暗号化索引を調べ、一致する索引エントリに含まれる累積情報ICだけでなく全ての索引項目FLjを検索者端末に返却する。
【００６８】
サーバから各索引項目FLjを受け取った後、検索者端末は、索引項目の解読のためにデータ所有者によって公開された解読キーDKeyにより各索引項目FLjを解読し、暗号化されたファイル名およびファイル、すなわちIj とKfilejの対応する解読キーを取得する。
【００６９】
その後、データ所有者端末は、受信した累積情報ICを使用し、取得した暗号化ファイル名Ijがすべて完全かどうかを検証する。
正確であると認定されれば、検索者端末は、それらの暗号化ファイル名Ijを利用する。例えば、対応する暗号化ファイル名を有する暗号化ファイルを引き出すためにサーバに対して暗号化ファイル名Ijを送信し、その後、対応するファイル解読鍵Kfilejで暗号化されたファイルを解読し、ファイルのプレーンテキストを取得する。検証が否定的であれば、上述したエラー処理を実行する。
【００７０】
上記の説明において、ファイルと検索情報はサーバ上に暗号化された形式で格納される。このため、サーバに対してファイル情報が漏洩することが防止される。
【００７１】
上記の例の改良した形態においては、検索情報Ijから直接累積情報を計算する代わりに、検索情報Ijを含む情報の暗号文あるいは検索情報Ijを含む情報からマッピングされたデータが、累積情報ICを計算し、検証し及び更新するのに、Ijの代わりに使用される。
例えば、Ij' = Ij||Xが、累積情報を計算するのに前述のＩｊの代わりに使用される。ここで、Xは予め設定された情報、例えば、上記の例におけるDKeyである。
また、Ij' = Ij||Xは、上記したＸＯＲ演算、剰余演算等によって累積情報を計算する式のIjの代わりに使用することが可能である。ここで、Xは予め設定された情報、例えば、上記の例におけるDKeyである。
【００７２】
上述したように、索引項目が検索情報を含む情報の暗号文であり、かつ、累積情報が検索情報の累積によって形成されるので、権限外の第三者は索引項目あるいは累積情報を改ざんすることができない。
【００７３】
他の改良した形態において、データ所有者は、異なるプライバシー・レベル（privacy level）を設定し、その異なるプライバシー・レベル毎に別々に索引項目の暗号化キーEKeyと解読キーDKeyを設定することが可能である。
索引を生成する場合、あるプライバシー・レベルで開示することが可能なファイルに関して、そのプライバシー・レベルの索引項目暗号鍵がそのファイルについて索引項目を生成するのに使用される。
このように、検索項目（キーワード）と関連する索引エントリに、異なるプライバシー・レベルの索引項目が存在することになる。このような場面においては、各プライバシー・レベルの索引項目について、累積情報が生成される。
すなわち、１つの検索項目に対応する索引エントリにおいて、ある１つのプライバシー・レベルの累積情報が、そのプライバシー・レベルの全ての索引項目に含まれる検索情報を累積することによって生成される。このようにして、異なるプライバシー・レベルの複数の累積情報が生成される。
【００７４】
上述した改良した方法においては、データ所有者はプライバシー・レベルに応じて検索者に権限を与える。すなわち、検索者のプライバシー・レベルに適した索引項目解読キーDKeyが検索者に公開される。
検索時、検索者は、公開された索引項目解読キーDKeyで、サーバから受信したすべての索引項目のうち、同じプライバシー・レベルの索引項目暗号鍵EKeyを使用してもともと生成された検索項目を解読する。これにより、検索者は、そのプライバシー・レベルの検索項目に関する検索情報を取得することができる。
暗号解読の正確さの検証のために索引項目に所定のフラグを設定することもできる。例えば、索引項目を以下のように生成する。
FLj = E(EKey, FLAG||Ij||Kfilej) (式１８)
ここで、FLAGは検索者に認識されているパラメータである。
これによって、解読された情報内における正しいFLAGの存在を検証することによって、検索者は、暗号解読が正確に実行されているかどうかを判定することができる。
【００７５】
また、暗号解読によって対応するプライバシー・レベルの検索情報を取得した後、検索者は、そのプライバシー・レベルに対応する受信した累積情報を使用することで、そのプライバシー・レベルの検索情報が完全かどうかを検証する。
検索者は、受信した索引エントリに含まれる複数累積情報を使用して検証を実行してもよい。そして、累積情報のいずれかの１つが正しいと確認されれば、検証は肯定的となる。
それは、計算された累積情報が異なるプライバシー・レベルの受信した累積情報と等しくなるという確率が非常に低いためである。
あるいは、索引エントリはセクションに分けられる。すなわち、同じプライバシー・レベルの索引項目は同じセクションに加えられる。その結果として、検索者は、どのセクションで索引項目が正確に解読されているかを判定することで、検証においてどの累積情報を使用するかを決定することができる。
あるいは、検索者が使用すべき正しい累積情報を決定するのを支援するために、各累積情報に付加情報（例えば、プライバシー・レベルを示すパラメータ）を付与することも可能である。
あるいは、サーバは、検索時に、検索者のプライバシー・レベルを判定する処理を実行し、次に、検索者のプライバシー・レベルに応じて対応するプライバシー・レベルの累積情報を検索者に返却する。そのような場合、受信した累積情報から累積情報を選択する処理は検索者にとって不要となる。
【００７６】
本発明によるいくつかの実施の形態について図面を参照して上記のように説明した。しかしながら、本発明は、上記実施の形態で説明した特定の構成および処理に何ら限定されるものではない。上述した構成、アルゴリズム、動作及び処理について、本発明の精神の範囲内で、種々の代替案、変更あるいは変形が可能であることは、当業者によって十分に理解できるであろう。
例えば、上記の説明では、逆索引の具体例について詳細に説明した。しかし、本発明を非可逆索引（non-inverted index）に適用することも可能である。さらに、例えば、上述した例における検索項目は、ファイル名あるいは暗号化されたファイル名でもよいし、また、検索情報は、ファイルに含まれるキーワードあるいは暗号化されたキーワード等でもよい。
非可逆索引において、累積情報は同様の方法で適用することが可能である。
さらに、上述した例では、索引エントリが少なくとも１つの検索項目識別子、索引項目および累積情報を含んでいる。しかしながら、特定のアプリケーションの要求によって他の必要な情報およびデータを索引エントリに追加することも可能である。
【００７７】
本明細書で使用される、いわゆる「ファイル」は、幅の広い概念として解釈されるべきである。それは、例えば、テキストファイル、ビデオ／オーディオ・ファイル、写真／図、および他のデータあるいは情報を含むが、これらに限定されない。
【００７８】
データ所有者端末、検索者端末およびサーバの構成として、相互に接続された幾つかのユニットを図面に示した。
これらのユニットは、それらの間で信号を転送するために、バスあるいは他の信号ライン、あるいは無線によって接続することができる。しかしながら、各装置に含まれる構成要素は、上述したユニットに限定されないし、特定の構成については変更しあるいは差し替えることが可能である。各装置は、装置の操作者に対して情報を表示するための表示ユニット、操作者の入力を受け付ける入力ユニット、各ユニットの演算を制御する制御装置、他の記憶装置等のような、他のユニットを含むことも考えられる。それらの構成要素については、当業界において公知であるので詳細は説明しない。また、当業者であれば、上述した装置にそれらの構成要素を追加することは容易に理解するであろう。
さらに、上述したユニットは、図面において個別のブロックとして示しているけれども、どのユニットも１つの構成要素として他のものと組み合わせることが可能あるし、さらにいくつかの構成要素に分けることも可能である。
【００７９】
さらに、データ所有者端末、検索者端末およびサーバは、上述した例において別個の装置として説明しかつ示したが、それらは通信ネットワークで互いに遠隔に設置される可能性もある。しかしながら、それらは、機能の強化に伴って１つの装置として組み合わせることも可能である。
例えば、ある場合には、データ所有者端末として動作する新たな装置を作成する際にデータ所有者端末と検索者端末を組み合わせることも可能であるし、一方、他の場合には、検索者端末として検索を実行することができる新たな装置を作成する際にデータ所有者端末と検索者端末を組み合わせることも可能である。他の例としては、サーバとデータ所有者端末あるいは検索者端末を、それがアプリケーションでそれらの機能を代行すれば、互いに組み合わせることが可能である。また、異なる処理においてデータ所有者端末、検索者端末およびサーバとして機能する装置を作成することも可能である。
【００８０】
上述した通信ネットワークは、あらゆる種類の電気通信ネットワークあるいはコンピュータネットワークを含むあらゆる種類のネットワークである。また、通信ネットワークは、例えば、データ所有者端末、検索者端末およびサーバが、単一の装置のパーツとして実施される場合、データバスあるいはハブ等の内部データ転送機構を含む。
【００８１】
本発明に要素は、ハードウェア、ソフトウェア、ファームウェアあるいはそれの組み合わせにおいて実現され、それのシステム、サブシステム、構成部品あるいはサブコンポーネントにおいて利用することができる。ソフトウェア中で実現された時、本発明に要素は、必要なタスクを実行するためのプログラム、あるいはコードセグメントである。プログラムまたはコードセグメントは、コンピュータ読み取り可能な媒体に格納するか、あるいは伝送ケーブルか通信リンク上の搬送波に包含されたデータ信号によって送信することが可能である。コンピュータ読み取り可能な媒体には、情報を格納するか転送することが可能であるすべての媒体を含む。コンピュータ読み取り可能な媒の具体例は、電子回路、半導体記憶装置、ＲＯＭ、フラッシュ・メモリー、消去可能ＲＯＭ（ＥＲＯＭ）、フロッピー・ディスク、ＣＤ−ＲＯＭ光ディスク、ハードディスク、光ファイバー媒体、無線周波数（ＲＦ）リンクなどを含む。コードセグメントは、インターネット、イントラネットなどのようなコンピュータネットワークを経由してダウンロードすることも可能である。
【００８２】
本発明は、本発明の精神および本質的な機能から外れずに、他の特定の形態で実装可能である。例えば、特徴が本発明に基本的な範囲から外れない限り、特定の実施の形態で述べられたアルゴリズムは修正することが可能である。従って、現在の実施の形態は、全ての点において例示でありかつ限定的でないとして考慮されるべきである。本発明の範囲は、前述の説明によってではなく添付された請求項によって示される。また、したがって、請求項と同等の意味と範囲の内で生ずる変更は全て本発明の範囲に包含される。
【符号の説明】
【００８３】
１０１：検索項目識別情報生成ユニット
１０２：索引項目生成ユニット
１０３：累積情報生成ユニット
１０４：索引形成ユニット
３０１：検索要求ユニット
３０２：検索情報抽出ユニット
３０３：検証ユニット
【特許請求の範囲】
【請求項１】
検索項目に対応する検索項目識別子を生成するステップと、
前記検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成するステップと、
１以上の前記検索情報について累積情報を生成するステップと、
索引を形成するために少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成するステップと
を含むことを特徴とする索引生成方法。
【請求項２】
前記累積情報の生成ステップが、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって１以上の情報を累積することを特徴とする請求項１に記載の索引生成方法。
【請求項３】
前記検索項目がキーワードであり、前記検索情報が前記キーワードを含むファイルの暗号化されたファイル名であることを特徴とする請求項１に記載の索引生成方法。
【請求項４】
前記検索項目識別子の生成ステップが、前記検索項目を含む情報の暗号文を生成し、又は、前記検索項目を含む情報からマッピングして取得されるデータを生成することを特徴とする請求項１に記載の索引生成方法。
【請求項５】
前記索引項目の生成ステップが、前記検索情報を含む情報の暗号文を生成することを特徴とする請求項１に記載の索引生成方法。
【請求項６】
前記索引項目の生成ステップが、索引項目暗号鍵で対応する前記検索情報を含む情報を暗号化することを特徴とする請求項１に記載の索引生成方法。
【請求項７】
前記累積情報の生成ステップが、前記検索情報を含む情報の暗号文を累積し、又は、前記検索情報を含む情報からマッピングすることにより取得されるデータを累積することを特徴とする請求項１に記載の索引生成方法。
【請求項８】
１の前記検索情報が追加され又は削除された場合に、前記累積情報を更新するステップをさらに有することを特徴とする請求項１に記載の索引生成方法。
【請求項９】
前記累積情報は、
【数１３】
として計算され（ここで、I1, I2,
…Inは累積される検索情報であり、
【数１４】
はＸＯＲ演算を表わす）、
検索情報Iaが追加され又は削除される場合、累積情報を、
【数１５】
と更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１０】
前記累積情報は、
【数１６】
として計算され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
検索情報Iaが追加される場合、累積情報を、ICupdated = (IC * Ia) mod p
と更新し、
検索情報Ib が追加される場合、累積情報を、ICupdated = (IC * Ib-1)
mod pと更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１１】
前記累積情報は、
【数１７】
として計算され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
検索情報Iaが追加される場合、累積情報を、ICupdated = (IC + Ia) mod p
と更新し、
検索情報Ib が追加される場合、累積情報を、ICupdated = (IC - Ib) mod pと更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１２】
前記累積情報は、
g2とKが公開され、あるいはg2kが公開された場合、
【数１８】
として計算され（ここで、Ijは、累積される検索情報であり、skは、秘密キーであり、pは大きな素数、HはG1に文字列をマッピングするハッシュ関数、KはZp*内の乱数、Zp*はp未満でpと互いに素であるすべての正整数の集合、g2はG2のジェネレータ、G1とG2は位数pのグループであり、G1とG2について双線型写像が存在する）、
検索情報Iaが追加される場合、累積情報を、
ICupdated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開し（ここで、K’はZp*内のKと異なる乱数）、
検索情報Ib が追加される場合、
[IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開する（ここで、K’はZp*内のKと異なる乱数）
ことを特徴とする請求項８に記載の索引生成方法。
【請求項１３】
検索項目に対応する検索項目識別子を生成する検索項目識別子生成ユニットと、
前記検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成する索引項目生成ユニットと、
１以上の前記検索情報について累積情報を生成する累積情報生成ユニットと、
少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成して、索引を形成する索引形成ユニットと
を備えることを特徴とする索引生成装置。
【請求項１４】
前記累積情報生成ユニットは、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって１以上の情報を累積することを特徴とする請求項１３に記載の索引生成装置。
【請求項１５】
前記検索項目がキーワードであり、前記検索情報が前記キーワードを含むファイルの暗号化されたファイル名であることを特徴とする請求項１３に記載の索引生成装置。
【請求項１６】
前記検索項目識別子生成ユニットが、前記検索項目を含む情報の暗号文を生成し、又は、前記検索項目を含む情報からマッピングして取得されるデータを生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１７】
前記索引項目生成ユニットが、前記検索情報を含む情報の暗号文を生成することにより前記索引項目を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１８】
前記索引項目生成ユニットが、索引項目暗号鍵で対応する前記検索情報を含む情報を暗号化することにより前記索引項目を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１９】
前記累積情報生成ユニットが、前記検索情報を含む情報の暗号文を累積し、又は、前記検索情報を含む情報からマッピングすることにより取得されるデータを累積することにより前記累積情報を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項２０】
１の前記検索情報が追加され又は削除された場合に、前記累積情報を更新する更新ユニットをさらに備えることを特徴とする請求項１３に記載の索引生成装置。
【請求項２１】
前記累積情報生成ユニットが、前記累積情報を、
【数１９】
として計算するように構成され（ここで、I1, I2,
…Inは、累積される検索情報であり、
【数２０】
はＸＯＲ演算を表わす）、
前記更新ユニットが、検索情報Iaが追加され又は削除される場合、累積情報を、
【数２１】
と更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２２】
前記累積情報生成ユニットが、
前記累積情報を、
【数２２】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
前記更新ユニットが、検索情報Iaが追加される場合、累積情報を、ICupdated = (IC * Ia) mod p
と更新し、検索情報Ib が追加される場合、累積情報を、ICupdated = (IC * Ib-1) mod pと更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２３】
前記累積情報生成ユニットが、
前記累積情報を、
【数２３】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
前記更新ユニットが、検索情報Iaが追加される場合、累積情報を、
ICupdated = (IC + Ia) mod p
と更新し、検索情報Ib が追加される場合、累積情報を、
ICupdated = (IC - Ib) mod p
と更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２４】
前記累積情報生成ユニットが、
前記累積情報を、
g2とKが公開され、あるいはg2kが公開された場合、
【数２４】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、skは、秘密キーであり、pは大きな素数、HはG1に文字列をマッピングするハッシュ関数、KはZp*内の乱数、Zp*はp未満でpと互いに素であるすべての正整数の集合、g2はG2のジェネレータ、G1とG2は位数pのグループであり、G1とG2について双線型写像が存在する）、
前記更新ユニットが、
検索情報Iaが追加される場合、累積情報を、
ICupdated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開し（ここで、K’はZp*内のKと異なる乱数）、
検索情報Ib が追加される場合、
[IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開する（ここで、K’はZp*内のKと異なる乱数）ように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２５】
検索要求を生成するステップと、
１以上の索引項目および１つの累積情報を受信するステップと、
受信した１以上の前記索引項目から１以上の検索情報を抽出するステップと、
受信した前記累積情報によって抽出した前記検索情報を検証するステップと
を含むことを特徴とする検索方法。
【請求項２６】
前記検索情報を検証するステップが、
抽出した前記検索情報によって累積情報を計算するステップと、
計算した累積情報を受信した累積情報と照合するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２７】
前記検索情報を検証するステップが、集合署名を検証するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２８】
前記検索情報を抽出するステップが、１以上の索引項目を解読するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２９】
前記累積情報を計算するステップが、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって検索情報を累積するステップを含むことを特徴とする請求項２６に記載の検索方法。
【請求項３０】
前記累積情報を計算するステップが、
前記検索情報を含む情報の暗号文を累積し、あるいは前記検索情報を含む情報からマッピングすることにより取得されたデータを累積するステップを含むことを特徴とする請求項２６に記載の検索方法。
【請求項３１】
検索要求を生成する検索要求ユニットと、
１以上の受信した索引項目から１以上の検索情報を抽出する検索情報抽出ユニットと、
受信した前記累積情報によって抽出した前記検索情報を検証する検証ユニットと
を備えることを特徴とする検索装置。
【請求項３２】
前記検証ユニットは、
抽出した前記検索情報によって累積情報を計算し、計算した累積情報を受信した累積情報と照合するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３３】
前記検証ユニットは、集合署名を検証するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３４】
前記検索情報抽出ユニットは、１以上の索引項目を解読することにより前記検索情報を抽出するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３５】
前記検証ユニットは、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって検索情報を累積することにより、累積情報を計算するように構成されることを特徴とする請求項３２に記載の検索装置。
【請求項３６】
前記検証ユニットは、
前記検索情報を含む情報の暗号文を累積し、あるいは前記検索情報を含む情報からマッピングすることにより取得されたデータを累積することにより、累積情報を計算するように構成されることを特徴とする請求項３２に記載の検索装置。
【請求項１】
検索項目に対応する検索項目識別子を生成するステップと、
前記検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成するステップと、
１以上の前記検索情報について累積情報を生成するステップと、
索引を形成するために少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成するステップと
を含むことを特徴とする索引生成方法。
【請求項２】
前記累積情報の生成ステップが、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって１以上の情報を累積することを特徴とする請求項１に記載の索引生成方法。
【請求項３】
前記検索項目がキーワードであり、前記検索情報が前記キーワードを含むファイルの暗号化されたファイル名であることを特徴とする請求項１に記載の索引生成方法。
【請求項４】
前記検索項目識別子の生成ステップが、前記検索項目を含む情報の暗号文を生成し、又は、前記検索項目を含む情報からマッピングして取得されるデータを生成することを特徴とする請求項１に記載の索引生成方法。
【請求項５】
前記索引項目の生成ステップが、前記検索情報を含む情報の暗号文を生成することを特徴とする請求項１に記載の索引生成方法。
【請求項６】
前記索引項目の生成ステップが、索引項目暗号鍵で対応する前記検索情報を含む情報を暗号化することを特徴とする請求項１に記載の索引生成方法。
【請求項７】
前記累積情報の生成ステップが、前記検索情報を含む情報の暗号文を累積し、又は、前記検索情報を含む情報からマッピングすることにより取得されるデータを累積することを特徴とする請求項１に記載の索引生成方法。
【請求項８】
１の前記検索情報が追加され又は削除された場合に、前記累積情報を更新するステップをさらに有することを特徴とする請求項１に記載の索引生成方法。
【請求項９】
前記累積情報は、
【数１３】
として計算され（ここで、I1, I2,
…Inは累積される検索情報であり、
【数１４】
はＸＯＲ演算を表わす）、
検索情報Iaが追加され又は削除される場合、累積情報を、
【数１５】
と更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１０】
前記累積情報は、
【数１６】
として計算され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
検索情報Iaが追加される場合、累積情報を、ICupdated = (IC * Ia) mod p
と更新し、
検索情報Ib が追加される場合、累積情報を、ICupdated = (IC * Ib-1)
mod pと更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１１】
前記累積情報は、
【数１７】
として計算され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
検索情報Iaが追加される場合、累積情報を、ICupdated = (IC + Ia) mod p
と更新し、
検索情報Ib が追加される場合、累積情報を、ICupdated = (IC - Ib) mod pと更新することを特徴とする請求項８に記載の索引生成方法。
【請求項１２】
前記累積情報は、
g2とKが公開され、あるいはg2kが公開された場合、
【数１８】
として計算され（ここで、Ijは、累積される検索情報であり、skは、秘密キーであり、pは大きな素数、HはG1に文字列をマッピングするハッシュ関数、KはZp*内の乱数、Zp*はp未満でpと互いに素であるすべての正整数の集合、g2はG2のジェネレータ、G1とG2は位数pのグループであり、G1とG2について双線型写像が存在する）、
検索情報Iaが追加される場合、累積情報を、
ICupdated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開し（ここで、K’はZp*内のKと異なる乱数）、
検索情報Ib が追加される場合、
[IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開する（ここで、K’はZp*内のKと異なる乱数）
ことを特徴とする請求項８に記載の索引生成方法。
【請求項１３】
検索項目に対応する検索項目識別子を生成する検索項目識別子生成ユニットと、
前記検索項目と関連する１以上の検索情報に従って１つ以上の索引項目を生成する索引項目生成ユニットと、
１以上の前記検索情報について累積情報を生成する累積情報生成ユニットと、
少なくとも検索項目識別子、１つ以上の索引項目および累積情報を有する索引エントリを生成して、索引を形成する索引形成ユニットと
を備えることを特徴とする索引生成装置。
【請求項１４】
前記累積情報生成ユニットは、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって１以上の情報を累積することを特徴とする請求項１３に記載の索引生成装置。
【請求項１５】
前記検索項目がキーワードであり、前記検索情報が前記キーワードを含むファイルの暗号化されたファイル名であることを特徴とする請求項１３に記載の索引生成装置。
【請求項１６】
前記検索項目識別子生成ユニットが、前記検索項目を含む情報の暗号文を生成し、又は、前記検索項目を含む情報からマッピングして取得されるデータを生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１７】
前記索引項目生成ユニットが、前記検索情報を含む情報の暗号文を生成することにより前記索引項目を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１８】
前記索引項目生成ユニットが、索引項目暗号鍵で対応する前記検索情報を含む情報を暗号化することにより前記索引項目を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項１９】
前記累積情報生成ユニットが、前記検索情報を含む情報の暗号文を累積し、又は、前記検索情報を含む情報からマッピングすることにより取得されるデータを累積することにより前記累積情報を生成するように構成されることを特徴とする請求項１３に記載の索引生成装置。
【請求項２０】
１の前記検索情報が追加され又は削除された場合に、前記累積情報を更新する更新ユニットをさらに備えることを特徴とする請求項１３に記載の索引生成装置。
【請求項２１】
前記累積情報生成ユニットが、前記累積情報を、
【数１９】
として計算するように構成され（ここで、I1, I2,
…Inは、累積される検索情報であり、
【数２０】
はＸＯＲ演算を表わす）、
前記更新ユニットが、検索情報Iaが追加され又は削除される場合、累積情報を、
【数２１】
と更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２２】
前記累積情報生成ユニットが、
前記累積情報を、
【数２２】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
前記更新ユニットが、検索情報Iaが追加される場合、累積情報を、ICupdated = (IC * Ia) mod p
と更新し、検索情報Ib が追加される場合、累積情報を、ICupdated = (IC * Ib-1) mod pと更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２３】
前記累積情報生成ユニットが、
前記累積情報を、
【数２３】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、pは大きな素数である。）、
前記更新ユニットが、検索情報Iaが追加される場合、累積情報を、
ICupdated = (IC + Ia) mod p
と更新し、検索情報Ib が追加される場合、累積情報を、
ICupdated = (IC - Ib) mod p
と更新するように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２４】
前記累積情報生成ユニットが、
前記累積情報を、
g2とKが公開され、あるいはg2kが公開された場合、
【数２４】
として計算するように構成され（ここで、Ijは、累積される検索情報であり、skは、秘密キーであり、pは大きな素数、HはG1に文字列をマッピングするハッシュ関数、KはZp*内の乱数、Zp*はp未満でpと互いに素であるすべての正整数の集合、g2はG2のジェネレータ、G1とG2は位数pのグループであり、G1とG2について双線型写像が存在する）、
前記更新ユニットが、
検索情報Iaが追加される場合、累積情報を、
ICupdated = [IC(sk+K) * H(Ia) mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開し（ここで、K’はZp*内のKと異なる乱数）、
検索情報Ib が追加される場合、
[IC(sk+K) * H(Ib)-1 mod p]1/(sk+K’)
と更新し、K’あるいはg2k’を公開する（ここで、K’はZp*内のKと異なる乱数）ように構成されることを特徴とする請求項２０に記載の索引生成装置。
【請求項２５】
検索要求を生成するステップと、
１以上の索引項目および１つの累積情報を受信するステップと、
受信した１以上の前記索引項目から１以上の検索情報を抽出するステップと、
受信した前記累積情報によって抽出した前記検索情報を検証するステップと
を含むことを特徴とする検索方法。
【請求項２６】
前記検索情報を検証するステップが、
抽出した前記検索情報によって累積情報を計算するステップと、
計算した累積情報を受信した累積情報と照合するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２７】
前記検索情報を検証するステップが、集合署名を検証するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２８】
前記検索情報を抽出するステップが、１以上の索引項目を解読するステップを含むことを特徴とする請求項２５に記載の検索方法。
【請求項２９】
前記累積情報を計算するステップが、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって検索情報を累積するステップを含むことを特徴とする請求項２６に記載の検索方法。
【請求項３０】
前記累積情報を計算するステップが、
前記検索情報を含む情報の暗号文を累積し、あるいは前記検索情報を含む情報からマッピングすることにより取得されたデータを累積するステップを含むことを特徴とする請求項２６に記載の検索方法。
【請求項３１】
検索要求を生成する検索要求ユニットと、
１以上の受信した索引項目から１以上の検索情報を抽出する検索情報抽出ユニットと、
受信した前記累積情報によって抽出した前記検索情報を検証する検証ユニットと
を備えることを特徴とする検索装置。
【請求項３２】
前記検証ユニットは、
抽出した前記検索情報によって累積情報を計算し、計算した累積情報を受信した累積情報と照合するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３３】
前記検証ユニットは、集合署名を検証するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３４】
前記検索情報抽出ユニットは、１以上の索引項目を解読することにより前記検索情報を抽出するように構成されることを特徴とする請求項３１に記載の検索装置。
【請求項３５】
前記検証ユニットは、集合署名、ＸＯＲ演算および剰余演算の少なくとも１つによって検索情報を累積することにより、累積情報を計算するように構成されることを特徴とする請求項３２に記載の検索装置。
【請求項３６】
前記検証ユニットは、
前記検索情報を含む情報の暗号文を累積し、あるいは前記検索情報を含む情報からマッピングすることにより取得されたデータを累積することにより、累積情報を計算するように構成されることを特徴とする請求項３２に記載の検索装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−２０５２５８（Ｐ２０１０−２０５２５８Ａ）
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【外国語出願】
【出願番号】特願２００９−２５７６４５（Ｐ２００９−２５７６４５）
【出願日】平成２１年１１月１１日（２００９．１１．１１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
【公開日】平成２２年９月１６日（２０１０．９．１６）
【国際特許分類】
【出願番号】特願２００９−２５７６４５（Ｐ２００９−２５７６４５）
【出願日】平成２１年１１月１１日（２００９．１１．１１）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（５０５４１８８７０）エヌイーシー（チャイナ）カンパニー， リミテッド (108)
【氏名又は名称原語表記】ＮＥＣ（Ｃｈｉｎａ）Ｃｏ．，Ｌｔｄ．
【Ｆターム（参考）】
[ Back to top ]