秘匿計算方法及び装置
【課題】暗号文を復号することなく、平文を秘匿したままデータ検索を行うことを可能にする。
【解決手段】変換装置１００は、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）、及び、検索対象のメッセージＭ＝（ｍＬ・・・ｍ１）を１ビットずつ暗号化した暗号文Ｅ（ｍｉ）（ｊ＝１，・・・，Ｌ）を入力し、ｊ＝１，・・・，Ｌ−ｓ＋１について、０以下の乱数ｒｊを生成し、
を計算し、Ｘｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を復号装置に送る。復号装置は、Ｘｊを復号し、復号結果が０であれば、対応するｊを出力する。このｊがメッシセージＭ内の文字列Ｂの含まれている箇所（ポインタ）を示す。
【解決手段】変換装置１００は、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）、及び、検索対象のメッセージＭ＝（ｍＬ・・・ｍ１）を１ビットずつ暗号化した暗号文Ｅ（ｍｉ）（ｊ＝１，・・・，Ｌ）を入力し、ｊ＝１，・・・，Ｌ−ｓ＋１について、０以下の乱数ｒｊを生成し、
を計算し、Ｘｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を復号装置に送る。復号装置は、Ｘｊを復号し、復号結果が０であれば、対応するｊを出力する。このｊがメッシセージＭ内の文字列Ｂの含まれている箇所（ポインタ）を示す。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関し、特にメッセージやファイルデータを秘匿したままデータ検索する技術に関する。
【背景技術】
【０００２】
従来より秘密鍵／公開鍵暗号方式は数多く提案されているが、安全性の観点から、一般に同一の平文であっても暗号化する度に暗号文が異なる方式であることが望ましいとされている。これには、例えば、Ｇoldwasser−Ｍicali暗号のような確率暗号が知れているが（例えば、非特許文献１参照）、従来の確率暗号は、一般に暗号文だけから、それに対応する平文を対象としたデータ検索を行うことはできない。
【０００３】
【非特許文献１】岡本龍明，山本博資共著「現代暗号」§７.８ 確率暗号，産業図書，１９９７年６月３０日
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、平文を秘匿したままでデータ検索できるようにする秘匿計算方法及び装置を提供することにある。
【課題を解決するための手段】
【０００５】
メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とする。検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とする。この時、ｊ＝１，・・・，Ｌ−ｓ＋１について以下を実施する。
（ｉ）Ｂ及びＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
【０００６】
【数１】
を計算する。
（ii）０以外の適当な範囲の乱数ｒｊを生成し、Ｘｊ及びｒｊからＥの準同型性を利用して
【０００７】
【数２】
を計算する。
（iii）Ｙｊを復号し、復号結果が０であれば一致、そうでなければ不一致とする。
【０００８】
ここで、上記（iii）について、（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であればＹｊの復号結果は０、そうでなければ０以外の乱数となる。これにより、ｍｉ（ｉ＝１，・・・，Ｌ）の情報を漏らすことなくメッセージＭ＝（ｍＬ・・・ｍ１）２に文字列Ｂ＝（ｂｓ・・・ｂ１）２が含まれているかどうか、また含まれている場合どの箇所に含まれているか分かる。すなわち、その時のｊの位置（ポインタ）で分かる。また、含まれていない場合、復号結果は０以外の乱数（ｒｊ）となるため、メッセージの解読は不可能である。なお、上記（ｉ）と（ii）は同時に実施してもよい。
【０００９】
これが本発明の基本原理であるが、これより簡易なやり方から複雑なやり方までの種々の方法が考えられる。以下にそれらを列記する。
（１） メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数として、以下の処理を実施する。
１．Ｂ及びＥ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
２．Ｘｊを復号する。
３．Ｘｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断する。
【００１０】
（２） メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数として、以下の処理を実施する。
１．Ｂ及びＥ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
２．０以外の適当な範囲の乱数ｒｊを生成し、前記Ｘｊ及びｒｊからＥの準同型性を利用して、
Ｙｊ＝Ｅ（ｒｊ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
３．Ｙｊを復号する。
４．Ｙｊ復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断する。
【００１１】
（３） 上記（１）または（２）において、ｍ及びｂをａとして、
【００１２】
【数３】
とする（ｔは正整数）、
【００１３】
（４） 上記（１）から（３）において、基本原理で説明したように、ｊを１からＬ−ｓ＋１の範囲で逐次行うことで、メッセージＭが文字列Ｂを含むか、また含む場合はどの箇所かを特定する。
【００１４】
（５） 上記（１）から（３）において、ｊ＝１，・・・，Ｌ−ｓ＋１について、ＸｊないしＹｊの計算を行い、該ＸｊないしＹｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の順序を撹乱し、その後、ＸｊないしＹｊを復号することで、メッセージＭが文字列Ｂを含む場合、該含む箇所を秘匿する。順序の撹乱方法としては、例えば、ＭＩＸ−net技術を用いる。
【００１５】
（６） 上記（１）から（５）において、Ｅは閾値暗号とし、一定数以上の鍵を用いた場合に限りＸｊないしＹｊを復号できるようにする。
【００１６】
（７） 上記（２）から（６）において、乱数ｒｊは複数の乱数の積とする。さらに、ゼロ知識証明技術を用いて処理の正当性を証明、検証する。
【００１７】
（８） 上記（１）から（７）において、メッセージＭの暗号文Ｅ′（Ｍ）に対し、該暗号文を復号することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を求める。さらには、ｍｉまたはｂｉの少なくとも一方を複数ビットとする。
【発明の効果】
【００１８】
本発明によれば、暗号文を復号することなくデータ検索を行うことが可能であり、復号時に生じる漏洩リスクをなくすことができる。またメッセージを秘匿したまま検閲することができ、ユーザのプライバシ保護にも役立つ。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態について、図面を用いて説明する。
【００２０】
［実施の形態１］
本実施の形態は、平文を秘匿したまま、メッセージ中に検索したい文字列が含まれている箇所を特定するものである。
【００２１】
図１は、本実施の形態のシステム構成を示したもので、変換装置１００と復号装置１１０で構成される。変換装置１００は、検索対象のメッセージの暗号文と検索したい文字列を入力として暗号文を出力する。復号装置１１０は、変換装置１００の出力である暗号文を入力として、最終的に文字列が含まれている箇所（ポインタ）を出力する。変換装置１００は乱数発生手段１０１、暗号計算手段１０２及び入力された暗号文と文字列、計算の途中結果などを記憶する記憶手段１０３などから構成される。復号装置１１０は復号手段１１１、判定手段１１２及び変換装置１００からの暗号文などを記憶する記憶手段１１３などから構成される。変換装置１００と復号装置１１０は、利用目的等により、一体的あるいはネットワークを介して構成されることになる。
【００２２】
以下、変換装置１００及び復号装置１１０の動作を詳細する。いま、メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（()２は２進数表記を意味する）、ＥをＰaillier暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とする。図２と図３は、このときの変換装置１００及び復号装置１１０の処理フローチャートを示したもので、これに基づいて説明する。
【００２３】
変換装置１００、検索すべき文字列であるＢ＝（ｂｓ・・・ｂ１）２、及び、検索対象の暗号文である、メッセージＭを１ビットずつ暗号化した値Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力する（ステップ２０１）。入力された文字列Ｂ＝（ｂｓ・・・ｂ１）２、暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）は、例えば記憶手段１０３に記憶される。
【００２４】
変換装置１００は、まず、ポインタをｊ＝１として（ステップ２０２）、乱数発生手段１０１で０以外の乱数ｒｊを生成し（ステップ２０３）、暗号計算手段１０２で、暗号文Ｘｊ
【００２５】
【数４】
を計算し（ステップ２０４）、該Ｘｊとｊの対（Ｘｊ，ｊ）を記憶手段１０３に記憶する（ステップ２０５）。
【００２６】
次に、変換装置１００は、ポインタｊを更新し（ステップ２０６）、同様にステップ２０３から２０５を実行する。以下、変換装置１００は、順次、ポインタｊを更新し、ｊ＝Ｌ−ｓ＋１になるまで（ステップ２０７でＮｏ）、ステップ２０３〜２０６の処理を繰り返す。
【００２７】
すなわち、変換装置１００は、検索対象のメッセージＭの暗号文（ｍｉ）（ｉ＝１，・・・，Ｌ）を最下位ビットから１ビットずつ順次ずらして、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）２に対応するｓビット個ずつ、順番にＸｊを計算する。
【００２８】
変換装置１００は、ｊ＞Ｌ−ｓ＋１になると（ステップ２０７でＹｅｓ）、すなわち、（ｍｉ）（ｉ＝１，・・・，Ｌ）の最上位ビットまで処理が終了すると、記憶手段１０３内の（Ｘｊ，ｊ）（ｊ＝１，・・・，（Ｌ−ｓ＋１））を復号装置１１０に送信する。
【００２９】
復号装置１１０は、変換装置１００からＸｊとｊの組（Ｘｊ，ｊ）（ｊ＝１，・・・，（Ｌ−ｓ＋１））を受信し（ステップ２１１）、例えば、記憶手段１１３に記憶する。
【００３０】
次に、復号装置１１０は、まず、ポインタをｊ＝１として（ステップ２１２）、対応するＸｊを復号手段１１１で復号し（ステップ２１３）、判定手段１１２で、復号結果が０か否か判定する（ステップ２１４）。そして、復号結果が０でない場合、ポインタｊを更新し（ステップ２１６）、同様にステップ２１３，２１４を実行する。以下、復号結果が０でない間、順次、ポインタｊを更新し、ステップ２１３，２１４を繰り返す。
【００３１】
こうして、復号装置１１０は、あるＸｊを復号し、復号結果として０が検出されたなら、その対応するポインタｊを出力し（ステップ２１５）、この時点で処理を終了とする。また、ｊ＝Ｌ−ｓ＋１になるまで、ステップ２１３，２１４を繰り返しても、復号結果として０が検出されない場合（ステップ２１７でＹｅｓ）、処理は終了となる。
【００３２】
ここで、ＸｊはＰaillier暗号が有する準同型性より、
【００３３】
【数５】
となることから、（ｍｊ＋２−１・・・ｍｊ）＝（ｂｓ・・・ｂ１）２であれば、Ｘｊの復号結果は０、そうでなけば０以外の乱数（ｒｊ）となる。これにより、復号装置１１０は、メッセージＭの中に文字列Ｂを含む最下位ビットのアドレスを示すポインタｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を正しく出力することが分かる。
【００３４】
なお、以上の説明では、変換装置１００はＸｊをｊ＝Ｌ−ｓ＋１まですべて計算した後、（Ｘｊ，ｊ）（ｊ＝１，・・・，Ｌ-ｓ＋１）を一括して復号装置１１０に送信するとしたが、変換装置１００はＸｊとｊの対を順次復号装置１１０に送信するようにしてもよい。この場合、復号装置１１０は、受信したＸｊを順次復号し、復号結果として０が検出されたなら、その旨を変換装置１００に返信する。変換装置１００は、復号装置１１０から０検出が返信されたなら、その時点で処理を終了とする。
【００３５】
［実施の形態２］
本実施の形態は、複数の変換装置により、ゼロ知識証明技術、順序の撹乱技術（ＭＩＸ−net技術）、分散復号技術等を適用して、暗号化されたメッセージを復号することなく、ある文字列が含まれているかどうかだけを特定するものである。
【００３６】
図４は本実施の形態のシステム構成例を示したもので、変換装置３００が複数（１〜Ｎとする）、ネットワーク等により互いに接続されている。各変換装置３００は、同一の検索対象メッセージの暗号文と検索したい文字列を初期入力とし、暗号文、部分復号情報、ゼロ知識証明文などを出力し、また、別の変換装置の出力である暗号文、部分復号知識証明文などを入力する。そして、最終的に、各変換装置３００は、検索したい文字列がメッセージに含まれているか否か示す結果（Ｙes／Ｎo）を出力する。管理装置４００は各変換装置３００の動作を制御するものであるが、各変換装置あるいは特定の変換装置が受け持てば、管理装置４００は省略しても良い。
【００３７】
各変換装置３００は、図５に示すように、管理装置４００や他の変換装置などから所定の情報を受信する受信インタフェース部（受信Ｉ／Ｆ部）３１０、各種の処理を実行する処理部３２０、管理装置４００や他の変換装置などへ所定の情報を送信する送信インタフェース部（送信Ｉ／Ｆ部）３３０、及び、入力された情報や処理結果の情報などを記憶する記憶部３４０で構成される。また、処理部３２０は乱数生成手段３２１、暗号計算手段３２２、暗号順序撹乱手段３２３、復号手段３２４、ゼロ知識証明情報生成手段３２５及びゼロ知識証明手段３２６などの処理機能を有している。
【００３８】
以下、本実施の形態の動作を詳述する。図６はｕ番目の変換装置３００の処理フローチャートを示したものであるが、他の変換装置３００も同様である。
【００３９】
いま、メッセージをＭ＝（ｍＬ・・・ｍ１）ｄとし（（）ｄはｄ進数表記を意味する）、Ｅを文献１「Ｇ．Ｙamamoto，et al．，“Ｅfficient，non−optimistic secure circuit evaluation based on the ＥlＧamal encryption，”Ｐroc．of ＷＩＳＡ 2005，2005．」で定義されている変形閾値ＥlＧamal暗号の暗号化関数とし、検索したい文字列をＢ＝（ｂｓ・・・ｂ１）ｄとする。閾値ＥlＧamal暗号とは、一定数以上の鍵を用いない限り復号できないＥlＧamal暗号である。これにより、単一の管理者による特権濫用（不正に復号する行為）を防ぐことができる。
【００４０】
また、ゼロ知識証明は、例えば文献２「Ｒ.Ｃramer,Ｉ.Ｄamgard and Ｂ.Ｓchoenmakers,“Ｐroofs of partialknowledge and Ｓimplified design of withss hiding protocols,”Ａcvances in Ｃryptology−ＣＲＹＰＴＯ ′９４」ＬＮＣＳ ８３９,pp．１７４−１８７,Ｓpringer−Ｖerlag,１９９４．」および文献３「Ｄ.Ｌ.Ｃhaum and Ｔ.Ｐ.Ｐedersen“Ｗallet databases with observers,”Ａcvances in Ｃryptology−ＣＲＹＰＴＯ ’92,ＬＮＣＳ ７４０,pp.８０−１０５,Ｓpringer−Ｖerlag,１９９３」の方法を組み合わせて行うことができる。なお、ゼロ知識証明自体は周知であるので、ここではその詳細は省略する。
【００４１】
各変換装置３００は、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）ｄ、及び、検索対象のメッセージＭをｄビットずつ暗号化した値の暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力する（ステップ５０１）。入力された文字列Ｂ＝（ｂｓ・・・ｂ１）ｄ、暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）は、例えば、記憶部３４０に記憶される。
【００４２】
各変換装置３００は、暗号計算手段３２２にて、ｉ＝１，・・・，Ｌ−ｓ＋１について、
【００４３】
【数６】
を計算する（ステップ５０２）。これは、先の実施の形態１において、変換装置１００がＸｊを計算する場合と同様である。計算された暗号文Ｘｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）は、例えば、記憶部３４０に記憶される。
【００４４】
ここで、ある変換装置３００で計算されたＸｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＸｊ，０とする。どの変換装置のものをＸｊ，０するかは、例えば、あらかじめ定めておくか、管理装置４００が決定する。ｕ＝１，・・・，Ｎとして、変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＸｊ，ｕ−1（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、乱数生成手段３２１にて０以外の乱数ｒｊ，ｕを生成し、暗号計算手段３２２にて、Ｘｊ，ｕ＝ｒｊ，ｕＸｊ，ｕ−１を計算し、ゼロ知識証明情報生成手段３２５にてゼロ知識証明情報を生成し、該Ｘｊ，ｕ及び該ゼロ知識証明情報を送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０３）。このステップ５０３の処理イメージを図７に示す。
【００４５】
各変換装置３００は、他の変換装置が出力したＸｊ，ｕ（ｕ＝１，・・・，Ｎ）及び該ゼロ知識証明情報を、受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０４）。ここでは、各変換装置３００が検証合格を出力したとする。
【００４６】
Ｎ番目の変換装置３００が出力したＸｊ，Ｎ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＹｊ，０とする。ｕ＝１，・・・，Ｎとして、変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＹｊ，ｕ−1（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、暗号順序撹乱手段３２３にて、例えば、検証可能ＭＩＸ−net技術を用いてｊの順序を撹乱した暗号文の組Ｙｊ，ｕ（ｊ＝１，・・・，Ｌ−ｓ＋１）を計算し、ゼロ知識証明情報生成手段３２５にてＹｊ，ｕの正当性を示すゼロ知識証明情報を生成し、該Ｙｊ，ｕ及び該ゼロ知識証明情報を送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０５）。このステップ５０５の処理イメージを図８に示す。
【００４７】
各変換装置３００は、他の変換装置が出力したＹｊ，ｕ及び該ゼロ知識証明情報を、受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０６）。ここでは、各変換装置３００が検証合格を出力したとする。
【００４８】
Ｎ番目の変換装置３００が出力したＹｊ，Ｎ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＺｊとする。ｕ＝１，・・・，Ｎとして、各変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＺｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、復号手段３２４にてＺｊを部分復号し（分散復号）、その部分復号結果Ｚｊ，ｕ及び該ゼロ知識証明情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０７）。各変換装置における分散復号の分担は、例えば、あらかじめ決めておくか、管理装置４００で決定する。
【００４９】
各変換装置３００は、他の変換装置が出力した部分復号結果Ｚｊ，ｕ及び該ゼロ知識証明情報を受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通してを出力する（ステップ５０８）。ここでは、各変換装置３００が検証合格を出力したとする。
【００５０】
各変換装置３００は、復号手段３２４にて、部分復号結果Ｚｊ，ｕ（ｊ＝１，・・・，Ｌ−ｓ＋１；ｕ＝１，・・・，Ｎ）からＺｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の復号結果を計算し、該結果に０を含まれていれば“Ｙes”を出力し、含まれていなければ“Ｎo”を出力する（ステップ５０９）。例えば、１〜Ｎのすべての変換装置３００が“Ｙes”を出力した場合、メッセージＭの中に文字列Ｂが含まれているとする。
【００５１】
ここで、Ｚｊは変形閾値ＥlＧamal暗号が有する準同型性及び検証可能ＭＩＸ−net技術を用いて
【００５２】
【数７】
となることから、（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であれば、Ｘｊの復号結果は０、そうでなければ０以外の乱数となる。これにより、各変換装置３００は出力Ｙes／ＮoによりメッセージＭの中に文字列Ｂが含まれているかどうか分かる。また、文字列Ｂが含まれる箇所は全ての変換装置３００が協力しないと得られない置換πによって秘匿される。更に（ｍｊ＋ｓ−１・・・ｍｊ）２≠（ｂｓ・・・ｂ１）２でない場合は全ての変換装置３００が協力しないと得られない乱数Πｕｒｊ，ｕによって復号結果がランダム化されるため、メッセージＭの情報は露呈しない。
【００５３】
なお、ステップ５０４、５０６、５０８において検証不合格を示す情報が出力された場合の対処は、一般には事前に決めた規則に従えば問題なく、例えば一定数以上の変換装置から、あるゼロ知識証明情報に対して検証不合格を示す情報が出力された場合は、該ゼロ知識証明情報を出力した変換装置を除外し、残りの変換装置で処理を継続するといった方法が考えられる。
【００５４】
［実施の形態３］
本実施の形態は、先の実施の形態１や２の前処理として、任意の暗号化関数εを用いて暗号化されたメッセージε（Ｍ）を準同型暗号の暗号化関数Ｅを用いて１ビットずつ暗号化されたメッセージＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）に変換するものである。これにより、実施の形態１や２の入力である暗号化メッセージＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）について、任意の暗号関数に対して適用できることから利用範囲が広がることが期待できる。
【００５５】
図４に示した実施の形態２のシステム構成を例にすると、１〜Ｎの各変換装置３００は、任意の暗号化関数εを用いて暗号化されたメッセージε（Ｍ）（Ｍ＝（ｍＬ・・・ｍ１）２）、変形閾値ＥlＧamal暗号を用いて１ビット毎に暗号化されたεの秘密鍵Ｅ（Ｋｉ）（ｉ＝１，・・・，ｖ）、検索したい文字列（ビット列）Ｂ＝（ｂｓ・・・ｂ１）２、及び復号関数ε−１のロジック回路記述ＬＣを入力する。すると、Ｂの分散秘密鍵ｓｕ（ｕ＝１，・・・，Ｎ）を変換装置ｕが格納し、各変換装置はｓｕ，ε（Ｍ），Ｅ（Ｍｉ）（ｕ＝１，・・・，Ｎ），ＬＣを入力し、例えば、先の文献１のマルチパーティプロトコルを実行することで、Ｍ，Ｋｉ（ｉ＝１，・・・，ｖ）の情報を露呈することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を得ることができる。なお、その取得方法は先の文献１から明らかであるため、ここではその説明を省略する。
【００５６】
以上より、Ｅ（ｍｉ）を取得すれば、後は各変換装置３００が図６、図７で示した手順を実行することで、各変換装置３００は出力Ｙes／ＮoによりメッセージＭの中に文字列Ｂが含まれているかどうか分かる。
【００５７】
なお、図１や図５で示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２や図３、図６で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００５８】
【図１】本発明の第１の実施の形態の構成例を示す図である。
【図２】第１の実施の形態の変換装置の処理フローチャート例である。
【図３】第１の実施の形態の復号装置の処理フローチャート例である。
【図４】本発明の第２の実施の形態のシステム構成例を示す図である。
【図５】第２の実施の形態の変換装置の構成例を示す図である。
【図６】第２の実施の形態の変換装置ｕの処理フローチャート例である。
【図７】第２の実施の形態の処理の一部を説明する図である。
【図８】第２の実施の形態の処理の他の一部を説明する図である。
【符号の説明】
【００５９】
１００ 暗号装置
１０１ 乱数発生手段
１０２ 暗号計算手段
１０３ 記憶手段
１１０ 変換装置
１１１ 復号手段
１１２ 判定手段
１１３ 記憶手段
３００ 変換装置
３１０ 受信Ｉ／Ｆ部
３２０ 処理部
３２１ 乱数発生手段
３２２ 暗号計算手段
３２３ 暗号順序撹乱手段
３２４ 復号手段
３２５ ゼロ知識証明情報生成手段
３２６ ゼロ知識証明手段
３３０ 送信Ｉ／Ｆ部
３４０ 記憶部
【技術分野】
【０００１】
本発明は暗号応用技術に関し、特にメッセージやファイルデータを秘匿したままデータ検索する技術に関する。
【背景技術】
【０００２】
従来より秘密鍵／公開鍵暗号方式は数多く提案されているが、安全性の観点から、一般に同一の平文であっても暗号化する度に暗号文が異なる方式であることが望ましいとされている。これには、例えば、Ｇoldwasser−Ｍicali暗号のような確率暗号が知れているが（例えば、非特許文献１参照）、従来の確率暗号は、一般に暗号文だけから、それに対応する平文を対象としたデータ検索を行うことはできない。
【０００３】
【非特許文献１】岡本龍明，山本博資共著「現代暗号」§７.８ 確率暗号，産業図書，１９９７年６月３０日
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明は、平文を秘匿したままでデータ検索できるようにする秘匿計算方法及び装置を提供することにある。
【課題を解決するための手段】
【０００５】
メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とする。検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とする。この時、ｊ＝１，・・・，Ｌ−ｓ＋１について以下を実施する。
（ｉ）Ｂ及びＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
【０００６】
【数１】
を計算する。
（ii）０以外の適当な範囲の乱数ｒｊを生成し、Ｘｊ及びｒｊからＥの準同型性を利用して
【０００７】
【数２】
を計算する。
（iii）Ｙｊを復号し、復号結果が０であれば一致、そうでなければ不一致とする。
【０００８】
ここで、上記（iii）について、（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であればＹｊの復号結果は０、そうでなければ０以外の乱数となる。これにより、ｍｉ（ｉ＝１，・・・，Ｌ）の情報を漏らすことなくメッセージＭ＝（ｍＬ・・・ｍ１）２に文字列Ｂ＝（ｂｓ・・・ｂ１）２が含まれているかどうか、また含まれている場合どの箇所に含まれているか分かる。すなわち、その時のｊの位置（ポインタ）で分かる。また、含まれていない場合、復号結果は０以外の乱数（ｒｊ）となるため、メッセージの解読は不可能である。なお、上記（ｉ）と（ii）は同時に実施してもよい。
【０００９】
これが本発明の基本原理であるが、これより簡易なやり方から複雑なやり方までの種々の方法が考えられる。以下にそれらを列記する。
（１） メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数として、以下の処理を実施する。
１．Ｂ及びＥ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
２．Ｘｊを復号する。
３．Ｘｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断する。
【００１０】
（２） メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数として、以下の処理を実施する。
１．Ｂ及びＥ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
２．０以外の適当な範囲の乱数ｒｊを生成し、前記Ｘｊ及びｒｊからＥの準同型性を利用して、
Ｙｊ＝Ｅ（ｒｊ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算する。
３．Ｙｊを復号する。
４．Ｙｊ復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断する。
【００１１】
（３） 上記（１）または（２）において、ｍ及びｂをａとして、
【００１２】
【数３】
とする（ｔは正整数）、
【００１３】
（４） 上記（１）から（３）において、基本原理で説明したように、ｊを１からＬ−ｓ＋１の範囲で逐次行うことで、メッセージＭが文字列Ｂを含むか、また含む場合はどの箇所かを特定する。
【００１４】
（５） 上記（１）から（３）において、ｊ＝１，・・・，Ｌ−ｓ＋１について、ＸｊないしＹｊの計算を行い、該ＸｊないしＹｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の順序を撹乱し、その後、ＸｊないしＹｊを復号することで、メッセージＭが文字列Ｂを含む場合、該含む箇所を秘匿する。順序の撹乱方法としては、例えば、ＭＩＸ−net技術を用いる。
【００１５】
（６） 上記（１）から（５）において、Ｅは閾値暗号とし、一定数以上の鍵を用いた場合に限りＸｊないしＹｊを復号できるようにする。
【００１６】
（７） 上記（２）から（６）において、乱数ｒｊは複数の乱数の積とする。さらに、ゼロ知識証明技術を用いて処理の正当性を証明、検証する。
【００１７】
（８） 上記（１）から（７）において、メッセージＭの暗号文Ｅ′（Ｍ）に対し、該暗号文を復号することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を求める。さらには、ｍｉまたはｂｉの少なくとも一方を複数ビットとする。
【発明の効果】
【００１８】
本発明によれば、暗号文を復号することなくデータ検索を行うことが可能であり、復号時に生じる漏洩リスクをなくすことができる。またメッセージを秘匿したまま検閲することができ、ユーザのプライバシ保護にも役立つ。
【発明を実施するための最良の形態】
【００１９】
以下、本発明の実施の形態について、図面を用いて説明する。
【００２０】
［実施の形態１］
本実施の形態は、平文を秘匿したまま、メッセージ中に検索したい文字列が含まれている箇所を特定するものである。
【００２１】
図１は、本実施の形態のシステム構成を示したもので、変換装置１００と復号装置１１０で構成される。変換装置１００は、検索対象のメッセージの暗号文と検索したい文字列を入力として暗号文を出力する。復号装置１１０は、変換装置１００の出力である暗号文を入力として、最終的に文字列が含まれている箇所（ポインタ）を出力する。変換装置１００は乱数発生手段１０１、暗号計算手段１０２及び入力された暗号文と文字列、計算の途中結果などを記憶する記憶手段１０３などから構成される。復号装置１１０は復号手段１１１、判定手段１１２及び変換装置１００からの暗号文などを記憶する記憶手段１１３などから構成される。変換装置１００と復号装置１１０は、利用目的等により、一体的あるいはネットワークを介して構成されることになる。
【００２２】
以下、変換装置１００及び復号装置１１０の動作を詳細する。いま、メッセージをＭ＝（ｍＬ・・・ｍ１）２とし（()２は２進数表記を意味する）、ＥをＰaillier暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とする。図２と図３は、このときの変換装置１００及び復号装置１１０の処理フローチャートを示したもので、これに基づいて説明する。
【００２３】
変換装置１００、検索すべき文字列であるＢ＝（ｂｓ・・・ｂ１）２、及び、検索対象の暗号文である、メッセージＭを１ビットずつ暗号化した値Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力する（ステップ２０１）。入力された文字列Ｂ＝（ｂｓ・・・ｂ１）２、暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）は、例えば記憶手段１０３に記憶される。
【００２４】
変換装置１００は、まず、ポインタをｊ＝１として（ステップ２０２）、乱数発生手段１０１で０以外の乱数ｒｊを生成し（ステップ２０３）、暗号計算手段１０２で、暗号文Ｘｊ
【００２５】
【数４】
を計算し（ステップ２０４）、該Ｘｊとｊの対（Ｘｊ，ｊ）を記憶手段１０３に記憶する（ステップ２０５）。
【００２６】
次に、変換装置１００は、ポインタｊを更新し（ステップ２０６）、同様にステップ２０３から２０５を実行する。以下、変換装置１００は、順次、ポインタｊを更新し、ｊ＝Ｌ−ｓ＋１になるまで（ステップ２０７でＮｏ）、ステップ２０３〜２０６の処理を繰り返す。
【００２７】
すなわち、変換装置１００は、検索対象のメッセージＭの暗号文（ｍｉ）（ｉ＝１，・・・，Ｌ）を最下位ビットから１ビットずつ順次ずらして、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）２に対応するｓビット個ずつ、順番にＸｊを計算する。
【００２８】
変換装置１００は、ｊ＞Ｌ−ｓ＋１になると（ステップ２０７でＹｅｓ）、すなわち、（ｍｉ）（ｉ＝１，・・・，Ｌ）の最上位ビットまで処理が終了すると、記憶手段１０３内の（Ｘｊ，ｊ）（ｊ＝１，・・・，（Ｌ−ｓ＋１））を復号装置１１０に送信する。
【００２９】
復号装置１１０は、変換装置１００からＸｊとｊの組（Ｘｊ，ｊ）（ｊ＝１，・・・，（Ｌ−ｓ＋１））を受信し（ステップ２１１）、例えば、記憶手段１１３に記憶する。
【００３０】
次に、復号装置１１０は、まず、ポインタをｊ＝１として（ステップ２１２）、対応するＸｊを復号手段１１１で復号し（ステップ２１３）、判定手段１１２で、復号結果が０か否か判定する（ステップ２１４）。そして、復号結果が０でない場合、ポインタｊを更新し（ステップ２１６）、同様にステップ２１３，２１４を実行する。以下、復号結果が０でない間、順次、ポインタｊを更新し、ステップ２１３，２１４を繰り返す。
【００３１】
こうして、復号装置１１０は、あるＸｊを復号し、復号結果として０が検出されたなら、その対応するポインタｊを出力し（ステップ２１５）、この時点で処理を終了とする。また、ｊ＝Ｌ−ｓ＋１になるまで、ステップ２１３，２１４を繰り返しても、復号結果として０が検出されない場合（ステップ２１７でＹｅｓ）、処理は終了となる。
【００３２】
ここで、ＸｊはＰaillier暗号が有する準同型性より、
【００３３】
【数５】
となることから、（ｍｊ＋２−１・・・ｍｊ）＝（ｂｓ・・・ｂ１）２であれば、Ｘｊの復号結果は０、そうでなけば０以外の乱数（ｒｊ）となる。これにより、復号装置１１０は、メッセージＭの中に文字列Ｂを含む最下位ビットのアドレスを示すポインタｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を正しく出力することが分かる。
【００３４】
なお、以上の説明では、変換装置１００はＸｊをｊ＝Ｌ−ｓ＋１まですべて計算した後、（Ｘｊ，ｊ）（ｊ＝１，・・・，Ｌ-ｓ＋１）を一括して復号装置１１０に送信するとしたが、変換装置１００はＸｊとｊの対を順次復号装置１１０に送信するようにしてもよい。この場合、復号装置１１０は、受信したＸｊを順次復号し、復号結果として０が検出されたなら、その旨を変換装置１００に返信する。変換装置１００は、復号装置１１０から０検出が返信されたなら、その時点で処理を終了とする。
【００３５】
［実施の形態２］
本実施の形態は、複数の変換装置により、ゼロ知識証明技術、順序の撹乱技術（ＭＩＸ−net技術）、分散復号技術等を適用して、暗号化されたメッセージを復号することなく、ある文字列が含まれているかどうかだけを特定するものである。
【００３６】
図４は本実施の形態のシステム構成例を示したもので、変換装置３００が複数（１〜Ｎとする）、ネットワーク等により互いに接続されている。各変換装置３００は、同一の検索対象メッセージの暗号文と検索したい文字列を初期入力とし、暗号文、部分復号情報、ゼロ知識証明文などを出力し、また、別の変換装置の出力である暗号文、部分復号知識証明文などを入力する。そして、最終的に、各変換装置３００は、検索したい文字列がメッセージに含まれているか否か示す結果（Ｙes／Ｎo）を出力する。管理装置４００は各変換装置３００の動作を制御するものであるが、各変換装置あるいは特定の変換装置が受け持てば、管理装置４００は省略しても良い。
【００３７】
各変換装置３００は、図５に示すように、管理装置４００や他の変換装置などから所定の情報を受信する受信インタフェース部（受信Ｉ／Ｆ部）３１０、各種の処理を実行する処理部３２０、管理装置４００や他の変換装置などへ所定の情報を送信する送信インタフェース部（送信Ｉ／Ｆ部）３３０、及び、入力された情報や処理結果の情報などを記憶する記憶部３４０で構成される。また、処理部３２０は乱数生成手段３２１、暗号計算手段３２２、暗号順序撹乱手段３２３、復号手段３２４、ゼロ知識証明情報生成手段３２５及びゼロ知識証明手段３２６などの処理機能を有している。
【００３８】
以下、本実施の形態の動作を詳述する。図６はｕ番目の変換装置３００の処理フローチャートを示したものであるが、他の変換装置３００も同様である。
【００３９】
いま、メッセージをＭ＝（ｍＬ・・・ｍ１）ｄとし（（）ｄはｄ進数表記を意味する）、Ｅを文献１「Ｇ．Ｙamamoto，et al．，“Ｅfficient，non−optimistic secure circuit evaluation based on the ＥlＧamal encryption，”Ｐroc．of ＷＩＳＡ 2005，2005．」で定義されている変形閾値ＥlＧamal暗号の暗号化関数とし、検索したい文字列をＢ＝（ｂｓ・・・ｂ１）ｄとする。閾値ＥlＧamal暗号とは、一定数以上の鍵を用いない限り復号できないＥlＧamal暗号である。これにより、単一の管理者による特権濫用（不正に復号する行為）を防ぐことができる。
【００４０】
また、ゼロ知識証明は、例えば文献２「Ｒ.Ｃramer,Ｉ.Ｄamgard and Ｂ.Ｓchoenmakers,“Ｐroofs of partialknowledge and Ｓimplified design of withss hiding protocols,”Ａcvances in Ｃryptology−ＣＲＹＰＴＯ ′９４」ＬＮＣＳ ８３９,pp．１７４−１８７,Ｓpringer−Ｖerlag,１９９４．」および文献３「Ｄ.Ｌ.Ｃhaum and Ｔ.Ｐ.Ｐedersen“Ｗallet databases with observers,”Ａcvances in Ｃryptology−ＣＲＹＰＴＯ ’92,ＬＮＣＳ ７４０,pp.８０−１０５,Ｓpringer−Ｖerlag,１９９３」の方法を組み合わせて行うことができる。なお、ゼロ知識証明自体は周知であるので、ここではその詳細は省略する。
【００４１】
各変換装置３００は、検索したい文字列Ｂ＝（ｂｓ・・・ｂ１）ｄ、及び、検索対象のメッセージＭをｄビットずつ暗号化した値の暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）を入力する（ステップ５０１）。入力された文字列Ｂ＝（ｂｓ・・・ｂ１）ｄ、暗号文Ｅ（ｍｉ）（ｉ＝１，・・・，Ｌ）は、例えば、記憶部３４０に記憶される。
【００４２】
各変換装置３００は、暗号計算手段３２２にて、ｉ＝１，・・・，Ｌ−ｓ＋１について、
【００４３】
【数６】
を計算する（ステップ５０２）。これは、先の実施の形態１において、変換装置１００がＸｊを計算する場合と同様である。計算された暗号文Ｘｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）は、例えば、記憶部３４０に記憶される。
【００４４】
ここで、ある変換装置３００で計算されたＸｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＸｊ，０とする。どの変換装置のものをＸｊ，０するかは、例えば、あらかじめ定めておくか、管理装置４００が決定する。ｕ＝１，・・・，Ｎとして、変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＸｊ，ｕ−1（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、乱数生成手段３２１にて０以外の乱数ｒｊ，ｕを生成し、暗号計算手段３２２にて、Ｘｊ，ｕ＝ｒｊ，ｕＸｊ，ｕ−１を計算し、ゼロ知識証明情報生成手段３２５にてゼロ知識証明情報を生成し、該Ｘｊ，ｕ及び該ゼロ知識証明情報を送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０３）。このステップ５０３の処理イメージを図７に示す。
【００４５】
各変換装置３００は、他の変換装置が出力したＸｊ，ｕ（ｕ＝１，・・・，Ｎ）及び該ゼロ知識証明情報を、受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０４）。ここでは、各変換装置３００が検証合格を出力したとする。
【００４６】
Ｎ番目の変換装置３００が出力したＸｊ，Ｎ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＹｊ，０とする。ｕ＝１，・・・，Ｎとして、変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＹｊ，ｕ−1（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、暗号順序撹乱手段３２３にて、例えば、検証可能ＭＩＸ−net技術を用いてｊの順序を撹乱した暗号文の組Ｙｊ，ｕ（ｊ＝１，・・・，Ｌ−ｓ＋１）を計算し、ゼロ知識証明情報生成手段３２５にてＹｊ，ｕの正当性を示すゼロ知識証明情報を生成し、該Ｙｊ，ｕ及び該ゼロ知識証明情報を送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０５）。このステップ５０５の処理イメージを図８に示す。
【００４７】
各変換装置３００は、他の変換装置が出力したＹｊ，ｕ及び該ゼロ知識証明情報を、受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０６）。ここでは、各変換装置３００が検証合格を出力したとする。
【００４８】
Ｎ番目の変換装置３００が出力したＹｊ，Ｎ（ｊ＝１，・・・，Ｌ−ｓ＋１）をＺｊとする。ｕ＝１，・・・，Ｎとして、各変換装置ｕは、受信Ｉ／Ｆ部３１０を通してＺｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）を入力し、復号手段３２４にてＺｊを部分復号し（分散復号）、その部分復号結果Ｚｊ，ｕ及び該ゼロ知識証明情報を、送信Ｉ／Ｆ部３３０を通して出力する（ステップ５０７）。各変換装置における分散復号の分担は、例えば、あらかじめ決めておくか、管理装置４００で決定する。
【００４９】
各変換装置３００は、他の変換装置が出力した部分復号結果Ｚｊ，ｕ及び該ゼロ知識証明情報を受信Ｉ／Ｆ部３１０を通して入力し、ゼロ知識証明手段３２６にて、その正当性を検証し、検証合格／不合格を表す情報を、送信Ｉ／Ｆ部３３０を通してを出力する（ステップ５０８）。ここでは、各変換装置３００が検証合格を出力したとする。
【００５０】
各変換装置３００は、復号手段３２４にて、部分復号結果Ｚｊ，ｕ（ｊ＝１，・・・，Ｌ−ｓ＋１；ｕ＝１，・・・，Ｎ）からＺｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の復号結果を計算し、該結果に０を含まれていれば“Ｙes”を出力し、含まれていなければ“Ｎo”を出力する（ステップ５０９）。例えば、１〜Ｎのすべての変換装置３００が“Ｙes”を出力した場合、メッセージＭの中に文字列Ｂが含まれているとする。
【００５１】
ここで、Ｚｊは変形閾値ＥlＧamal暗号が有する準同型性及び検証可能ＭＩＸ−net技術を用いて
【００５２】
【数７】
となることから、（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であれば、Ｘｊの復号結果は０、そうでなければ０以外の乱数となる。これにより、各変換装置３００は出力Ｙes／ＮoによりメッセージＭの中に文字列Ｂが含まれているかどうか分かる。また、文字列Ｂが含まれる箇所は全ての変換装置３００が協力しないと得られない置換πによって秘匿される。更に（ｍｊ＋ｓ−１・・・ｍｊ）２≠（ｂｓ・・・ｂ１）２でない場合は全ての変換装置３００が協力しないと得られない乱数Πｕｒｊ，ｕによって復号結果がランダム化されるため、メッセージＭの情報は露呈しない。
【００５３】
なお、ステップ５０４、５０６、５０８において検証不合格を示す情報が出力された場合の対処は、一般には事前に決めた規則に従えば問題なく、例えば一定数以上の変換装置から、あるゼロ知識証明情報に対して検証不合格を示す情報が出力された場合は、該ゼロ知識証明情報を出力した変換装置を除外し、残りの変換装置で処理を継続するといった方法が考えられる。
【００５４】
［実施の形態３］
本実施の形態は、先の実施の形態１や２の前処理として、任意の暗号化関数εを用いて暗号化されたメッセージε（Ｍ）を準同型暗号の暗号化関数Ｅを用いて１ビットずつ暗号化されたメッセージＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）に変換するものである。これにより、実施の形態１や２の入力である暗号化メッセージＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）について、任意の暗号関数に対して適用できることから利用範囲が広がることが期待できる。
【００５５】
図４に示した実施の形態２のシステム構成を例にすると、１〜Ｎの各変換装置３００は、任意の暗号化関数εを用いて暗号化されたメッセージε（Ｍ）（Ｍ＝（ｍＬ・・・ｍ１）２）、変形閾値ＥlＧamal暗号を用いて１ビット毎に暗号化されたεの秘密鍵Ｅ（Ｋｉ）（ｉ＝１，・・・，ｖ）、検索したい文字列（ビット列）Ｂ＝（ｂｓ・・・ｂ１）２、及び復号関数ε−１のロジック回路記述ＬＣを入力する。すると、Ｂの分散秘密鍵ｓｕ（ｕ＝１，・・・，Ｎ）を変換装置ｕが格納し、各変換装置はｓｕ，ε（Ｍ），Ｅ（Ｍｉ）（ｕ＝１，・・・，Ｎ），ＬＣを入力し、例えば、先の文献１のマルチパーティプロトコルを実行することで、Ｍ，Ｋｉ（ｉ＝１，・・・，ｖ）の情報を露呈することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を得ることができる。なお、その取得方法は先の文献１から明らかであるため、ここではその説明を省略する。
【００５６】
以上より、Ｅ（ｍｉ）を取得すれば、後は各変換装置３００が図６、図７で示した手順を実行することで、各変換装置３００は出力Ｙes／ＮoによりメッセージＭの中に文字列Ｂが含まれているかどうか分かる。
【００５７】
なお、図１や図５で示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２や図３、図６で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００５８】
【図１】本発明の第１の実施の形態の構成例を示す図である。
【図２】第１の実施の形態の変換装置の処理フローチャート例である。
【図３】第１の実施の形態の復号装置の処理フローチャート例である。
【図４】本発明の第２の実施の形態のシステム構成例を示す図である。
【図５】第２の実施の形態の変換装置の構成例を示す図である。
【図６】第２の実施の形態の変換装置ｕの処理フローチャート例である。
【図７】第２の実施の形態の処理の一部を説明する図である。
【図８】第２の実施の形態の処理の他の一部を説明する図である。
【符号の説明】
【００５９】
１００ 暗号装置
１０１ 乱数発生手段
１０２ 暗号計算手段
１０３ 記憶手段
１１０ 変換装置
１１１ 復号手段
１１２ 判定手段
１１３ 記憶手段
３００ 変換装置
３１０ 受信Ｉ／Ｆ部
３２０ 処理部
３２１ 乱数発生手段
３２２ 暗号計算手段
３２３ 暗号順序撹乱手段
３２４ 復号手段
３２５ ゼロ知識証明情報生成手段
３２６ ゼロ知識証明手段
３３０ 送信Ｉ／Ｆ部
３４０ 記憶部
【特許請求の範囲】
【請求項１】
暗号文を復号することなくデータ検索を可能にする秘匿計算方法であって、
検索対象のメッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数とし、
文字列Ｂ及び暗号文Ｅ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
前記Ｘｊを復号するステップ、
前記Ｘｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断するステップ、
からなることを特徴とする秘匿計算方法。
【請求項２】
暗号文を復号することなくデータ検索を可能にする秘匿計算方法であって、
検索対象のメッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数とし、
文字列Ｂ及び暗号文Ｅ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
０以外の適当な範囲の乱数ｒｊを生成し、前記Ｘｊ及びｒｊからＥの準同型性を利用して、
Ｙｊ＝Ｅ（ｒｊ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
前記Ｙｊを復号するステップ、
前記Ｙｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断するステップ、
からなることを特徴とする秘匿計算方法。
【請求項３】
請求項１または２に記載の秘匿計算方法において、ｍ及びｂをａとして、
【数１】
とする（ｔは正整数）、
ことを特徴とする秘匿計算方法。
【請求項４】
請求項１から３のいずれか１項に記載の秘匿計算方法において、ｊを１からＬ−ｓ＋１の範囲で逐次行うことで、メッセージＭが文字列Ｂを含むか、また含む場合はどの箇所かを特定する、
ことを特徴とする秘匿計算方法。
【請求項５】
請求項１から３のいずれか１項に記載の秘匿計算方法において、ｊ＝１，・・・，Ｌ−ｓ＋１についてＸｊないしＹｊの計算を行い、該ＸｊないしＹｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の順序を撹乱し、その後、ＸｊないしＹｊを復号することで、メッセージＭが文字列Ｂを含む場合、該含む箇所を秘匿する、
ことを特徴とする秘匿計算方法。
【請求項６】
請求項１から５のいずれか１項に記載の秘匿計算方法において、Ｅは閾値暗号とし、一定数以上の鍵を用いた場合に限りＸｊないしＹｊを復号できるようにする、
ことを特徴とする秘匿計算方法。
【請求項７】
請求項２から６のいずれか１項に記載の秘匿計算方法において、乱数ｒｊは複数の乱数の積とする、
ことを特徴とする秘匿計算方法。
【請求項８】
請求項１から７のいずれか１項に記載の秘匿計算方法において、ゼロ知識証明技術を用いて処理の正当性を証明、検証する、
ことを特徴とする秘匿計算方法。
【請求項９】
請求項１から８のいずれか１項に記載の秘匿計算方法において、メッセージＭの暗号文Ｅ′（Ｍ）に対し、該暗号文を復号することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を求める、
ことを特徴とする秘匿計算方法。
【請求項１０】
請求項１から９のいずれか１項に記載の秘匿計算方法において、ｍｉまたはｂｉの少なくとも一方を複数ビットとする、
ことを特徴とする秘匿計算方法。
【請求項１１】
請求項１から１０のいずれか１項に記載の秘匿計算方法を実施することを特徴とする秘匿計算装置。
【請求項１】
暗号文を復号することなくデータ検索を可能にする秘匿計算方法であって、
検索対象のメッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数とし、
文字列Ｂ及び暗号文Ｅ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
前記Ｘｊを復号するステップ、
前記Ｘｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断するステップ、
からなることを特徴とする秘匿計算方法。
【請求項２】
暗号文を復号することなくデータ検索を可能にする秘匿計算方法であって、
検索対象のメッセージをＭ＝（ｍＬ・・・ｍ１）２とし（（）２は２進数表記を意味する）、Ｅを準同型暗号の暗号化関数とし、検索したい文字列（ビット列）をＢ＝（ｂｓ・・・ｂ１）２とし、ｆを適当なｓ個の入力関数とし、
文字列Ｂ及び暗号文Ｅ（ｍｉ）（ｉ＝ｊ，・・・，ｊ＋ｓ−１）を入力とし、Ｅの準同型性を利用してＥ（ｍｉ）を復号することなく
Ｘｊ＝Ｅ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
０以外の適当な範囲の乱数ｒｊを生成し、前記Ｘｊ及びｒｊからＥの準同型性を利用して、
Ｙｊ＝Ｅ（ｒｊ（ｆ（ｍｊ，ｍｊ＋１，・・・，ｍｊ＋ｓ−１）−ｆ（ｂ１，ｂ２，・・・，ｂｓ））
を計算するステップ、
前記Ｙｊを復号するステップ、
前記Ｙｊの復号結果が０であるときに限り（ｍｊ＋ｓ−１・・・ｍｊ）２＝（ｂｓ・・・ｂ１）２であると判断するステップ、
からなることを特徴とする秘匿計算方法。
【請求項３】
請求項１または２に記載の秘匿計算方法において、ｍ及びｂをａとして、
【数１】
とする（ｔは正整数）、
ことを特徴とする秘匿計算方法。
【請求項４】
請求項１から３のいずれか１項に記載の秘匿計算方法において、ｊを１からＬ−ｓ＋１の範囲で逐次行うことで、メッセージＭが文字列Ｂを含むか、また含む場合はどの箇所かを特定する、
ことを特徴とする秘匿計算方法。
【請求項５】
請求項１から３のいずれか１項に記載の秘匿計算方法において、ｊ＝１，・・・，Ｌ−ｓ＋１についてＸｊないしＹｊの計算を行い、該ＸｊないしＹｊ（ｊ＝１，・・・，Ｌ−ｓ＋１）の順序を撹乱し、その後、ＸｊないしＹｊを復号することで、メッセージＭが文字列Ｂを含む場合、該含む箇所を秘匿する、
ことを特徴とする秘匿計算方法。
【請求項６】
請求項１から５のいずれか１項に記載の秘匿計算方法において、Ｅは閾値暗号とし、一定数以上の鍵を用いた場合に限りＸｊないしＹｊを復号できるようにする、
ことを特徴とする秘匿計算方法。
【請求項７】
請求項２から６のいずれか１項に記載の秘匿計算方法において、乱数ｒｊは複数の乱数の積とする、
ことを特徴とする秘匿計算方法。
【請求項８】
請求項１から７のいずれか１項に記載の秘匿計算方法において、ゼロ知識証明技術を用いて処理の正当性を証明、検証する、
ことを特徴とする秘匿計算方法。
【請求項９】
請求項１から８のいずれか１項に記載の秘匿計算方法において、メッセージＭの暗号文Ｅ′（Ｍ）に対し、該暗号文を復号することなくＥ（ｍｉ）（ｉ＝１，・・・，Ｌ）を求める、
ことを特徴とする秘匿計算方法。
【請求項１０】
請求項１から９のいずれか１項に記載の秘匿計算方法において、ｍｉまたはｂｉの少なくとも一方を複数ビットとする、
ことを特徴とする秘匿計算方法。
【請求項１１】
請求項１から１０のいずれか１項に記載の秘匿計算方法を実施することを特徴とする秘匿計算装置。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２００７−１１４４９４（Ｐ２００７−１１４４９４Ａ）
【公開日】平成１９年５月１０日（２００７．５．１０）
【国際特許分類】
【出願番号】特願２００５−３０５９６５（Ｐ２００５−３０５９６５）
【出願日】平成１７年１０月２０日（２００５．１０．２０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１９年５月１０日（２００７．５．１０）
【国際特許分類】
【出願日】平成１７年１０月２０日（２００５．１０．２０）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]