(57)【要約】  暗号化部は、保管データＤが分割された３個の要素データｗ１，ｗ２，ｗ３を用いて、第１番目から第３番目までの要素データを順に並べた第１の集合Ａ１、第２番目から第３番目までの要素データを順に並べた第２の集合Ａ２、第３番目の要素データからなる第３の集合Ａ３までの、３個の集合を生成する。暗号化部は、各集合に含まれるそれぞれの要素データを、乱数Ｒ（１）を用いてＣＢＣモードによって暗号化する。
2017126000.tif 000002
【特許請求の範囲】
【請求項１】
検索されるデータを複数の要素データに分割するデータ分割部と、
複数の要素データの各要素データを、秘匿検索の可能な暗号モードによって、乱数を用いて暗号化する暗号化部と
を備えた暗号化装置。
【請求項２】
前記データは、
先頭から順に分割可能なデータ構造であり、
前記データ分割部は、
前記データを先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割し、
前記暗号化部は、
分割されたそれぞれの要素データを、前記乱数を用いて暗号化する請求項１に記載の暗号化装置。
【請求項３】
前記暗号モードは、
ＣＢＣモードと、ＣＴＲモードとのいずれかである請求項２に記載の暗号化装置。
【請求項４】
前記暗号化部は、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、
第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、前記乱数を用いて前記ＣＢＣモードによって暗号化する請求項３に記載の暗号化装置。
【請求項５】
前記暗号化部は、
前記第１の集合から前記第Ｎの集合の集合ごとに、
前記ＣＢＣモードの第１段において、前記乱数と、前記集合の最初の要素データとの排他的論理和を演算し、
前記ＣＢＣモードの第２段以降おいて、前段の出力値と、前段で排他的論理和の演算に使用された要素データの次の順番の要素データとの排他的論理和を演算する請求項４に記載の暗号化装置。
【請求項６】
複数の乱数が保管された乱数保管部と、
検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、前記乱数保管部に保管された前記乱数ごとに前記乱数を用いて暗号化を行い、暗号化された複数の前記検索データを含む検索暗号化データを生成する暗号化部と、
前記乱数保管部に保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する送信部と
を備えた検索装置。
【請求項７】
前記検索装置は、さらに、
乱数生成部を備え、
前記暗号化部は、
前記乱数ごとに前記乱数を用いて暗号化された前記検索データのそれぞれを、前記乱数生成部によって生成された生成乱数を用いて暗号化することにより、前記検索暗号化データを生成する請求項６に記載の検索装置。
【請求項８】
前記検索装置は、さらに、
前記検索データを取得する検索データ取得部を備え、
前記乱数生成部は、
前記検索データ取得部によって取得された複数の前記検索データの前記検索データごとに、生成乱数を生成し、
前記暗号化部は、
前記乱数生成部によって前記検索データごとに生成された生成乱数を、対応する前記検索データの暗号化に用いる請求項７に記載の検索装置。
【請求項９】
前記暗号化部は、
前記検索データを複数の要素データに分割し、前記検索データの前記暗号化として、前記乱数ごとに前記乱数で各要素データを暗号化する請求項７または請求項８に記載の検索装置。
【請求項１０】
前記送信部は、
前記検索暗号化データと、前記検索暗号化データの生成に使用された前記生成乱数とを対として送信する請求項７から請求項９のいずれか一項に記載の検索装置。
【請求項１１】
コンピュータに、
検索されるデータを複数の要素データに分割する処理、
複数の要素データの各要素データを、秘匿検索の可能な暗号モードによって、乱数を用いて暗号化する処理
を実行させるための暗号化プログラム。
【請求項１２】
コンピュータに、
複数の乱数を保管する処理、
検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、保管された前記乱数ごとに前記乱数を用いて暗号化を行い、暗号化された複数の前記検索データを含む検索暗号化データを生成する処理、
保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する処理、
を実行させるための検索プログラム。
【請求項１３】
データ分割部、暗号化部を備えた暗号化装置が行う暗号化方法であって、
データ分割部が、データを複数の要素データに分割し、
暗号化部が、複数の要素データの各要素データを、秘匿検索の可能な暗号モードによって、乱数を用いて暗号化する暗号化方法。
【請求項１４】
乱数保管部、暗号化部、送信部を備えた検索装置が行う検索方法であって、
乱数保管部が、複数の乱数を保管し、
暗号化部が、検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、前記乱数保管部に保管された前記乱数ごとに前記乱数を用いて暗号化を行い、暗号化された複数の前記検索データを含む検索暗号化データを生成し、
送信部が、保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘匿検索システムで使用される、暗号化装置、検索装置、暗号化プログラム、検索プログラム、暗号化方法及び検索方法に関する。
【背景技術】
【０００２】
秘匿検索とは、検索対象データと検索内容を暗号化したまま検索できる技術である。【０００３】
近年、クラウドサービス等の普及によりインターネット上でデータ管理が可能となった。しかし、インターネット上でのデータ管理には、データ管理の委託先であるクラウドなどのサーバがコンピュータウィルス等のマルウェアに感染することやサーバの管理者が不正を働くことによって、預けたデータが外部に漏洩する危険性がある。もしサーバに預けたデータが個人情報や企業機密データであった場合、この漏洩は非常に問題である。【０００４】
このようなセキュリティの脅威を回避する方法として暗号化技術があるが、単純にデータを暗号化してサーバに保管すると、データの検索ができない問題が発生する。この問題を回避するために、検索を行うときにサーバ上に保管された暗号化データを一旦復号してから検索を行う手法が今までに考えられた。しかし、データがサーバ内で一定期間平文に戻ってしまうため、対策として十分とはいえない。
そこで、データを暗号化したまま検索可能な暗号技術である「秘匿検索技術」が考案された。秘匿検索技術の具体的な手法は近年多く開示されている。【０００５】
秘匿検索技術では、単純な検索である「完全一致検索」ができる方式（例えば、非特許文献１参照）が主に検討されていた。近年はより柔軟な検索、例えば「部分一致検索」ができる方式（例えば、特許文献１、非特許文献２参照）や「類似検索」ができる方式（例えば、非特許文献３、非特許文献２参照）なども検討されている。これ以降、部分一致検索の可能な方式を「秘匿部分一致の検索技術」、類似検索可能な秘匿検索技術を「秘匿類似の検索技術」と呼ぶこととする。【０００６】
なお、秘匿検索技術は大まかに分けて、公開鍵暗号をベースとした方式や、共通鍵暗号をベースとした方式の２種類がある。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１４−１２６６２１号公報
【非特許文献】
【０００８】
【非特許文献１】Ｒ．Ｃｕｒｔｍｏｌａ，Ｊ．Ｇａｒａｙ，Ｓ．Ｋａｍａｒａ，ａｎｄ  Ｒ．Ｏｓｔｒｏｖｓｋｙ．“Ｓｅａｒｃｈａｂｌｅ  Ｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ：Ｉｍｐｒｏｖｅｄ  Ｄｅｆｉｎｉｔｉｏｎｓ  ａｎｄ  Ｅｆｆｉｃｉｅｎｔ  Ｃｏｎｓｔｒｕｃｔｉｏｎｓ”．ＡＣＭ  ＣＣＳ  ２００６．
【非特許文献２】Ｍ．Ｃｈａｓｅ  ａｎｄ  Ｅ．Ｓｈｅｎ．“Ｓｕｂｓｔｒｉｎｇ−Ｓｅａｒｃｈａｂｌｅ  Ｓｙｍｍｅｔｒｉｃ  Ｅｎｃｒｙｐｔｉｏｎ”，ＰＥＴＳ  ２０１５．
【非特許文献３】Ｊ．Ｌｉ，Ｑ．Ｗａｎｇ，Ｃ．Ｗａｎｇ，Ｎ．Ｃａｏ，Ｋ．Ｒｅｎ，ａｎｄ  Ｗ．Ｌｏｕ．“Ｆｕｚｚｙ  Ｋｅｙｗｏｒｄ  Ｓｅａｒｃｈ  ｏｖｅｒ  Ｅｎｃｒｙｐｔｅｄ  Ｄａｔａ  ｉｎ  Ｃｌｏｕｄ  Ｃｏｍｐｕｔｉｎｇ”，Ｍｉｎｉ−Ｃｏｎｆｅｒｅｎｃｅ  ａｔ  ＩＥＥＥ  Ｉｎｆｏｃｏｍ  ２０１０．
【非特許文献４】Ｃ．Ｗａｎｇ，Ｋ．Ｒｅｎ，Ｓ．Ｙｕ，ａｎｄ  Ｋ．Ｍ．Ｒ．Ｕｒｓ．“Ａｃｈｉｅｖｉｎｇ  Ｕｓａｂｌｅ  ａｎｄ  Ｐｒｉｖａｃｙ−ａｓｓｕｒｅｄ  Ｓｉｍｉｌａｒｉｔｙ  Ｓｅａｒｃｈ  ｏｖｅｒ  Ｏｕｔｓｏｕｒｃｅｄ  Ｃｌｏｕｄ  Ｄａｔａ”，ＩＥＥＥ  Ｉｎｆｏｃｏｍ  ２０１２．
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ＡＥＳやＨＭＡＣ、またＳＨＡ−２５６のような共通鍵暗号技術をベースとした高速な既存の秘匿部分一致検索技術には次のような課題がある。【００１０】
特許文献１では、データを数文字単位に分割し、それぞれを暗号化することによって、暗号化したまま部分一致検索を達成している技術が開示されている。例えば、１文字や２文字などの単位でデータを区切って暗号化している。
しかしながら、データを少ない文字数で分割すると、全く同じような分割データが多く現れる可能性がある。本技術では、同じデータからいつも同じ暗号文が生成される確定的暗号化方式を利用するため、同じ分割データを暗号化しても、全く同じ暗号文が生成される。よって、頻度分析攻撃を受けやすいといった課題がある。
ここで、頻度分析攻撃とは、同じ値を持つ暗号文の頻度と、頻度に関する公な情報（日本人の名字の分布など）とを照合することで、暗号化に用いる鍵を使わなくても、暗号文から元のデータを推測する攻撃手法である。【００１１】
非特許文献２では、上記のような頻度分析攻撃を受けず、またある木構造を利用して保管する暗号化データ（以降、保管暗号化タグと呼ぶ）のサイズを小さくできるような秘匿部分一致検索技術が開示されている。しかしながら、本技術では、検索に用いる暗号化データ（以降、検索暗号化タグと呼ぶ）のサイズが大きくなってしまうことや、検索時にユーザとサーバとの対話回数が多いため、通信量に課題がある。加えて、検索する際に生成されるデータは、同じ文字に関しては同じ値となるため、保管暗号化タグを持つもの（例えばサーバなど）は、やはり頻度分析が可能という課題がある。【００１２】
非特許文献３及び非特許文献４では、部分一致検索も含む秘匿類似検索技術が開示されている。これらの技術は、部分一致検索よりも柔軟な検索ができるが、保管暗号化タグのサイズ及び検索暗号化タグのサイズがともに大きいといった課題がある。
よって、本発明は、保管暗号化タグ、検索暗号化タグに対して、頻度分析などの攻撃に耐性を持つような高い安全性を確保し、データサイズが小さく、かつ通信量が小さい秘匿部分一致検索技術の提供を目的とする。
【課題を解決するための手段】
【００１３】
この発明の暗号化装置は、検索されるデータを複数の要素データに分割するデータ分割部と、複数の要素データの各要素データを、秘匿検索の可能な暗号モードによって、乱数を用いて暗号化する暗号化部とを備えたことを特徴とする。
【発明の効果】
【００１４】
本発明によれば、検索されるデータを分割し、乱数を用いて秘匿検索の可能な暗号モードで暗号化する。乱数を用いることによって、頻度分析攻撃に対して、検索されるデータである暗号文どうしの比較ができなくなる。このため、安全性を高めることができる。また、データを分割するので暗号化したまま部分一致検索を達成できる。
【図面の簡単な説明】
【００１５】
【図１】実施の形態１の図で、秘匿検索システムのブロック図。
【図２】実施の形態１の図で、鍵生成装置のブロック図。
【図３】実施の形態１の図で、登録装置のブロック図。
【図４】実施の形態１の図で、検索装置のブロック図。
【図５】実施の形態１の図で、管理装置のブロック図。
【図６】実施の形態１の図で、秘匿検索システムの鍵生成、保管処理を示すフローチャート。
【図７】実施の形態１の図で、秘匿検索システムのデータ登録処理を示すフローチャート。
【図８】実施の形態１の図で、秘匿検索システムのデータ検索処理を示すフローチャート。
【図９】実施の形態１の図で、登録装置による暗号化処理を説明する図。
【図１０】実施の形態１の図で、検索装置による暗号化処理を説明する図。
【図１１】実施の形態１の図で、鍵生成装置、登録装置等のハードウェア資源を示す図。
【図１２】実施の形態１の図で、鍵生成装置、登録装置等のハードウェア資源を示す別の図。
【図１３】実施の形態２の図で、登録装置による暗号化処理を説明する図。
【図１４】実施の形態２の図で、検索装置による暗号化処理を説明する図。
【発明を実施するための形態】
【００１６】
以下、本発明の実施の形態について、図を用いて説明する。なお、各図中、同一又は相当する部分には、同一符号を付している。実施の形態の説明において、同一又は相当する部分については、その説明を適宜省略又は簡略化する。
【００１７】
実施の形態１．
本実施の形態では、高安全かつ効率的な秘匿部分一致検索技術を開示する。
以下、本実施の形態の概要について説明する。
図１は、本実施の形態に係る検索システム１００の構成を示すブロック図である。図１に示すように、秘匿検索システム１００は、鍵生成装置２００と、複数の登録装置３００と、複数の検索装置４００と、管理装置５００とを備える。登録装置３００は、暗号化装置である。秘匿検索システム１００は、複数の鍵生成装置２００を備えていてもよい。秘匿検索システム１００は、１つの登録装置３００のみを備えていてもよい。秘匿検索システム１００は、１つの検索装置４００のみを備えていてもよい。秘匿検索システム１００は、複数の管理装置５００を備えていてもよい。
【００１８】
秘匿検索システム１００は、鍵生成装置２００、複数の登録装置３００、複数の検索装置４００、管理装置５００と、それぞれインターネット１０１を経由して接続されず、同じ企業内に敷設されたＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）内に設置されていてもよい。
【００１９】
インターネット１０１は、鍵生成装置２００と、複数の登録装置３００と、複数の検索装置４００と、管理装置５００とを接続する通信路である。インターネット１０１は、ネットワークの例である。インターネット１０１の代わりに、他の種類のネットワークが用いられてもよい。
【００２０】
鍵生成装置２００は、暗号化に利用する鍵を作成し、インターネット１０１を介して、複数の登録装置３００と、複数の検索装置４００とへ鍵を送信する。なお、この鍵は、インターネット１０１を介さず、郵送などで直接的に、複数の登録装置３００と、複数の検索装置４００とへ送信してもよい。
【００２１】
登録装置３００は、例えば、パーソナルコンピュータである。登録装置３００は、保管暗号化データを管理装置５００に登録する登録端末として動作するコンピュータである。ここで保管暗号化データとは、
後述するＣ（Ｄ（ｊ））＝｛Ｃ１→，Ｃ２→，．．．，ＣＬ→｝
におけるＣ１→，Ｃ２→等である。
登録装置３００は、暗号化装置及び登録装置として機能する。即ち、登録装置３００は、保管暗号化データを生成し、保管暗号化データの保管を管理装置５００に要求する。
登録装置３００は、削除要求装置として機能する。即ち、登録装置３００は、管理装置５００に対して、保管されている保管暗号化データの削除を要求する。
【００２２】
検索装置４００は、例えば、パーソナルコンピュータである。検索装置４００は、検索暗号化データを管理装置５００に送信し、その後管理装置５００から暗号化検索結果を受信し、暗号化検索結果を出力するコンピュータである。
【００２３】
検索装置４００は、検索要求装置として機能する。即ち、検索装置４００は、検索暗号化データを管理装置５００に送信して保管暗号化データと検索暗号化データの照合を要求する。
検索装置４００は、出力装置として機能する。即ち、検索装置４００は、管理装置５００から返信される検索結果を出力する。
【００２４】
管理装置５００は、登録装置３００によって作成された保管暗号化データを保管する大容量の記録媒体を持つ装置である。管理装置５００は、保管装置として機能する。即ち、管理装置５００は、登録装置３００から保管暗号化データの保管の要求があれば、保管暗号化データを保管する。管理装置５００は、検索装置として機能する。即ち、管理装置５００は、検索装置４００からの検索の要求があれば、保管暗号化データと検索暗号化データを照合し、検索結果を検索装置４００に送信する。管理装置５００は、削除装置として機能する。即ち、管理装置５００は、登録装置３００から保管暗号化データの削除の要求があれば、保管している保管暗号化データを削除する。なお、同じパーソナルコンピュータ内に、鍵生成装置２００、登録装置３００、検索装置４００のいずれかが同時に含まれていてもよい。なお、保管暗号化データ及び検索暗号化データは、いずれも暗号化されている。鍵を持たない登録装置３００と検索装置４００以外は、保管暗号化データや検索暗号化データから有益な情報を得ることは困難である。
【００２５】
＜＊＊＊構成の説明＊＊＊＞
図２〜図５を参照して、鍵生成装置２００、登録装置３００、検索装置４００、管理装置５００の構成について順番に説明する。図２〜図５は、コンピュータである、鍵生成装置２００、登録装置３００、検索装置４００、管理装置５００の構成を示すブロック図である。
また図１１は、鍵生成装置２００〜管理装置５００のハードウェア構成を示す図である。図１２は、鍵生成装置２００〜管理装置５００のハードウェア構成を示す別の図である。
【００２６】
本実施の形態において、鍵生成装置２００、登録装置３００、検索装置４００、管理装置５００は、コンピュータである。鍵生成装置２００等は、プロセッサ９１、記憶装置９２、入力インタフェース９３、出力インタフェース９４といったハードウェアを備える。以下、入力インタフェース９３、出力インタフェース９４は、入力Ｉ／Ｆ９３、出力Ｉ／Ｆ９４と記す。図２〜図５では、各機能部とハードウェアとの関係を示している。図２〜図５において、プロセッサ９１として示す「〜部」は、ソフトウェアで実現される。つまり、プロセッサ９１として示す「〜部」は、プロセッサ９１がソフトウェアを実行することで実現される。
また、図３〜図５における「〜保管部」は、記憶装置９２で実現される。
【００２７】
プロセッサ９１は、信号線を介して他のハードウェアと接続され、これら他のハードウェアを制御する。プロセッサ９１は、プロセッシングを行うＩＣ（Ｉｎｔｅｇｒａｔｅｄ・Ｃｉｒｃｕｉｔ）である。プロセッサ９１は、具体的には、ＣＰＵ（Ｃｅｎｔｒａｌ・Ｐｒｏｃｅｓｓｉｎｇ・Ｕｎｉｔ）である。
【００２８】
記憶装置９２は、補助記憶装置９２ａ及びメモリ９２ｂを含む。補助記憶装置９２ａは、具体的には、ＲＯＭ（Ｒｅａｄ・Ｏｎｌｙ・Ｍｅｍｏｒｙ）、フラッシュメモリ、又は、ＨＤＤ（Ｈａｒｄ・Ｄｉｓｋ・Ｄｒｉｖｅ）である。メモリ９２ｂは、具体的には、ＲＡＭ（Ｒａｎｄｏｍ・Ａｃｃｅｓｓ・Ｍｅｍｏｒｙ）である。
【００２９】
入力Ｉ／Ｆ９３は、信号が入力されるポートである。また、入力Ｉ／Ｆ９３は、マウス、キーボード、タッチパネルといった入力装置と接続されるポートであってもよい。入力Ｉ／Ｆ９３は、具体的には、ＵＳＢ（Ｕｎｉｖｅｒｓａｌ・Ｓｅｒｉａｌ・Ｂｕｓ）端子である。なお、入力Ｉ／Ｆ９３は、ＬＡＮ（Ｌｏｃａｌ・Ａｒｅａ・Ｎｅｔｗｏｒｋ）と接続されるポートであってもよい。
【００３０】
出力Ｉ／Ｆ９４は、信号を出力するポートである。出力Ｉ／Ｆ９４は、ＵＳＢ端子でもよい。
【００３１】
補助記憶装置９２ａには、プロセッサ９１として示す「〜部」の機能を実現するプログラムが記憶されている。このプログラムは、メモリ９２ｂにロードされ、プロセッサ９１に読み込まれ、プロセッサ９１によって実行される。補助記憶装置９２ａには、ＯＳ（Ｏｐｅｒａｔｉｎｇ・Ｓｙｓｔｅｍ）も記憶されている。ＯＳの少なくとも一部がメモリ９２ｂにロードされ、プロセッサ９１はＯＳを実行しながら、プロセッサ９１として示す「部」の機能を実現するプログラムを実行する。
【００３２】
鍵生成装置２００、登録装置３００、検索装置４００、管理装置５００は、１つのプロセッサ９１のみを備えていてもよいし、複数のプロセッサ９１を備えていてもよい。複数のプロセッサ９１が「部」の機能を実現するプログラムを連携して実行してもよい。
【００３３】
プロセッサ９１として示す「部」の機能による処理の結果を示す情報、データ、信号値、及び、変数値は、補助記憶装置９２ａ、メモリ９２ｂ、又は、プロセッサ９１内のレジスタ又はキャッシュメモリに記憶される。
【００３４】
プロセッサ９１として示す「部」の機能を実現するプログラムは、磁気ディスク、フレキシブルディスク、光ディスク、コンパクトディスク、ＤＶＤ（Ｄｉｇｉｔａｌ・Ｖｅｒｓａｔｉｌｅ・Ｄｉｓｃ）といった可搬記録媒体に記憶されてもよい。
【００３５】
図１２を説明する。本実施の形態ではプロセッサ９１として示す「部」の機能がソフトウェアで実現されるが、変形例として、プロセッサ９１として示す「部」の機能がハードウェアで実現されてもよい。つまり、処理回路９９によって、前述したプロセッサ９１として示す「部」の機能及び「〜保管部」の機能を実現する。処理回路９９が信号線９９ａに接続している。処理回路９９は、プロセッサ９１として示す「部」の機能及び「〜保管部」の機能を実現する専用の電子回路である。処理回路９９は、具体的には、単一回路、複合回路、プログラム化したプロセッサ、並列プログラム化したプロセッサ、ロジックＩＣ、ＧＡ（Ｇａｔｅ・Ａｒｒａｙ）、ＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ・Ｓｐｅｃｉｆｉｃ・Ｉｎｔｅｇｒａｔｅｄ・Ｃｉｒｃｕｉｔ）、又は、ＦＰＧＡ（Ｆｉｅｌｄ−Ｐｒｏｇｒａｍｍａｂｌｅ・Ｇａｔｅ・Ａｒｒａｙ）である。
【００３６】
プロセッサ９１として示す「部」の機能は、１つの処理回路９９で実現されてもよいし、複数の処理回路９９により分散して実現されてもよい。
【００３７】
別の変形例として、図２〜図５に示す装置がソフトウェアとハードウェアとの組合せで実現されてもよい。即ち、図２〜図５に示す装置の一部の機能が専用のハードウェアで実現され、残りの機能がソフトウェアで実現されてもよい。
【００３８】
プロセッサ９１、記憶装置９２、及び、処理回路９９を、総称して「プロセッシングサーキットリ」という。つまり、図２〜図５における、プロセッサ９１として示す「部」の機能及び「〜保管部」は、プロセッシングサーキットリにより実現される。
【００３９】
プロセッサ９１として示す「部」を「工程」又は「手順」又は「処理」に読み替えてもよい。また、プロセッサ９１として示す「部」の機能をファームウェアで実現してもよい。
【００４０】
図２は、鍵生成装置２００の構成を示すブロック図である。
図２に示すように、鍵生成装置２００は、入力部２０１、鍵生成部２０２、送信部２０３を備える。図示していないが、鍵生成装置２００は、鍵生成装置２００の各部で使用されるデータを記憶する記録媒体を備える。
【００４１】
入力部２０１は、本システムで用いる鍵のビット長や、検索時に用いる最大文字数Ｌなどを入力する。鍵生成部２０２は、データを暗号化、復号するための鍵Ｋと、検索時に用いる鍵Ｋ’とを、入力された鍵のビット長Ｌｂｉｔを用いて生成する。鍵Ｋや鍵Ｋ’は登録装置３００と検索装置４００、及び管理装置５００とに保管される秘密情報であるため、厳重に生成される。なお、ここでは共通鍵暗号技術を用いて説明しているが、公開鍵暗号技術を用いてもよい。以下では鍵Ｋと鍵Ｋ’を用いた説明を行うが、必要でない場合は鍵Ｋ’はなくてもよい。つまり、以下の説明ではＥ（Ｋ’，＊）が登場し、Ｅ（Ｋ’，＊）の意味は、鍵Ｋ’で、データ「＊」を暗号化することを意味する。Ｅ（Ｋ’，＊）以外の暗号化を採用する場合は鍵Ｋ’は不要である。鍵Ｋ’が必要でない場合とは、この意味である。
また、以下において、鍵Ｋあるいは鍵Ｋ’を用いる説明がある場合、鍵Ｋあるいは鍵Ｋ’は鍵生成装置２００から送信されている。
【００４２】
送信部２０３は、鍵生成部２０２で生成された鍵Ｋを、登録装置３００と、検索装置４００とへ送信し、鍵Ｋ’を検索装置４００と、管理装置５００へと送信する。送信部２０３は、入力部２０１に入力された最大文字数Ｌを、パラメータＬとして、登録装置３００、管理装置５００へ送信する。
【００４３】
図３は、登録装置３００の構成を示すブロック図である。図３に示すように、登録装置３００は、受信部３０１、鍵保管部３０２、パラメータ保管部３０３、入力部３０４、データ分割部３０５、乱数生成部３０６、暗号化部３０７、送信部３０８、乱数送信部３０９を備える。図示していないが、登録装置３００は、登録装置３００の各部で使用されるデータを記憶する記録媒体を備える。
【００４４】
受信部３０１は、鍵生成装置２００から送信されてきた鍵ＫとパラメータＬとを受信する。鍵保管部３０２は、受信部３０１から受け取った鍵Ｋを保管する。パラメータ保管部３０３は、受信部３０１から受け取ったパラメータＬを保管する。
【００４５】
入力部３０４は、データ登録者から入力された保管データと、保管データのデータ名を受け取る。なお、本実施の形態では、保管データを保管データＤ、データ名をＩＤ（Ｄ）と表記して説明する。
もし、データ登録者からデータ名の入力がなければ、入力部３０４は、入力された保管データＤのデータ名ＩＤ（Ｄ）に乱数を割り当ててもよいし、他の保管データのデータ名と重複しないように０より大きい整数の値を順に割り当ててもよい。
また、入力部３０４は、データ登録者から削除したい保管暗号化データ集合についての削除データ名を受け取る。削除データ名は、例えば、登録時に入力したデータ名や、登録した時刻、データ登録者の名前など、保管データを特定できるものなら何でもよい。
【００４６】
データ分割部３０５は、パラメータ保管部３０３からパラメータＬを読み出し、入力部３０４から受け取った保管データＤを（ｗ１，・・・，ｗＬ）と分割する。この場合、分割数はＬより小さい値でもよい。各ｗｉ（１≦ｉ≦Ｌ）は、データを１文字や複数文字ずつ順に分割したものでもいいし、単語単位で分割してもよい。
【００４７】
パラメータ保管部３０３はセキュリティパラメータλを保管している。乱数生成部３０６は、乱数Ｒを一つ生成する。Ｒの大きさは、特に規定されないがパラメータ保管部３０３に保管されたセキュリティパラメータλの大きさに応じて大きく取ることが望ましい。
【００４８】
暗号化部３０７は、鍵保管部３０２から鍵Ｋを読み出し、乱数生成部３０６で生成された乱数Ｒを用いて暗号文Ｃを以下のように生成する。
文字ｗｉ，．．．ｗＬに対して、データ分割部３０５から受け取った分割データ（ｗ１，・・・，ｗＬ）から、次のような集合Ａを生成する。
Ａ＝｛Ａ１，Ａ２，・・・，ＡＬ｝。
以降では、集合Ａを部分文字列集合と呼ぶ場合がある。
詳細は登録装置の動作の説明で述べるが、暗号化部３０７は、集合Ａを用いて、保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））を生成する。
【００４９】
送信部３０８は、暗号化部３０７から受け取った保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））を、管理装置５００へ送信する。乱数送信部３０９は、乱数生成部３０６から受け取った乱数Ｒを検索装置４００へ送信する。この乱数Ｒは、検索装置４００で管理される、後述の乱数Ｒ（ｊ）である。乱数Ｒ（ｊ）はＲｊと記す場合もある。
【００５０】
図４は、検索装置４００の構成を示すブロック図である。図４に示すように、検索装置４００は、乱数入力部４０１と、乱数保管部４０２と、受信部４０３と、鍵保管部４０４と、入力部４０５と、暗号化部４０６と、送信部４０７と、出力部４０８と、乱数生成部４０９とを備える。図示していないが、検索装置４００は、検索装置４００の各部で使用されるデータを記憶する記録媒体を備える。
【００５１】
（１）乱数入力部４０１は、登録装置３００から送信されてきた乱数Ｒを受信する。
（２）乱数保管部４０２は、乱数入力部４０１に入力された乱数Ｒを、記憶した順番を示す識別子ｊと共に記憶する。すなわち、乱数保管部４０２には、それまでに乱数入力部４０１に入力された乱数Ｒが、（ｊ、Ｒｊ）という対で複数記憶されている。乱数保管部４０２は、（ｊ、Ｒｊ）をリストとして持っている。
（３）受信部４０３は、鍵生成装置２００から送信されてきた鍵Ｋ、及び鍵Ｋ’、または管理装置５００から送信されてきた検索結果を受信する。
（４）鍵保管部４０４は、受信部４０３から受け取った鍵Ｋを保管する。
（５）入力部４０５は、データ検索者から入力された検索データＳを受け取る。入力部４０５は、データ検索者から、検索データＳと同時に、その検索データＳと、検索したい保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））を指定するような保管データ名も複数受けとってもよい。
（６）暗号化部４０６は、鍵保管部４０４から鍵Ｋと、鍵Ｋ’とを読み出し、入力部４０５から受け取った検索データＳに対して鍵Ｋを用いて、以下のような暗号文ｔを生成する。
詳細は、検索装置４００の動作で述べるが、概要は以下の様である。
【００５２】
（１）まず、暗号化部４０６は検索データＳを分割し
Ｓ：（ｓ１，．．．，ｓｋ）
とする。なお、分割は必須ではない。
（２）次に、暗号化部４０６は、乱数保管部４０２より（ｊ、Ｒｊ）を読み出し、
ｕ＝（ｕ１，．．．，ｕｋ）
を生成する。
すなわち、乱数保管部４０２は、リストとして、
（１、Ｒ１）、（２、Ｒ２），．．．，（Ｍ、ＲＭ）
というＭ対の値を持っている。Ｍは登録装置３００によって登録された保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））の個数と等しい。乱数保管部４０２により読みだされた（ｊ、Ｒｊ）を用いて、暗号化部４０６によって、一つ一つの暗号文は、
ｕｉ＝Ｅ（Ｋ，ｓｉ＜＋＞ｕｉ―１）
から生成される。＜＋＞は、便宜的に排他的論理和の演算を示す記号である。
Ｒｊについて考えているので、ｕ０＝Ｒｊとする。
【００５３】
次に、生成乱数Ｒ’を一つ選ぶ。生成乱数Ｒ’は乱数生成部４０９が生成した。
そして、
ｔｊ＝Ｅ（Ｋ’，Ｒ’，ｕ１（ｊ），．．．，ｕｋ（ｊ））
とする。なお、Ｅは暗号化関数とする。
なお、ｔｊ＝Ｅ（Ｋ’，Ｒ’，ｕｋ（ｊ））
でもよい。暗号化部４０６は、乱数保管部４０２から受け取った全ての（ｊ、Ｒｊ）について同様のことを実行する。（ｊ、Ｒｊ）がＭ個対存在するならば、ｔｊは対に対応してＭ個生成される。以降では、このＭ個全てのｔｊを検索暗号化データと呼び、
検索暗号化データＴ→＝（ｔ（１），．．．，ｔ（Ｍ））
と記述する。
【００５４】
送信部４０７は、暗号化部４０６から受け取った検索暗号化データＴ→と生成乱数Ｒ’を管理装置５００へ送信する。もし、データ検索者から検索データと同時に保管データ名も入力されていた場合は、検索暗号化データと保管データ名の両方を管理装置５００へ送信する。
【００５５】
出力部４０８は、受信部４０３から受け取った検索結果に基づき、検索結果をデータ検索者に対して出力する。もし、検索結果が暗号化されていた場合は、鍵保管部４０４に保管されている鍵Ｋなどを用いて検索結果を復号して出力する。
【００５６】
図５は、管理装置５００の構成を示すブロック図である。図５に示すように、管理装置５００は、受信部５０１と、パラメータ保管部５０２と、データ保管部５０３と、照合部５０４と、送信部５０５とを備える。図示していないが、管理装置５００は、管理装置５００の各部で使用されるデータを記憶する記録媒体を備える。
【００５７】
（１）受信部５０１は、鍵生成装置２００から送信されてきたパラメータＬ、登録装置３００から送信されてきた保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））、削除データ名、検索装置４００から送信されてきた検索暗号化データＴ→、乱数Ｒ’、保管データ名を受信する。
（２）パラメータ保管部５０２は、受信部５０１から受け取ったパラメータＬを保管する。
（３）データ保管部５０３は、受信部５０１から受け取った保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））を保管する。必要があれば、送信されてきた日時なども同時に保管してもよい。また、データ保管部５０３は、受信部５０１から受け取った削除データ名に基づき、保管している保管暗号化データ集合を削除する。
【００５８】
照合部５０４は、検索結果に関わる空集合Ｉを生成し、データ保管部５０３からすべての保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））を読み出し、受信部５０１から受け取った検索暗号化データＴ→＝（ｔ（１），．．．，ｔ（Ｍ））に基づき、照合を行う。照合部５０４は、照合処理を行い、あるいは検索結果を生成する。なお詳細な処理は管理装置５００の動作で説明する。
送信部５０５は、照合部５０４から受け取った検索結果Ｒを検索装置４００へ送信する。
【００５９】
＜＊＊＊動作の説明＊＊＊＞
以下では、本実施の形態に係る検索方法に相当する、秘匿検索システム１００の動作について説明する。
図６は、秘匿検索システム１００の鍵生成・保管処理を示すフローチャートである。
図６のＳ６０１〜Ｓ６１１は、鍵生成装置２００と、登録装置３００と、検索装置４００と、管理装置５００とが実行する処理である。Ｓ６０１〜Ｓ６０４は鍵生成装置２００に、Ｓ６０５〜Ｓ６０７は登録装置３００に、Ｓ６０８〜Ｓ６０９は検索装置４００に、Ｓ６１０〜Ｓ６１１は管理装置５００によって実行される。
【００６０】
（鍵生成装置２００）
Ｓ６０１において、鍵生成部２０２は、入力部２０１に入力された鍵のビット長Ｌｂｉｔを用いて、データの暗号化に使用される鍵Ｋ、鍵Ｋ’を生成する。
なお入力部２０１に入力されるパラメータＬは、保管データＤを分割する最大分割数である。
なお、本実施の形態では共通鍵暗号技術を用いて説明しているが、公開鍵暗号技術を用いてもよい。その場合は、鍵生成部２０２は、鍵Ｋについては公開鍵ＰＫと秘密鍵ＳＫのペアを鍵Ｋとして設定して、鍵Ｋ’については公開鍵ＰＫ’と秘密鍵ＳＫ’のペアを鍵Ｋ’として設定して、以降に説明する処理を同じように実施すればよい。
【００６１】
Ｓ６０２において、送信部２０３は、入力部２０１に入力されたパラメータＬ、Ｓ６０１で生成した鍵Ｋと、を、登録装置３００へ送信する。
Ｓ６０３において、送信部２０３は、Ｓ６０１で生成した鍵Ｋを、検索装置４００へ送信する。
Ｓ６０４において、送信部２０３は、入力部２０１に入力されたパラメータＬを、管理装置５００へ送信する。
【００６２】
（登録装置３００）
Ｓ６０５において、受信部３０１は、Ｓ６０２で送信された鍵ＫとパラメータＬを受信する。
Ｓ６０６において、鍵保管部３０２は、Ｓ６０５で受信した鍵Ｋを記憶媒体に保管する。
Ｓ６０７において、パラメータ保管部３０３は、Ｓ６０５で受信したパラメータＬを記憶媒体に保管する。
【００６３】
（検索装置４００）
Ｓ６０８において、受信部４０３は、Ｓ６０３で送信された鍵Ｋおよび鍵Ｋ’を受信する。
Ｓ６０９において、鍵保管部４０４は、Ｓ６０８で受信した鍵Ｋおよび鍵Ｋ’を記憶媒体に保管する。
【００６４】
（管理装置５００）
Ｓ６１０において、受信部５０１は、Ｓ６０４で送信された鍵Ｋ’およびパラメータＬを受信する。
Ｓ６１１において、パラメータ保管部５０２は、Ｓ６１０で受信した鍵Ｋ’およびパラメータＬを記憶媒体に保管する。
Ｓ６１１により、秘匿検索システム１００の鍵生成・保管処理は終了する。
【００６５】
なお、鍵Ｋおよび鍵Ｋ’は秘密情報であるため、登録装置３００の鍵保管部３０２と、検索装置４００の鍵保管部４０４とは、鍵Ｋおよび鍵Ｋ’が外部に漏れないように厳重に保管する必要がある。
【００６６】
図７は、秘匿検索システム１００の登録処理を示すフローチャートである。図７のＳ７０１〜Ｓ７０７は、登録装置３００と管理装置５００とが実行する処理である。Ｓ７０１〜Ｓ７０５は登録装置３００に、Ｓ７０６〜Ｓ７０７は管理装置５００によって実行される処理である。
【００６７】
（登録装置３００）
Ｓ７０１において、入力部３０４は、データ登録者から入力された、保管データＤとデータ名ＩＤ（Ｄ）とを受け取る。なお、データ登録者からデータ名の入力がなければ、入力部３０４は、入力された保管データＤのデータ名ＩＤ（Ｄ）に乱数を割り当ててもよいし、他の保管データのデータ名と重複しないように、０より大きい整数の値を順に割り当ててもよい。
【００６８】
Ｓ７０２において、データ分割部３０５は、検索されるデータである保管データＤを、複数の要素データｗｉに分割する。
具体的には以下である。
データ分割部３０５は、パラメータ保管部３０３からパラメータＬを読み出し、Ｓ７０１でデータ登録者から受け取った保管データＤを（ｗ１，・・・，ｗＬ）と、パラメータＬの示すＬ個の要素データｗｉ，ｉ＝１、．．．、Ｌに分割する。
なお、分割数をＮとした場合、分割数Ｎは、Ｌ以下の個数でもよい。
このように、保管データＤは先頭から順に分割可能なデータ構造であり、データ分割部３０５は、保管データＤを先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データｗｉに分割する。
【００６９】
（具体例）
具体例を示す。パラメータＬ＝３の場合、データ分割部３０５は保管データＤを
（ｗ１，ｗ２，ｗ３）と３分割してもよいし、
（ｗ１，ｗ２）と２分割してもよい。このように、分割数はパラメータＬ以下であればよい。
（ｗ１，ｗ２，ｗ３）を例にさらに説明すれば、
ｗ１，ｗ２，ｗ３等として、データ分割部３０５は、保管データＤを１文字、あるいは複数文字ずつ順に分割してもよいし、単語単位で分割してもよい。
【００７０】
Ｓ７０３において、乱数生成部３０６は、乱数Ｒを一つ生成する。
【００７１】
Ｓ７０４において、暗号化部３０７は、鍵保管部３０２から鍵Ｋを読み出し、Ｓ７０３で生成された乱数Ｒを用いて、以下のように処理１の集合Ａの生成、処理２のＣｉ→の生成により、暗号文Ｃを生成する。
【００７２】
（処理１：集合Ａの生成）
以下では一つの保管データＤ（ｊ）について考える。保管データＤ（ｊ）は、ｊ＝１の場合とし、Ｄ（１）と記す。以下では、ｊは保管データＤを区別する文字とし（ｊ）と記す。また、保管データＤ（ｊ）に対応して、乱数Ｒ（ｊ）が乱数生成部３０６によって生成される。データ分割部３０５は保管データＤ（１）をＬ個に分割したとする。
つまり、保管データＤ（１）は、
（ｗ１，ｗ２，ｗ３，．．．ｗＬ）
と分割される。
暗号化部３０７は、以下の部分文字列Ａｉ，ｉ＝１，２，．．．Ｌを要素とする集合Ａ（１）を生成する。
Ａ＝｛Ａ１，Ａ２，．．．，ＡＬ｝
Ａｉ＝（ｗｉ，ｗｉ＋１，．．．，ｗＬ）
である。
つまり、
Ａ１＝（ｗ１，ｗ２，．．．，ｗＬ），
Ａ２＝（ｗ２，ｗ３，．．．，ｗＬ），
．．．，
ＡＬ＝（ｗＬ）
である。
【００７３】
（処理２：Ｃｉ→の生成）
Ａｉ＝（ｗｉ，ｗｉ＋１，．．．，ｗＬ）、ｉ＝１，２，．．，Ｌに対して、
暗号化部３０７は、
Ｃｉ＝（ｃｉ．ｉ，．．．，ｃｉ．Ｌ）
を生成する。
ＣｉはＡｉに対応し、Ｌ−ｉ＋１個の要素を持つ。
以下、Ｃｉは成分ｃｉ，ｉ等との区別のため、ベクトル表記によりＣｉ→と表記する。
つまり、
Ｃｉ→＝（ｃｉ．ｉ，．．．，ｃｉ．Ｌ）
である。
Ｃｉ→＝の成分である一つ一つの暗号文ｃは、
ｃｉ．ｊ．＝Ｅ（Ｋ，ｗｊ＜＋＞ｃｉ．ｊ−１）    （式１）
ｃｉ．ｉ−１＝Ｒ（ｊ）                        （式２）
により生成される。ｉはＡｉに対応する。式１のｊはｉ〜Ｌまでをとる。
式１のｊは保管データＤを区別する（ｊ）とは異なる。
式１、式２は、ＣＢＣモード（Ｃｉｐｈｅｒ  Ｂｌｏｃｋ  Ｃｈａｉｎｉｎｇ  Ｍｏｄｅ）を示す。
（式１）のＥ（Ｋ，ｗｊ＜＋＞ｃｉ．ｊ−１）において記号の意味は下記である。
＜＋＞は、排他的論理和の演算を示すのは上述のとおりである。
よって、ｗｊ＜＋＞ｃｉ．ｊ−１は、ｗｊとｃｉ．ｊ−１との、排他的論理和の演算を示す。
また、前記のとおり、Ｅ（Ｋ，＊）は、鍵Ｋを用いて＊を暗号化することを意味する。
保管データＤ（１）に対して、暗号化部３０７は、全てのＡｉに対して、Ｃｉ→を生成する。
以上の処理を全てのＡｉに対して実行する。
すべてのＣｉ→をまとめた集合をＣ（Ｄ（ｊ））と書くことにする。
Ｃｉ→はＡｉに対応するので、
Ｃ（Ｄ（ｊ））＝｛Ｃ１→，Ｃ２→，．．．，ＣＬ→｝
である。
なお、Ｅ（Ｋ，ｗｊ＜＋＞ｃｉ．ｊ−１）におけるＥは暗号化関数である。Ｅとして、共通鍵暗号方式、メッセージ認証符号、ハッシュ関数が、その一例である。
【００７４】
上記の処理１、処理２を具体例で説明する。
データ分割部３０５によって、保管データＤ（１）は（ｗ１，ｗ２，ｗ３）と分割されたとする。
以下はすべて暗号化部３０７の処理である。
暗号化部３０７は、
集合Ａ＝｛Ａ１，Ａ２，Ａ３｝を生成する。
この場合、
Ａ１＝（ｗ１，ｗ２，ｗ３）、Ａ２＝（ｗ２，ｗ３）、Ａ３＝（ｗ３）、
である。
暗号化部３０７は、
Ａｉ（ｉ＝１，２，３）に対してＣｉ→を生成する。
Ａ１、Ａ２、Ａ３に、Ｃ１→、Ｃ２→、Ｃ３→が対応する。
式１により、以下のｃ１．１が計算される。
式１は、図９に示すＣＢＣモードである。
図９は、以下のＡ１〜Ａ３の場合を示す。
ｉ＝１：（Ａ１に対応）
Ｃ１→＝（ｃ１．１，ｃ１．２，ｃ１．３）
ｃ１．１＝Ｅ（Ｋ，ｗ１＜＋＞ｃ１．０）＝Ｅ（Ｋ，ｗ１＜＋＞Ｒ（１））
ｃ１．２＝Ｅ（Ｋ，ｗ２＜＋＞ｃ１．１）＝Ｅ（Ｋ，ｗ２＜＋＞Ｅ（Ｋ，ｗ１＜＋＞Ｒ（１）））
ｃ１．３＝Ｅ（Ｋ，ｗ３＜＋＞ｃ１．２）＝Ｅ（Ｋ，ｗ３＜＋＞Ｅ（Ｋ，ｗ２＜＋＞Ｅ（Ｋ，ｗ１＜＋＞Ｒ（１））））
ｉ＝２：（Ａ２に対応）：
Ｃ２→＝（ｃ２．２，ｃ２．３）
ｃ２．２＝Ｅ（Ｋ，ｗ２＜＋＞ｃ２．１）＝Ｅ（Ｋ，ｗ２＜＋＞Ｒ（１））
ｃ２．３＝Ｅ（Ｋ，ｗ３＜＋＞ｃ２．２）＝Ｅ（Ｋ，ｗ３＜＋＞Ｅ（Ｋ，ｗ２＜＋＞Ｒ（１）））
ｉ＝３：（Ａ３に対応）：
Ｃ３→＝（ｃ３．３）
＝Ｅ（Ｋ，ｗ３＜＋＞ｃ３．２）＝Ｅ（Ｋ，ｗ３＜＋＞Ｒ（１））
以上により、
集合Ａ＝｛Ａ１，Ａ２，ＡＬ｝
に対して、
Ｃ１→，Ｃ２→，Ｃ３→が生成された。
よって、
Ｃ（Ｄ（１））＝｛Ｃ１→，Ｃ２→，Ｃ３→｝
である。
ここで、
Ｃ１→＝（ｃ１．１，ｃ１．２，ｃ１．３）、
Ｃ２→＝（ｃ２．２，ｃ２．３）、
Ｃ３→＝（ｃ３．３）
である。
また、ｃ１．１等の値は上記のＥ（Ｋ，ｗ１＜＋＞Ｒ（１））等による。
以上が処理１、処理２の具体例である。
図９に示すように、暗号化部３０７は、複数の要素データｗｉの各要素データｗｉを、秘匿検索の可能な暗号モードによって、乱数Ｒを用いて暗号化する。図９では秘匿検索の可能な暗号モードは、ＣＢＣモードである。
より具体的には、暗号化部３０７は、分割されたＮ個の要素データを用いて、第１番目から第Ｎ番目までの要素データを順に並べた第１の集合Ａ１、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合Ａ２、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合ＡＮ−１、第Ｎ番目の要素データからなる第Ｎの集合ＡＮまでの、Ｎ個の集合Ａｉを生成する。実施の形態１ではＮ＝Ｌとしており、また具体例ではＮ＝３である。
そして、図９に示すように、暗号化部３０７は、各集合に含まれるそれぞれの要素データｗｉを、乱数Ｒを用いてＣＢＣモードによって暗号化する。
図９は、第１の集合Ａ１の場合を示しているが、全部の集合Ａｉに集合Ａ１と同じ処理がされる。暗号化部３０７は、図９に示すように、第１の集合Ａ１から前記第Ｎの集合ＡＮの集合ごとに、ＣＢＣモードの第１段において乱数Ｒと、集合の最初の要素データとの排他的論理和を演算し、ＣＢＣモードの第２段以降おいて、前段の出力値と、前段で排他的論理和の演算に使用された要素データの次の順番の要素データとの排他的論理和を演算する。
【００７５】
Ｓ７０５において、乱数送信部３０９は、Ｓ７０４で生成した保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ（ｊ）））および乱数Ｒ（ｊ）を管理装置５００へ送信する。
また、乱数送信部３０９は、乱数Ｒ（ｊ）を検索装置４００に送信する。
【００７６】
（管理装置５００）
Ｓ７０６において、受信部５０１は、Ｓ７０６で送信された保管暗号化データ集合を受信する。
Ｓ７０７において、データ保管部５０３は、Ｓ７０７で受信した保管暗号化データ集合を保管する。
Ｓ７０７により、秘匿検索システム１００の登録処理は終了する。
【００７７】
図８は、秘匿検索システム１００の検索処理を示すフローチャートである。
図８のＳ８０１〜Ｓ８１０は、検索装置４００と管理装置５００とが実行する処理である。
Ｓ８０１〜Ｓ８０４及びＳ８１０〜Ｓ８１１は、検索装置４００に、Ｓ８０５〜Ｓ８０９は管理装置５００によって実行される処理である。
【００７８】
Ｓ８０１において、
入力部４０５は、データ検索者から入力された検索データＳを受け取る。
入力部４０５は、検索データＳを取得する検索データ取得部である。
なお、複数の検索データＳを同時に受け取ってもよい。
その場合は、以降の処理を各検索データに対して同じように実施すればよい。
また、前述の通り、入力部４０５は、データ検索者から、検索データと同時に、その検索データと検索したい保管暗号化データ集合を指定するような保管データ名も複数受けとってもよい。
【００７９】
Ｓ８０２において、暗号化部４０６は、乱数保管部４０２から乱数（ｊ、Ｒ（ｊ））をうけとる。ただし、１≦ｊ≦Ｍである。Ｍは、今までに登録装置３００によって登録された保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ（ｊ）））の個数と等しい。
Ｓ８０２では、乱数Ｒ（１）〜Ｒ（Ｍ）を取得する。
【００８０】
Ｓ８０３において、暗号化部４０６は検索データＳを暗号化する。
Ｓ８０３の処理は暗号化部４０６による。暗号化部４０６は、鍵保管部４０４から鍵Ｋおよび鍵Ｋ’を読み出し、Ｓ８０１で受け取った検索データＳに対して、次のようにして、検索暗号化データＴを生成する。検索暗号化データＴは、通常、複数の成分を有するので、ベクトル表示してＴ→と記す。検索暗号化データＴ→は、それぞれのｊに対応する成分であるｕ（ｊ）を有する。ｕ（ｊ）も複数の成分を有するのでベクトル表記により、ｕ（ｊ）→と記す。ｕ（ｊ）→はｊに対応するが、つまり乱数Ｒ（ｊ）に対応する。
（ｊ＝１の場合）
まずｊ＝１の場合を考える。暗号化部４０６は、検索データＳを分割し、（Ｓ１，．．．，Ｓｋ）を生成する。
なお、分割することは必須ではない。検索データＳを分割せずに用いてもよい。
暗号化部４０６は、分割する場合、検索データＳを複数の要素データＳｉ，ｉ＝１，．．．ｋに分割し、検索データＳの暗号化として、乱数Ｒ（ｊ）ごとに、この乱数Ｒ（ｊ）で各要素データＳｉを暗号化する。図１０で具体例を後述する。
以下ではｋ個に分割する場合を説明する。またｋは任意の数でよい。
次に、ｕ（１）→＝（ｕ１，．．．，ｕｋ）が生成される。
一つ一つの暗号文は、
ｕｉ（１）＝Ｅ（Ｋ，Ｓｉ＜＋＞ｕｉ―１（１））    （式３）
ｕ０＝Ｒ（ｊ）      （式４）
のように生成される。式３の意味は式１と同様である。
次に、暗号化部４０６は、乱数生成部４０９の生成した生成乱数Ｒ’を一つ取得する。なお、乱数生成部４０９は、検索データ取得部である入力部４０５によって取得された複数の検索データＳの検索データＳごとに、生成乱数Ｒ’を生成する。暗号化部４０６は、乱数生成部４０９によって検索データＳごとに生成された生成乱数Ｒ’を、対応する検索データＳに用いる。
生成乱数Ｒ’を用いて、暗号化部４０６は、
ｔ（ｊ＝１）＝Ｅ（Ｋ’，Ｒ’，ｕ１（１），．．．，ｕｋ（１））      （式５）
を生成する。なお、Ｅは暗号化関数とする。
なお、ｔ（１）＝Ｅ（Ｋ’，Ｒ’，ｕｋ（１））でもよい。
つまり、ｔ（ｊ）＝Ｅ（Ｋ’，Ｒ’，ｕｋ（ｊ））でもよい。
以上がｊ＝１についての処理である。
【００８１】
（ｊ＝２〜ｊの処理）
式５のｔ（ｊ）の生成を、暗号化部４０６は乱数保管部４０２から受け取った全ての（ｊ、Ｒ（ｊ））について実行する。
つまり、式５ではｔ（１）が生成されたが、同様に、ｔ（２）〜ｔ（Ｍ）も生成される。
これらを記載すれば、
ｔ（２）＝Ｅ（Ｋ’，Ｒ’，ｕ１（２），．．．，ｕｋ（２））、
．．．、
ｔ（Ｍ）＝Ｅ（Ｋ’，Ｒ’，ｕ１（Ｍ），．．．，ｕｋ（Ｍ））、
である。
式３より、ｔ（２）、ｔ（３）等は、乱数Ｒ（２）、Ｒ（３）等が異なる。
（ｊ、Ｒ（ｊ））がＭ個対存在するならば、ｔ（ｊ）はＭ個生成される。
このＭ個全てのｔ（ｊ）を、上記のように検索暗号化データＴ→と呼び、
Ｔ→＝（ｔ（１），．．．，ｔ（Ｍ））と記述する。
【００８２】
Ｓ８０４において、送信部４０７は、Ｓ８０３で生成した検索暗号化データＴ→と生成乱数Ｒ’を対として、管理装置５００へ送信する。もし、Ｓ８０１で保管データ名も入力されていれば、保管データ名も送信する。
具体的には、送信部４０７は、乱数保管部４０２に保管された複数の乱数Ｒｊと同じ複数の乱数Ｒｊの乱数ごとに、その乱数を用いて暗号化された複数の暗号化データＣ（Ｄ（ｊ））を有する管理装置５００に、検索暗号化データＴ→を送信する。
【００８３】
（検索処理の具体例）
図１０を参照して、具体例によってＴ→の生成を説明する。図１０は、検索装置による暗号化処理を説明する図である。
【００８４】
＜１．検索データＳの分割＞
（ｊ＝１）
（ｊ，Ｒｊ）は、（１，Ｒ１），（２，Ｒ２）の２組とする。
検索データＳは、Ｓ＝（Ｓ１，Ｓ２）に分割されたとする。
＜２．ｕ（ｊ）→の生成＞
ｕ（１）→は分割の数だけ成分を有するので、２成分である。
ｕ（１）→＝（ｕ１（１），ｕ２（１））
式３の、
ｕｉ（１）＝Ｅ（Ｋ，ｓｉ＜＋＞ｕｉ−１（１））において、
ｉ＝１，２である。
図１０は、ｊ＝１，２のｕ（１）→、ｕ（２）→の生成を示す。
ｕ１（１）＝Ｅ（Ｋ，Ｓ１＜＋＞ｕ０（１））＝Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（１））、
ｕ２（１）＝Ｅ（Ｋ，Ｓ２＜＋＞ｕ１（１））＝Ｅ（Ｋ，Ｓ２＜＋＞Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（１）））、
（ｊ＝２）
ｕ（２）→＝（ｕ１（２），ｕ２（２））
の各成分は、ｕ（１）→に対して、乱数Ｒ（１）が乱数Ｒ（２）になったのみである。
つまり、下記である。
【００８５】
（ｊ＝２の場合）
ｕ１（２）＝Ｅ（Ｋ，Ｓ１＜＋＞ｕ０（２））＝Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（２））
ｕ２（２）＝Ｅ（Ｋ，Ｓ２＜＋＞ｕ１（２））＝Ｅ（Ｋ，Ｓ２＜＋＞Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（２））、
以上により、（１，Ｒ１），（２，Ｒ２）について、
ｕ（１）→、ｕ（２）→が生成された。
＜３．検索暗号化データの生成＞
上記式５のように、
ｔ（ｊ）＝Ｅ（Ｋ’，Ｒ’，ｕ１（ｊ），．．．，ｕｋ（ｊ））
であるが、
具体例ではｊ＝１，２、
ｔ（１）＝Ｅ（Ｋ’，Ｒ’，ｕ１（１），ｕ２（１））
ｔ（２）＝Ｅ（Ｋ’，Ｒ’，ｕ１（２），ｕ２（２））
である。
よって、
Ｔ→＝（ｔ（１），．．．，ｔ（Ｍ））は、
具体例では，
Ｔ→＝（ｔ（１），ｔ（２））
である。
ｔ（１）を具体的に書き出すと、
ｔ（１）＝Ｅ（Ｋ’，Ｒ’，ｕ１（１），ｕ２（１））
＝Ｅ（Ｋ’，Ｒ’，Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（１）），Ｅ（Ｋ，Ｓ２＜＋＞Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（１）））
である。
ｔ（２）を具体的に書き出すと、ｔ（１）に対してｕ成分が、ｕ（２）となるのみである。
ｔ（２）＝Ｅ（Ｋ’，Ｒ’，ｕ１（２），ｕ２（２））
＝Ｅ（Ｋ’，Ｒ’，Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（２）），Ｅ（Ｋ，Ｓ２＜＋＞Ｅ（Ｋ，Ｓ１＜＋＞Ｒ（２））））
である。
送信部４０７は、検索暗号化データＴ→と、生成乱数である生成乱数Ｒ’とを、管理装置５００へ送信する。
以上が検索装置４００における具体例である。
図１０の具体例で説明したように、暗号化部４０６は、検索されるデータの検索に使用されるキーワードである検索データＳを、秘匿検索の可能な暗号モードによって、乱数保管部４０２に保管された前記乱数Ｒｊごとに乱数Ｒｊを用いて暗号化を行いｕ（１）→，ｕ（２）→等を生成する。そして、暗号化部４０６は、暗号化された複数の検索データであるｕ（１）→，ｕ（２）→等を含む、検索暗号化データＴ→を生成する。暗号化部４０６は、乱数Ｒ（ｊ）ごとにその乱数Ｒ（ｊ）を用いて暗号化された検索データｕ（１）→，ｕ（２）→等のそれぞれを、乱数生成部４０９によって生成された生成乱数Ｒ’を用いて暗号化することにより、検索暗号化データＴ→を生成する。
【００８６】
Ｓ８０５において、管理装置５００の受信部５０１は、検索装置４００から検索暗号化データＴ→を受信する。
【００８７】
Ｓ８０６において、管理装置５００の照合部５０４は、データ保管部５０３から保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ（ｊ）））を読み出す。なお、Ｓ８０５で保管データ名も受信していた場合は、照合部５０４は、その保管データ名に基づき、対象の保管暗号化データ集合のみを読み出す。Ｓ８０５で受信部５０１が保管データ名を受信していなかった場合は、保管されているすべての保管暗号化データ集合である（ＩＤ（Ｄ），Ｃ（Ｄ（１）））〜（ＩＤ（Ｄ），Ｃ（Ｄ（Ｍ）））を読み出す。
【００８８】
Ｓ８０７において、照合部５０４は、検索結果に関わる空集合Ｉを生成する。
また照合部５０４は、受信部５０１から
検索暗号化データＴ→＝（ｔ（１），．．．，ｔ（Ｍ））を受け取る。
照合部５０４は、Ｓ８０７において以下のように、照合データｔ’ｉを生成する。
以下では、具体例で説明する。
【００８９】
管理装置５００は、生成乱数Ｒ’、検索暗号化データＴ→、保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））、鍵Ｋ’、パラメータＬ、を受信している。生成乱数Ｒ’、検索暗号化データＴ→は検索装置４００から受信している。保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ））は、登録装置３００から受信している。鍵Ｋ’、パラメータＬは、鍵生成装置２００から受信している。管理装置５００は、検索暗号化データＴ→に基づき照合を行い、検索結果を出力する。
【００９０】
管理装置５００は、
Ｔ→＝（ｔ（１），ｔ（２））と生成乱数Ｒ’を受信したとする。管理装置５００は、（ＩＤ（Ｄ），Ｃ（Ｄ（１）））、（ＩＤ（Ｄ），Ｃ（Ｄ（２）））の２つの保管暗号化データ集合を読み出すとする。
つまり、ｊ＝１，２である。
（ＩＤ（Ｄ），Ｃ（Ｄ（１）））は、上記の（ＩＤ（Ｄ），Ｃ（Ｄｊ＝１））であり、
Ｃ（Ｄｊ＝１）＝｛Ｃ１→，Ｃ２→，Ｃ３→｝＝｛（ｃ１．１〜ｃ１．３），（ｃ２．２〜ｃ２．３），（ｃ３．３）｝
である。
【００９１】
管理装置５００は、検索暗号化データＴ→＝（ｔ（１），ｔ（２））に基づき、次のようにして照合を行う。
Ｃ（Ｄ（１））＝｛Ｃ１→，Ｃ２→，Ｃ３→｝のＣ１→，Ｃ２→，Ｃ３→について、
以下のｔ’ｉを計算する。
一般的には、
ｔ’ｉ＝Ｅ（Ｋ’，Ｒ’，Ｃｉ→）      （式６）
である。
この例では、
Ｃ１→，Ｃ２→，Ｃ３→ごとに、ｔ’ｉ＝を生成する。
つまり、
ｔ’１＝Ｅ（Ｋ’，Ｒ’，Ｃ１→）、
ｔ’２＝Ｅ（Ｋ’，Ｒ’，Ｃ２→）、
ｔ’３＝Ｅ（Ｋ’，Ｒ’，Ｃ３→）、
である。
Ｓ７０４の具体例により、
Ｃ１→＝（ｃ１．１，ｃ１．２，ｃ１．３）、
Ｃ２→＝（ｃ２．２，ｃ２．３）、
Ｃ３→＝（ｃ３．３）
である。よって、
ｔ’１＝Ｅ（Ｋ’，Ｒ’，Ｃ１→）＝Ｅ（Ｋ’，Ｒ’，ｃ１．１，ｃ１．２，ｃ１．３），
ｔ’２＝Ｅ（Ｋ’，Ｒ’，Ｃ２→）＝Ｅ（Ｋ’，Ｒ’，ｃ２．２，ｃ２．３）
ｔ’３＝Ｅ（Ｋ’，Ｒ’，Ｃ３→）＝Ｅ（Ｋ’，Ｒ’，ｃ３．３）
である。ｃ１．１，ｃ１．２，等の値は、Ｓ８０３の説明で述べたとおりである。
【００９２】
上記の式６ではｔ’ｉにＣｉ→を用いた。つまりｔ’ｉの生成にＣｉ→のすべての成分を用いたが、Ｃｉ→の最後の成分ｃｉ．Ｌを用いてもよい。この場合は、Ｓ８０３において、ｔ（ｊ）＝Ｅ（Ｋ’，Ｒ’，ｕｋ（ｊ））を用いることが前提である。
【００９３】
Ｓ８０８において、
照合部５０４は、検索結果に関わる空集合Ｉを生成し、Ｓ８０７で生成した各照合データｔｉ（１≦ｉ≦Ｌ）が検索暗号化データＴ→に含まれているかを確認する。それぞれの照合データｔ’ｉについて、照合データｔ’ｉが、検索暗号化データＴ→に含まれていれば、空集合であるＩに（ＩＤ（Ｄ），ｉ）を含める。上記ではＣ（Ｄ（１））の保管暗号化データ集合（ｊ＝１）について説明したが、照合部５０４は、これを全ての保管暗号化データ集合（ｊ＝２〜Ｍ）に対して行う。
また、本処理の結果、初期の空集合Ｉから最終的に生成される集合Ｉを、検索結果Ｉと呼ぶ。
【００９４】
Ｓ８０９において、送信部５０５は、Ｓ８０８で生成した検索結果Ｉを、検索装置４００へ送信する。
【００９５】
Ｓ８１０において、検索装置４００の受信部４０３は、Ｓ８０９で送信された検索結果Ｉを受信する。
【００９６】
Ｓ８１１において、出力部４０８は、Ｓ８１０で受信した検索結果Ｉを出力する。
【００９７】
Ｓ８１１により、秘匿検索システム１００の検索処理は終了する。
【００９８】
＜＊＊＊実施の形態１の効果＊＊＊＞
本実施の形態は、以下のような効果を奏する。
（１）本実施の形態では、たとえ同じ保管データをサーバへ保管したとしても、乱数Ｒにより毎回必ず異なる保管暗号化データ集合が生成される。このため、頻度分析攻撃への耐性が向上し、高い安全性をもつ秘匿部分一致検索を実現できる。
（２）本実施の形態では、検索暗号化データがただ一つの暗号文から構成されるため、検索に用いるデータサイズが非常に小さく、また検索時にデータ検索者とサーバとのやりとりが１回しか発生しないため、効率的に秘匿部分一致検索することが可能である。
（３）本実施の形態では、検索暗号化データに生成乱数Ｒ’を用いているので、頻度分析攻撃が困難となり、頻度分析攻撃の耐性が向上する。
（４）本実施の形態では、保管データを暗号化して保管しているため、たとえ管理装置５００から保管暗号化データ集合が漏洩しても、保管データの中身を知られることはない。
（５）本実施の形態では、検索データのみならず保管データも暗号化したまま処理ができるため、検索暗号化データから検索データの中身を知られることはない。
【００９９】
実施の形態２．
次に、実施の形態２を説明する。実施の形態２は実施の形態１と、システム構成及び各装置の構成は同じである。実施の形態１は、図９、図１０に示すように、ＣＢＣモード）を使用した。実施の形態２は、ＣＴＲモード（Ｃｏｕｎｔｅｒ  Ｍｏｄｅ）を使用する。
【０１００】
実施の形態１の中で、登録装置３００において、暗号化部３０７は以下のような動作でもよい。
【０１０１】
（暗号化部３０７の動作）
暗号化部３０７は、鍵保管部３０２から鍵Ｋを読み出し、乱数生成部３０６で生成された乱数Ｒを用いて暗号文を以下のように生成する。
保管データＤ（１）は、（ｗ１，．．．，ｗＬ）と分割されたとする。
ｗ１，．．．，ｗＬは、ｗｉ，ｉ＝１，２，．．．Ｌである。
暗号化部３０７は、
（ｗ１，．．．，ｗＬ）に対して、
Ｃｉ＝Ｅ（Ｋ，Ｒ＋ｉ―１）＜＋＞ｗｉ      （式７）
の演算を行う。
そして、暗号化部３０７は保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ（１）））を生成する。
ここで、Ｃ（Ｄ（１））＝（Ｃｉ，Ｃ２，．．，ＣＬ）である。
つまり、Ｃ（Ｄ（１））の成分の数は、保管データの分割数である。
【０１０２】
図１３は、ＣＴＲモードによって、Ｃ１〜Ｃ３が生成される具体例を示す。保管データＤ（１）は、（ｗ１，ｗ２，ｗ３）と分割されたとする。
暗号化部３０７は、Ｃ（Ｄ（１））＝（Ｃ１，Ｃ２，Ｃ３）を生成する。
このように、Ｃ（Ｄ（１））において、
ここで、
Ｃ１＝Ｅ（Ｋ，Ｒ＋０）＜＋＞ｗ１、
Ｃ２＝Ｅ（Ｋ，Ｒ＋１）＜＋＞ｗ２、
Ｃ３＝Ｅ（Ｋ，Ｒ＋２）＜＋＞ｗ３、
である。
Ｃ１〜Ｃ３は、ｗ１〜ｗ３に対応する。
つまり、Ｃｉは、ｗｉに対応する。
【０１０３】
（検索装置４００の動作）
登録装置３００の暗号化部３０７を上記のように動作させる場合、検索装置４００の暗号化部４０６は以下のような動作である。
【０１０４】
（暗号化部４０６の動作）
図１４は実施の形態２の検索装置４００の暗号化部４０６の動作を説明する図である。
図１４を参照して説明する。暗号化部４０６は、鍵保管部４０４から鍵Ｋを読み出し、入力部４０５から受け取った検索データＳに対して鍵Ｋを用いて、次のように暗号文ｔを生成する。
まず、検索データＳを分割し（Ｓ１，．．．，Ｓｋ）とする。
図１４では（Ｓ１，Ｓ２）と分割する。なお実施の形態１と同様に、分割しなくても構わない。
【０１０５】
次に、暗号化部４０６は乱数保管部４０２より（ｊ、Ｒｊ）を読み出し、
ｕ＝（ｕ１，．．．，ｕｋ）を生成する。
ｋは検索データＳの分割数である。
一つ一つの暗号文は、
ｕｉ＝Ｅ（Ｋ，Ｒ（ｊ）＋ｉ―１）＜＋＞Ｓｉ
のように計算される。ｉ＝１，．．．，ｋである。
【０１０６】
次に、暗号化部４０６は乱数生成部４０９の生成した生成乱数Ｒ’を一つ取得する。
そして、暗号化部４０６は、
ｊ＝１について、ｔ（１）＝Ｅ（Ｋ’，Ｒ’，ｕ１（ｊ），．．．，ｕｋ（ｊ））
を計算する。
図１４の例では、
ｔ（１）＝Ｅ（Ｋ’，Ｒ’，ｕ１（１），ｕ２（１））
を計算する。
ここで、
ｕ１（１）＝Ｅ（Ｋ，Ｒ（１））＜＋＞Ｓ１、
ｕ２（１）＝Ｅ（Ｋ，Ｒ（１）＋１）＜＋＞Ｓ２
である。
ｊ＝２についても同様に、暗号化部４０６は、
ｔ（２）＝Ｅ（Ｋ’，Ｒ’，ｕ１（２），ｕ２（２））
を計算する。
ここで、
ｕ１（２）＝Ｅ（Ｋ，Ｒ（２））＜＋＞Ｓ１、
ｕ２（２）＝Ｅ（Ｋ，Ｒ（２）＋１）＜＋＞Ｓ２
である。
暗号化部４０６は、
検索暗号化データＴ→（ｔ（１），ｔ（２））を生成する。
送信部４０７は、索暗号化データＴ→（ｔ（１），ｔ（２））と、生成乱数Ｒ’を、管理装置５００に送信する。
【０１０７】
登録装置３００の暗号化部３０７の動作、及び検索装置４００の暗号化部４０６の動作を上記のように動作させる場合、管理装置５００の照合部５０４は以下のような動作である。
【０１０８】
（照合部５０４の動作）
照合部５０４は、検索結果に関わる空集合Ｉを生成し、データ保管部５０３からすべての保管暗号化データ集合（ＩＤ（Ｄ），Ｃ（Ｄ（ｊ）））を読み出す。
照合部５０４は、受信された検索暗号化データＴ→＝（ｔ（１），．．．，ｔ（Ｍ））に基づき、次のようにして照合を行うことや検索結果を生成する。
この例では、
検索暗号化データＴ→＝（ｔ（１），ｔ（２））
である。
以下では、上記で述べた、
Ｃ（Ｄ（１））＝（Ｃ１，Ｃ２，Ｃ３）を例に説明する。
照合部５０４は、Ｃ（Ｄ（１））について下記のｔ’（ｊ）を計算する。
この例ではｊ＝１なのでｔ’（ｊ）＝ｔ’（１）である。
ｔ’（ｊ）＝Ｅ（Ｋ’，Ｒ’，Ｃ（Ｄ（ｊ）））＝Ｅ（Ｋ’，Ｒ’，Ｃ１，．．．，ＣＬ）    （式８）
を計算する。
ここで、Ｃ（Ｄ（１））の成分数はＣ１，．．．，ＣＬのＬ個であるが、Ｌは保管データＤ（１）の分割数である。
よって、この例では、
ｔ’（１）＝Ｅ（Ｋ’，Ｒ’，Ｃ（Ｄ（１）））＝Ｅ（Ｋ’，Ｒ’，Ｃ１，Ｃ２，Ｃ３）
である。
照合部５０４は、Ｃ（Ｄ（２））〜Ｃ（Ｄ（Ｍ））についてもＣ（Ｄ（１））と同様の処理を行う。
照合部５０４は、それぞれのｔ’（ｊ）（ｊ＝１，２，．．．，Ｍ）について、ｔ’（ｊ）が検索暗号化データＴ→に含まれていれば、Ｉに（ＩＤ（Ｄ（ｊ）），ｊ）を含める。
本処理の結果、最終的に生成される集合Ｉを検索結果Ｉと呼ぶのは実施の形態１と同じである。
【０１０９】
実施の形態２は実施の形態１に対して、使用される暗号モードが異なるだけであるので、実施の形態１と同様の効果を得ることができる。
【０１１０】
なお、実施の形態２のシステム構成、装置の機能及びハードウェア構成も実施の形態１と同様である。異なるのは暗号モードである。
【０１１１】
実施の形態１、実施の形態２で示した鍵生成装置２００、登録装置３００、検索装置４００、管理装置５００の動作は、方法、プログラムとして把握できる。暗号化装置である登録装置３００は、暗号化プログラムによって動作する。登録装置３００の動作は、暗号化方法に相当する。検索装置４００は、検索プログラムによって動作する。検索装置４００の動作は、検索方法に相当する。
【符号の説明】
【０１１２】
１００  秘匿検索システム、１０１  インターネット、２００  鍵生成装置、２０１  入力部、２０２  鍵生成部、２０３  送信部、３００  登録装置、３０１  受信部、３０２  鍵保管部、３０３  パラメータ保管部、３０４  入力部、３０５  データ分割部、３０６  乱数生成部、３０７  暗号化部、３０８  送信部、３０９  乱数送信部、４００  検索装置、４０１  乱数入力部、４０２  乱数保管部、４０３  受信部、４０４  鍵保管部、４０５  入力部、４０６  暗号化部、４０７  送信部、４０８  出力部、４０９  乱数生成部、５００  管理装置、５０１  受信部、５０２  パラメータ保管部、５０３  データ保管部、５０４  照合部、５０５  送信部。
【図１】
2017126000.tif 000003
【図２】
2017126000.tif 000004
【図３】
2017126000.tif 000005
【図４】
2017126000.tif 000006
【図５】
2017126000.tif 000007
【図６】
2017126000.tif 000008
【図７】
2017126000.tif 000009
【図８】
2017126000.tif 000010
【図９】
2017126000.tif 000011
【図１０】
2017126000.tif 000012
【図１１】
2017126000.tif 000013
【図１２】
2017126000.tif 000014
【図１３】
2017126000.tif 000015
【図１４】
2017126000.tif 000016
【手続補正書】
【提出日】平成29年9月4日(2017.9.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割するデータ分割部と、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードによって暗号化する暗号化部と
を備えた暗号化装置。
【請求項２】
前記暗号化部は、
前記第１の集合から前記第Ｎの集合の集合ごとに、
前記ＣＢＣモードの第１段において、前記乱数と、前記集合の最初の要素データとの排他的論理和を演算し、
前記ＣＢＣモードの第２段以降おいて、前段の出力値と、前段で排他的論理和の演算に使用された要素データの次の順番の要素データとの排他的論理和を演算する請求項１に記載の暗号化装置。
【請求項３】
複数の乱数が保管された乱数保管部と、
乱数生成部と、
検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、前記乱数保管部に保管された前記乱数ごとに前記乱数を用いて暗号化を行い、前記乱数ごとに前記乱数を用いて暗号化された前記検索データのそれぞれを、前記乱数生成部によって生成された生成乱数を用いて暗号化し、前記生成乱数によって暗号化された複数の前記検索データを含む検索暗号化データを生成する暗号化部と、
前記乱数保管部に保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する送信部と
を備えた検索装置。
【請求項４】
前記検索装置は、さらに、
前記検索データを取得する検索データ取得部を備え、
前記乱数生成部は、
前記検索データ取得部によって取得された複数の前記検索データの前記検索データごとに、生成乱数を生成し、
前記暗号化部は、
前記乱数生成部によって前記検索データごとに生成された生成乱数を、対応する前記検索データの暗号化に用いる請求項３に記載の検索装置。
【請求項５】
前記暗号化部は、
前記検索データを複数の要素データに分割し、前記検索データの前記暗号化として、前記乱数ごとに前記乱数で各要素データを暗号化する請求項３または請求項４に記載の検索装置。
【請求項６】
前記送信部は、
前記検索暗号化データと、前記検索暗号化データの生成に使用された前記生成乱数とを対として送信する請求項３から請求項５のいずれか一項に記載の検索装置。
【請求項７】
コンピュータに、
先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割する処理、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードによって暗号化する処理
を実行させるための暗号化プログラム。
【請求項８】
コンピュータに、
複数の乱数を保管する処理、
乱数を生成する処理、
検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、保管された前記乱数ごとに前記乱数を用いて暗号化を行い、前記乱数ごとに前記乱数を用いて暗号化された前記検索データのそれぞれを、乱数を生成する前記処理によって生成された生成乱数を用いて暗号化し、前記生成乱数によって暗号化された複数の前記検索データを含む検索暗号化データを生成する処理、
保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する処理、
を実行させるための検索プログラム。
【請求項９】
データ分割部、暗号化部を備えた暗号化装置が行う暗号化方法であって、
データ分割部が、先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割し、
暗号化部が、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードによって暗号化する暗号化方法。
【請求項１０】
複数の乱数が保管された乱数保管部、乱数生成部、暗号化部、送信部を備えた検索装置が行う検索方法であって、
乱数生成部が、乱数を生成し、
暗号化部が、検索されるデータの検索に使用されるキーワードである検索データを、秘匿検索の可能な暗号モードによって、前記乱数保管部に保管された前記乱数ごとに前記乱数を用いて暗号化を行い、前記乱数ごとに前記乱数を用いて暗号化された前記検索データのそれぞれを、前記乱数生成部によって生成された乱数である生成乱数を用いて暗号化し、前記生成乱数によって暗号化された複数の前記検索データを含む検索暗号化データを生成し、
送信部が、前記乱数保管部に保管された複数の乱数と同じ複数の乱数の乱数ごとにその乱数を用いて暗号化された複数の暗号化データを有する管理装置に、前記検索暗号化データを送信する検索方法。
【手続補正書】
【提出日】平成29年11月27日(2017.11.27)
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割するデータ分割部と、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードと秘匿検索の可能な暗号モードであるＣＴＲモードとのいずれかによって暗号化する暗号化部と
を備えた暗号化装置。
【請求項２】
前記暗号化部は、
各集合に含まれるそれぞれの要素データを、乱数を用いて、前記ＣＢＣモードによって暗号化するとともに、暗号化に際し、
前記第１の集合から前記第Ｎの集合の集合ごとに、
前記ＣＢＣモードの第１段において、前記乱数と、前記集合の最初の要素データとの排他的論理和を演算し、
前記ＣＢＣモードの第２段以降おいて、前段の出力値と、前段で排他的論理和の演算に使用された要素データの次の順番の要素データとの排他的論理和を演算する請求項１に記載の暗号化装置。
【請求項３】
前記暗号化部は、
各集合に含まれるそれぞれの要素データを、乱数を用いて、前記ＣＴＲモードによって暗号化するとともに、暗号化に際し、
前記第１の集合から前記第Ｎの集合の集合ごとに、
前記ＣＴＲモードのそれぞれの段において、前記乱数とそれぞれの段におけるカウンタ値との和を暗号化するとともに暗号化された前記和の値と前記集合の要素データとの排他的論理和を演算する請求項１に記載の暗号化装置。
【請求項４】
コンピュータに、
データ分割部が、先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割する処理、
暗号化部が、分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードと秘匿検索の可能な暗号モードであるＣＴＲモードとのいずれかによって暗号化する処理
を実行させるための暗号化プログラム。
【請求項５】
データ分割部、暗号化部を備えた暗号化装置が行う暗号化方法であって、
データ分割部が、先頭から順に分割可能なデータ構造を持つ検索されるデータを、先頭から順に、第１番目から第Ｎ番目までのＮ個の要素データに分割し、
暗号化部が、
分割されたＮ個の要素データを用いて、
第１番目から第Ｎ番目までの要素データを順に並べた第１の集合、
第２番目から第Ｎ番目までの要素データを順に並べた第２の集合、
以降、順に、第Ｎ−１番目から第Ｎ番目までの要素データを順に並べた第Ｎ−１の集合、第Ｎ番目の要素データからなる第Ｎの集合までの、
Ｎ個の集合を生成し、各集合に含まれるそれぞれの要素データを、乱数を用いて、秘匿検索の可能な暗号モードであるＣＢＣモードと秘匿検索の可能な暗号モードであるＣＴＲモードとのいずれかによって暗号化する暗号化方法。
【国際調査報告】
2017126000.tif 000017
2017126000.tif 000018
2017126000.tif 000019
2017126000.tif 000020
2017126000.tif 000021
2017126000.tif 000022
2017126000.tif 000023
2017126000.tif 000024