(57)【特許請求の範囲】
【請求項１】
複数の検索対象データを記憶する検索対象データ記憶部と、
複数の配列要素を有する索引データであって、前記複数の配列要素のうち前記索引データに対応付けるラベルと前記複数の検索対象データの少なくともいずれかの検索対象データに関連するキーワードとに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定された複数の索引データを記憶する索引データ記憶部と、
特定のラベルと特定のキーワードとに基づいて定まる配列要素を指定する検索要求データが入力される検索要求データ入力部と、
前記複数の配列要素のうち前記検索要求データ入力部に入力された前記検索要求データが指定する配列要素からデータ名を取得し、取得したデータ名の検索対象データを前記検索対象データ記憶部から取得するデータ検索部と、
前記データ検索部によって取得された検索対象データを含んだ検索結果データを出力する検索結果データ出力部と
を備えることを特徴とする検索装置。
【請求項２】
前記索引データは、
前記キーワードと前記ラベルと前記キーワードに関連することを示す関連識別子とに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定され、
前記キーワードと前記ラベルと前記キーワードに関連しないことを示す非関連識別子とに基づいて定まる配列要素に、前記キーワードに関連しない検索対象データのデータ名が設定されたデータである
ことを特徴とする請求項１記載の検索装置。
【請求項３】
前記索引データは、前記キーワードを表すビット列と前記ラベルを表すビット列とを含んだビット列データを所定の関数に入力して得られる関数値を用いて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである
ことを特徴とする請求項１または請求項２記載の検索装置。
【請求項４】
前記索引データは、前記関数値によって識別される配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである
ことを特徴とする請求項３記載の検索装置。
【請求項５】
キーワードと、検索対象データのデータ名が設定される複数の配列要素を有する索引データに対応付けるラベルとが入力されるキーワード入力部と、
前記キーワード入力部に入力された前記キーワードと前記ラベルとに基づいて、前記索引データのいずれかの配列要素を指定する検索要求データを生成する検索要求データ生成部と、
前記検索要求データ生成部によって生成された前記検索要求データを複数の検索対象データと前記索引データとを記憶する検索装置に送信し、前記複数の検索対象データのうち前記検索要求データによって指定される前記配列要素に設定されたデータ名の検索対象データを含んだ検索結果データを受信する検索結果データ受信部と
を備えることを特徴とする検索端末装置。
【請求項６】
検索対象データと、前記検索対象データに関連するキーワードとを記憶する検索対象データ記憶部と、
複数の配列要素を有する索引データを生成する索引データ生成部であって、前記索引データに対応付けるラベルと前記キーワードとに基づいて前記検索対象データのデータ名を設定する配列要素を決定し、決定した配列要素に前記検索対象データのデータ名を設定する索引データ生成部と、
前記検索対象データと前記索引データ生成部によって生成された前記索引データとを、前記索引データを用いて前記検索対象データの検索を行わせる検索装置に送信することによって、前記検索装置に前記検索対象データと前記索引データとを記憶させる検索対象データ登録部と
を備えることを特徴とするデータ登録装置。
【請求項７】
前記検索対象データ記憶部は、新たな検索対象データと、前記新たな検索対象データに関連するキーワードとを記憶し、
前記データ登録装置は、
前記索引データに対応付ける前記ラベルと前記新たな検索対象データに関連する前記キーワードとに基づいて前記新たな検索対象データのデータ名を設定する配列要素を決定し、決定した配列要素を識別するアドレスと前記新たな検索対象データとを含んだ追加要求データを生成する追加要求データ生成部を備え、
前記検索対象データ登録部は、前記追加要求データ生成部によって生成された前記追加要求データを前記検索装置に送信することによって、前記検索装置に前記追加要求データに含まれる前記新たな検索対象データを記憶させ、前記索引データの前記複数の配列要素のうち前記追加要求データに含まれる前記アドレスで識別される配列要素に前記新たな検索対象データのデータ名を設定させる
ことを特徴とする請求項６記載のデータ登録装置。
【請求項８】
検索対象データ記憶部と、索引データ記憶部と、検索要求データ入力部と、データ検索部と、検索結果データ出力部とを備える検索装置によって実行する検索方法であって、
前記検索対象データ記憶部は、複数の検索対象データを記憶する記憶部であり、
前記索引データ記憶部は、複数の配列要素を有する索引データであって、前記複数の配列要素のうち前記索引データに対応付けるラベルと前記複数の検索対象データの少なくともいずれかの検索対象データに関連するキーワードとに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定された複数の索引データを記憶する記憶部であり、
前記検索要求データ入力部が、特定のラベルと特定のキーワードとに基づいて定まる配列要素を指定する検索要求データを入力し、
前記データ検索部が、前記複数の配列要素のうち前記検索要求データ入力部に入力された前記検索要求データが指定する配列要素からデータ名を取得し、取得したデータ名の検索対象データを前記検索対象データ記憶部から取得し、
前記検索結果データ出力部が、前記データ検索部によって取得された検索対象データを含んだ検索結果データを出力する
ことを特徴とする検索方法。
【請求項９】
請求項８記載の検索方法をコンピュータに実行させるための検索プログラム。
【請求項１０】
キーワード入力部と、検索要求データ生成部と、検索結果データ受信部とを備える検索端末装置によって実行する検索方法であって、
前記キーワード入力部が、キーワードと、検索対象データのデータ名が設定される複数の配列要素を有する索引データに対応付けるラベルとを入力し、
前記検索要求データ生成部が、前記キーワード入力部に入力された前記キーワードと前記ラベルとに基づいて、前記索引データのいずれかの配列要素を指定する検索要求データを生成し、
前記検索結果データ受信部が、前記検索要求データ生成部によって生成された前記検索要求データを複数の検索対象データと前記索引データとを記憶する検索装置に送信し、前記複数の検索対象データのうち前記検索要求データによって指定される前記配列要素に設定されたデータ名の検索対象データを含んだ検索結果データを受信する
ことを特徴とする検索方法。
【請求項１１】
請求項１０記載の検索方法をコンピュータに実行させるための検索プログラム。
【請求項１２】
検索対象データと前記検索対象データに関連するキーワードとを記憶する検索対象データ記憶部と、索引データ生成部と、検索対象データ登録部とを備えるデータ登録装置によって実行するデータ登録方法であって、
前記索引データ生成部が、複数の配列要素を有する索引データを生成する索引データ生成部であって、前記索引データに対応付けるラベルと前記キーワードとに基づいて前記検索対象データのデータ名を設定する配列要素を決定し、決定した配列要素に前記検索対象データのデータ名を設定し、
前記検索対象データ登録部が、前記検索対象データと前記索引データ生成部によって生成された前記索引データとを、前記索引データを用いて前記検索対象データの検索を行わせる検索装置に送信することによって、前記検索装置に前記検索対象データと前記索引データとを記憶させる
ことを特徴とするデータ登録方法。
【請求項１３】
請求項１２記載のデータ登録方法をコンピュータに実行させるためのデータ登録プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、例えば、秘匿検索を行うための検索装置、検索端末装置、データ登録装置、検索方法、検索プログラム、データ登録方法およびデータ登録プログラムに関するものである。
【背景技術】
【０００２】
秘匿検索とは、暗号化データを暗号化したまま検索できる技術である。
近年、クラウドサービス等の普及によりインターネット上でデータ管理が可能となった。しかし、インターネット上でのデータ管理には、預けたデータがコンピュータウィルスやデータセンタの管理者の不正によって漏洩する、といったセキュリティ上の課題がある。秘匿検索はそのような課題を解決する技術の１つとして注目されている。
【０００３】
秘匿検索は、大きく分けて、公開鍵暗号を利用した方式（例えば、非特許文献５と非特許文献６）と、共通鍵暗号（秘密鍵暗号または対称鍵暗号ともいう）を利用した方式（例えば、非特許文献１、非特許文献２、非特許文献３、非特許文献４、非特許文献７）との２種類が存在する。
公開鍵暗号ベースの秘匿検索方式は、（公開鍵を用いて）どのエンティティ（ユーザ端末）もデータセンタへのデータ登録が可能であり、また秘密鍵を所持しているエンティティのみからキーワード検索が可能である方式である。
共通鍵暗号ベースの秘匿検索方式は、データ登録とキーワード検索共に、秘密鍵を所持しているエンティティのみが可能な方式である。
【０００４】
共通鍵暗号ベースの秘匿検索方式は、上記のようにデータ登録とキーワード検索共に秘密鍵を所持しているエンティティに限られているものの、公開鍵暗号ベースの方式と比べて検索処理が高速である。
公開鍵暗号ベースの多くの方式は、登録データ数の線型に比例して検索コストがかかり、様々な工夫を施さない限り現実的な利用は難しい。登録データ数のログに比例した検索コストで済むような高速な方式も一部で提案されているが（例えば、非特許文献６）、登録データに対して強い制約を課しており、現実的には十分な安全性を持っているとはいえない。
なお、現在最も高速な検索が可能であると考えられている共通鍵暗号ベースの秘匿検索方式は、（予め設定されている）利用可能なキーワード数のログ程度のコストで検索することができる（例えば、非特許文献１、非特許文献２、非特許文献３、非特許文献７）。
【０００５】
共通鍵暗号ベースの秘匿検索の中で特に高速に検索可能な方式は、以下のような流れをベースにして実行される。ただし、データの登録および検索をしたいエンティティ（以下、ユーザ、登録者または検索者とも呼ぶ）は、事前準備として、秘密鍵を生成しておき、この秘密鍵を他人に漏らさないように厳重に保管しておく。
【０００６】
クラウドサービス等を利用してデータをデータセンタに預けたいユーザ（登録者）は、登録したいデータのキーワードを決定して、各キーワードに対してヒットするデータのデータ名のリストを作成する（図２０参照）。例えば、図２０は、ｋｅｙｗｏｒｄ−１が検索キーワードである場合、検索でヒットするデータのデータ名がデータ１、データ３およびデータ５であることを示している。
【０００７】
次に、ユーザは、秘密鍵を用いて索引を作成する。索引とは、検索結果をまとめたものである。索引の生成方法や索引の構造は方式によって異なる。
例えば、配列構造の索引を用意し、各キーワードの検索結果（または暗号化した検索結果）をランダムなアドレス（配列要素の記憶領域）に格納して索引を生成する。このランダムなアドレスは、キーワードと秘密鍵とを入力にして確定的に生成される乱数によって決定される。確定的とは、入力する秘密鍵とキーワードとが同じであれば、いつも同じ乱数が生成される、といった意味である。
索引にはキーワードは格納されず検索結果のみが格納され、秘密鍵を持っているユーザのみがキーワードと検索結果とを結びつけることができる。
【０００８】
最後に、ユーザは、登録したいデータをＡＥＳやＣａｍｅｌｌｉａなどの共通鍵暗号方式を用いて暗号化し、索引と暗号化データとをデータセンタに登録する。
【０００９】
データセンタに預けた暗号化データを検索したいユーザ（検索者）は、検索したいキーワードと秘密鍵とを使って乱数を生成し、生成した乱数を含んだ検索クエリをデータセンタに送信する。方式によっては、キーワードと秘密鍵とを使って部分検索鍵を生成し、乱数と部分検索鍵とを含んだ検索クエリをデータセンタに送信する。
【００１０】
次に、データセンタは、受け取った検索クエリ内の乱数に基づき索引内のあるアドレスから検索結果を引き出す。この検索結果が暗号化されていれば、検索クエリ内の部分検索鍵を用いて検索結果を復号する。データセンタは、検索結果が示すデータ名に対応した暗号化データをユーザに送る。
【００１１】
最後に、ユーザは、受け取った暗号化データを秘密鍵を使って復号する。これにより、検索にヒットしたデータが得られる。
【００１２】
以上のような流れで、共通鍵暗号ベースの秘匿検索においてデータ登録およびキーワード検索が行われる。
但し、実際の運用上では、ユーザからデータを追加登録したいといった要請がある。非特許文献１と非特許文献３とを除く高速検索が可能な共通鍵暗号ベースの秘匿検索方式は、暗号化データを追加登録する度に新たな索引が生成され、追加の暗号化データと共に新たな索引がデータセンタに預けられる。
【００１３】
非特許文献１または非特許文献３の秘匿検索方式（または高速検索可能ではないが非特許文献４の秘匿検索方式）は、データを追加登録する度に新たな索引を生成しなくてもよい。
これらの方式において、ユーザは、追加の暗号化データに加えて、すでに登録されている索引に対して追加の暗号化データに関する（暗号化した）更新情報を作成し、追加の暗号化データと更新情報とをデータセンタに送る。データセンタは、受け取った更新情報に基づき索引に対して更新処理を行う。これにより、追加の暗号化データの情報を漏らさずに追加の暗号化データの検索結果を索引に反映することができる。
しかしながら、この方式は、索引の生成時に暗号化データを追加登録できる回数が予め決定されてしまうため、その回数を越えて暗号化データの追加登録を行うことができない。このため、この方式を用いても、追加登録できる回数を超えて暗号化データの追加登録を行うときには索引を追加する必要がある。
【００１４】
索引を追加する秘匿検索方式では、安全性の観点から、新たな索引を生成するたびに新たな秘密鍵を生成する必要がある。もし秘密鍵を新たに生成せずにすべての索引を共通の秘密鍵を用いて生成してしまうと、検索クエリがすべての索引に対して共通なものになってしまう。つまり、ある索引に対してのみ適用可能な検索クエリを生成することができない。もし、ある検索キーワードに対してヒットするデータ数が索引によって大きく異なる場合、悪意のあるデータセンタの管理者によって以下のような頻度分析が可能となり、登録データについての情報が漏洩する可能性を引き起こす。
【００１５】
例えば、ユーザがあるメーカーの広報部に所属しているものとする。このユーザは、ドキュメントを月ごとにまとめて追加登録している。このため、索引は１ヶ月ごとに新たに作成される。また、悪意のあるデータセンタの管理者は、そのユーザがあるメーカーの広報部に所属していること、索引１が２０１１年９月に作成されたこと、および索引２が２０１１年１０月に作成されたことを知っているものとする。
ここで、ユーザは索引２に対してあるキーワードを用いて検索するために検索クエリをデータセンタに送る。
しかし、悪意のあるデータセンタの管理者は、検索クエリを索引２に対してだけではなく索引１にも適用して検索を行う。このとき、索引２から非常に多くの検索結果が得られたが、索引１からはほとんど検索結果が得られなかった。この場合、悪意のあるデータセンタの管理者は、索引間の頻度の差からこの検索クエリに含まれているキーワードが「新製品」に関するものだと推測することができる。もし、検索キーワードがそのような情報を含んでいたとしたら、企業機密（インサイダー情報）が外部に流出してしまい大きな問題となる。
【００１６】
また、入退室に関するログ情報の検索を例に挙げる。
悪意のあるデータセンタの管理者は、それぞれの索引の検索ヒット数の大きな違いから、人事異動で新しく配属された人に関するキーワードが検索クエリに含まれていると推測することができる。さらに、悪意のあるデータセンタの管理者が人事情報を知っている場合、検索クエリに含まれるキーワードが一意に特定されてしまう可能性がある。特に、ログデータの中身はキーワードと直結する場合が多いため、キーワードが特定されることによってデータの情報が漏洩する危険性がある。
【００１７】
上記のような安全性の問題から、従来の秘匿検索方式は、秘密鍵を索引毎に生成することで検索クエリがすべての索引間で共通にならず、キーワードが漏洩しないように対応していた。
しかしながら、そのような対策は、データが頻繁に追加されるとデータ数と索引数とがほぼ等しくなり、索引が増加するにつれて秘密鍵を管理する手間が発生してしまう。
【００１８】
特許文献１は、共通鍵暗号の中で確定的暗号を用いてデータを暗号化したまま検索可能な技術を開示している。この技術は、暗号文が確定的であることを使って、データを暗号化したまま柔軟な検索が可能であり、かつデータの追加および削除が可能である。但し、特許文献１は、データ追加時に秘密鍵の数を増やさないための技術については開示も示唆もしていない。
【００１９】
特許文献２は、データを暗号化したまま検索するための暗号化データベースの管理方法を開示している。この方法は、鍵数を増やして安全性を高めようとする方法であるため、鍵管理の手間が発生してしまう。
【００２０】
特許文献３は、データを暗号化したまま検索するためにデータの登録や検索などを代理人に委託する方法を開示している。この方法は、データ登録や検索をユーザやサーバ以外のエンティティである検索代理人に実行させ、「ユーザ以外にデータ情報が一切漏れない」という秘匿検索の特徴について開示も示唆もしていない。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００２−２７８９７０号公報
【特許文献２】特開平１１−１１３７８０号公報
【特許文献３】特開２００９−２１１３８４号公報
【非特許文献】
【００２２】
【非特許文献１】Ｓ．Ｋａｍａｒａ，Ｃ．Ｐａｐａｍａｎｔｈｏｕ，ａｎｄ  Ｔ．Ｒｏｅｄｅｒ．“ＣＳ２：Ａ  Ｓｅａｒｃｈａｂｌｅ  Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｃｌｏｕｄ  Ｓｔｒａｇｅ  Ｓｙｓｔｅｍ”．ＭＳＲ  Ｔｅｃｈ  Ｒｅｐｏｒｔ  ｎｏ．  ＭＳＲ−ＴＲ−２０１１−５８，２０１１．
【非特許文献２】Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｇａｒａｙ，Ｓ．Ｋａｍａｒａ，ａｎｄ  Ｒ．Ｏｓｔｒｏｖｓｋｙ．“Ｓｅａｒｃｈａｂｌｅ  Ｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ：Ｉｍｐｒｏｖｅｄ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ”．ＡＣＭ  ＣＣＳ  ２００６，ＡＣＭ，２００６．
【非特許文献３】Ｐ．ｖａｎ  Ｌｉｅｓｄｏｎｋ，Ｓ．Ｓｅｄｇｈｉ，Ｊ．Ｄｏｕｍｅｎ，Ｐ．Ｈａｒｔｅｌ，ａｎｄ  Ｗ．Ｊｏｎｋｅｒ．“Ｃｏｍｐｕｔａｔｉｏｎａｌｌｙ  Ｅｆｆｉｃｉｅｎｔ  Ｓｅａｒｃｈａｂｌｅ  Ｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ”．ＳＤＭ  ２０１０，Ｌｅｃｕｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ６３５８，Ｓｐｒｉｎｇｅｒ，２０１０．
【非特許文献４】Ｃ．Ｂｏｓｃｈ，Ｒ．Ｂｒｉｎｋｍａｎ，Ｐ．Ｈａｒｔｅｌ，ａｎｄ  Ｗ．Ｊｏｎｋｅｒ．“Ｃｏｎｊｕｎｃｔｉｖｅ  Ｗｉｌｄｃａｒｄ  Ｓｅａｒｃｈ  ｏｖｅｒ  Ｅｎｃｒｙｐｔｅｄ  Ｄａｔａ”．ＳＤＭ  ２０１１，Ｌｅｃｕｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ６９３３，Ｓｐｒｉｎｇｅｒ，２０１１．
【非特許文献５】Ｄ．Ｂｏｎｅｈ，Ｇ．Ｄ．Ｃｒｅｓｃｅｎｚｏ，Ｒ．Ｏｓｔｒｏｖｓｋｙ，ａｎｄ  Ｇ．Ｐｅｒｓｉａｎｏ．“Ｐｕｂｌｉｃ  Ｋｅｙ  Ｅｎｃｒｙｐｔｉｏｎ  ｗｉｔｈ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ”．ＥＵＲＯＣＲＹＰＴ  ２００４，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ３０２７，Ｓｐｒｉｎｇｅｒ，２００４．
【非特許文献６】Ｍ．Ｂｅｌｌａｒｅ，Ａ．Ｂｏｌｄｙｒｅｖａ，ａｎｄ  Ａ．Ｏ’Ｎｅｉｌｌ．“Ｄｅｔｅｒｍｉｎｉｓｔｉｃ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔｌｙ  Ｓｅａｒｃｈａｂｌｅ  Ｅｎｃｒｙｐｔｉｏｎ”．ＣＲＹＰＴＯ  ２００７，Ｌｅｃｔｕｒｅ  Ｎｏｔｅｓ  ｉｎ  Ｃｏｍｐｕｔｅｒ  Ｓｃｉｅｎｃｅ  ４６２２，２００７．
【非特許文献７】尾形，金岡，松尾．“ＳＥＡＲＣＨＡＢＬＥ  ＳＹＭＭＥＴＲＩＣ  ＥＮＣＲＹＰＴＩＯＮはどこまで安全にすべきか？”．ＳＣＩＳ２０１２，２０１２．
【発明の概要】
【発明が解決しようとする課題】
【００２３】
本発明は、例えば、秘匿検索を容易に行えるようにすることを目的とする。
【課題を解決するための手段】
【００２４】
本発明の検索装置は、
複数の検索対象データを記憶する検索対象データ記憶部と、
複数の配列要素を有する索引データであって、前記複数の配列要素のうち前記索引データに対応付けるラベルと前記複数の検索対象データの少なくともいずれかの検索対象データに関連するキーワードとに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定された複数の索引データを記憶する索引データ記憶部と、
特定のラベルと特定のキーワードとに基づいて定まる配列要素を指定する検索要求データが入力される検索要求データ入力部と、
前記複数の配列要素のうち前記検索要求データ入力部に入力された前記検索要求データが指定する配列要素からデータ名を取得し、取得したデータ名の検索対象データを前記検索対象データ記憶部から取得するデータ検索部と、
前記データ検索部によって取得された検索対象データを含んだ検索結果データを出力する検索結果データ出力部とを備える。
【発明の効果】
【００２５】
本発明によれば、例えば、秘匿検索を容易に行うことができる。
【図面の簡単な説明】
【００２６】
【図１】実施の形態１における秘匿検索システム１００の構成図。
【図２】実施の形態１におけるアクセス端末２０１の機能構成図。
【図３】実施の形態１におけるデータセンタ３０１の機能構成図。
【図４】実施の形態１における秘匿検索システム１００の初期設定処理（概要）を示すフローチャート。
【図５】実施の形態１における秘匿検索システム１００のデータ登録処理（概要）を示すフローチャート。
【図６】実施の形態１における秘匿検索システム１００の検索処理（概要）を示すフローチャート。
【図７】実施の形態１における秘匿検索システム１００のデータ追加処理（概要）を示すフローチャート。
【図８】実施の形態１におけるラベル付き索引の削除更新処理（概要）を示すフローチャート。
【図９】実施の形態１における秘匿検索システム１００のデータ削除処理（概要）を示すフローチャート。
【図１０】実施の形態１における秘匿検索システム１００の索引削除処理（概要）を示すフローチャート。
【図１１】実施の形態１における秘匿検索システム１００初期設定処理（具体例）を示すフローチャート。
【図１２】実施の形態１における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャート。
【図１３】実施の形態１における秘匿検索システム１００の検索処理（具体例）を示すフローチャート。
【図１４】実施の形態１における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャート。
【図１５】実施の形態１における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャート。
【図１６】実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャート。
【図１７】実施の形態１における秘匿検索システム１００のデータ削除処理および索引削除処理（具体例）を示すフローチャート。
【図１８】実施の形態１におけるラベル管理部２０４の管理テーブルを示す図。
【図１９】実施の形態１におけるアクセス端末２０１およびデータセンタ３０１のハードウェア資源の一例を示す図。
【図２０】キーワード別の検索結果情報を管理するための検索結果テーブルを示す図。
【図２１】実施の形態２における秘匿検索システム１００初期設定処理（具体例）を示すフローチャート。
【図２２】実施の形態２における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャート（１／３）。
【図２３】実施の形態２における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャート（２／３）。
【図２４】実施の形態２における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャート（３／３）。
【図２５】実施の形態２における秘匿検索システム１００の検索処理（具体例）を示すフローチャート。
【図２６】実施の形態２における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャート（１／３）。
【図２７】実施の形態２における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャート（２／３）。
【図２８】実施の形態２における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャート（３／３）。
【図２９】実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャート（１／３）。
【図３０】実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャート（２／３）。
【図３１】実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャート（３／３）。
【図３２】実施の形態２におけるラベル管理部２０４の管理テーブルを示す図。
【発明を実施するための形態】
【００２７】
実施の形態１．
索引に対応付けるラベルを用いることによって秘匿検索を容易にする秘匿検索システムについて説明する。
【００２８】
図１は、実施の形態１における秘匿検索システム１００の構成図である。
実施の形態１における秘匿検索システム１００の構成について、図１に基づいて説明する。
【００２９】
秘匿検索システム１００は、データセンタ３０１と複数のアクセス端末２０１ａからｍとを備える。
データセンタ３０１とアクセス端末２０１ａ−ｍは、社内ＬＡＮ１０２やネットワーク１０１を介して通信を行う。
【００３０】
アクセス端末２０１は、企業内のユーザが利用するＰＣ（パーソナルコンピュータ）である。アクセス端末２０１は、登録装置、更新装置、削除装置、検索要求装置、暗号化装置または復号装置として機能する。
アクセス端末２０１は、後述する暗号化データやラベル付き索引を生成してデータセンタ３０１に保管を依頼する。
アクセス端末２０１は、後述するラベル付き検索クエリをデータセンタ３０１に送信してデータの検索を依頼し、データセンタ３０１から送られてくる暗号化データを復号する。
アクセス端末２０１は、データセンタ３０１に対してラベル付き索引の更新、暗号化データの追加登録、暗号化データの削除、またはラベル付き索引の削除を更新情報によって依頼する。
【００３１】
データセンタ３０１は、アクセス端末２０１によって作成された暗号化データやラベル付き索引を保管する大容量の記憶装置を持つとともに、アクセス端末２０１の更新情報をもとにラベル付き索引などを更新するサーバである。データセンタ３０１は暗号化データ保管装置、索引保管装置、索引更新装置または検索装置として機能する。
データセンタ３０１は、ラベル付き検索クエリに基づいてラベル付き索引から検索結果情報を得るとともに、検索結果情報が示す暗号化データをアクセス端末２０１に送信する。
また、データセンタ３０１は、ラベル付き索引や暗号化データの削除依頼があれば保管しているラベル付き索引や暗号化データを削除する。
【００３２】
データ、ラベル付き索引、ラベル付き検索クエリは暗号化されるため、データセンタ３０１ではそれらの中身を閲覧することができない。
また、アクセス端末２０１によって作成される更新情報は暗号化されるため、データセンタ３０１はラベル付き索引に対してどのような情報の更新がなされたのか知ることはできない。
アクセス端末２０１ａ−ｍは、検索対象のデータをデータセンタ３０１に登録する登録端末またはデータセンタ３０１に対してデータ検索を要求する検索端末として動作するコンピュータである。
アクセス端末２０１ａ−ｍは、社内ＬＡＮ１０２（ネットワークの一例）に接続し、情報を共有する。
【００３３】
ネットワーク１０１は、社内ＬＡＮ１０２とデータセンタ３０１とを接続する通信路である。インターネットはネットワーク１０１の一例である。
【００３４】
社内ＬＡＮ１０２は、企業内に施設された通信路であり、企業内で利用される様々なサーバやパソコンが接続される。なお、複数の建物にオフィスを持つ場合は、ルータや専用線などを介して複雑な通信路構成となる。
【００３５】
図２は、実施の形態１におけるアクセス端末２０１の機能構成図である。
実施の形態１におけるアクセス端末２０１の機能構成について、図２に基づいて説明する。
【００３６】
アクセス端末２０１は、秘密鍵生成部２０２、秘密鍵管理部２０３、ラベル管理部２０４、キーワード設定部２０５（検索対象データ記憶部の一例）、データ暗号化部２０６、ラベル付き索引生成部２０７（索引データ生成部の一例）、追加更新情報生成部２０８（追加要求データ生成部の一例）、削除更新情報生成部２０９、削除要求生成部２１０、ラベル付き検索クエリ生成部２１１（キーワード入力部、検索要求データ生成部の一例）、データ復号部２１２、端末側データ送受信部２１３（検索結果データ受信部、検索対象データ登録部の一例）を備える。
アクセス端末２０１は、アクセス端末２０１で使用するデータを記憶する記憶部（記憶装置）（図示省略）を備える。
【００３７】
秘密鍵生成部２０２は、データを暗号化するための共通鍵暗号方式の暗号化鍵（復号鍵）を生成することに加えて、索引を生成するための索引鍵（検索鍵）を生成する。なお、暗号化鍵と索引鍵は本秘匿検索システムの秘密鍵であって、データの登録・追加・削除やキーワード検索を行うユーザ以外には開示しないように厳重に管理する。
なお、実施の形態では共通鍵暗号方式を用いる場合を例にして説明するが、ＲＳＡなどの公開鍵暗号方式を用いてもよい。公開鍵暗号方式において、暗号化に用いる公開鍵は公にしてもよいが、復号に用いる秘密鍵は厳重に管理する。
【００３８】
秘密鍵管理部２０３は、秘密鍵生成部２０２で生成された暗号化鍵と索引鍵を記憶装置に記憶する。
【００３９】
ラベル管理部２０４は、登録データ、追加データ、削除データ、キーワードと同時に入力されるラベル情報に基づいて、ラベル付き索引に付けるラベルを生成するとともに、入力されたラベル情報とラベルとを一緒に管理する。ラベル情報、ラベル、ラベル付き索引については後述する。
ラベル管理部２０４は、ラベル付き索引生成部２０７でラベル付き索引の生成時に設定されるパラメータや、追加更新情報生成部２０８や削除更新情報生成部２０９で変更されるパラメータをラベル情報と一緒に管理する。パラメータについては後述する。
ラベル管理部２０４は、ラベル付き索引生成時または更新時にキーワード設定部２０５で生成されるキーワードをラベル情報と一緒に管理する。
ラベルやラベル情報は厳重に管理する必要はない。例えば、ラベル付き索引生成部２０７で生成されるラベル付き索引やラベル付き検索クエリ生成部２１１で作成されるラベル付き検索クエリは、ラベルやラベル情報を知っていても秘密鍵を知らなければ誰にも作成することができない。
【００４０】
ラベル情報は、ビット列や文字列であれば何でもよい。例えば、データ登録やデータ追加時のラベル情報は、索引に付けたいラベル名や日付などでもよい。また、削除データのラベル情報は、削除データの検索結果情報が埋め込まれているラベル付き索引のラベル名やラベルの生成時に用いたラベル報でもよい。キーワードのラベル情報であれば、検索したいラベル付き索引のラベル名やラベルの生成時に用いたラベル情報でもよい。
ラベル情報は必ずしも登録データ、追加データ、削除データ、キーワードと同時に入力する必要はなく、ラベル管理部２０４が自動的にラベル情報を生成してもよい。例えば、登録データや追加データのラベル情報が空であれば、ラベル管理部２０４が保管しているラベル数に応じてラベル名を自動的に生成し、ラベル付き索引を作成してもよい。例えば、現在までにｎ個のラベルが保管されている場合、次のラベル名を「ｎ＋１」とする。また、削除データのラベル情報が空であれば、ラベルの生成時に登録データまたは追加データのデータ名をラベルと一緒に管理し、削除データのデータ名に対応するラベルを自動的に読み出してもよい。また、キーワードの補助情報が空であれば、今までに作られたすべてのラベル付き索引に対するラベル情報を自動的に読み出してもよい。
【００４１】
キーワード設定部２０５は、複数の登録データまたは追加データからキーワードを抽出するとともに、抽出した各キーワードに対して検索結果情報を作成する。キーワードは登録データまたは追加データから自動的に抽出せず、登録データまたは追加データの個々のデータに予めキーワードを定めておき、定められた各キーワードを用いて検索結果情報を作成してもよい。また、キーワード設定部２０５は、必要があればラベル付き索引の生成時または更新時にキーワード情報をラベル管理部２０４に送る。
【００４２】
データ暗号化部２０６は、秘密鍵管理部２０３に記憶されている暗号化鍵を用いて登録データまたは追加データを暗号化する。
【００４３】
ラベル付き索引生成部２０７は、秘密鍵管理部２０３に記憶されている索引鍵とラベル管理部２０４で管理されているラベルやパラメータを用いて、キーワード設定部２０５で生成された検索結果情報に関するラベル付き索引を生成する。ラベル付き索引はラベルが埋め込まれて暗号化されているため、ラベル付き索引から埋め込まれているラベルは漏れない。
ラベル付き索引生成部２０７は、ラベル付き索引の生成時に用いたパラメータをラベル管理部２０４に送る。
【００４４】
追加更新情報生成部２０８は、秘密鍵管理部２０３に記憶されている索引鍵とラベル管理部２０４で管理されている更新ターゲットのラベル付き索引に使われたラベルおよびパラメータを用いて、更新ターゲットのラベル付き索引に対する追加更新情報を生成する。追加更新情報は、キーワード設定部２０５で追加データを元に作られる追加の検索結果情報に関する情報である。追加更新情報は追加データの検索結果情報を暗号化して埋め込んだものであるため、追加更新情報から追加データの情報は漏れない。
追加更新情報生成部２０８は、追加更新情報の生成時に用いたパラメータの更新情報をラベル管理部２０４に送る。
【００４５】
削除更新情報生成部２０９は、秘密鍵管理部２０３に記憶されている索引鍵とラベル管理部２０４で管理されているラベルとパラメータとを用いて削除索引更新情報を生成する。削除索引更新は登録データを削除してラベル付き索引を更新するための情報である。削除更新情報は削除データの検索結果情報を暗号化して埋め込んだものであるため、削除更新情報から削除データの情報は漏れない。
削除更新情報生成部２０９は、削除更新情報の生成時に用いたパラメータの更新情報をラベル管理部２０４に送る。
【００４６】
削除要求生成部２１０は、削除データ名または削除索引名（または両方）とラベル管理部２０４で管理されているラベルとを用いて、ラベル付き索引または暗号化データ（または両方）の削除を要求する削除要求を生成する。
【００４７】
ラベル付き検索クエリ生成部２１１は、秘密鍵管理部２０３に記憶されている索引鍵とラベル管理部２０４で管理されているラベルとを用いて、検索キーワードに関するラベル付き検索クエリを生成する。ラベル付き検索クエリはユーザが指定したラベル付き索引に対してのみ検索可能な情報であって、指定されていないラベル付き索引に対する検索はできない。つまり、索引と検索クエリとに埋め込まれたラベルが同じであるときに限り、検索が可能な仕組みである。ラベル付き検索クエリはキーワードやラベルを暗号化して埋め込んだものであるため、ラベル付き検索クエリからキーワードに関する情報やラベルは漏洩しない。
【００４８】
データ復号部２１２は、データセンタ３０１から受け取った暗号化データを、秘密鍵管理部２０２に記憶されている暗号化鍵を用いてを復号する。
【００４９】
端末側データ送受信部２１３は、データ暗号化部２０６で生成される暗号化データ、ラベル付き索引生成部２０７で生成されるラベル付き索引、追加更新情報生成部２０８で生成される追加更新情報、削除更新情報生成部２０９で生成される削除更新情報、索引削除要求生成部２１０で生成される索引削除要求、ラベル付き検索クエリ生成部２１１で生成されるラベル付き検索クエリなどを送信する。
端末側データ送受信部２１３は、データセンタ３０１から送信される暗号化データを受信する。
【００５０】
図３は、実施の形態１におけるデータセンタ３０１の機能構成図である。
実施の形態１におけるデータセンタ３０１の機能構成について、図３に基づいて説明する。
【００５１】
データセンタ３０１は、センタ側データ送受信部３０２（検索要求データ入力部、検索結果データ出力部の一例）、暗号化データ保管部３０３（検索対象データ記憶部の一例）、ラベル付き索引保管部３０４（索引データ記憶部の一例）、検索処理部３０５（データ検索部の一例）、ラベル付き索引更新部３０６を備える。
データセンタ３０１は、データセンタ３０１で使用するデータを記憶する記憶部（記憶装置）（図示省略）を備える。
【００５２】
センタ側データ送受信部３０２は、アクセス端末２０１から暗号化データ、ラベル付き索引、追加更新情報、削除更新情報、索引削除要求、ラベル付き検索クエリなどを受信する。
センタ側データ送受信部３０２は、検索処理部３０５の検索によって得られる暗号化データをアクセス端末２０１に送信する。
【００５３】
暗号化データ保管部３０３は暗号化データを記憶装置に記憶する。暗号化データ保管部３０３は検索処理部３０５からデータ名が送られてきたら、記憶装置からそのデータ名の暗号化データを取り出し、取り出した暗号化データを検索処理部３０５に送る。
暗号化データ保管部３０３は、ラベル付き索引更新部３０６から送られてくるデータ名の暗号化データを記憶装置から削除する。
【００５４】
ラベル付き索引保管部３０４は、センタ側データ送受信部３０２が受信したラベル付き索引を記憶装置に記憶する。
検索処理部３０５の要求があれば、ラベル付き索引保管部３０４は、ラベル付き索引を記憶装置から読み出し、読み出したラベル付き索引を検索処理部３０５に送る。
ラベル付き索引更新部３０６の要求があれば、ラベル付き索引保管部３０４は、ラベル付き索引を記憶装置から読み出し、読み出したラベル付き索引をラベル付き索引更新部３０６に送る。また、ラベル付き索引保管部３０４は、ラベル付き索引更新部３０６によって更新されるラベル付き索引を読み出したラベル付き索引に上書きする。ラベル付き索引更新部３０６によって更新されたラベル付き索引が空であれば、ラベル付き索引保管部３０４は読み出したラベル付き索引を記憶装置から削除する。
【００５５】
検索処理部３０５は、センタ側データ送受信部３０２が受信したラベル付き検索クエリを用いてラベル付き索引保管部３０４から検索したいラベル付き索引を受け取って検索処理を行い、検索結果情報を得る。
検索処理部３０５は、検索結果情報が示すデータ名で識別される暗号化データを暗号化データ保管部３０３から取得し、取得した暗号化データをセンタ側データ送受信部３０２からアクセス端末２０１に送る。
検索処理から得られる情報は検索結果情報であり、検索キーワードに関する情報は漏洩しない。
【００５６】
ラベル付き索引更新部３０６は、センタ側データ送受信部３０２が受信した追加更新情報を用いてラベル付き索引保管部３０４から更新したいラベル付き索引を受け取り、ラベル付き索引を更新し、更新したラベル付き索引をラベル付き索引保管部３０４に送る。
ラベル付き索引更新部３０６は、センタ側データ送受信部３０２が受信した削除更新情報を用いてラベル付き索引保管部３０４から更新するラベル付き索引を受け取り、ラベル付き索引を更新し、更新したラベル付き索引をラベル付き索引保管部３０４に送る。また、ラベル付き索引更新部３０６は、暗号化データ保管部３０３に削除したい暗号化データのデータ名を送って暗号化データを削除する。
ラベル付き索引更新部３０６は、センタ側データ送受信部３０２が受信した削除要求を用いてラベル付き索引保管部３０４から削除するラベル付き索引を受け取り、空のラベル付き索引をラベル付き索引更新部３０６に送り返してラベル付き索引を削除する。また、ラベル付き索引更新部３０６は、暗号化データ保管部３０３に削除する暗号化データのデータ名を送って暗号化データを削除する。
【００５７】
次に、秘匿検索システム１００の処理の概要について説明する。
【００５８】
図４は、実施の形態１における秘匿検索システム１００の初期設定処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００の初期設定処理（概要）について、図４に基づいて説明する。
【００５９】
秘匿検索システム１００の初期設定処理は、検索対象のデータを登録する登録処理やデータの検索処理を実行する前にアクセス端末２０１によって実行される。
【００６０】
ステップＳ１０１において、秘密鍵生成部２０２は、データを暗号化するための共通鍵暗号方式（ＡＥＳ、Ｃａｍｅｌｌｉａ（登録商標）など）を選択する。共通鍵暗号方式は予め決めておいても構わない。以下、Ｓ１０１で選択した共通鍵暗号方式（または、予め決められた共通鍵暗号方式）を単に「共通鍵暗号方式」という。
【００６１】
ステップＳ１０２において、秘密鍵生成部２０２は、共通鍵暗号方式の暗号化鍵（復号鍵）を生成する。共通鍵暗号方式の暗号化鍵はデータの暗号化および暗号化されたデータの復号に用いられる。
【００６２】
ステップＳ１０３において、秘密鍵生成部２０２は、ラベル付き索引やラベル付き検索クエリを生成するための索引鍵（検索鍵ともいう）を生成する。
【００６３】
ステップＳ１０４において、秘密鍵管理部２０３は、Ｓ１０２で生成された暗号化鍵とＳ１０３で生成した索引鍵とを記憶装置（記憶部）を用いて記憶する。
【００６４】
Ｓ１０４により、秘匿検索システム１００の初期設定処理は終了する。
【００６５】
図５は、実施の形態１における秘匿検索システム１００のデータ登録処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ登録処理（概要）について、図５に基づいて説明する。
【００６６】
秘匿検索システム１００のデータ登録処理において、検索対象の暗号化データと検索対象のデータを検索するためのラベル付き索引とが生成され、生成された検索対象の暗号化データとラベル付き索引とがデータセンタ３０１に登録される。
秘匿検索システム１００のデータ登録処理のうち、Ｓ２０１からＳ２０９はアクセス端末２０１によって実行され、Ｓ２１０はデータセンタ３０１によって実行される。
【００６７】
ステップＳ２０１において、ユーザは入力装置（キーボード、マウス、記憶装置など）を用いてアクセス端末２０１に登録データとラベル情報とを指定し、アクセス端末２０１のキーワード設定部２０５は指定された登録データとラベル情報とを入力装置から入力する。
登録データは、検索対象の平文データ（暗号化していないデータ）である。
ラベル情報は、ラベル付き索引の生成に使用するラベルを生成するための情報（日付、ラベル名、索引名、複数の登録データの共通キーワードなど）であり、文字列、記号列またはビット列などで表される。
【００６８】
ステップＳ２０２において、ラベル管理部２０４は、Ｓ２０１で入力されたラベル情報に基づいてラベルを生成し、生成したラベルとＳ２０１で入力されたラベル情報とを対応付けて記憶装置を用いて記憶する。
例えば、ラベル管理部２０４は、ラベル情報をそのままラベルとして使用し、またはラベル情報として入力された文字列をビット列に変換する。また、ラベル管理部２０４は、（ラベル情報のビット数が所定値より大きい場合）ラベル情報を入力にして所定のハッシュ関数を演算し、ラベル情報のハッシュ値をラベルとして算出してもよい。また、Ｓ２０１でユーザがラベル情報を指定せず、ラベル管理部２０４がラベルを自動的に生成（例えば、日付、通し番号、乱数値などを使用）してもよい。
【００６９】
ステップＳ２０３において、キーワード設定部２０５は、Ｓ２０１で入力された登録データに関連付ける１つ以上のキーワードを生成する。
例えば、キーワード設定部２０５は、登録データからキーワード（例えば、所定の名詞）を抽出する。また、ユーザがアクセス端末２０１にキーワードを指定してもよいし、予め決定されたデータ（またはデータ名）とキーワードとを記憶しておいてもよい。
【００７０】
ステップＳ２０４において、キーワード設定部２０５は、Ｓ２０３で生成したキーワード別に検索結果情報を生成する。検索結果情報は、登録データのデータ名を示す情報である（例えば、図２０参照）。
【００７１】
ステップＳ２０５において、キーワード設定部２０５は、Ｓ２０３で生成したキーワードをラベル情報に対応付けてラベル管理部２０４に記憶する。
【００７２】
ステップＳ２０６において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３に記憶されている索引鍵とＳ２０２で生成されたラベルと特定のパラメータ（例えば、後述するデータ数ｎ、整数値ｚ）とを用いてＳ２０４で生成された検索結果情報を暗号化してラベル付き索引を生成する。
【００７３】
ステップＳ２０７において、ラベル付き索引生成部２０７は、Ｓ２０６で使用したパラメータをラベル情報に対応付けてラベル管理部２０４に記憶する。
【００７４】
ステップＳ２０８において、データ暗号化部２０６は、秘密鍵管理部２０３に記憶されている暗号化鍵を用いて、Ｓ２０１で入力された登録データを暗号化して暗号化データを生成する。
【００７５】
ステップＳ２０９において、端末側データ送受信部２１３は、Ｓ２０８で生成された暗号化データとＳ２０６で生成されたラベル付き索引とをデータセンタ３０１に送信する。
【００７６】
ステップＳ２１０において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ２０９で送信された各暗号化データとラベル付き索引とを受信する。
暗号化データ保管部３０３は各暗号化データを記憶装置を用いて記憶し、ラベル付き索引保管部３０４はラベル付き索引を記憶装置を用いて記憶する。
【００７７】
Ｓ２１０により、秘匿検索システム１００のデータ登録処理は終了する。
登録データおよびラベル付き索引が暗号化されるため、登録データおよびキーワードは秘匿される。
【００７８】
図６は、実施の形態１における秘匿検索システム１００の検索処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００の検索処理（概要）について、図６に基づいて説明する。
【００７９】
秘匿検索システム１００の検索処理のうち、Ｓ３０１からＳ３０４およびＳ３０９はアクセス端末２０１によって実行され、Ｓ３０５からＳ３０８はデータセンタ３０１によって実行される。
【００８０】
ステップＳ３０１において、ユーザは入力装置を用いてアクセス端末２０１に検索キーワードとラベル情報とを指定し、アクセス端末２０１のラベル付き検索クエリ生成部２１１は指定された検索キーワードとラベル情報とを入力装置から入力する。
【００８１】
ステップＳ３０２において、ラベル管理部２０４は、Ｓ３０１で入力されたラベル情報と同じ情報に対応付けられたラベルを読み出す。但し、Ｓ３０１でユーザがラベルを指定してもよい。
【００８２】
ステップＳ３０３において、ラベル付き検索クエリ生成部２１１は、秘密鍵管理部２０３に記憶されている索引鍵と、Ｓ３０２で読み出されたラベルとを用いて、Ｓ３０１で入力された検索キーワードを暗号化してラベル付き検索クエリを生成する。
ラベル付き検索クエリは、ラベルを用いて生成する検索要求データである。実施の形態において、ラベル付き検索クエリは、ラベル付き索引に含まれる少なくともいずれかの検索結果情報を指定する。
【００８３】
ステップＳ３０４において、端末側データ送受信部２１３は、Ｓ３０３で生成されたラベル付き検索クエリをデータセンタ３０１に送信する。
【００８４】
ステップＳ３０５において、データセンタ３０１のセンタ側データ送受信部３０２はＳ３０４で送信されたラベル付き検索クエリを受信し、検索処理部３０５は受信されたラベル付き検索クエリに基づいてラベル付き索引をラベル付き索引保管部３０４から読み出す。但し、検索処理部３０５はラベル付き索引保管部３０４に記憶されている全てのラベル付き索引を読み出しても構わない。
【００８５】
ステップＳ３０６において、検索処理部３０５は、Ｓ３０５で受信されたラベル付き検索クエリに基づいてＳ３０５で読み出したラベル付き索引から検索結果情報（データ名）を取得する。
【００８６】
ステップＳ３０７において、検索処理部３０５は、Ｓ３０６で取得した検索結果情報に含まれるデータ名で識別される暗号化データを暗号化データ保管部３０３から読み出す。
【００８７】
ステップＳ３０８において、センタ側データ送受信部３０２は、Ｓ３０７で読み出された暗号化データをアクセス端末２０１に送信する。
【００８８】
ステップＳ３０９において、アクセス端末２０１の端末側データ送受信部２１３は、Ｓ３０８で送信された暗号化データを受信する。
データ復号部２１２は、受信された暗号化データを秘密鍵管理部２０３に記憶されている暗号化鍵を用いて復号し、復号して得られる平文データを出力装置（ディスプレイ、プリンタなど）に出力する。
【００８９】
Ｓ３０９により、秘匿検索システム１００の検索処理は終了する。
【００９０】
図７は、実施の形態１における秘匿検索システム１００のデータ追加処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ追加処理（概要）について、図７に基づいて説明する。
【００９１】
秘匿検索システム１００のデータ追加処理は、検索対象の暗号化データをデータセンタ３０１に追加登録する処理である。
秘匿検索システム１００のデータ追加処理のうち、Ｓ４０１からＳ４０９はアクセス端末２０１によって実行され、Ｓ４１０からＳ４１３はデータセンタ３０１によって実行される。
【００９２】
ステップＳ４０１において、ユーザは入力装置を用いてアクセス端末２０１に追加データ（検索対象として追加する平文データ）とラベル情報とを指定し、アクセス端末２０１のキーワード設定部２０５は指定された追加データとラベル情報とを入力装置から入力する。
【００９３】
ステップＳ４０２において、ラベル管理部２０４は、Ｓ４０１で入力されたラベル情報と同じ情報に対応付けられたラベルとパラメータとを読み出す。但し、Ｓ４０１でユーザがラベルを指定しても構わない。また、ラベル管理部２０４は、追加データのキーワード（Ｓ４０３参照）と共通するラベル（登録データの共通キーワード）を選択しても構わない。
【００９４】
ステップＳ４０３において、キーワード設定部２０５は、Ｓ４０１で入力された追加データに関連付けるキーワードを生成する。キーワードの生成方法はＳ２０３と同様である。
【００９５】
ステップＳ４０４において、キーワード設定部２０５は、Ｓ４０３で生成したキーワード毎に検索結果情報を生成する。検索結果情報の生成方法はＳ２０４と同様である。
【００９６】
ステップＳ４０５において、キーワード設定部２０５は、Ｓ４０３で生成した各キーワードをＳ４０１で入力されたラベル情報と同じ情報に対応付けて追加で記憶する。
【００９７】
ステップＳ４０６において、追加更新情報生成部２０８は、秘密鍵管理部２０３に記憶されている索引鍵とＳ４０２で読み出されたラベルとパラメータとを用いて、Ｓ４０４で生成された検索結果情報を暗号化して追加更新情報を生成する。
【００９８】
ステップＳ４０７において、追加更新情報生成部２０８は、Ｓ４０６で更新されるパラメータに基づいて、Ｓ４０１で入力されたラベル情報と同じ情報に対応付けられたパラメータを更新する。
【００９９】
ステップＳ４０８において、データ暗号化部２０６は、秘密鍵管理部２０３に記憶されている暗号化鍵を用いて、Ｓ４０１で入力された追加データを暗号化して暗号化データを生成する。
【０１００】
ステップＳ４０９において、端末側データ送受信部２１３は、Ｓ４０８で生成された暗号化データとＳ４０６で生成された追加更新情報とをデータセンタ３０１に送信する。
【０１０１】
ステップＳ４１０において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ４０９で送信された暗号化データと追加更新情報とを受信する。
暗号化データ保管部３０３は、受信された暗号化データを追加で記憶する。
【０１０２】
ステップＳ４１１において、ラベル付き索引更新部３０６は、Ｓ４１０で受信された追加更新情報に基づいて、ラベル付き索引保管部３０４から更新するラベル付き索引を読み出す。
【０１０３】
ステップＳ４１２において、ラベル付き索引更新部３０６は、Ｓ４１０で受信された追加更新情報に基づいて、Ｓ４１１で読み出したラベル付き索引を更新する。
【０１０４】
ステップＳ４１３において、ラベル付き索引更新部３０６は、Ｓ４１２で更新されたラベル付き索引をラベル付き索引保管部３０４に上書きする。
【０１０５】
Ｓ４１３により、秘匿検索システム１００のデータ追加処理は終了する。
追加更新情報が暗号化されるため、追加データおよびキーワードは秘匿される。
【０１０６】
図８は、実施の形態１におけるラベル付き索引の削除更新処理（概要）を示すフローチャートである。
実施の形態１におけるラベル付き索引の削除更新処理（概要）について、図８に基づいて説明する。
【０１０７】
ラベル付き索引の削除更新処理は、一部の登録データを削除してラベル付き索引を更新する処理である。
ラベル付き索引の削除更新処理のうち、Ｓ５０１からＳ５０５はアクセス端末２０１によって実行され、Ｓ５０６からＳ５０９はデータセンタ３０１によって実行される。
【０１０８】
ステップＳ５０１において、ユーザは入力装置を用いてアクセス端末２０１に削除データとラベル情報とを指定し、アクセス端末２０１の削除更新情報生成部２０９は指定された削除データとラベル情報とを入力装置から入力する。
削除データとは、削除する暗号化データ、削除する暗号化データに対応する平文データ、または削除する暗号化データ（および平文データ）のデータ名を意味する。
【０１０９】
ステップＳ５０２において、ラベル管理部２０４は、Ｓ５０１で入力されたラベル情報と同じ情報に対応付けられたラベルとラベル付き索引とパラメータとを読み出す。但し、Ｓ５０１でユーザがラベルを指定しても構わない。また、ラベル管理部２０４は、削除データのキーワードと共通するラベル（登録データの共通キーワード）を選択しても構わない。
【０１１０】
ステップＳ５０３において、削除更新情報生成部２０９は、Ｓ５０１で入力された削除データと、秘密鍵管理部２０３に記憶されている索引鍵と、Ｓ５０２で読み出されたラベルとパラメータとを用いて、削除データを暗号化して削除更新情報を生成する。
【０１１１】
ステップＳ５０４において、削除更新情報生成部２０９は、Ｓ５０３で更新されるパラメータに基づいて、Ｓ５０１で入力されたラベル情報と同じ情報に対応付けられたパラメータを更新する。
【０１１２】
ステップＳ５０５において、端末側データ送受信部２１３は、Ｓ５０３で生成された削除更新情報をデータセンタ３０１に送信する。
【０１１３】
ステップＳ５０６において、データセンタ３０１のセンタ側データ送受信部３０２はＳ５０５で送信された削除更新情報を受信し、ラベル付き索引更新部３０６は受信された削除更新情報に基づいて更新するラベル付き索引をラベル付き索引保管部３０４から読み出す。
【０１１４】
ステップＳ５０７において、ラベル付き索引更新部３０６は、Ｓ５０６で受信された削除更新情報に基づいて、Ｓ５０６で読み出されたラベル付き索引を更新する。
【０１１５】
ステップＳ５０８において、ラベル付き索引更新部３０６は、Ｓ５０７で更新されたラベル付き索引をラベル付き索引保管部３０４に上書きする。
【０１１６】
ステップＳ５０９において、ラベル付き索引更新部３０６は、Ｓ５０６で受信された削除更新情報に基づいて、暗号化データ保管部３０３から削除データに対応する暗号化データを削除する。
【０１１７】
Ｓ５０９により、ラベル付き索引の削除更新処理は終了する。ラベル付き索引は暗号化されているため、登録データおよびキーワードは秘匿される。
【０１１８】
図９は、実施の形態１における秘匿検索システム１００のデータ削除処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ削除処理（概要）について、図９に基づいて説明する。
【０１１９】
秘匿検索システム１００のデータ削除処理は、一部の登録データをデータセンタ３０１から削除する処理である。
秘匿検索システム１００のデータ削除処理のうち、Ｓ６０１からＳ６０３はアクセス端末２０１によって実行され、Ｓ６０４はデータセンタ３０１によって実行される。
【０１２０】
ステップＳ６０１において、ユーザは入力装置を用いてアクセス端末２０１に削除データ名を指定し、アクセス端末２０１の削除要求生成部２１０は削除データ名を入力装置から入力する。
【０１２１】
ステップＳ６０２において、削除要求生成部２１０は、Ｓ６０１で入力された削除データ名を含んだ削除要求データを生成する。
【０１２２】
ステップＳ６０３において、端末側データ送受信部２１３は、Ｓ６０２で生成された削除要求データをデータセンタ３０１に送信する。
【０１２３】
ステップＳ６０４において、データセンタ３０１のセンタ側データ送受信部３０２はＳ６０３で送信された削除要求データを受信し、ラベル付き索引更新部３０６は受信された削除要求データに含まれる削除データ名で識別される暗号化データを暗号化データ保管部３０３から削除する。
【０１２４】
Ｓ６０４により、秘匿検索システム１００のデータ削除処理は終了する。
【０１２５】
図１０は、実施の形態１における秘匿検索システム１００の索引削除処理（概要）を示すフローチャートである。
実施の形態１における秘匿検索システム１００の索引削除処理（概要）について、図１０に基づいて説明する。
【０１２６】
秘匿検索システム１００の索引削除処理は、ラベル付き索引をデータセンタ３０１から削除する処理である。
秘匿検索システム１００の索引削除処理のうち、Ｓ７０１からＳ７０３はアクセス端末２０１によって実行され、Ｓ７０４はデータセンタ３０１によって実行される。
【０１２７】
ステップＳ７０１において、ユーザは入力装置を用いてアクセス端末２０１に削除索引名を指定し、アクセス端末２０１の削除要求生成部２１０は指定された削除索引名を入力装置から入力する。
【０１２８】
ステップＳ７０２において、削除要求生成部２１０は、Ｓ７０１で入力された削除索引名を含んだ削除要求データを生成する。
【０１２９】
ステップＳ７０３において、端末側データ送受信部２１３は、Ｓ７０２で生成された削除要求データをデータセンタ３０１に送信する。
【０１３０】
ステップＳ７０４において、データセンタ３０１のセンタ側データ送受信部３０２はＳ７０３で送信された削除要求データを受信し、ラベル付き索引更新部３０６は受信された削除要求データに含まれる削除索引名によって識別されるラベル付き索引をラベル付き索引保管部３０４から削除する。
【０１３１】
Ｓ７０４により、秘匿検索システム１００の索引削除処理は終了する。
索引削除処理（図１０）とデータ削除処理（図９）とは同時に実行しても構わない。例えば、削除要求データに削除データ名と削除索引名との両方を含める。
【０１３２】
図４から図１０の各処理は、フローチャート通りの処理でなくても構わない。例えば、フローチャートが示す処理順序を変更しても構わない。
【０１３３】
次に、秘匿検索システム１００の処理の詳細（具体例）について説明する。
【０１３４】
まず、以下の説明で使用する項目や記号の一部について説明する。
【０１３５】
データＤｉおよびその暗号化データＣｉのデータ名を「ｉｄｉ」と記す。ただし、データ名ｉｄｉは単なる識別子であり、データＤｉの中身を表すものではない。つまり、データ名ｉｄｉによってデータＤｉの内容は知得されないものとする。
データ名ｉｄｉのサイズをＭビットとする。もし、データ名ｉｄｉの長さがＭビットより短い場合、例えば０をパディングすることでデータ名ｉｄｉをＭビットにする。
【０１３６】
ラベルｌａｂｅｌの（最大の）ビット長をｘビットとし、キーワードｗの（最大の）ビット長をｙビットとする。
暗号化鍵ＥＫのビット数をｋ１ビットとし、索引鍵Ｋのビット数をｋ２ビットとする。
【０１３７】
関数πは、入力値に基づいて入力値と同じサイズの乱数値を算出するためのものである。関数πは「疑似ランダム置換」ともいう。但し、入力値が同じであれば、出力値はいつも同じである。
関数πは、｛０，１｝ｋ２×｛０，１｝ｘ＋１＋ｙ＋Ｍ  →  ｛０，１｝ｘ＋１＋ｙ＋Ｍで表される。｛０，１｝ＸはＸビットのビット列（０または１）を意味し、「×」は直積を意味する。
つまり、関数π（Ｋ，ｎ）は、ｋ２ビットの索引鍵Ｋと、ｘ＋１＋ｙ＋Ｍビットの値ｎとを入力にして、０から２ｘ＋１＋ｙ＋Ｍ−１の整数（｛０，１｝ｘ＋１＋ｙ＋Ｍの元）のうちランダムな値を出力する。
【０１３８】
共通鍵暗号方式の暗号化関数Ｅｎｃは、｛０，１｝ｋ１×｛０，１｝＊→｛０，１｝＊で表される。つまり、暗号化関数Ｅｎｃは、ｋ１ビットの鍵ＥＫを用いて任意のビット長のデータを暗号化する。
【０１３９】
ラベル付き索引Ｉは配列構造のデータであり、１つ以上の配列要素を有する。ラベル付き索引Ｉの１つの配列要素に設定できる値の最大サイズはＭビットである。
ラベル付き索引Ｉの配列要素Ｉ［ａ］を識別する値ａを「アドレス」という。
ラベル付き索引Ｉは、｛０，１｝ｘ＋１＋ｙ＋Ｍのアドレス空間を有する配列である。つまり、ラベル付き索引Ｉの配列要素の最大数は、２ｘ＋１＋ｙ＋Ｍビットで表すことができる数である。
ラベル付き索引Ｉの配列要素のうち、使用される配列要素（値が設定される配列要素）にだけ記憶領域を確保する。つまり、ラベル付き索引Ｉのアドレス空間は指数サイズであるが、多項式程度のアドレス空間しか利用せず、かつ利用していないアドレス空間には何も設定しない。このため、ラベル付き索引Ｉの実質的なサイズは多項式サイズに抑えられる。
【０１４０】
「＃Ｘ」はＸの要素数を意味し、「Ｘ‖Ｙ」はビット列Ｘとビット列Ｙとの結合（連結）を意味する。その他の記号については、一般的に使用される数学の記号と同様の意味である。
【０１４１】
図１１は、実施の形態１における秘匿検索システム１００初期設定処理（具体例）を示すフローチャートである。
実施の形態１における秘匿検索システム１００の初期設定処理（具体例）について、図１１に基づいて説明する。
【０１４２】
図１１のフローチャートは図４に示したフローチャートに対応している。
Ｓ１１０１はＳ１０２に対応し、Ｓ１１０２はＳ１０３に対応し、Ｓ１１０３はＳ１０４に対応する処理である。Ｓ１１０１からＳ１１０３の処理にＳ１０１からＳ１０４で説明した事項を適用しても構わない。
【０１４３】
ステップＳ１１０１において、秘密鍵生成部２０２は、共通鍵暗号方式のｋ１ビットの暗号化鍵ＥＫをランダムに生成する。ｋ１は任意の整数値である。
【０１４４】
ステップＳ１１０２において、秘密鍵生成部２０２は、ｋ２ビットの乱数Ｋを生成する。ｋ２は任意の整数値である。以下、ステップＳ１１０２で生成した乱数Ｋを「索引鍵Ｋ」という。
【０１４５】
ステップＳ１１０３において、秘密鍵管理部２０３は、Ｓ１１０１で生成された暗号化鍵ＥＫとＳ１１０２で生成された索引鍵Ｋとを記憶する。
【０１４６】
Ｓ１１０３により、秘匿検索システム１００の初期化処理（具体例）は終了する。
【０１４７】
図１２は、実施の形態１における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ登録処理（具体例）について、図１２に基づいて説明する。
【０１４８】
図１２のフローチャートは図５に示したフローチャートに対応している。
Ｓ１２０２はＳ２０１に対応し、Ｓ１２０２はＳ２０２に対応し、Ｓ１２０３はＳ２０７に対応し、Ｓ１２０４はＳ２０３とＳ２０５とに対応し、Ｓ１２０５はＳ２０４に対応し、Ｓ１２０６からＳ１２０８はＳ２０６に対応し、Ｓ１２０９はＳ２０８に対応し、Ｓ１２１０はＳ２０９とＳ２１０とに対応する処理である。Ｓ１２０１からＳ１２１０の処理にＳ２０１からＳ２１０で説明した事項を適用しても構わない。
【０１４９】
ステップＳ１２０１において、ユーザは入力装置を用いてアクセス端末２０１にデータ集合Ｄ＝｛Ｄ１，…，Ｄｎ｝とラベル情報ｄとを指定し、アクセス端末２０１のキーワード設定部２０５は指定されたデータ集合Ｄとラベル情報ｄとを入力装置から入力する。
データ集合Ｄは１つ以上の登録データＤｉ（平文データ）を含む（添え字ｉは１以上の整数。以下同様）。以下、データ集合Ｄ内のデータ数を「ｎ」とする。
【０１５０】
ステップＳ１２０２において、ラベル管理部２０４は、Ｓ１２０１で入力されたラベル情報ｄに基づいてラベルｌａｂｅｌを生成し、生成したラベルｌａｂｅｌとラベル情報ｄとを対応付けて記憶する。
【０１５１】
ステップＳ１２０３において、ラベル管理部２０４は、データ集合Ｄ内のデータ数ｎを算出し、算出したデータ数ｎをラベル情報ｄに対応付けて記憶する。
【０１５２】
ステップＳ１２０４において、キーワード設定部２０５は、Ｓ１２０１で入力されたデータ集合Ｄに関連するキーワード集合Ｗ＝｛ｗ１，…，ｗｑ｝を生成し、生成したキーワード集合Ｗをラベル情報ｄに対応付けてラベル管理部２０４に記憶する。キーワード集合Ｗの生成方法は、Ｓ２０３と同様である。
キーワード集合Ｗは１つ以上のキーワードｗｉを含む。以下、キーワード集合Ｗ内のキーワード数を「ｑ」とする。キーワードｗｉはデータ集合Ｄの少なくともいずれかの登録データＤｊに関連する（添え字ｊは１以上の整数。以下同様）。
【０１５３】
ステップＳ１２０５において、キーワード設定部２０５は、Ｓ１２０４で生成したキーワード集合Ｗに含まれるキーワードｗｉ別に検索結果情報Ｄ（ｗｉ）を生成する。検索結果情報Ｄ（ｗｉ）はキーワードｗｉに関連する１つ以上のデータＤｊのデータ名ｉｄｊを含む。以下、検索結果情報Ｄ（ｗｉ）に含まれるデータ名数を「検索結果数＃Ｄ（ｗｉ）」という。
キーワード設定部２０５は、検索結果数＃Ｄ（ｗｉ）をラベル情報ｄに対応付けてラベル管理部２０４に記憶する。
【０１５４】
ステップＳ１２０６において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋを読み出す。
ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵ＫとＳ１２０２で生成したラベルｌａｂｅｌとを用いて、ラベル付き索引Ｉに検索結果情報Ｄ（ｗｉ）を設定する。
検索結果情報Ｄ（ｗｉ）の設定は、１≦ｉ≦＃Ｗ、１≦ｊ≦＃Ｄ（ｗｉ）に対して、Ｉ［π（Ｋ，ｌａｂｅｌ‖１‖ｗｉ‖ｊ）］＝Ｄ（ｗｉ）［ｊ］で表される。＃Ｗはキーワード集合Ｗに含まれるキーワード数を意味する。
つまり、検索結果情報Ｄ（ｗｉ）に含まれる＃Ｄ（ｗｉ）個のデータ名ｉｄｊがラベル付き索引Ｉのランダムな配列要素に格納される。
【０１５５】
ステップＳ１２０７において、ラベル付き索引生成部２０７は、Ｓ１２０５で生成した検索結果情報Ｄ（ｗｉ）に基づいてキーワードｗｉ別に非検索結果情報Ｊ（ｗｉ）を生成する。非検索結果情報Ｊ（ｗｉ）はデータ集合Ｄに含まれるデータのうちキーワードｗｉに関連しないデータのデータ名ｉｄ、つまり、検索結果情報Ｄ（ｗｉ）以外のデータ名ｉｄを含む。
非検索結果情報Ｊ（ｗｉ）は、ｉｄ１，…，ｉｄｎに対して、ｉｄｊ∈Ｊ（ｗｉ）、ｉｄｊ！∈Ｄ（ｗｉ）で表される。ここで、「！∈」は∈の否定形を意味する（以下同様）。つまり、ｗ∈Ｗに対して、Ｊ（ｗ）∪Ｄ（ｗ）＝｛ｉｄ１，…，ｉｄｎ｝かつＪ（ｗ）∩Ｄ（ｗ）＝φ（ゼロ）が成り立つ。
【０１５６】
ステップＳ１２０８において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋを読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵ＫとＳ１２０２で読み出されたラベルｌａｂｅｌとＳ１２０７で生成した非検索結果情報Ｊ（ｗｉ）とを用いて、ラベル付き索引Ｉに非検索結果情報Ｊ（ｗｉ）を設定する。
非検索結果情報Ｊ（ｗｉ）の設定は、１≦ｉ≦＃Ｗ、１≦ｊ≦＃Ｊ（ｗｉ）に対して、Ｉ［π（Ｋ，ｌａｂｅｌ‖０‖ｗｉ‖ｊ）］＝Ｊ（ｗｉ）［ｊ］で表される。
つまり、Ｊ（ｗ）に含まれる＃Ｊ（ｗｉ）個のデータ名ｉｄ（ｎ−＃Ｄ（ｗｉ）個のデータ名ｉｄ）がラベル付き索引Ｉのランダムな配列要素に格納される。
【０１５７】
ステップＳ１２０９において、データ暗号化部２０６は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。データ暗号化部２０６は、暗号化関数Ｅｎｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、Ｓ１２０１で入力されたデータ集合Ｄ＝｛Ｄ１，…，Ｄｎ｝を暗号化する。
以下、登録データＤｉを暗号化した暗号化データを「Ｃｉ」と記す。
データ集合Ｄの暗号化は、１≦ｉ≦ｎに対して、Ｃｉ＝Ｅｎｃ（ＥＫ，Ｄｉ）で表される。
【０１５８】
ステップＳ１２１０において、端末側データ送受信部２１３は、Ｓ１２０９で生成された暗号化データ集合Ｃ＝｛Ｃ１，…，Ｃｎ｝と、Ｓ１２０６からＳ１２０８で生成されたラベル付き索引Ｉとをデータセンタ３０１に送信する。
データセンタ３０１のセンタ側データ送受信部３０２は暗号化データ集合Ｃとラベル付き索引Ｉとを受信し、暗号化データ保管部３０３は暗号化データ集合Ｃを記憶し、ラベル付き索引保管部３０４はラベル付き索引Ｉを記憶する。ラベル付き索引名は「ｉｄＩ」である。
【０１５９】
図１３は、実施の形態１における秘匿検索システム１００の検索処理（具体例）を示すフローチャートである。
実施の形態１における秘匿検索システム１００の検索処理（具体例）について、図１３に基づいて説明する。
【０１６０】
図１３のフローチャートは図６に示したフローチャートに対応している。
Ｓ１３０１はＳ３０１に対応し、Ｓ１３０２はＳ３０２に対応し、Ｓ１３０３はＳ３０３に対応し、Ｓ１３０４はＳ３０４に対応し、Ｓ１３０５はＳ３０５とＳ３０６とに対応し、Ｓ１３０６はＳ３０７とＳ３０８とに対応し、Ｓ１３０７はＳ３０９に対応する処理である。Ｓ１３０１からＳ１３０７の処理にＳ３０１からＳ３０９で説明した事項を適用しても構わない。
【０１６１】
ステップＳ１３０１において、ユーザは、入力装置を用いてアクセス端末２０１に検索キーワードｗとラベル情報ｄとを指定し、アクセス端末２０１のラベル付き検索クエリ生成部２１１は指定されたキーワードｗとラベル情報ｄとを入力装置から入力する。
【０１６２】
ステップＳ１３０２において、ラベル管理部２０４は、Ｓ１３０１で入力されたラベル情報ｄに対応付けられたラベルｌａｂｅｌとラベル付き索引Ｉと検索結果数＃Ｄ（ｗ）とを読み出す。
【０１６３】
ステップＳ１３０３において、ラベル付き検索クエリ生成部２１１は、秘罪鍵管理部２０３から索引鍵Ｋを読み出す。ラベル付き検索クエリ生成部２１１は、秘密鍵管理部２０３から読み出した索引鍵Ｋと、Ｓ１３０２で読み出したラベルｌａｂｅｌと検索結果数＃Ｄ（ｗ）とを用いて、以下のアドレスａｊを算出する。
アドレスａｊは、１≦ｊ≦＃Ｄ（ｗ）に対して、ａｊ＝π（Ｋ，ｌａｂｅｌ‖１‖ｗ‖ｊ）で表される。アドレスａｊはラベル付き索引Ｉの配列要素を指定する値である。
ラベル付き検索クエリ生成部２１１は、算出したａｊ＝（ａ１，…，ａ＃Ｄ（ｗ））を含んだ検索クエリｑｕｅｒｙ（ラベル付き検索クエリ）を生成する。
【０１６４】
ステップＳ１３０４において、端末側データ送受信部２１３は、Ｓ１３０３で生成された検索クエリｑｕｅｒｙをデータセンタ３０１に送信する。
【０１６５】
ステップＳ１３０５において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ１３０４で送信された検索クエリｑｕｅｒｙを受信する。
検索処理部３０５は、ラベル付き索引保管部３０４から全てのラベル付き索引Ｉを読み出す。
検索処理部３０５は、検索クエリｑｕｅｒｙに含まれるアドレスａｊを用いて、全てのラベル付き索引Ｉから配列要素Ｉ［ａｊ］に設定されているデータ名ｉｄｊを抽出する。但し、複数のラベル付き索引Ｉが存在する場合であっても、ラベル付き索引Ｉ毎に使用するアドレスが異なるため、配列要素Ｉ［ａｊ］にデータ名ｉｄｊが設定されているラベル付き索引Ｉは通常一つである。つまり、抽出されるデータ名ｉｄｊはアドレスａｊ毎に一つずつである。
【０１６６】
ステップＳ１３０６において、検索処理部３０５は、Ｓ１３０５で抽出した各データ名ｉｄｊで識別される暗号化データＣｊを暗号化データ保管部３０３から読み出し、読み出した各暗号化データＣｊを含んだ検索結果データを生成する。
センタ側データ送受信部３０２は検索処理部３０５によって生成された検索結果データをアクセス端末２０１に送信する。
【０１６７】
ステップＳ１３０７において、アクセス端末２０１の端末側データ送受信部２１３は検索結果データを受信する。
データ復号部２１２は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。
データ復号部２１２は、復号関数Ｄｅｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、受信された検索結果データに含まれる各暗号化データＣｊを復号する。暗号化データＣｊを復号することにより、暗号化前のデータＤｊが得られる。
暗号化データＣｊの復号は、Ｄｊ＝Ｄｅｃ（ＥＫ，Ｃｊ）で表される。
データ復号部２１２は、復号により得られた各データＤｊを出力装置に出力する。
【０１６８】
Ｓ１３０７により、秘匿検索システム１００の検索処理（具体例）は終了する。
【０１６９】
但し、Ｓ１３０５において、データセンタ３０１に保管されている全てのラベル付き索引Ｉを検索する代わりに、ユーザから指定されたラベル付き索引Ｉだけを検索してもよい。
この場合、Ｓ１３０４において、端末側データ送受信部２１３は、ユーザから指定されたラベル情報に対応付けられたラベル付き索引Ｉの索引名ｉｄＩを含んだ検索クエリｑｕｅｒｙをデータセンタ３０１に送信する。Ｓ１３０５において、検索処理部３０５は、検索クエリｑｕｅｒｙに含まれる索引名ｉｄＩのラベル付き索引Ｉだけを検索する。
【０１７０】
図１４、図１５は、実施の形態１における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ追加処理（具体例）について、図１４、図１５に基づいて説明する。
【０１７１】
図１４、図１５のフローチャートは図７に示したフローチャートに対応している。
Ｓ１４０１はＳ４０１に対応し、Ｓ１４０２はＳ４０２に対応し、Ｓ１４０３はＳ４０３とＳ４０４とに対応し、Ｓ１４０４はＳ４０５に対応し、Ｓ１４０５から１３０７はＳ４０６に対応し、Ｓ１４０８はＳ４０７に対応し、Ｓ１４０９はＳ４０８に対応し、Ｓ１４１０はＳ４０９に対応し、Ｓ１４１１はＳ４１０に対応し、Ｓ１４１２はＳ４１１からＳ４１３に対応する処理である。Ｓ１４０１からＳ１４１２の処理にＳ４０１からＳ４１３で説明した事項を適用しても構わない。
【０１７２】
ステップＳ１４０１において、ユーザは入力装置を用いてアクセス端末２０１に追加データ集合Ｄ’とラベル情報ｄ’とを指定し、アクセス端末２０１のキーワード設定部２０５は指定された追加データ集合Ｄ’とラベル情報ｄ’とを入力装置から入力する。
追加データ集合Ｄ’は１つ以上の追加データＤｉ’（平文データ）を含む。以下、追加データ集合Ｄ’内のデータ数を「ｍ」とする。つまり、追加データ集合Ｄ’は、Ｄ’＝｛Ｄ１’，…，Ｄｍ’｝で表すことができる。
【０１７３】
ステップＳ１４０２において、ラベル管理部２０４は、Ｓ１４０１で入力されたラベル情報ｄ’に対応付けられたラベルｌａｂｅｌ、ラベル付き索引Ｉ、データ数ｎ、キーワード集合Ｗおよび検索結果数＃Ｄ（ｗ）を読み出す。
【０１７４】
ステップＳ１４０３において、キーワード設定部２０５は、Ｓ１４０１で入力された追加データ集合Ｄ’に関連するキーワード集合Ｗ’＝｛ｗ１’，…，ｗｐ’｝を生成する。ここで、キーワード集合Ｗ’内のキーワード数を「ｐ」とする。キーワード集合Ｗ’の生成方法はＳ２０３と同様である。
キーワード設定部２０５は、キーワード集合Ｗ’に含まれるキーワードｗｉ’別に検索結果情報Ｄ’（ｗｉ’）を生成する。
【０１７５】
ステップＳ１４０４において、キーワード設定部２０５は、Ｓ１４０２で読み出されたキーワード集合ＷにＳ１４０３で生成したキーワード集合Ｗ’を結合してキーワード集合Ｗを更新し、更新したキーワード集合Ｗをラベル管理部２０４に上書きする。つまり、キーワード設定部２０５は、Ｗ＝Ｗ∪Ｗ’で表されるキーワード集合Ｗをラベル管理部２０４に上書きする。
【０１７６】
ステップＳ１４０５において、追加更新情報生成部２０８は、秘密鍵管理部２０３から索引鍵Ｋを読み出す。追加更新情報生成部２０８は、秘密鍵管理部２０３から読み出した索引鍵Ｋと、Ｓ１４０２で読み出されたラベルｌａｂｅｌと検索結果数＃Ｄ（ｗ）と、Ｓ１４０３で生成された検索結果Ｄ’（ｗ’）と、Ｓ１４０４で更新されたキーワード集合Ｗとを用いて、第１の追加更新情報Ａｄｄ１を生成する。
第１の追加更新情報Ａｄｄ１は、１≦ｉ≦＃Ｗ、＃Ｄ（ｗｉ）＋１≦ｊ≦＃Ｄ（ｗｉ）＋＃Ｄ’（ｗｉ）に対して、Ａｄｄ１＝（π（Ｋ，ｌａｂｅｌ‖１‖ｗｉ‖ｊ），Ｄ’（ｗｉ）［ｊ］）で表される。ただし、＃Ｄ’（ｗｉ）＝０の関係を満たすｉについては除く。
【０１７７】
ステップＳ１４０６において、追加更新情報生成部２０８は、Ｓ１４０３で生成された検索結果情報Ｄ’（ｗｉ’）に基づいてキーワードｗｉ別に非検索結果情報Ｊ’（ｗｉ’）を生成する。非検索結果情報Ｊ’（ｗｉ’）の生成方法はＳ１２０７と同様である。
非検索結果情報Ｊ’（ｗｉ’）は、ｉｄ１’，…，ｉｄｍ’に対して、ｉｄｊ’∈Ｊ’（ｗｉ’）⇔ｉｄｊ’！∈Ｄ’（ｗｉ’）で表される。つまり、ｗ’∈Ｗ’に対して、Ｊ’（ｗ’）∪Ｄ’（ｗ’）＝｛ｉｄ１’，…，ｉｄｍ’｝かつＪ’（ｗ’）∩Ｄ’（ｗ’）＝φである。
【０１７８】
ステップＳ１４０７において、追加更新情報生成部２０８は、秘密鍵管理部２０３から索引鍵Ｋを読み出す。追加更新情報生成部２０８は、秘密鍵管理部２０３から読み出した索引鍵Ｋと、Ｓ１４０２で読み出されたラベルｌａｂｅｌとデータ数ｎと検索結果数＃Ｄ（ｗｉ）と、Ｓ１４０４で更新されたキーワード集合Ｗと、Ｓ１４０６で生成された非検索結果情報Ｊ’（ｗｉ’）とを用いて、第２の追加更新情報Ａｄｄ２を生成する。
第２の追加更新情報Ａｄｄ２は、１≦ｉ≦＃Ｗ、ｎ−＃Ｄ（ｗｉ）＋１≦ｊ≦ｎ−＃Ｄ（ｗｉ）＋＃Ｊ’（ｗｉ）に対して、Ａｄｄ２＝（π（Ｋ，ｌａｂｅｌ‖０‖ｗｉ‖ｊ），Ｊ’（ｗｉ）［ｊ］）で表される。ただし、＃Ｊ’（ｗｉ）＝０の関係を満たすｉについては除く。
【０１７９】
ステップ１４０８において、追加更新情報生成部２０８は、データ数ｎに追加データ数ｍを加算してデータ数ｎを更新し、検索結果数＃Ｄ（ｗ）に追加の検索結果数＃Ｄ’（ｗ’）を加算して検索結果数＃Ｄ（ｗ）を更新し、更新したデータ数ｎと検索結果数＃Ｄ（ｗ）とを記憶装置に上書きする。つまり、ｎ＝ｎ＋ｍで表されるデータ数ｎと、＃Ｄ（ｗ）＝＃Ｄ（ｗ）＋＃Ｄ’（ｗ’）で表される検索結果数＃Ｄ（ｗ）とをラベル管理部２０４に上書きする。
【０１８０】
ステップＳ１４０９において、データ暗号化部２０６は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。データ暗号化部２０６は、暗号化関数Ｅｎｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、Ｓ１４０１で入力された追加データ集合Ｄ’＝｛Ｄ１’，…，Ｄｍ’｝を暗号化する。以下、データＤｉ’を暗号化した暗号化データを「Ｃｉ’」と記す。追加データ集合Ｄ’の暗号化は、１≦ｉ≦ｍに対して、Ｃｉ’＝Ｅｎｃ（ＥＫ，Ｄｉ’）で表される。
【０１８１】
ステップＳ１４１０において、端末側データ送受信部２１３は、追加の暗号化データ集合Ｃ’＝｛Ｃ１’，…，Ｃｍ’｝と第１の追加更新情報Ａｄｄ１と第２の追加更新情報Ａｄｄ２と索引名ｉｄＩとをデータセンタ３０１に送信する。
【０１８２】
ステップＳ１４１１において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ１４１０で送信された追加の暗号化データ集合Ｃ’と第１の追加更新情報Ａｄｄ１と第２の追加更新情報Ａｄｄ２と索引名ｉｄＩとを受信する。
暗号化データ保管部３０３は、受信された追加の暗号化データ集合Ｃ’を暗号化データ保管部３０３に記憶する。
【０１８３】
ステップＳ１４１２において、ラベル付き索引更新部３０６は、Ｓ１４１１で受信された索引名ｉｄＩによって識別されるラベル付き索引Ｉをラベル付き索引保管部３０４から読み出す。
ラベル付き索引更新部３０６は、Ｓ１４１１で受信された第１の追加更新情報Ａｄｄ１と第２の追加更新情報Ａｄｄ２とを用いてラベル付き索引Ｉを更新し、更新したラベル付き索引Ｉをラベル付き索引保管部３０４に上書きする。
ここで、第１の追加更新情報Ａｄｄ１に含まれる各要素を（ａ，ｂ）で表し，第２の追加更新情報Ａｄｄ２に含まれる各要素を（ａ’，ｂ’）で表す。
ラベル付き索引Ｉの更新は、Ｉ［ａ］＝ｂ，Ｉ［ａ’］＝ｂ’で表される。
【０１８４】
Ｓ１４１２により、秘匿検索システム１００のデータ追加処理（具体例）は終了する。
【０１８５】
図１６は、実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャートである。
実施の形態１におけるラベル付き索引の削除更新処理（具体例）について、図１６に基づいて説明する。
【０１８６】
図１６のフローチャートは図８に示したフローチャートに対応している。
Ｓ１５０１はＳ５０１に対応し、Ｓ１５０２はＳ５０２に対応し、Ｓ１５０３はＳ５０５に対応し、Ｓ１５０４はＳ５０６からＳ５０８に対応し、Ｓ１５０５はＳ５０９に対応する処理である。Ｓ１５０１からＳ１５０５の処理にＳ５０１からＳ５０９で説明した事項を適用しても構わない。
【０１８７】
ステップＳ１５０１において、ユーザは、入力装置を用いてアクセス端末２０１に削除データ集合Ｄ’’の各データ名とラベル情報ｄ’’とを指定し、アクセス端末２０１の削除更新情報生成部２０９は指定された削除データ集合Ｄ’’の各データ名とラベル情報ｄ’’とを入力装置から入力する。
削除データ集合Ｄ’’は１つ以上の削除データＤｉ’’を含む。削除データ集合Ｄ’’内のデータ数を「ｎ」とした場合、削除データ集合Ｄ’’＝｛Ｄ１’’，…，Ｄｎ’’｝であり、そのデータ名は｛ｉｄ１’’，…，ｉｄｎ’’｝である。
【０１８８】
ステップＳ１５０２において、ラベル管理部２０４は、Ｓ１５０１で入力されたラベル情報ｄ’’に対応付けられたラベル付き索引Ｉの索引名ｉｄＩを読み出す。
削除更新情報生成部２０９は、読み出した索引名ｉｄＩと、Ｓ１５０１で入力された削除データ集合Ｄ’’のデータ名｛ｉｄ１’’，…，ｉｄｎ’’｝とを含んだ削除更新情報を生成する。
【０１８９】
ステップＳ１５０３において、端末側データ送受信部２１３は、Ｓ１５０２で生成された削除更新情報をデータセンタ３０１に送信する。
【０１９０】
ステップＳ１５０４において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ１５０３で送信された削除更新情報を受信する。
ラベル付き索引更新部３０６は、受信された削除更新情報に含まれる索引名ｉｄＩで識別されるラベル付き索引Ｉをラベル付き索引保管部３０４から読み出す。
ラベル付き索引更新部３０６は、受信された削除更新情報に含まれるデータ名｛ｉｄ１’’，…，ｉｄｎ’’｝で識別されるデータ名｛ｉｄ１’’，…，ｉｄｎ’’｝をラベル付き索引Ｉの各配列要素から削除してラベル付き索引Ｉを更新し、更新したラベル付き索引Ｉをラベル付き索引保管部３０４に上書きする。また、ラベル付き索引更新部３０６は、データ名を削除した配列要素の記憶領域を開放する。
【０１９１】
ステップＳ１５０５において、ラベル付き索引更新部３０６は、Ｓ１５０３で受信されたデータ名｛ｉｄ１’’，…，ｉｄｎ’’｝で識別される暗号化データ｛Ｃ１，…，Ｃｎ｝を暗号化データ保管部３０３から削除する。
【０１９２】
Ｓ１５０５により、ラベル付き索引の削除更新処理（具体例）は終了する。
【０１９３】
図１７は、実施の形態１における秘匿検索システム１００のデータ削除処理および索引削除処理（具体例）を示すフローチャートである。
実施の形態１における秘匿検索システム１００のデータ削除処理および索引削除処理（具体例）について、図１７に基づいて説明する。
【０１９４】
図１７のフローチャートは図９、図１０に示したフローチャートに対応している。
Ｓ１６０１はＳ６０１とＳ６０２（またはＳ７０１とＳ７０２）に対応し、Ｓ１６０２はＳ６０３（またはＳ７０３）に対応し、Ｓ１６０３はＳ６０４（またはＳ７０４）に対応する処理である。Ｓ１６０１からＳ１６０３の処理にＳ６０１からＳ６０４（またはＳ７０１からＳ７０４）で説明した事項を適用しても構わない。
【０１９５】
ステップＳ１６０１において、ユーザは、入力装置を用いてアクセス端末２０１に削除データ名｛ｉｄ１’’’，…，ｉｄｎ’’’｝または削除索引名ｉｄＩを指定し、アクセス端末２０１の削除要求生成部２１０は指定された削除データ名または削除索引名ｉｄＩを入力装置から入力する。
削除要求生成部２１０は、入力された削除データ名または削除索引名ｉｄＩを含んだ削除要求データを生成する。
【０１９６】
ステップＳ１６０２において、端末側データ送受信部２１３は、Ｓ１６０１で生成された削除要求データをデータセンタ３０１に送信する。
【０１９７】
ステップＳ１６０３において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ１６０２で送信された削除要求データを受信する。
ラベル付き索引更新部３０６は、受信された削除要求データに含まれる削除データ名｛ｉｄ１’’’，…，ｉｄｎ’’’｝で識別される暗号化データ｛Ｃ１，…，Ｃｎ｝を暗号化データ保管部３０３から削除する。
または、ラベル付き索引更新部３０６は、受信された削除要求データに含まれる削除索引名ｉｄＩで識別されるラベル付き索引Ｉをラベル付き索引保管部３０４から削除する。
【０１９８】
Ｓ１６０３により、秘匿検索システム１００のデータ削除処理および索引削除処理（具体例）は終了する。
【０１９９】
図１８は、実施の形態１におけるラベル管理部２０４の管理テーブルを示す図である。
例えば、ラベル管理部２０４は、図１８に示すような管理テーブルで各種情報を管理する。
図１８に示す管理テーブルは、ラベル情報およびラベルに対応付けて、索引名、パラメータ、キーワードおよび検索結果情報数を示している。
【０２００】
図１９は、実施の形態１におけるアクセス端末２０１およびデータセンタ３０１のハードウェア資源の一例を示す図である。
図１９において、アクセス端末２０１およびデータセンタ３０１（コンピュータの一例）は、ＣＰＵ９０１（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）を備えている。ＣＰＵ９０１は、バス９０２を介してＲＯＭ９０３、ＲＡＭ９０４、通信ボード９０５、ディスプレイ９１１（表示装置）、キーボード９１２、マウス９１３、ドライブ９１４、磁気ディスク装置９２０などのハードウェアデバイスと接続され、これらのハードウェアデバイスを制御する。ドライブ９１４は、ＦＤ（Ｆｌｅｘｉｂｌｅ  Ｄｉｓｋ  Ｄｒｉｖｅ）、ＣＤ（Ｃｏｍｐａｃｔ  Ｄｉｓｃ）、ＤＶＤ（Ｄｉｇｉｔａｌ  Ｖｅｒｓａｔｉｌｅ  Ｄｉｓｃ）などの記憶媒体を読み書きする装置である。
ＲＯＭ９０３、ＲＡＭ９０４、磁気ディスク装置９２０およびドライブ９１４は記憶装置の一例である。キーボード９１２、マウス９１３および通信ボード９０５は入力装置の一例である。ディスプレイ９１１および通信ボード９０５は出力装置の一例である。
【０２０１】
通信ボード９０５は、有線または無線で、ＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネット、電話回線などの通信網に接続している。
【０２０２】
磁気ディスク装置９２０には、ＯＳ９２１（オペレーティングシステム）、プログラム群９２２、ファイル群９２３が記憶されている。
【０２０３】
プログラム群９２２には、実施の形態において「〜部」として説明する機能を実行するプログラムが含まれる。プログラム（例えば、データ検索プログラム、データ登録プログラム）は、ＣＰＵ９０１により読み出され実行される。すなわち、プログラムは、「〜部」としてコンピュータを機能させるものであり、また「〜部」の手順や方法をコンピュータに実行させるものである。
【０２０４】
ファイル群９２３には、実施の形態において説明する「〜部」で使用される各種データ（入力、出力、判定結果、計算結果、処理結果など）が含まれる。
【０２０５】
実施の形態において構成図およびフローチャートに含まれている矢印は主としてデータや信号の入出力を示す。
フローチャートなどに基づいて説明する実施の形態の処理はＣＰＵ９０１、記憶装置、入力装置、出力装置などのハードウェアを用いて実行される。
【０２０６】
実施の形態において「〜部」として説明するものは「〜回路」、「〜装置」、「〜機器」であってもよく、また「〜ステップ」、「〜手順」、「〜処理」であってもよい。すなわち、「〜部」として説明するものは、ファームウェア、ソフトウェア、ハードウェアまたはこれらの組み合わせのいずれで実装されても構わない。
【０２０７】
実施の形態１における秘匿検索システム１００は、例えば、以下のような効果を奏する。
秘匿検索システム１００は、索引数が増えたとしても秘密鍵の数が増えず、キーワードが漏洩せず、共通鍵暗号ベースで高速な検索が可能である。
データを追加・削除するためにラベル付き索引を更新する場合、登録データに関する情報を一切復元（復号）せずにラベル付き索引を更新することができる、つまり暗号化したまま更新処理が可能なため、安全性が高い。
データを削除するためにラベル付き索引を更新する場合、索引鍵が不要であり、データ名のみでラベル付き索引を更新できる。つまり、効率的な削除更新処理が可能である。
非特許文献１，２，３，４，７では、登録・追加データに関連付けることが可能なキーワードが予め決められている。一方で、実施の形態１の秘匿検索システム１００は、キーワードが制限されておらず、登録・追加データに応じて柔軟にキーワードを関連付けることができる。
データ名のビット長Ｍ、ラベル情報のビット長ｘ、キーワードのビット長ｙは、予め、決めておいてもよい。但し、秘密鍵生成部２０２または秘密鍵管理部２０３が索引鍵Ｋのビット数ｋ２によって定まる所定の値の範囲内で自動的に設定してもよい。または、ラベル管理部２０４がラベル付き索引毎に異なるビット長を設定してもよい。このようにすることで、ラベル付き索引の生成を柔軟に行うことができる。
【０２０８】
以下のように処理を変更することにより、キーワード集合Ｗとキーワード別の検索結果数＃Ｄ（ｗ）とを記憶する必要がなく、記憶領域の効率化が図れる。
ステップＳ１２０４において、キーワード設定部２０５は、登録データＤに関連付けるキーワード集合Ｗ＝｛ｗ１，…，ｗｑ｝を生成する。
ステップＳ１２０５において、キーワード設定部２０５は、キーワードｗ（ｗ∈Ｗ）に対する検索結果Ｄ（ｗ）を作成する。
ステップＳ１４０２において、ラベル管理部２０４は、ラベル情報ｄ’に対応するラベルｌａｂｅｌ、索引名ｉｄＩおよびパラメータｎを読み出す。
ステップＳ１４０４の処理は不要である。
ステップＳ１４０５において、ラベル付き索引生成部２０７は、キーワード集合Ｗ’と検索結果情報Ｄ’（ｗ）と索引鍵Ｋとを用いて第１の追加更新情報Ａｄｄ１を生成する。１≦ｉ≦＃Ｗ’、１≦ｊ≦＃Ｄ’（ｗｉ）に対して、Ａｄｄ１＝（π（Ｋ，ｌａｂｅｌ‖１‖ｗｉ‖ｎ＋ｊ）］，Ｄ’（ｗｉ）［ｊ］）である。
ステップＳ１４０７において、ラベル付き索引生成部２０７は、キーワード集合Ｗ’、検索結果情報Ｄ’（ｗ）、非検索結果情報Ｊ’（ｗ）および索引鍵Ｋを用いて第２の追加更新情報Ａｄｄ２を生成する。１≦ｉ≦＃Ｗ’、１≦ｊ≦＃Ｊ’（ｗｉ）に対して、Ａｄｄ２＝（π（Ｋ，ｌａｂｅｌ‖１‖ｗｉ‖ｎ＋ｊ）］，Ｄ’（ｗｉ）［ｊ］）である。
ステップＳ１３０２において、ラベル管理部２０４は、ラベル情報ｄに対応するラベルｌａｂｅｌとデータ数ｎとを読み出す。
ステップＳ１３０３において、ラベル付き検索クエリ生成部２１１は、索引鍵Ｋとラベルｌａｂｅｌとデータ数ｎとを用いてアドレスａｊを算出する。１≦ｊ≦ｎに対して、ａｊ＝π（Ｋ，ｌａｂｅｌ‖１‖ｗ‖ｊ）である。
ステップＳ１３０４において、端末側データ送受信部２１３は、検索クエリｑｕｅｒｙ＝（ａ１，…，ａｎ）をデータセンタ３０１に送信する。
【０２０９】
実施の形態１において、例えば、以下のような検索装置（データセンタ３０１）について説明した。
検索装置は、検索対象データ記憶部（暗号化データ保管部３０３）と、索引データ記憶部（ラベル付き索引保管部３０４）と、検索要求データ入力部（センタ側データ送受信部３０２）と、データ検索部（検索処理部３０５）と、検索結果データ出力部（センタ側データ送受信部３０２）とを備える。
検索対象データ記憶部は、複数の検索対象データ（暗号化データまたは平文データ）を記憶する。
索引データ記憶部は、複数の配列要素を有する索引データ（ラベル付き索引データ）を記憶する。索引データは、前記複数の配列要素のうち前記索引データに対応付けるラベルと前記複数の検索対象データの少なくともいずれかの検索対象データに関連するキーワードとに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである。
検索要求データ入力部は、特定のラベルと特定のキーワードとに基づいて定まる配列要素を指定する検索要求データ（ラベル付き検索クエリ）を入力する。
データ検索部は、前記複数の配列要素のうち前記検索要求データ入力部に入力された前記検索要求データが指定する配列要素からデータ名（検索結果情報）を取得し、取得したデータ名の検索対象データを前記検索対象データ記憶部から取得する。
検索結果データ出力部は、前記データ検索部によって取得された検索対象データを含んだ検索結果データを出力する。
【０２１０】
前記索引データは、前記キーワードと前記ラベルと前記キーワードに関連することを示す関連識別子「１」とに基づいて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである（Ｓ１２０６参照）。
前記索引データは、前記キーワードと前記ラベルと前記キーワードに関連しないことを示す非関連識別子「０」とに基づいて定まる配列要素に、前記キーワードに関連しない検索対象データのデータ名が設定されたデータである（Ｓ１２０８参照）。
キーワードに関連する検索対象データのデータ名だけを索引データに設定した場合、索引データに設定された各データ名の数を頻度分析することによってキーワードまたは検索対象データの内容が推測されてしまう可能性がある。
そこで、キーワードに関連しない検索対象データのデータ名を索引データに設定することによって、頻度分析をさせないようにすることができる。
【０２１１】
前記索引データは、前記キーワードを表すビット列と前記ラベルを表すビット列とを含んだビット列データ「ｌａｂｅｌ‖１‖ｗｉ‖ｊ」を所定の関数πに入力して得られる関数値を用いて定まる配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである（Ｓ１２０６参照）。
前記索引データは、前記関数値によって識別される配列要素に、前記キーワードに関連する検索対象データのデータ名が設定されたデータである（Ｓ１２０６参照）。
【０２１２】
実施の形態１において、例えば、以下のような検索端末装置（アクセス端末２０１）について説明した。
検索端末装置は、キーワード入力部（ラベル付き検索クエリ生成部２１１）と、検索要求データ生成部（ラベル付き検索クエリ生成部２１１）と、検索結果データ受信部（端末側データ送受信部２１３）とを備える。
キーワード入力部は、キーワードと、検索対象データのデータ名が設定される複数の配列要素を有する索引データに対応付けるラベル（ラベル情報）とを入力する。
検索要求データ生成部は、前記キーワード入力部に入力された前記キーワードと前記ラベルとに基づいて、前記索引データのいずれかの配列要素を指定する検索要求データ（ラベル付き検索クエリ）を生成する。
検索結果データ受信部は、前記検索要求データ生成部によって生成された前記検索要求データを複数の検索対象データと前記索引データとを記憶する検索装置（データセンタ３０１）に送信する。検索結果データ受信部は、前記複数の検索対象データのうち前記検索要求データによって指定される前記配列要素に設定されたデータ名の検索対象データ（暗号化データまたは平文データ）を含んだ検索結果データを受信する。
【０２１３】
実施の形態１において、例えば、以下のようなデータ登録装置（アクセス端末２０１）について説明した。
データ登録装置は、検索対象データ記憶部（キーワード設定部２０５）と、索引データ生成部（ラベル付き索引生成部２０７）と、検索対象データ登録部（端末側データ送受信部２１３）とを備える。
検索対象データ記憶部は、検索対象データ（登録データ）と、前記検索対象データに関連するキーワードとを記憶する。
索引データ生成部は、複数の配列要素を有する索引データ（ラベル付き索引）を生成する。索引データ生成部は、前記索引データに対応付けるラベルと前記キーワードとに基づいて前記検索対象データのデータ名を設定する配列要素を決定し、決定した配列要素に前記検索対象データのデータ名を設定する。
検索対象データ登録部は、前記検索対象データと前記索引データ生成部によって生成された前記索引データとを、前記索引データを用いて前記検索対象データの検索を行わせる検索装置（データセンタ３０１）に送信することによって、前記検索装置に前記検索対象データと前記索引データとを記憶させる。
【０２１４】
前記データ登録装置は、追加要求データ生成部（追加更新情報生成部２０８）を備える。
前記検索対象データ記憶部は、新たな検索対象データと、前記新たな検索対象データに関連するキーワードとを記憶する。
前記追加要求データ生成部は、前記索引データに対応付ける前記ラベルと前記新たな検索対象データに関連する前記キーワードとに基づいて前記新たな検索対象データのデータ名を設定する配列要素を決定する。前記追加要求データ生成部は、決定した配列要素を識別するアドレスと前記新たな検索対象データとを含んだ追加要求データ（追加更新情報）を生成する。
前記検索対象データ登録部は、前記追加要求データ生成部によって生成された前記追加要求データを前記検索装置に送信する。これにより、前記検索対象データ登録部は、前記検索装置に前記追加要求データに含まれる前記新たな検索対象データを記憶させ、前記索引データの前記複数の配列要素のうち前記追加要求データに含まれる前記アドレスで識別される配列要素に前記新たな検索対象データのデータ名を設定させる。
【０２１５】
実施の形態２．
実施の形態１とは異なる秘匿検索システム１００アルゴリズムについて説明する。
以下、実施の形態１と異なる事項について主に説明する。説明を省略する事項については実施の形態１と同様である。
【０２１６】
秘匿検索システム１００、アクセス端末２０１およびデータセンタ３０１の構成は、実施の形態１と同様である（図１から図３参照）。
【０２１７】
秘匿検索システム１００の処理概要は、実施の形態１と同様である（図４から図１０参照）。
【０２１８】
以下に、秘匿検索システム１００の処理の詳細（具体例）について説明する。
【０２１９】
まず、以下の説明で使用する項目や記号の一部について説明する。
【０２２０】
ラベル付き索引Ｉは、配列Ａｓ、Ａｄ、Ｔｓ、Ｔｄを用いてＩ＝（Ａｓ、Ａｄ、Ｔｓ、Ｔｄ）で表される。
配列Ａｓ、Ａｄの配列要素の最大数を「Ｚ」とする。配列Ａｓ、Ａｚのアドレス空間を｛０，１｝ｌｇＺとする。また、配列Ａｓの１つの配列要素に設定できる値の最大サイズはｌｇ  Ｍ＋（２×ｌｇ  Ｚ）＋ｋｒビットであり、配列Ａｄの１つの配列要素に設定できる値の最大サイズは（６×ｌｇ  Ｚ）＋ｔｓ＋ｋｒビットとする。ここで、ｌｇ  Ｘ＝ｌｏｇ２  Ｘであり、ｋｒは乱数の所定のビット長である。
配列Ｔｓのアドレス空間を｛０，１｝ｔｓとし、配列Ｔｄのアドレス空間を｛０，１｝ｔｄとする。また、配列Ｔｓの１つの配列要素に設定できる値の最大サイズは２×ｌｇ  Ｚビットであり、配列Ｔｄの１つの配列要素に設定できる値の最大サイズはｌｇ  Ｚビットである。なお、配列Ｔｓ、Ｔｄともにアドレス空間は指数サイズであるが、多項式程度のアドレス空間しか利用せず、かつ利用していないアドレス空間には何も設定しない。このため、配列Ｔｓ、Ｔｄの実質的なサイズは多項式サイズに抑えられる（実施の形態１のラベル付き索引Ｉと同様）。
【０２２１】
関数Ｆ１は｛０，１｝ｋ２×｛０，１｝ｘ＋ｙ  →  ｛０，１｝ｔｓで表される。つまり、関数Ｆ１（Ｋ，ｎ）は、ｋ２ビットの索引鍵Ｋとｘ＋ｙビットの値ｎとを入力にして、０から２ｔｓ−１の整数（｛０，１｝ｔｓの元）のうち（擬似）ランダムな値を出力する。
関数Ｆ２は｛０，１｝ｋ２×｛０，１｝ｘ＋Ｍ  →  ｛０，１｝ｔｄで表される。
関数Ｇ１は｛０，１｝ｋ２×｛０，１｝ｘ＋ｙ  →  ｛０，１｝２ｌｇＺで表される。
関数Ｇ２は｛０，１｝ｋ２×｛０，１｝ｘ＋Ｍ  →  ｛０，１｝ｌｇＺで表される。
関数Ｐ１は｛０，１｝ｋ２×｛０，１｝ｘ＋ｙ  →  ｛０，１｝ｋＨで表される。
関数Ｐ２は｛０，１｝ｋ２×｛０，１｝ｘ＋Ｍ  →  ｛０，１｝ｋＨで表される。
関数Ｑは、｛０，１｝ｋ２×｛０，１｝ｘ＋ｌｇＺ  →  ｛０，１｝Ｍ＋２ｌｇＺで表される。
いずれの関数も、入力値のビット数と同じビット数または異なるビット数の乱数値を出力する擬似ランダム関数である。
【０２２２】
関数Ｈ１は｛０，１｝ｋＨ×｛０，１｝ｋｒ  →  ｛０，１｝Ｍ＋２ｌｇＺで表されるランダムオラクル（鍵付きハッシュ関数ともいう）である。つまり、ランダムなＫＨビットの鍵とｋｒビットの値とを関数Ｈ１に入力すると、関数Ｈ１の出力値は｛０，１｝Ｍ＋２ｌｇＺの中から一様にランダムである。
関数Ｈ２は｛０，１｝ｋＨ×｛０，１｝ｋｒ  →  ｛０，１｝６ｌｇＺ＋ｔｓ＋ｋｒで表されるランダムオラクルである。
【０２２３】
共通鍵暗号方式の暗号化関数Ｅｎｃは、｛０，１｝ｋ１×｛０，１｝＊→｛０，１｝＊で表される。つまり、暗号化関数Ｅｎｃは、ｋ１ビットの鍵ＥＫを用いて任意のビット長のデータを暗号化する。
【０２２４】
図２１は、実施の形態２における秘匿検索システム１００初期設定処理（具体例）を示すフローチャートである。
実施の形態２における秘匿検索システム１００の初期設定処理（具体例）について、図２１に基づいて説明する。
【０２２５】
図２１のフローチャートは図４に示したフローチャートに対応している。
Ｓ２１０１はＳ１０２に対応し、Ｓ２１０２はＳ１０３に対応し、Ｓ２１０３はＳ１０４に対応する処理である。Ｓ２１０１からＳ２１０３の処理にＳ１０１からＳ１０４で説明した事項を適用しても構わない。
【０２２６】
ステップＳ２１０１において、秘密鍵生成部２０２は、共通鍵暗号方式のｋ１ビットの暗号化鍵ＥＫをランダムに生成する。ｋ１は任意の整数値である。
【０２２７】
ステップＳ２１０２において、秘密鍵生成部２０２は、ｋ２ビットの７つの乱数Ｋ１，Ｋ２，Ｋ３，Ｋ４，Ｋ５，Ｋ６，Ｋ７を生成する。ｋ２は任意の整数値である。以下、ステップＳ２１０８で生成した乱数Ｋｘを「索引鍵Ｋｘ」という。
【０２２８】
ステップＳ２１０３において、秘密鍵管理部２０３は、Ｓ２１０１で生成した暗号化鍵ＥＫとＳ２１０２で生成した索引鍵Ｋ１からＫ７を記憶する。
【０２２９】
Ｓ２１０３により、秘匿検索システム１００の初期設定処理は終了する。
【０２３０】
図２２、図２３および図２４は、実施の形態２における秘匿検索システム１００のデータ登録処理（具体例）を示すフローチャートである。
実施の形態２における秘匿検索システム１００のデータ登録処理（具体例）について、図２２から図２４に基づいて説明する。
【０２３１】
図２２から図２４のフローチャートは図５に示したフローチャートに対応している。
Ｓ２２０１はＳ２０１に対応し、Ｓ２２０２はＳ２０２に対応し、Ｓ２２０３はＳ２０７に対応し、Ｓ２２０４はＳ２０３に対応し、Ｓ２２０５はＳ２０４に対応し、Ｓ２２０６からＳ２２２５はＳ２０６に対応し、Ｓ２２２６はＳ２０８に対応し、Ｓ２２２７はＳ２０９とＳ２２０とに対応する処理である。Ｓ２２０１からＳ２２２７の処理にＳ２０１からＳ２１０で説明した事項を適用しても構わない。
【０２３２】
ステップＳ２２０１において、ユーザは入力装置を用いてアクセス端末２０１にデータ集合Ｄ＝｛Ｄ１，…，Ｄｎ｝とラベル情報ｄとを指定し、アクセス端末２０１のキーワード設定部２０５は指定されたデータ集合Ｄとラベル情報ｄとを入力装置から入力する。
【０２３３】
ステップＳ２２０２において、ラベル管理部２０４は、Ｓ２２０１で入力されたラベル情報ｄに基づいてラベルｌａｂｅｌを生成し、生成したラベルｌａｂｅｌとラベル情報ｄとを対応付けて記憶する。
【０２３４】
ステップＳ２２０３において、ラベル管理部２０４は、データ集合Ｄ内のデータ数ｎを算出し、算出したデータ数ｎをラベル情報ｄに対応付けて記憶する。
【０２３５】
ステップＳ２２０４において、キーワード設定部２０５は、Ｓ２２０１で入力されたデータ集合Ｄに関連するキーワード集合Ｗ＝｛ｗ１，…，ｗｑ｝を生成する。キーワード集合Ｗの生成方法は実施の形態１のＳ２０３と同様である。生成したキーワード集合Ｗは、実施の形態１のようにラベル情報ｄに対応付けて記憶しなくても構わない。
【０２３６】
ステップＳ２２０５において、キーワード設定部２０５は、Ｓ２２０４で生成したキーワード集合Ｗに含まれるキーワードｗｉ別に検索結果情報Ｄ（ｗｉ）を生成し、生成した検索結果情報Ｄ（ｗｉ）の検索結果数＃Ｄ（ｗｉ）をラベルｌａｂｅｌに対応付けてラベル管理部２０４に記憶する。
【０２３７】
ステップＳ２２０６において、ラベル付き索引生成部２０７は、Ｓ２２０４で生成されたキーワード集合Ｗに含まれるキーワードｗｉ別にｂｉ個のｋｒビットの乱数ｒ（ｗｉ，１），…，ｒ（ｗｉ，ｂｉ）を生成する。但し、ｂｉ＝＃Ｄ（ｗｉ）である。
つまり、ラベル付き索引生成部２０７は、ｂ１＋…＋ｂ＃Ｗ個の乱数ｒを生成する。
【０２３８】
ステップＳ２２０７において、ラベル付き索引生成部２０７は、Ｓ２２０４で生成されたキーワード集合Ｗに含まれるキーワードｗｉ別に配列Ａｓの配列要素を識別するｂｉ個のアドレスａＡｓ（ｗｉ，１），…，ａＡｓ（ｗｉ，ｂｉ）をランダムに選択する。つまり、ラベル付き索引生成部２０７は、ｂ１＋…＋ｂ＃Ｗ個のアドレスａＡｓを選択する。
【０２３９】
ステップＳ２２０８において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ３を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ３と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２０６で生成した乱数ｒとを用いて、キーワードｗｉ別に関数値ｋｗｉ、ｈ１（ｗｉ，ｊ）を算出する。
ここで、ｗｉ∈Ｗ、１≦ｊ≦ｂｉに対して、ｋｗｉ＝Ｐ１（Ｋ３，ｌａｂｅｌ‖ｗｉ）であり、ｈ１（ｗｉ，ｊ）＝Ｈ１（ｋｗｉ，ｒ（ｗｉ，ｊ））である。
【０２４０】
ステップＳ２２０９において、ラベル付き索引生成部２０７は、Ｓ２２０５で生成された検索結果情報Ｄ（ｗｉ）と、Ｓ２２０６で生成した乱数ｒと、Ｓ２２０７で選択したアドレスａＡｓと、Ｓ２２０８で算出した関数値ｈ１（ｗｉ，ｊ）とを用いて、配列Ａｓの設定を行う。
ここで、ｗｉ∈Ｗ、１≦ｊ≦ｂｉに対して、Ｎ（ｗｉ，ｊ）＝（＜Ｄ（ｗｉ）［ｊ］‖ａＡｓ（ｗｉ，ｊ−１）‖ａＡｓ（ｗｉ，ｊ＋１）＞  ＸＯＲ  ｈ１（ｗｉ，ｊ），ｒ（ｗｉ，ｊ））とする。Ｄ（ｗｉ）［ｊ］は各データ名ｉｄが辞書順（名前順）にソートされた検索結果情報Ｄ（ｗｉ）のｊ番目のデータ名ｉｄを意味する。
このとき、配列Ａｓの設定は、Ａｓ［ａＡｓ（ｗｉ，ｊ）］＝Ｎ（ｗｉ，ｊ）で表される。ただし、ａＡｓ（ｗｉ，０）＝ａＡｓ（ｗｉ，ｂｉ＋１）＝０ｌｇＺとする。
【０２４１】
ステップＳ２２１０において、ラベル付き索引生成部２０７は、Ｓ２２０５で生成された検索結果情報Ｄ（ｗｉ）に基づいて整数値ｚを算出し、算出した整数値ｚをラベルｌａｂｅｌに対応付けてラベル管理部２０４に記憶する。
整数値ｚは配列Ａｓの最大の配列要素数Ｚから検索結果数＃Ｄ（ｗｉ）の合計値を差し引いた値である。
【０２４２】
【数１】
0005800721.tif 000002
【０２４３】
ステップＳ２２１１において、ラベル付き索引生成部２０７は、Ｓ２２０１で入力されたデータＤｉ別にＢｉ個のｋｒビットの乱数ｒ（Ｄｉ，１），…，ｒ（Ｄｉ，Ｂｉ）を生成する。
ここで、Ｂｉ＝＃ｋｗ（Ｄｉ）である。ｋｗ（Ｄｉ）はデータＤｉに関連するキーワード集合を意味し、＃ｋｗ（Ｄｉ）はキーワード集合ｋｗ（Ｄｉ）内のキーワード数を意味する。
つまり、ラベル付き索引生成部２０７は、Ｂ１＋…＋Ｂｎ個の乱数ｒを生成する。乱数ｒの個数Ｂ１＋…＋Ｂｎは、Ｓ２２０６で生成される乱数ｒの個数ｂ１＋…＋ｂ＃Ｗと同じである。
【０２４４】
ステップＳ２２１２において、ラベル付き索引生成部２０７は、Ｓ２２０１で入力されたデータＤｉ別に配列Ａｄの配列要素を識別するＢｉ個のアドレスａＡｄ（Ｄｉ，１），…，ａＡｄ（Ｄｉ，Ｂｉ）をランダムに選択する。つまり、ラベル付き索引生成部２０７は、Ｂ１＋…＋Ｂｎ個のアドレスａＡｄを選択する。
【０２４５】
ステップＳ２２１３において、ラベル付き索引生成部２０７は、Ｓ２２１２で選択したアドレスａＡｄを用いてアドレスａＡｓ＊を定義する。
このとき、ラベル付き索引生成部２０７は、ｗｉ∈Ｗ、１≦ｊ≦＃Ｄ（ｗｉ）に対して、Ｄ（ｗｉ）［ｊ］＝ｉｄｋと、ｋｗ（Ｄｋ）［ｊ’］＝ｗｉとを満たす１≦ｊ’≦Ｄｋを求め、ａＡｓ＊（ｗｉ，ｊ）＝ａＡｄ（Ｄｋ，ｊ’）を計算してアドレスａＡｓ＊を定義する。ただし、ｋｗ（Ｄｋ）［ｊ’］はキーワードｗが辞書順にソートされたキーワード集合ｋｗ（Ｄｋ）のｊ’番目のキーワードｗを意味する。
「ａＡｓ＊（ｗｉ，ｊ）＝ａＡｄ（Ｄｋ，ｊ’）」は、キーワードｗｉに対する検索結果情報Ｄ（ｗｉ）があるｉｄを含んでいる場合、そのｉｄに対するデータＤには必ずキーワードｗｉが設定されている（または関連する）、という関係性を表している。
【０２４６】
ステップＳ２２１４において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ１、Ｋ６を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ１、Ｋ６と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２０４で生成されたキーワード集合Ｗと、Ｓ２２１１で生成した乱数ｒとを用いて、関数値ａＴｓ、ＫＤｉ、ｈ２を算出する。
ここで、Ｄｉ∈Ｄ、１≦ｊ≦＃ｋｗ（Ｄｉ）に対して、ａＴｓ（ｗ）＝Ｆ１（Ｋ１，ｌａｂｅｌ‖ｗ）であり、ＫＤｉ＝Ｐ２（Ｋ６，ｌａｂｅｌ‖ｉｄｉ）であり、ｈ２（Ｄｉ，ｊ）＝Ｈ２（ＫＤｉ，ｒ（Ｄｉ，ｊ））である。
【０２４７】
ステップＳ２２１５において、ラベル付き索引生成部２０７は、Ｓ２２１１で生成した乱数ｒと、Ｓ２２１３で定義したアドレスａＡｓ＊（ｗｉ，ｊ）と、Ｓ２２１４で算出した関数値ｈ２（Ｄｉ，ｊ）とを用いて、配列Ａｄの設定を行う。
ここで、Ｄｋ∈Ｄ、１≦ｊ’≦Ｂｋに対して、Ｎ（Ｄｋ，ｊ’）を以下のように表す。
Ｎ（Ｄｋ，ｊ’）＝（＜ａＡｄ（Ｄｋ，ｊ’＋１）‖ａＡｓ＊（ｗｉ，ｊ−１）‖ａＡｓ＊（ｗｉ，ｊ＋１）‖ａＡｓ（ｗｉ，ｊ）‖ａＡｓ（ｗｉ，ｊ−１）‖ａＡｓ（ｗｉ，ｊ＋１）‖ａＴｓ（ｗｉ）＞  ＸＯＲ  ｈ２（Ｄｋ，ｒ（Ｄｋ，ｊ’）），ｒ（Ｄｋ，ｊ’））
このとき、配列Ａｄの設定は、Ａｄ［ａＡｄ（Ｄｋ，ｊ’）］＝Ｎ（Ｄｋ，ｊ’）で表される。
【０２４８】
ステップＳ２２１６において、ラベル付き索引生成部２０７は、Ｓ２２０４で生成されたキーワード集合Ｗに含まれるいずれのキーワードｗとも異なる２×ｚ個のキーワードｆｒｅｅをランダムに生成し、生成したキーワードｆｒｅｅをラベル情報ｄに対応付けてラベル管理部２０４に記憶する。
以下、２×ｚ個のキーワードｆｒｅｅをｆｒｅｅ１，…，ｆｒｅｅｚ、ｆｒｅｅ１＊，…，ｆｒｅｅｚ＊と記す。
【０２４９】
ステップＳ２２１７において、ラベル付き索引生成部２０７は、配列Ａｓの未設定の配列要素を識別するｚ個のアドレスａＡｓ（ｆｒｅｅ１），…，ａＡｓ（ｆｒｅｅｚ）をランダムに定義する。
また、ラベル付き索引生成部２０７は、配列Ａｄの未設定の配列要素を識別するｚ個のアドレスａＡｄ（ｆｒｅｅ１＊），…，ａＡｄ（ｆｒｅｅｚ＊）をランダムに定義する。
【０２５０】
ステップＳ２２１８において、ラベル付き索引生成部２０７は、（６×ｌｇ  Ｚ）＋ｔｓ＋ｋｒビットの乱数をｚ個生成し、生成したｚ個の乱数をＳ２２１７で定義したアドレスで識別される配列要素Ａｓ［ａＡｄ（ｆｒｅｅ１＊）］，…，Ａｓ［ａＡｄ（ｆｒｅｅｚ＊）］に設定する。
【０２５１】
ステップＳ２２１９において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ７を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ７と、Ｓ２２０２で生成されたラベルｌａｂｅｌとを用いて、関数値Ｑｉを算出する。
ここで、１≦ｉ≦ｚに対して、Ｑｉ＝Ｑ（Ｋ７，ｌａｂｅｌ‖ｉ）である。
【０２５２】
ステップＳ２２２０において、ラベル付き索引生成部２０７は、Ｓ２２１７で定義したアドレスａＡｓ（ｆｒｅｅｉ）とａＡｄ（ｆｒｅｅｉ＊）と、Ｓ２２１９で算出した関数値Ｑｉとを用いて、配列Ａｓの設定を行う。
配列Ａｓの設定は、Ａｓ［ａＡｓ（ｆｒｅｅｉ）］＝＜０Ｍ‖ａＡｓ（ｆｒｅｅｉ−１）‖ａＡｄ（ｆｒｅｅｉ＊）＞  ＸＯＲ  Ｑｉで表される。
【０２５３】
ステップＳ２２２１において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ２を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ２と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２０７で選択したアドレスａＡｓ（ｗ，１）と、Ｓ２２１３で定義したアドレスａＡｓ＊（ｗ，１）とを用いて、配列Ｔｓの設定を行う。
配列Ｔｓの設定は、ｗ∈Ｗに対して、Ｔｓ［ａＴｓ（ｗ）］＝＜ａＡｓ（ｗ，１）‖ａＡｓ＊（ｗ，１）＞  ＸＯＲ  Ｇ１（Ｋ２，ｌａｂｅｌ‖ｗ）で表される。
【０２５４】
ステップＳ２２２２において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ４を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ４と、Ｓ２２０２で生成されたラベルｌａｂｅｌとを用いて、アドレスａＴｄ（Ｄｉ）を算出する。
ここで、Ｄｉ∈Ｄに対して、ａＴｄ（Ｄｉ）＝Ｆ２（Ｋ４，ｌａｂｅｌ‖ｉｄｉ）である。
【０２５５】
ステップＳ２２２３において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ５を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ５と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２２２で算出したアドレスａＴｄ（Ｄｉ）とを用いて、配列Ｔｄの設定を行う。
配列Ｔｄの設定は、Ｄｉ∈Ｄに対して、Ｔｄ［ａＴｄ（Ｄｉ）］＝ａＡｄ（Ｄｉ，１）  ＸＯＲ  Ｇ２（Ｋ５，ｌａｂｅｌ‖ｉｄｉ）で表される。
【０２５６】
ステップＳ２２２４において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ１を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ１と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２１６で生成したキーワードｆｒｅｅとを用いて、アドレスａＴｓ（ｆｒｅｅ）を算出する。
ここで、ａＴｓ（ｆｒｅｅ）＝Ｆ１（Ｋ１，ｌａｂｅｌ‖ｆｒｅｅ）である。
【０２５７】
ステップＳ２２２５において、ラベル付き索引生成部２０７は、秘密鍵管理部２０３から索引鍵Ｋ２を読み出す。ラベル付き索引生成部２０７は、秘密鍵管理部２０３から読み出した索引鍵Ｋ２と、Ｓ２２０２で生成されたラベルｌａｂｅｌと、Ｓ２２１６で生成したキーワードｆｒｅｅと、Ｓ２２１７で生成したアドレスａＡｓ（ｆｒｅｅｚ）と、Ｓ２２２４で算出したアドレスａＴｓ（ｆｒｅｅ）とを用いて、配列Ｔｓの設定を行う。
配列Ｔｓの設定は、Ｔｓ［ａＴｓ（ｆｒｅｅ）］＝＜ａＡｓ（ｆｒｅｅｚ）‖０ｌｇ  Ｚ＞  ＸＯＲ  Ｇ１（Ｋ２，ｌａｂｅｌ‖ｆｒｅｅ）で表される。
【０２５８】
ステップＳ２２２６において、データ暗号化部２０６は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。データ暗号化部２０６は、暗号化関数Ｅｎｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、Ｓ２２０１で入力されたデータ集合Ｄ＝｛Ｄ１，…，Ｄｎ｝を暗号化する。
データ集合Ｄの暗号化は、１≦ｉ≦ｎに対して、Ｃｉ＝Ｅｎｃ（ＥＫ，Ｄｉ）で表される。ＣｉはデータＤｉを暗号化した暗号化データである。
【０２５９】
ステップＳ２２２７において、端末側データ送受信部２１３は、配列Ａｓ、Ａｄ、Ｔｓ、Ｔｄを用いてラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）を生成し、生成したラベル付き索引ＩとＳ２２２６で生成した暗号化データ集合Ｃ＝｛Ｃ１，…，Ｃｎ｝とをデータセンタ３０１に送信する。
データセンタ３０１のセンタ側データ送受信部３０２はラベル付き索引Ｉと暗号化データ集合Ｃと受信し、暗号化データ保管部３０３は暗号化データ集合Ｃを記憶し、ラベル付き索引保管部３０４はラベル付き索引Ｉを記憶する。
【０２６０】
Ｓ２２２７により、秘匿検索システム１００のデータ登録処理は終了する。
【０２６１】
図２５は、実施の形態２における秘匿検索システム１００の検索処理（具体例）を示すフローチャートである。
実施の形態２における秘匿検索システム１００の検索処理（具体例）について、図２５に基づいて説明する。
【０２６２】
図２５のフローチャートは図６に示したフローチャートに対応している。
Ｓ２３０１はＳ３０１に対応し、Ｓ２３０２はＳ３０２に対応し、Ｓ２３０３はＳ３０３に対応し、Ｓ２３０４はＳ３０４に対応し、Ｓ２３０５はＳ３０５に対応し、Ｓ２３０６からＳ２３０８はＳ３０６に対応し、Ｓ２３０９はＳ３０７とＳ３０８とに対応し、Ｓ２３１０はＳ３０９に対応する処理である。Ｓ２３０１からＳ２３１０の処理にＳ３０１からＳ３０９で説明した事項を適用しても構わない。
【０２６３】
ステップＳ２３０１において、ユーザは、入力装置を用いてアクセス端末２０１に検索キーワードｗとラベル情報ｄとを指定し、アクセス端末２０１のラベル付き検索クエリ生成部２１１は指定された検索キーワードｗとラベル情報ｄとを入力装置から入力する。
【０２６４】
ステップＳ２３０２において、ラベル管理部２０４は、Ｓ２３０１で入力されたラベル情報ｄに対応付けられたラベルｌａｂｅｌとラベル付き索引Ｉとを読み出す。
【０２６５】
ステップＳ２３０３において、ラベル付き検索クエリ生成部２１１は、秘密鍵管理部２０３から索引鍵Ｋ１、Ｋ２、Ｋ３を読み出す。ラベル付き検索クエリ生成部２１１は、秘密鍵管理部２０３から読み出した索引索Ｋ１、Ｋ２、Ｋ３と、Ｓ２３０２で読み出されたラベルｌａｂｅｌとを用いて、検索クエリｑｕｅｒｙ（ラベル付き検索クエリ）を生成する。
ここで、ｑｕｅｒｙ＝（Ｆ１（Ｋ１，ｌａｂｅｌ‖ｗ），Ｇ１（Ｋ２，ｌａｂｅｌ‖ｗ），Ｐ１（Ｋ３，ｌａｂｅｌ‖ｗ））である。
【０２６６】
ステップＳ２３０４において、端末側データ送受信部２１３はＳ２３０３で生成した検索クエリｑｕｅｒｙをデータセンタ３０１に送信する。
【０２６７】
ステップＳ２３０５において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ２３０４で送信された検索クエリｑｕｅｒｙを受信する。
以下、検索クエリｑｕｅｒｙをｑｕｅｒｙ＝（ｑｌ１，ｑｌ２，ｑｌ３）と記す。
【０２６８】
ステップＳ２３０６において、検索処理部３０５は、ラベル付き索引保管部３０４に記憶されているラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）を読み出す。検索処理部３０５は、ラベル付き索引保管部３０４から読み出したラベル付き索引Ｉと、Ｓ２３０５で受信された検索クエリｑｕｅｒｙとを用いて、アドレスａ１、ａ１＊を算出する。
アドレスａ１、ａ１＊は、Ｔｓ［ｑｌ１］  ＸＯＲ  ｑｌ２＝（ａ１‖ａ１＊）を満たす値である。
【０２６９】
ステップＳ２３０７において、検索処理部３０５は、Ｓ２３０５で受信された検索クエリｑｕｅｒｙとＳ２３０６で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２３０６で算出したアドレスａ１とを用いて、データ名ＩＤ１とアドレスａ２とを算出する。
ここで、Ａｓ［ａ１］＝（Ｎ１，ｒ１）とする。データ名ＩＤ１およびアドレスａ２は、Ｎ１  ＸＯＲ  Ｈ１（ｑｌ３，ｒ１）＝（ＩＤ１‖０ｌｇ  Ｚ‖ａ２）を満たす値である。
【０２７０】
ステップＳ２３０８において、検索処理部３０５は、Ｓ２３０５で受信された検索クエリｑｕｅｒｙと、Ｓ２３０６で読み出したラベル付き索引Ｉと、Ｓ２３０７で算出したアドレスａ２とを用いて、データ名ＩＤ２とアドレスａ３とを算出する。
ここで、Ａｓ［ａ２］＝（Ｎ２，ｒ２）とする。データ名ＩＤ２およびアドレスａ３は、Ｎ２  ＸＯＲ  Ｈ１（ｑｌ３，ｒ２）＝（ＩＤ２‖ａ１‖ａ３）を満たす値である。
さらに、検索処理部３０５は、同様に計算を繰り返し、データ名｛ＩＤ３，…，ＩＤｍ｝を算出する。但し、ｍは、ａｍ＋１＝０ｌｇ  Ｚ（１≦ｍ）を満たす値である。
【０２７１】
ステップＳ２３０９において、検索処理部３０５は、Ｓ２３０７およびＳ２３０８で算出したデータ名｛ＩＤ１，…，ＩＤｍ｝で識別される暗号化データ｛Ｃ１，…，Ｃｍ｝を暗号化データ保管部３０３から抽出し、抽出した暗号化データ｛Ｃ１，…，Ｃｍ｝を含んだ検索結果データを生成する。
センタ側データ送受信部３０２は検索処理部３０５によって生成された検索結果データをアクセス端末２０１に送信する。
【０２７２】
ステップＳ２３１０において、アクセス端末２０１の端末側データ送受信部２１３は、Ｓ２３０９で送信された検索結果データを受信する。
データ復号部２１２は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。データ復号部２１２は、復号関数Ｄｅｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、受信された暗号化データ｛Ｃ１，…，Ｃｍ｝を復号する。暗号化データ｛Ｃ１，…，Ｃｍ｝を復号することにより、暗号化前のデータ｛Ｄ１，…，Ｄｍ｝が得られる。
暗号化データＣｊの復号は、Ｄ＝Ｄｅｃ（ＥＫ，Ｃｊ）で表される。
データ復号部２１２は、復号により得られたデータ｛Ｄ１，…，Ｄｍ｝を出力装置に出力する。
【０２７３】
Ｓ２３１０により、秘匿検索システム１００の検索処理は終了する。
【０２７４】
但し、Ｓ２３０６からＳ２３０９において、データセンタ３０１に保管されている全てのラベル付き索引Ｉを検索する代わりに、ユーザから指定されたラベル付き索引Ｉだけを検索してもよい。
この場合、Ｓ２３０４において、端末側データ送受信部２１３は、ユーザから指定されたラベル情報に対応付けられたラベル付き索引Ｉの索引名ｉｄＩを含んだ検索クエリｑｕｅｒｙをデータセンタ３０１に送信する。Ｓ２３０６からＳ２３０９において、検索処理部３０５は、検索クエリｑｕｅｒｙに含まれる索引名ｉｄＩのラベル付き索引Ｉだけを検索する。
【０２７５】
図２６、図２７および図２８は、実施の形態２における秘匿検索システム１００のデータ追加処理（具体例）を示すフローチャートである。
実施の形態２における秘匿検索システム１００のデータ追加処理（具体例）について、図２６、図２７および図２８に基づいて説明する。
【０２７６】
図２６から図２８のフローチャートは図７に示したフローチャートに対応している。
Ｓ２４０１はＳ４０１に対応し、Ｓ２４０２はＳ４０２に対応し、Ｓ２４０３はＳ４０３に対応し、Ｓ２４０４からＳ２４０６はＳ４０６に対応し、Ｓ２４０７はＳ４０８に対応し、Ｓ２４０８はＳ４０６とＳ４０９とに対応し、Ｓ２４０９はＳ４１０とＳ４１１とに対応し、Ｓ２４１０からＳ２４１９はＳ４１２に対応し、Ｓ２４２０はＳ４１３に対応する処理である。Ｓ２４０１からＳ２４２０の処理にＳ４０１からＳ４１３で説明した事項を適用しても構わない。
【０２７７】
ステップＳ２４０１において、ユーザは入力装置を用いてアクセス端末２０１に追加データ集合Ｄ’ ＝｛Ｄ１’，…，Ｄｍ’｝とラベル情報ｄ’とを指定し、アクセス端末２０１のキーワード設定部２０５は指定された追加データ集合Ｄ’とラベル情報ｄ’とを入力装置から入力する。
【０２７８】
ステップＳ２４０２において、ラベル管理部２０４は、Ｓ２４０１で入力されたラベル情報ｄ’に対応付けられたラベルｌａｂｅｌ、ラベル付き索引Ｉ、整数値ｚおよびキーワードｆｒｅｅを読み出す。
【０２７９】
ステップＳ２４０３において、キーワード設定部２０５は、Ｓ２４０１で入力された追加データ集合Ｄ’に関連するキーワード集合Ｗ’＝｛ｗ１’，…，ｗｐ’｝を生成する。キーワード集合Ｗ’の生成方法は実施の形態１のＳ２０３と同様である。
【０２８０】
ステップＳ２４０４において、追加更新情報生成部２０８は、２×ｐ個のｋｒビットの乱数ｒ（１），…，ｒ（ｐ）、ｒ（１）＊，…，ｒ（ｐ）＊を生成する。ここで、ｐは、Ｓ２４０３で生成されたキーワード集合Ｗ’のキーワード数である。
【０２８１】
ステップＳ２４０５において、追加更新情報生成部２０８は、秘密鍵管理部２０３から索引鍵Ｋ１、Ｋ２、Ｋ３、Ｋ７を読み出す。追加更新情報生成部２０８は、秘密鍵管理部２０３から読み出した索引鍵Ｋ１、Ｋ２、Ｋ３、Ｋ７と、Ｓ２４０２で読み出したラベルｌａｂｅｌと整数値ｚと、Ｓ２４０３で生成したキーワード集合Ｗ’と、Ｓ２４０４で生成した乱数ｒ（ｉ）とを用いて、ｘｉを算出する。
ここで、１≦ｉ≦ｐに対して、ｘｉは以下のように表される。
ｘｉ＝（Ｆ１（Ｋ１，ｌａｂｅｌ‖ｗｉ’），Ｇ１（Ｋ２，ｌａｂｅｌ‖ｗｉ’），Ｑ（Ｋ７，ｌａｂｅｌ‖ｚ＋１−ｉ），＜ｉｄ’‖０ｌｇＺ‖０ｌｇＺ＞  ＸＯＲ  Ｈ１（Ｐ１（Ｋ３，ｌａｂｅｌ‖ｗｉ’），ｒ（ｉ）），ｒ（ｉ））
【０２８２】
ステップＳ２４０６において、追加更新情報生成部２０８は、Ｓ２４０２で読み出した整数値ｚからＳ２４０３で生成されたキーワード集合Ｗ’のキーワード数ｐを差し引いて整数値ｚを更新し、更新した整数値ｚをラベル管理部２０４に上書きする。つまり、追加更新情報生成部２０８は、ｚ＝ｚ−ｐで表される整数値ｚをラベル管理部２０４に上書きする。
【０２８３】
ステップＳ２４０７において、データ暗号化部２０６は、秘密鍵管理部２０３から暗号化鍵ＥＫを読み出す。データ暗号化部２０６は、暗号化関数Ｅｎｃと秘密鍵管理部２０３から読み出した暗号化鍵ＥＫとを用いて、Ｓ２４０１で入力された追加データ集合Ｄ’ ＝｛Ｄ１’，…，Ｄｍ’｝を暗号化する。
追加データ集合Ｄ’の暗号化は、１≦ｉ≦ｍに対して、Ｃ’＝Ｅｎｃ（ＥＫ，Ｄｉ’）で表される。Ｃｉ’は追加データＤｉ’を暗号化した暗号化データである。
【０２８４】
ステップ２２０８において、追加更新情報生成部２０８は、秘密鍵管理部２０３から索引鍵Ｋ１、Ｋ２、Ｋ４、Ｋ５、Ｋ６を読み出す。
追加更新情報生成部２０８は、秘密鍵管理部２０３から読み出した索引鍵Ｋ１、Ｋ２、Ｋ４、Ｋ５、Ｋ６と、Ｓ２４０２で読み出したキーワードｆｒｅｅとを用いて、追加更新情報ｔａｄｄを生成する。
ここで、追加更新情報ｔａｄｄは、ｔａｄｄ＝（Ｆ１（Ｋ１，ｌａｂｅｌ‖ｆｒｅｅ），Ｇ１（Ｋ２，ｌａｂｅｌ‖ｆｒｅｅ），Ｐ２（Ｋ６，ｌａｂｅｌ‖ｉｄ’），Ｆ２（Ｋ４，ｌａｂｅｌ‖ｉｄ’），Ｇ２（Ｋ５，ｌａｂｅｌ‖ｉｄ’），ｘ１，…，ｘｐ，ｒ（１）＊，…，ｒ（ｐ）＊，Ｃ’）で表される。
端末側データ送受信部２１３は暗号化データ集合Ｃ’ ＝｛Ｃ１’，…，Ｃｍ’｝と追加更新情報ｔａｄｄと索引名ｉｄＩとをデータセンタ３０１に送信する。
【０２８５】
ステップＳ２４０９において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ２４０８で送信された暗号化データ集合Ｃ’と追加更新情報ｔａｄｄと索引名ｉｄＩとを受信する。
ラベル付き索引更新部３０６は、受信された索引名ｉｄＩで識別されるラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）をラベル付き索引保管部３０４から読み出す。
以下、Ｓ２４０８で受信された追加更新情報ｔａｄｄをｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と記す。
【０２８６】
ステップＳ２４１０において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）とを用いて、アドレスｆ１を算出する。
アドレスｆ１は、Ｔｓ［ｔ１］  ＸＯＲ  ｔ２＝ｆ１‖０ｌｇ  Ｚを満たす値である。
【０２８７】
ステップＳ２４１１において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１０で算出したアドレスｆ１とを用いて、アドレスｆ２，…，ｆｐ＋１，ｆ１＊，…，ｆｐ＊を算出する。
ここで、アドレスｆｉ、ｆｉ＊は、Ａｓ［ｆ１］  ＸＯＲ  ｘ１［３］＝０‖ｆ２‖ｆ１＊，…，Ａｓ［ｆｐ］  ＸＯＲ  ｘｐ［３］＝０‖ｆｐ＋１‖ｆｐ＊の関係を満たす。
【０２８８】
ステップＳ２４１２において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で求めたｆｐ＋１とを用いて、配列Ｔｓを更新する。
配列Ｔｓの更新は、Ｔｓ［ｔ１］＝＜ｆｐ＋１‖０ｌｇ  Ｚ＞  ＸＯＲ  ｔ２で表される。
【０２８９】
ステップＳ２４１３において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）とを用いて、アドレスａ１，…，ａｐ，ａ１＊，…，ａｐ＊を算出する。
ここで、アドレスａｉ，ａｉ＊は、Ｔｓ［ｘ１［１］］  ＸＯＲ  ｘ１［２］＝ａ１‖ａ１＊，…，Ｔｓ［ｘｐ［１］］  ＸＯＲ  ｘｐ［２］＝ａｐ‖ａｐ＊の関係を満たす。
【０２９０】
ステップＳ２４１４において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で算出されたアドレスｆ１，…，ｆｐと、Ｓ２４１３で算出されたアドレスａ１，…，ａｐとを用いて、配列Ａｓを更新する。
ここで、更新前の配列ＡｓをＡｓ［ａ１］＝（Ｎ１，ｒ１），…，Ａｓ［ａｐ］＝（Ｎｐ，ｒｐ）とする。
このとき、更新後の配列ＡｓはＡｓ［ａ１］＝（Ｎ１  ＸＯＲ  ＜０Ｍ‖ｆ１‖０ｌｇ  Ｚ＞，ｒ１），…，Ａｓ［ａｐ］＝（Ｎｐ  ＸＯＲ  ＜０Ｍ‖ｆｐ‖０ｌｇ  Ｚ＞，ｒｐ）で表される。
【０２９１】
ステップＳ２４１５において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で算出されたアドレスｆ１，…，ｆｐと、Ｓ２４１３で算出されたアドレスａ１，…，ａｐとを用いて、配列Ａｓを更新する。
配列Ａｓの更新は、Ａｓ［ｆ１］＝（ｘ１［４］  ＸＯＲ  ＜０Ｍ‖０ｌｇ  Ｚ‖ａ１＞，ｘ１［５］），…，Ａｓ［ｆｐ］＝（ｘｐ［４］  ＸＯＲ  ＜０Ｍ‖０ｌｇ  Ｚ‖ａｐ＞，ｘｐ［５］）で表される。
【０２９２】
ステップＳ２４１６において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で算出されたアドレスｆ１，…，ｆｐ，ｆ１＊，…，ｆｐ＊とを用いて、配列Ｔｓを更新する。
配列Ｔｓの更新は、Ｔｓ［ｘ１［１］］＝＜ｆ１‖ｆ１＊＞  ＸＯＲ  ｘ１［２］，…，Ｔｓ［ｘｐ［１］］＝＜ｆｐ‖ｆｐ＊＞  ＸＯＲ  ｘｐ［２］で表される。
【０２９３】
ステップＳ２４１７において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１３で算出したアドレスａ１＊，…，ａｐ＊と、Ｓ２４１１で算出したアドレスｆ１，…，ｆｐ，ｆ１＊，…，ｆｐ＊とを用いて、配列Ａｄを更新する。
ここで、更新前の配列ＡｄをＡｄ［ａ１＊］＝（Ｎ１＊，ｒ１＊），…，Ａｄ［ａｐ＊］＝（Ｎｐ＊，ｒｐ＊）とする。
このとき、更新後の配列Ａｄは、Ａｄ［ａ１＊］＝（Ｎ１＊  ＸＯＲ  ＜０ｌｇ  Ｚ‖ｆ１＊‖０ｌｇ  Ｚ‖０ｌｇ  Ｚ‖ｆ１‖０ｌｇ  Ｚ‖０ｌｇ  Ｚ＞，ｒ１＊），…，Ａｄ［ａｐ＊］＝（Ｎｐ＊  ＸＯＲ  ＜０ｌｇ  Ｚ‖ｆｐ＊‖０ｌｇ  Ｚ‖０ｌｇ  Ｚ‖ｆｐ‖０ｌｇ  Ｚ‖０ｌｇ  Ｚ＞，ｒｐ＊）で表される。
【０２９４】
ステップＳ２４１８において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で算出したアドレスｆ１，…，ｆｐ，ｆ１＊，…，ｆｐ＊と、Ｓ２４１３で算出したアドレスａ１，…，ａｐ，ａ１＊，…，ａｐ＊とを用いて、配列Ａｄを更新する。
配列Ａｄの更新は、Ａｄ［ｆ１＊］＝（＜ｆ２＊‖０ｌｇ  Ｚ‖ａ１＊‖ｆ１‖０ｌｇ  Ｚ‖ａ１‖ｘ１［１］＞  ＸＯＲ  Ｈ２（ｔ３，Ｒ１），Ｒ１），…，Ａｄ［ｆｐ＊］＝（＜０ｌｇ  Ｚ‖０ｌｇ  Ｚ‖ａｐ＊‖ｆｐ‖０ｌｇ  Ｚ‖ａｐ‖ｘｐ［１］＞  ＸＯＲ  Ｈ２（ｔ３，Ｒｐ），Ｒｐ）で表される。
【０２９５】
ステップＳ２４１９において、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された追加更新情報ｔａｄｄ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｘ１，…，ｘｐ，Ｒ１，…，Ｒｐ，ｃ）と、Ｓ２４０９で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２４１１で算出したアドレスｆ１＊とを用いて、配列Ｔｄを更新する。
配列Ｔｄの更新は、Ｔｄ［ｔ４］＝ｆ１＊  ＸＯＲ  ｔ５で表される。
【０２９６】
ステップＳ２４２０において、ラベル付き索引更新部３０６は、Ｓ２４１９までで更新したラベル付き索引Ｉをラベル付き索引保管部３０４に上書きする。
また、ラベル付き索引更新部３０６は、Ｓ２４０９で受信された暗号化データ集合Ｃ’を暗号化データ保管部３０３に記憶する。
【０２９７】
Ｓ２４２０により、秘匿検索システム１００のデータ追加処理は終了する。
【０２９８】
図２９、図３０および図３１は、実施の形態１におけるラベル付き索引の削除更新処理（具体例）を示すフローチャートである。
実施の形態２におけるラベル付き索引の削除更新処理（具体例）について、図２９から図３１に基づいて説明する。
【０２９９】
図２９から図３１のフローチャートは図８に示したフローチャートに対応している。
Ｓ２５０１はＳ５０１に対応し、Ｓ２５０２はＳ５０２に対応し、Ｓ２５０３からＳ２５０５はＳ５０３に対応し、Ｓ２５０６はＳ５０４に対応し、Ｓ２５０７はＳ５０５に対応し、Ｓ２５０８はＳ５０６に対応し、Ｓ２５０９からＳ２５１９はＳ５０７に対応し、Ｓ２５２０はＳ５０８とＳ５０９とに対応する処理である。Ｓ２５０１からＳ２５２０の処理にＳ５０１からＳ５０９で説明した事項を適用しても構わない。
【０３００】
ステップＳ２５０１において、ユーザは、入力装置を用いてアクセス端末２０１に削除データ集合Ｄ’’ ＝｛Ｄ１’’，…，Ｄｍ’’｝とラベル情報ｄ’’とを指定し、アクセス端末２０１の削除更新情報生成部２０９は指定された削除データ集合Ｄ’’とラベル情報ｄ’’とを入力装置から入力する。
【０３０１】
ステップＳ２５０２において、ラベル管理部２０４は、Ｓ２５０１で入力されたラベル情報ｄ’’に対応付けられたラベルｌａｂｅｌとラベル付き索引Ｉの索引名ｉｄＩと整数値ｚとを読み出す。
【０３０２】
ステップＳ２５０３において、ラベル管理部２０４は、Ｓ２５０１で入力された削除データ集合Ｄ’’ ＝｛Ｄ１’’，…，Ｄｍ’’｝に関連するキーワード集合Ｗ’’＝｛ｗ１’’，…，ｗｑ’’｝を生成する。キーワード集合Ｗ’’の生成方法は、実施の形態１のＳ２０３と同様である。
但し、Ｓ２５０３は、必ずしも実行する必要はない。
【０３０３】
ステップＳ２５０４において、削除更新情報生成部２０９は、（６×ｌｇ  Ｚ）＋ｔｓ＋ｋｒビットのｑ個の乱数Ｒ（１），…，Ｒ（ｑ）を生成する。ここで、ｑは、Ｓ２５０３で生成されたキーワード集合Ｗ’’のキーワード数である。
【０３０４】
ステップＳ２５０５において、削除更新情報生成部２０９は、秘密鍵管理部２０３から索引鍵Ｋ１、Ｋ２、Ｋ４、Ｋ５、Ｋ６、Ｋ７を読み出す。削除更新情報生成部２０９は、秘密鍵管理部２０３から読み出した索引鍵Ｋ１、Ｋ２、Ｋ４、Ｋ５、Ｋ６、Ｋ７と、Ｓ２５０２で得られたラベルｌａｂｅｌと整数値ｚと、Ｓ２５０４で生成した乱数Ｒ（ｉ）とを用いて、削除更新情報ｔｄｅｌを生成する。
削除更新情報ｔｄｅｌは、ｔｄｅｌ＝（Ｆ２（Ｋ４，ｌａｂｅｌ‖ｉｄ’’），Ｇ２（Ｋ５，ｌａｂｅｌ‖ｉｄ’’），Ｐ２（Ｋ６，ｌａｂｅｌ‖ｉｄ’’），Ｆ１（Ｋ１，ｌａｂｅｌ‖ｆｒｅｅ），Ｇ１（Ｋ２，ｌａｂｅｌ‖ｆｒｅｅ），Ｑ（Ｋ７，ｌａｂｅｌ‖ｚ＋１），…，Ｑ（Ｋ７，ｌａｂｅｌ‖ｚ＋ｑ），Ｒ（１），…，Ｒ（ｑ），ｉｄ’’）で表される。
【０３０５】
ステップＳ２５０６において、削除更新情報生成部２０９は、Ｓ２５０２で読み出した整数値ｚにＳ２５０３で生成されたキーワード集合Ｗ’’のキーワード数ｑを加算して整数値ｚを更新し、更新した整数値ｚをラベル管理部２０４に上書きする。つまり、削除更新情報生成部２０９は、ｚ＝ｚ＋ｑで表される整数値ｚをラベル管理部２０４に上書きする。
【０３０６】
ステップＳ２５０７において、端末側データ送受信部２１３はＳ２５０５で生成された削除更新情報ｔｄｅｌと、Ｓ２５０２で読み出した索引名ｉｄＩとをデータセンタ３０１に送信する。
【０３０７】
ステップＳ２５０８において、データセンタ３０１のセンタ側データ送受信部３０２は、Ｓ２５０７で送信された削除更新情報ｔｄｅｌと索引名ｉｄＩとを受信する。
ラベル付き索引更新部３０６は、受信された索引名ｉｄＩで識別されるラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）をラベル付き索引保管部３０４から読み出す。
以下、削除更新情報ｔｄｅｌをｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と記す。
【０３０８】
ステップＳ２５０９において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）とを用いて、アドレスｂ１０を算出する。
ここで、アドレスｂ１０は、Ｔｓ［ｔ１］  ＸＯＲ  ｔ２＝ｂ１０を満たす値である。
【０３０９】
ステップＳ２５１０において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５０９で算出したアドレスｂ１０とを用いて、アドレスｂ１ｉ、ｂ２ｉ、ｂ３ｉ、ｂ４ｉ、ｂ５ｉ、ｂ６ｉおよびｂ７ｉ（１≦ｉ≦ｑ）を算出する。
ここで、各アドレスは、Ｎ１  ＸＯＲ  Ｈ２（ｔ３，ｒ１）＝ｂ１１‖ｂ２１‖ｂ３１‖ｂ４１‖ｂ５１‖ｂ６１‖ｂ７１，…，Ｎｐ  ＸＯＲ  Ｈ２（ｔ３，ｒｑ）＝ｂ１ｑ‖ｂ２ｑ‖ｂ３ｑ‖ｂ４ｑ‖ｂ５ｑ‖ｂ６ｑ‖ｂ７ｑを満たす値である。ただし、Ａｄ［ｂ１ｉ−１］＝（Ｎｉ，ｒｉ）  （１≦ｉ≦ｑ）である。
【０３１０】
ステップＳ２５１１において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）とを用いて、以下のｆｚを算出する。
ここで、ｆｚは、Ｔｓ［ｔ４］  ＸＯＲ  ｔ５＝ｆｚ‖０ｌｇ  Ｚを満たす値である。
【０３１１】
ステップＳ２５１２において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ１ｉ，ｂ４ｉとを用いて、配列Ａｓを更新する。
配列Ａｓの更新は、Ａｓ［ｂ４ｑ］＝＜０Ｍ‖ｂ４ｑ−１‖ｂ１ｑ−１＞  ＸＯＲ  ｙｑ，…，Ａｓ［ｂ４２］＝＜０Ｍ‖ｂ４１‖ｂ１１＞  ＸＯＲ  ｙ２，Ａｓ［ｂ４１］＝＜０Ｍ‖ｆｚ‖ｂ１０＞  ＸＯＲ  ｙ１で表される。
【０３１２】
ステップＳ２５１３において、ラベル付き索引更新部３０６は、Ｓ２５１０で算出したアドレスｂ５ｉ（１≦ｉ≦ｑ）が０ｌｇ  Ｚであるか否かを判定する。アドレスｂ５ｉが０ｌｇ  Ｚでない場合、ラベル付き索引更新部３０６は、以下の処理を実行する。
ラベル付き索引更新部３０６は、Ｓ２５０７で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ２ｉ，ｂ５ｉとを用いて、ａ１ｉ，ａ２ｉ，ａ３ｉ，Ｒｉ，ａ１ｉ＊，ａ２ｉ＊，ａ３ｉ＊，ａ４ｉ＊，ａ５ｉ＊，ａ６ｉ＊，ａ７ｉ＊，Ｒｉ＊を算出する。
ここで、ａ１ｉ，ａ２ｉ，ａ３ｉ，Ｒｉは、Ａｓ［ｂ５ｉ］＝（ａ１ｉ‖ａ２ｉ‖ａ３ｉ，Ｒｉ）を満たす値である。
また、ａ１ｉ＊，ａ２ｉ＊，ａ３ｉ＊，ａ４ｉ＊，ａ５ｉ＊，ａ６ｉ＊，ａ７ｉ＊，Ｒｉ＊は、Ａｄ［ｂ２ｉ］＝（ａ１ｉ＊‖ａ２ｉ＊‖ａ３ｉ＊‖ａ４ｉ＊‖ａ５ｉ＊‖ａ６ｉ＊‖ａ７ｉ＊，Ｒｉ＊）を満たす値である。
【０３１３】
ステップＳ２５１４において、ラベル付き索引更新部３０６は、Ｓ２５１０で算出したアドレスｂ６ｉ（１≦ｉ≦ｑ）が０ｌｇ  Ｚであるか否かを判定する。アドレスｂ６ｉが０ｌｇ  Ｚでない場合、ラベル付き索引更新部３０６は、以下の処理を実行する。
ラベル付き索引更新部３０６は、Ｓ２５０７で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ３ｉとｂ６ｉとを用いて、ａ１ｉ’，ａ２ｉ’，ａ３ｉ’，Ｒｉ’，ａ１ｉ＊’，ａ２ｉ＊’，ａ３ｉ＊’，ａ４ｉ＊’，ａ５ｉ＊’，ａ６ｉ＊’，ａ７ｉ＊’，Ｒｉ＊’を算出する。
ここで、ａ１ｉ’，ａ２ｉ’，ａ３ｉ’，Ｒｉ’は、Ａｓ［ｂ６ｉ］＝（ａ１ｉ’‖ａ２ｉ’‖ａ３ｉ’，Ｒｉ’）を満たす値である。
また、ａ１ｉ＊’，ａ２ｉ＊’，ａ３ｉ＊’，ａ４ｉ＊’，ａ５ｉ＊’，ａ６ｉ＊’，ａ７ｉ＊’，Ｒｉ＊’は、Ａｄ［ｂ３ｉ］＝（ａ１ｉ＊’‖ａ２ｉ＊’‖ａ３ｉ＊’‖ａ４ｉ＊’‖ａ５ｉ＊’‖ａ６ｉ＊’‖ａ７ｉ＊’，Ｒｉ＊’）を満たす値である。
【０３１４】
ステップＳ２５１５において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ１ｉ，ｂ２ｉ，ｂ３ｉ，ｂ４ｉ，ｂ５ｉ，ｂ６ｉ，ｂ７ｉと、Ｓ２５１３およびＳ２５１４で算出した各値とを用いて、配列Ａｓの配列要素［ｂ５ｉ］［ｂ６ｉ］と配列Ａｄの配列要素［ｂ２ｉ］［ｂ３ｉ］とを更新する。
但し、ｂ５ｉ≠０ｌｇ  Ｚかつｂ６ｉ≠０ｌｇ  Ｚを満たすｉに限る。
配列要素Ａｓ［ｂ５ｉ］の更新は、Ａｓ［ｂ５ｉ］＝（ａ１ｉ‖ａ２ｉ‖ａ３ｉ  ＸＯＲ  ｂ４ｉ  ＸＯＲ  ｂ６ｉ，Ｒｉ）で表される。
配列要素Ａｓ［ｂ６ｉ］の更新は、Ａｓ［ｂ６ｉ］＝（ａ１ｉ’‖ａ２ｉ’  ＸＯＲ  ｂ４ｉ  ＸＯＲ  ｂ５ｉ‖ａ３ｉ’，Ｒｉ’）で表される。
配列要素Ａｄ［ｂ２ｉ］の更新は、Ａｄ［ｂ２ｉ］＝（ａ１ｉ＊‖ａ２ｉ＊‖ａ３ｉ＊  ＸＯＲ  ｂ１ｉ−１  ＸＯＲ  ｂ３ｉ‖ａ４ｉ＊‖ａ５ｉ＊‖ａ６ｉ＊  ＸＯＲ  ｂ４ｉ  ＸＯＲ  ｂ６ｉ‖ａ７ｉ＊，Ｒｉ＊）で表される。
配列要素Ａｄ［ｂ３ｉ］の更新は、Ａｄ［ｂ３ｉ］＝（ａ１ｉ＊’‖ａ２ｉ＊’  ＸＯＲ  ｂ１ｉ−１  ＸＯＲ  ｂ２ｉ‖ａ３ｉ＊’‖ａ４ｉ＊’‖ａ５ｉ＊’  ＸＯＲ  ｂ４ｉ  ＸＯＲ  ｂ５ｉ‖ａ６ｉ＊’‖ａ７ｉ＊’，Ｒｉ＊’）で表される。
【０３１５】
ステップＳ２５１６において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ３ｉ，ｂ５ｉ，ｂ６ｉと、Ｓ２５１３およびＳ２５１４で算出した各値とを用いて、配列Ａｓの配列要素［ｂ６ｉ］と配列Ａｄの配列要素［ｂ３ｉ］とを更新する。
但し、ｂ５ｉ＝０ｌｇ  Ｚかつｂ６ｉ≠０ｌｇ  Ｚを満たすｉに限る。
配列要素Ａｓ［ｂ６ｉ］の更新は、Ａｓ［ｂ６ｉ］  ＝（ａ１ｉ’‖ａ２ｉ’  ＸＯＲ  ｂ４ｉ‖ａ３ｉ’，Ｒｉ’）で表される。
配列要素Ａｄ［ｂ３ｉ］の更新は、Ａｄ［ｂ３ｉ］＝（ａ１ｉ＊’‖ａ２ｉ＊’  ＸＯＲ  ｂ１ｉ−１‖ａ３ｉ＊’‖ａ４ｉ＊’‖ａ５ｉ＊’  ＸＯＲ  ｂ４ｉ‖ａ６ｉ＊’‖ａ７ｉ＊’，Ｒｉ＊’）で表される。
【０３１６】
ステップＳ２５１７において、ラベル付き索引更新部３０６は、Ｓ２５０８で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５１０で算出したアドレスｂ２ｉ，ｂ５ｉ，ｂ６ｉと、Ｓ２５１３およびＳ２５１４で算出した各値とを用いて、配列Ａｓの配列要素［ｂ６ｉ］と配列Ａｄの配列要素［ｂ３ｉ］とを更新する。
但し、ｂ５ｉ≠０ｌｇ  Ｚかつｂ６ｉ＝０ｌｇ  Ｚを満たすｉに限る。
配列要素Ａｓ［ｂ５ｉ］の更新は、Ａｓ［ｂ５ｉ］＝（ａ１ｉ‖ａ２ｉ‖ａ３ｉ  ＸＯＲ  ｂ４ｉ，Ｒｉ）で表される。
配列要素Ａｄ［ｂ２ｉ］の更新は、Ａｄ［ｂ２ｉ］＝（ａ１ｉ＊‖ａ２ｉ＊‖ａ３ｉ＊  ＸＯＲ  ｂ１ｉ−１‖ａ４ｉ＊‖ａ５ｉ＊‖ａ６ｉ＊  ＸＯＲ  ｂ４ｉ‖ａ７ｉ＊，Ｒｉ＊）で表される。
【０３１７】
ステップＳ２５１８において、ラベル付き索引更新部３０６は、Ｓ２５０７で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）と、Ｓ２５０９およびＳ２５１０で算出したアドレスｂ１０，…，ｂ１ｐ−１とを用いて、配列Ａｄを更新する。
配列Ａｄの更新は、Ａｄ［ｂ１０］＝Ｒ（１）’，…，Ａｄ［ｂ１ｐ−１］＝Ｒ（ｑ）’で表される。
【０３１８】
ステップＳ２５１９において、ラベル付き索引更新部３０６は、Ｓ２５０７で受信された削除更新情報ｔｄｅｌ＝（ｔ１，ｔ２，ｔ３，ｔ４，ｔ５，ｙ１，…，ｙｑ，Ｒ（１）’，…，Ｒ（ｑ），ＩＤ）と、Ｓ２５０８で読み出したラベル付き索引Ｉ＝（Ａｓ，Ａｄ，Ｔｓ，Ｔｄ）とを用いて、配列Ｔｄの配列要素Ｔｄ［ｔ１］に設定されている値を削除する。また、ラベル付き索引更新部３０６は配列要素Ｔｄ［ｔ１］の記憶領域を開放する。
【０３１９】
ステップＳ２５２０において、ラベル付き索引更新部３０６は、Ｓ２５１９までで更新したラベル付き索引Ｉをラベル付き索引保管部３０４に上書きする。
また、ラベル付き索引更新部３０６は、Ｓ２５０７で受信された削除更新情報ｔｄｅｌに含まれるデータ名ＩＤで識別される暗号化データＣを暗号化データ保管部３０３から削除する。
【０３２０】
Ｓ２５２０により、ラベル付き索引の削除更新処理は終了する。
【０３２１】
秘匿検索システム１００のデータ削除処理および索引削除処理は、実施の形態１（図１７参照）と同様である。
【０３２２】
図３２は、実施の形態２におけるラベル管理部２０４の管理テーブルを示す図である。
例えば、ラベル管理部２０４は、図３２に示すような管理テーブルで各種情報を管理する。
図３２に示す管理テーブルは、ラベル情報およびラベルに対応付けて、索引名、パラメータ、キーワードおよび検索結果情報数を示している。但し、キーワードはデータに関連付けるキーワードｗではなく、データに関連付けるキーワードｗ以外のキーワードｆｒｅｅである。
【０３２３】
実施の形態２における秘匿検索システム１００は、実施の形態１と同様の効果を奏する。
また、秘匿検索システム１００は、以下のような効果を奏する。
データ名のビット長Ｍ、ラベル情報のビット長ｘ、キーワードのビット長ｙに加えて、一部の乱数のビット長ｋｒ、配列ＡｓとＡｄの格納可能数Ｚ、配列ＴｓとＴｄのアドレス空間のビット長ｔｓとｔｄ、関数Ｈ１とＨ２の鍵のビット長ｋＨを、秘密鍵生成部２０２または秘密鍵管理部２０３が自動的に設定してもよい。または、ラベル管理部２０４がラベル付き索引毎に異なるビット長を設定してもよい。このようにすることで、ラベル付き索引の生成を柔軟に行うことができる。
配列ＡｓとＡｄの格納可能数Ｚは、データの追加回数に関するパラメータである。このため、Ｚの値は、比較的大きな値であることが好ましい。ただし、Ｚの値を指数的に大きなサイズにすることはできず、Ｚが大きすぎるとデータの追加・削除・検索の効率が落ちる可能性がある。
実施の形態１ではラベル付き検索クエリの大きさが登録データの数に比例して大きくなるが、実施の形態２ではラベル付き検索クエリの大きさが登録データの数が増えても一定である。
【０３２４】
データを追加しても秘密鍵が増えず、かつキーワード情報が漏れない秘匿検索システムの具体的なアルゴリズムを実施の形態１および実施の形態２に開示した。
但し、実施の形態１および実施の形態２は他のアルゴリズムにも適用することが可能である。例えば、非特許文献３、非特許文献４、非特許文献７などに開示されているアルゴリズムではキーワードを入力とする関数が使用される。この関数の入力をキーワードと実施の形態１、２で説明したラベルとを連結させた情報に変更することにより、データを追加しても秘密鍵が増えず、かつキーワード情報が漏れない秘匿検索システムを構成することができる。ただし、入力を変更した関数の定義域はラベルのビット長だけ拡大する必要があることに注意する。
【符号の説明】
【０３２５】
１００  秘匿検索システム、１０１  ネットワーク、１０２  社内ＬＡＮ、２０１  アクセス端末、２０２  秘密鍵生成部、２０３  秘密鍵管理部、２０４  ラベル管理部、２０５  キーワード設定部、２０６  データ暗号化部、２０７  ラベル付き索引生成部、２０８  追加更新情報生成部、２０９  削除更新情報生成部、２１０  削除要求生成部、２１１  ラベル付き検索クエリ生成部、２１２  データ復号部、２１３  端末側データ送受信部、３０１  データセンタ、３０２  センタ側データ送受信部、３０３  暗号化データ保管部、３０４  ラベル付き索引保管部、３０５  検索処理部、３０６  ラベル付き索引更新部、９０１  ＣＰＵ、９０２  バス、９０３  ＲＯＭ、９０４  ＲＡＭ、９０５  通信ボード、９１１  ディスプレイ、９１２  キーボード、９１３  マウス、９１４  ドライブ、９２０  磁気ディスク装置、９２１  ＯＳ、９２２  プログラム群、９２３  ファイル群。
【図１】
0005800721.tif 000003
【図２】
0005800721.tif 000004
【図３】
0005800721.tif 000005
【図４】
0005800721.tif 000006
【図５】
0005800721.tif 000007
【図６】
0005800721.tif 000008
【図７】
0005800721.tif 000009
【図８】
0005800721.tif 000010
【図９】
0005800721.tif 000011
【図１０】
0005800721.tif 000012
【図１１】
0005800721.tif 000013
【図１２】
0005800721.tif 000014
【図１３】
0005800721.tif 000015
【図１４】
0005800721.tif 000016
【図１５】
0005800721.tif 000017
【図１６】
0005800721.tif 000018
【図１７】
0005800721.tif 000019
【図１８】
0005800721.tif 000020
【図１９】
0005800721.tif 000021
【図２０】
0005800721.tif 000022
【図２１】
0005800721.tif 000023
【図２２】
0005800721.tif 000024
【図２３】
0005800721.tif 000025
【図２４】
0005800721.tif 000026
【図２５】
0005800721.tif 000027
【図２６】
0005800721.tif 000028
【図２７】
0005800721.tif 000029
【図２８】
0005800721.tif 000030
【図２９】
0005800721.tif 000031
【図３０】
0005800721.tif 000032
【図３１】
0005800721.tif 000033
【図３２】
0005800721.tif 000034