(57)【特許請求の範囲】
【請求項１】
暗号変換装置を用いて、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）についてａiを明かすことなく、ある準同型暗号Ｅにより暗号化した暗号文Ｅ（ａ）から、別の準同型暗号Ｅ’によりビットごとに暗号化した暗号文Ｅ’（ａm-1），・・・，Ｅ’（ａ0）を求める暗号変換方法であって、
暗号変換装置は、
Ｅ（ａ）から、ａを乱数ｒを用いてかく乱した値ｙの暗号文Ｅ（ｙ）を求めるステップと、
Ｅ（ｙ）を復号することでyを求めるステップと、
ｉ＝０，・・・，ｍ−１について、
乱数ビットr iをＥ’で暗号化してＥ’（ｒi）を求めるステップと、
Ｅ’（ｒi）とｙのi位ビットから、準同型暗号の特性を利用してＥ’（ａi）を求めるステップと
を含むことを特徴とする暗号変換方法。
【請求項２】
公開演算装置、暗号化乱数生成装置及び復号装置を用いて、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）についてａiを明かすことなく、ある準同型暗号Ｅにより暗号化した暗号文Ｅ（ａ）から、別の準同型暗号Ｅ’により暗号化した暗号文Ｅ’（ａ0）を求める暗号変換方法であって、
暗号化乱数生成装置は、乱数ビットｒ0の暗号文Ｅ（ｒ0），Ｅ’（ｒ0）、及び、０以上２m＋k未満（ｋは適当な自然数）の乱数ｓの暗号文Ｅ（ｓ）を生成し、
公開演算装置は、Ｅ（ａ），Ｅ（ｒ0），Ｅ（ｓ）を入力として、ａを乱数ビットｒ0とｓでマスクした値ｙの暗号Ｅ（ｙ）を計算し、
復号装置は、Ｅ（ｙ）を入力してｙを復号し、
公開演算装置は、Ｅ’（ｒ0）及びｙの最下位ビットｙ0を入力として、準同型暗号の特性を利用してｙ０からマスクｒ０を除去した値であるａ0の暗号文Ｅ’（ａ0）
を計算する、
ことを特徴とする暗号変換方法。
【請求項３】
公開演算装置、暗号化乱数生成装置、復号装置及び秘匿論理演算装置を用いて、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）についてａiを明かすことなく、ある準同型暗号Ｅにより暗号化した暗号文Ｅ（ａ）から、別の準同型暗号Ｅ’によりビットごとに暗号化した暗号文（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を求める暗号変換方法であって、
暗号化乱数生成装置は、乱数ビット（ｒm-1，・・・，ｒ0）の暗号文Ｂ＝（Ｅ（ｒm-1），・・・，Ｅ（ｒ0）），Ｃ＝（Ｅ’（ｒm-1），・・・，Ｅ’（ｒ0））、及び０以上２m+k未満の乱数ｓの暗号文Ｅ（ｓ）を生成し、
公開演算装置は、Ｅ（ａ），Ｂ，Ｅ（ｓ）を入力として、ａを乱数ｒとsでマスクした値ｙの暗号Ｅ（ｙ）を計算し、
復号装置は、Ｅ（ｙ）を入力して、ｙを復号し、
公開演算装置は、Ｃ中のＥ’（ｒ0）及びｙの最下位ビットｙ0を入力として、準同型暗号の特性を利用してｙ０のマスクｒ０を除去した値であるａ0の暗号文Ｅ’（ａ0）
及びｒ0，ｙ0のキャリーＥ’（ｃ1）を計算し、
秘匿論理演算装置は、ｉ＝１，・・・，ｍ−１について、Ｅ’（ｒi），ｙi、及びキャリーＥ’（ｃi）を入力として、ｙｉからマスクｒｉを除去した値にキャリーを加算した値であるａｉの暗号文Ｅ’（ａi）及び、ｒi，ｙiのキャリーＥ’（ｃｉ＋１）をｒｉ、ｙｉ、ｃｉから求めること
を繰り返す、
ことを特徴とする暗号変換方法。
【請求項４】
暗号変換装置を用いて、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）についてａiを明かすことなく、ある準同型暗号Ｅにより暗号化した暗号文Ｅ（ａm-1），・・・，（ａ0）から、別の準同型暗号Ｅ’により暗号化した暗号文Ｅ’（ａm-1），・・・，Ｅ’（ａ0）を求める暗号変換方法であって、
暗号変換装置は、
ｉ＝０，・・・，ｍ−１について、
Ｅ（ａi）に対して乱数ビットでマスクした暗号文を求めるステップと、
マスクした暗号文を復号するステップと、
前記復号した結果をＥ’により暗号化するステップと、
前記Ｅ’で暗号化された結果から乱数のマスクを除去してＥ’（ａi）を求めるステップ
を含むことを特徴とする暗号変換方法。
【請求項５】
公開演算装置、暗号化乱数生成装置及び復号装置を用いて、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）についてａiを明かすことなく、ある準同型暗号Ｅによりビットごとに暗号化した暗号文Ａ＝（Ｅ（ａm-1），・・・，（ａ0））から、別の準同型暗号Ｅ’によりビットごとに暗号化した暗号文Ｄ＝（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を求める暗号変換方法であって、
置換装置は、Ａを入力して、乱数ｒのビット（ｒm-1，・・・，ｒ0）に基づき、
ｉ＝０，・・・，ｍ−１についてａのビットａｉを乱数ビットｒｉでマスクしたビットの暗号文Ｅの列Ｂ
及び、乱数ビットの暗号文Ｒ＝（Ｅ’（ｒm-1），・・・，Ｅ’（ｒ0））を生成し、
復号装置は、Ｂを入力して、復号処理を行い、
ｉ＝０，・・・，ｍ−１についてａのビットａｉを乱数ビットｒｉでマスクしたビットの列Ｃ
を取得し、
公開演算装置は、Ｃ及びＲを入力として、
ｉ＝０，・・・，ｍ−１についてＣのビットからマスクｒｉを除去したビットであるａｉの暗号文Ｅ’の列Ｄ
を計算する、
ことを特徴とする暗号変換方法。
【請求項６】
請求項４乃至５の何れか１項に記載の暗号変換方法において、秘匿計算装置により、数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）について、準同型暗号Ｅで暗号化した暗号文Ｅ（ａ）に対して、ビットごとに暗号化した暗号文Ａ＝（Ｅ（ａm-1），・・・，（ａ0））を生成することを特徴とする暗号変換方法。
【請求項７】
請求項１乃至６の何れか１項に記載の暗号変換方法において、
検証装置により、準同型暗号Ｅ，Ｅ’で同一のビットｂを暗号化したＥ（ｂ），Ｅ’（ｂ）の復号結果が等しいビットであることをゼロ知識証明することを特徴とする暗号変換方法。
【請求項８】
請求項１乃至７の何れか１項に記載の暗号変換方法において、
準同型暗号ＥはＰaillier暗号、準同型暗号Ｅ’は加法準同型ＥlＧamal暗号であることとを特徴とする暗号変換方法。
【請求項９】
請求項１乃至８のいずれか１項に記載の暗号変換方法を適用してなる暗号変換装置。
【請求項１０】
請求項１乃至８のいずれか１項に記載の暗号変換方法を実行するためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関するものであり、特に暗号文を入力として平文を明かすことなく別の暗号化関数を用いた暗号文に変換する技術に関する。
【背景技術】
【０００２】
従来技術として、ある暗号化関数（準同型暗号）Ｅによって暗号化された数値に対して、当該数値を明かすことなく、当該数値をビット毎に同じ暗号化関数Ｅを用いて暗号化する方法（以下、方法１）が提案されている（非特許文献１）。
【０００３】
一方、数値をビット毎に暗号化することで、任意の論理演算についてデータを明かすことなく実行可能とする方法（秘匿回路計算）が多数報告されている（例えば、非特許文献２、３）。従って、方法１を用いれば、数値の暗号文を入力として秘匿回路計算が実行できるようになる。これにより、秘匿回路計算の入力を提供する装置（入力提供装置）は、ビット毎の暗号文を計算、保存する必要はなく、数値の暗号文のみ計算、保存すれば良くなるため、入力提供装置が計算資源やメモリ資源に乏しい場合の秘匿回路計算に有効となる。
【０００４】
【非特許文献１】B.Schoenmakers  and  P.Tuyls．Effcient  binary  conversion  for  Paillier  encrypted  values，Advances  in  Cryptology-EUROCRYPT  2006，Lecture  Notes  in  Computer  Science  4004，pp.522-537，Springer-Verlag，2006.
【非特許文献２】R.Cramer，I.Damgard，and  J.B.Nielsen，Multiparty  computation  from  threshold  homomorphic  encryption，Advances  in  Cryptology&#8212;EUROCRYPT  2001，Lecture  Notes  in  Computer  Science  2045，pp.280-300，Springer-Verlag，2001.
【非特許文献３】G.Yamamoto，K.Chida，A.Nasciment，K.Suzuki，and  S.Uchiyama，Effcient  non-optimistic  secure  circuit  evaluation  based  on  the  ElGamal  encryption，WISA  2005，Lecture  Notes  in  Computer  Science，pp.328-343，Springer-Verlag，2005.
【発明の開示】
【発明が解決しようとする課題】
【０００５】
準同型暗号を用いた、論理演算における秘匿関数計算は、Ｐaillier暗号に基づく方式と加法準同型ＥlＧamal暗号に基づく方式が知られている。また、加法準同型ＥlＧamal暗号はＰaillier暗号に比べ高速であることが知られている。しかし、加法準同型ＥlＧamal暗号に基づく秘匿関数計算は、一般的な算術演算には適していないことも知られている。
【０００６】
方法１は暗号化関数ＥをＰaillier暗号とした方法である。非特許文献２では、Ｐaillier暗号を用いて、数値を明かすことなく算術演算を実行する方法が示されている。また、非特許文献３では、加法準同型ＥlＧamal暗号を用いて、データを明かすことなくＰaillier暗号を用いた場合よりも効率良く論理演算を実行する方法が示されている。
【０００７】
このように、数値等のデータを明かすことなく算術演算と論理演算を効率良く計算するためには、方法１のようにデータ形式を変換するだけでなく、利用している暗号化関数も変換できることが望ましい場合がある。
【０００８】
本発明が解決しようとする課題は、数値等のデータを明かすことなく、データ形式だけでなくや暗号化関数も変換可能とすることである。
【課題を解決するための手段】
【０００９】
ある準同型暗号Ｅで暗号化された数値に対し、別の準同型暗号Ｅ’で暗号化されたビット毎の値を計算する。即ち、数値をａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）としたとき、Ｅ（ａ）を入力として（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を計算する。例えば、ＥをＰaillier暗号、Ｅ’を加法準同型ＥlＧamal暗号としたとき、非特許文献１の方法でＥ（ａ）からＡ＝（Ｅ（ａm-1），・・・，Ｅ（ａ0））を計算し（ステップ１）、乱数ビットｒm-1，・・・，ｒ0を用いてＡからＢ＝（Ｅ（ａm-1 ｘｏｒ  ｒm-1），・・・，Ｅ（ａ0 ｘｏｒ  ｒ0））を計算し（ステップ２）、Ｂを復号してＣ＝（ａm-1 ｘｏｒ  ｒm-1，・・・，ａ0 ｘｏｒ  ｒ0）を求め（ステップ３）、ＣをＥ’で暗号化してＤ＝（Ｅ’（ａm-1 ｘｏｒ  ｒm-1），・・・，Ｅ’（ａ0 ｘｏｒ  ｒ0））を求め（ステップ４）、Ｄから乱数ビットを除去し（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を得る。なお、ここで発明の詳細な説明における「ｘｏｒ」および図面における「「＋」を「○」で囲った一文字」は排他的論理和を意味する。
これは本発明の一例にすぎず、様々な変形、拡張が考えられる。それらについては実施の形態で説明する。
【発明の効果】
【００１０】
本発明によれば、方法１を用いた場合と比べ、データを明かすことなく算術演算や論理演算の組合せからなる処理を高速に実行することが可能になる。
【発明を実施するための最良の形態】
【００１１】
以下、本発明の様々な実施の形態を説明する。
【実施例１】
【００１２】
本実施例では、ある準同型暗号Ｅ（例えば、Ｐaillier暗号）を用いて数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）を暗号化した暗号文Ｅ（ａ）から、別の準同型暗号Ｅ’（例えば、加法準同型ＥlＧamal暗号）を用いて数値ａの最下位ビットａ0を暗号化した暗号文Ｅ’（ａ0）を計算する簡単な例について説明する。
【００１３】
図１は本実施例の構成図であり、暗号変換装置１００は公開演算装置１１０、暗号化乱数生成装置１２０、復号装置１３０からなる。各装置１１０、１２０、１３０はネットワークを介して接続されることでもよい。公開演算装置１１０は秘密鍵や乱数を一切必要せずに与えられた処理を実行する。そのため他の装置が同一処理を再現し、公開演算装置１１０の処理正当性を検証できる。暗号化乱数生成装置１２０は、指定された領域の乱数を生成して暗号化して出力する。装置から不正に乱数を取り出す攻撃に対して耐性を高めるために、非特許文献１で述べられた方法により、複数の装置が協力して単一の暗号化乱数を生成しても良い。これにより一部の装置の乱数を取り出しても数値ａに関する情報を得にくくできる。復号装置１３０は内部に復号鍵を保持し、暗号文を入力として復号結果を出力する。これも装置から不正に復号鍵を取り出す攻撃に対して耐性を高めるために、複数の装置の鍵を用いて処理した場合に限り復号できるようにしても良い。
【００１４】
図２は本実施例の処理フロー図である。以下、図１、図２により本実施例の処理手続きを説明する。
１．公開演算装置１１０は、ある準同型暗号Ｅを用いて数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）を暗号化した暗号文Ｅ（ａ）を入力する（ステップ１００１）。
２．暗号化乱数生成装置１２０は、乱数ビットｒ0を生成し、準同型暗号Ｅ，Ｅ’により、該乱数ビットｒ0の暗号文Ｅ（ｒ0），Ｅ’（ｒ0）を生成する（ステップ１００２）。また、暗号化乱数生成装置１２０は、０以上２m+k未満の乱数ｓを生成し、準同型暗号Ｅにより、該乱数ｓの暗号文Ｅ（ｓ）を生成する（ステップ１００３）。ここで、ｋは適当な自然数で、セキュリティパラメータを示す。暗号化乱数生成装置１２０は、生成したＥ（ｒ0），Ｅ’（ｒ0），Ｅ（ｓ）を公開演算装置１１０に送る。
３．公開演算装置１１０は、Ｅ（ａ），Ｅ（ｒ0），Ｅ（ｓ）を入力として、Ｅの準同型性を利用してＥ（ｙ）＝Ｅ（ａ＋ｒ0＋２ｓ）を計算し、復号装置１３０に送る（ステップ１００４）。
４．復号装置１３０は、Ｅ（ｙ）を復号し、復号結果ｙ＝ａ＋ｒ0＋２ｓ＝Σi=0m+k２iｙi（ｙi∈｛０，１｝）を公開演算装置１１０に送る（ステップ１００５）。なお、復号装置１３０は、復号結果ｙの最下位ビットｙ0のみを公開演算装置１１０へ送ることでもよい。
５．公開演算装置１１０は、Ｅ’（ｒ0）及び復号結果ｙの最下位ビットｙ0を入力として、
【００１５】
［数１］
Ｅ’（ａ０）＝Ｅ’（ｒ０ ｘｏｒ  ｙ０）＝Ｅ’（ｒ０）      ｉｆ  ｙ０＝０
＝Ｅ’（１−ｒ０）  ｉｆ  ｙ０＝１
を計算し、出力する（ステップ１００６、１００７）。
結果の正当性については、
【００１６】
［数２］
ｙ０＝ａ０ ｘｏｒ  ｒ０
が成り立つことから明らかである。
【実施例２】
【００１７】
本実施例では、実施例１を発展させて、ある準同型暗号Ｅ（例えば、Ｐaillier暗号）を用いて数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）を暗号化した暗号文Ｅ（ａ）から、別の準同型暗号Ｅ’（例えば、加法準同型ＥlＧamal暗号）を用いて数値ａをビット毎に暗号化した暗号文（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を計算する例について説明する。
【００１８】
図３は本実施例の構成図であり、暗号変換装置２００は公開演算装置２１０、暗号化乱数生成装置２２０、復号装置２３０及び秘匿論理演算装置２４０からなる。公開演算装置２１０、暗号化乱数生成装置２２０、復号装置２３０の機能は実施例１と基本的に同様である。秘匿論理演算装置２４０は、複数のビットの暗号文を入力として論理演算結果の暗号文を出力する。装置から不正に乱数や復号鍵といった秘密情報を取り出す攻撃に対して耐性を高めるために、例えば非特許文献２や３で述べられた方法により，複数の装置が協力して、閾値未満の装置の秘密情報を取り出しても数値ａに関する情報を得にくくするように論理演算を計算するようにしても良い。
【００１９】
図４は本実施例の処理フロー図である。以下、図３、図４により本実施例の処理手続きを説明する。
１．公開演算装置２１０は、ある準同型暗号Ｅを用いて数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）を暗号化した暗号文Ｅ（ａ）を入力する（ステップ２００１）。
２．暗号化乱数生成装置２２０は、乱数ビット（ｒm-1，・・・，ｒ0）を生成し、準同型暗号Ｅ，Ｅ’により、該乱数ビットの暗号文Ｂ＝（Ｅ（ｒm-1），・・・，Ｅ（ｒ0）），Ｃ＝（Ｅ’（ｒm-1），・・・，Ｅ’（ｒ0））を生成する（ステップ２００２）。また、暗号化乱数生成装置２２０は、０以上２m+k未満の乱数ｓを生成し、準同型暗号Ｅにより、該乱数ｓの暗号文Ｅ（ｓ）を生成する（ステップ２００３）。ここで、ｋはセキュリティパラメータを示す。暗号化乱数生成装置２２０は、Ｂ，Ｅ（ｓ）及びＣのＥ’（ｒ0）を公開演算装置２１０に送り、Ｅ’（ｒ0）以外のＣを秘匿論理演算装置２４０に送る。
３．公開演算装置２１０は、Ｅ（ａ），Ｂ，Ｅ（ｓ）を入力として、Ｅの準同型性を利用して、Ｅ（ｙ）＝Ｅ（ａ−Σi=0m-1２iｒi−２mｓ）を計算し、復号装置２３０に送る（ステップ２００４）。
４．復号装置２３０は、Ｅ（ｙ）を復号し、復号結果ｙ＝ａ−Σi=0m-1２iｒi−２mｓ＝（−１）cΣi=0m+k２iｙi（ｃ，ｙi∈｛０，１｝）を得る（ステップ２００５）。復号装置２３０は、復号結果ｙの最下位ビットｙ0を公開演算装置２１０に送り、残りのビットは秘匿論理演算装置２４０に送る。
５．公開演算装置２１０は、Ｅ’（ｒ0）及びｙ0を入力として、Ｅ’の準同型性を利用して、
【００２０】
［数３］
Ｅ’（ａ０）＝Ｅ’（ｒ０ ｘｏｒ  ｙ０）
及び、ｒ0，ｙ0のキャリーＥ’（ｃ1）＝Ｅ’（ｒ0∧ｙ0）を計算する（ステップ２００６）。
公開演算装置２１０は、Ｅ’（ａ0）はそのまま出力し（ステップ２００８）、Ｅ’（ｃ1）は秘匿論理演算装置２４０に送る。
６．ｉ＝１，・・・，ｍ−１について、秘匿論理演算装置２４０は、Ｅ’（ｒi），ｙi、及びキャリーＥ’（ｃi）を入力として、
【００２１】
［数４］
Ｅ’（ａｉ）＝Ｅ’（ｒｉ ｘｏｒ  ｙｉ ｘｏｒ  ｃｉ）
及び、ｒi，ｙiのキャリー
【００２２】
［数５］
Ｅ’（ｃｉ＋１）＝Ｅ’（（（ｒｉ ｘｏｒ  ｙｉ）∧ｃｉ）∨（ｒｉ∧ｙｉ））
を生成する処理を繰り返す（ステップ２００７）。なお、ｉ＝ｍ−１であれば、キャリーの生成は不要である。
７．秘匿論理演算装置２４０は、Ｅ’（ａi）（ｉ＝１，・・・，ｍ−１）を出力する（ステップ２００８）。
【００２３】
本実施例の拡張として、暗号化乱数生成装置２２０はｔ台とし、０以上２m+k未満の乱数の暗号文Ｅ（ｓj）（ｊ＝１，・・・，ｔ）を生成するようにしてもよい。この場合、公開演算装置２１０はＥ（ａ），Ｂ，Ｅ（ｓj）からＥ（ｙ）＝Ｅ（ａ−Σi=0m-1２iｒi−２mΣi=1tｓj）を計算する。復号装置２３０は、復号結果ｙ＝ａ−Σi=0m-1２iｒi−２mΣi=1tｓjを得る。
【実施例３】
【００２４】
本実施例では、ある準同型暗号Ｅ（例えば、Ｐaillier暗号）を用いて数値ａ＝Σi=0m-1２iａi（ａi∈｛０，１｝）を暗号化した暗号文Ｅ（ａ）に対して、ビットごとに暗号化した暗号文（Ｅ（ａm-1），・・・，Ｅ（ａ0））から、別の準同型暗号Ｅ’（例えば、加法準同型ＥlＧamal暗号）を用いて同じくビット毎に暗号化した暗号文（Ｅ’（ａm-1），・・・，Ｅ’（ａ0））を計算する例について説明する。Ｅ（ａ）から（Ｅ（ａm-1），・・・，Ｅ（ａ0））を計算する方法は非特許文献１に述べられている（方法１）。即ち、本実施例では、Ｅ（ａ）から（Ｅ（ａm-1），・・・，Ｅ（ａ0））は秘匿計算装置を用いて計算済みであるとする。
【００２５】
図５は本実施例の構成図であり、暗号変換装置３００は公開演算装置３１０、置換装置３２０、復号装置３３０からなる。公開演算装置３１０、復号装置３３０の機能は実施例１と基本的に同様である。置換装置３２０は、ビットの暗号文Ｅ（ａi）を入力として当該ビットを確率的に反転し、反転情報の暗号文と共に出力する。装置から不正に反転情報を取り出す攻撃に対して耐性を高めるために、複数の装置が多重に処理を行うようにしても良い。
【００２６】
図６は本実施例の処理フロー図である。以下、図５、図６により本実施例の処理手続を説明する。
１．置換装置３２０は、Ａ＝（Ｅ(ａm-1),・・・,Ｅ(ａ0)）を入力する（ステップ３００１）。
２．置換装置３２０は、乱数ビット（ｒm-1，・・・，ｒ0）を生成して、該乱数ビットに基づき、Ａの置換結果、
【００２７】
［数６］
Ｂ＝（Ｅ（ａｍ−１ ｘｏｒ  ｒｍ−１），・・・，Ｅ（ａ０ ｘｏｒ  ｒ０）
及び、準同型暗号Ｅ’により乱数ビットの暗号文Ｒ＝（Ｅ’（ｒm-1），・・・，Ｅ’（ｒ0））を計算する（ステップ３００２）。置換装置３２０は、Ｒを公開演算装置３１０に送り、Ｂを復号装置３３０に送る。
３．復号装置３３０は、Ｂを復号し、復号結果、
【００２８】
［数７］
Ｃ＝（ａｍ−１ ｘｏｒ  ｒｍ−１，・・・，ａ０ ｘｏｒ  ｒ０）
を公開演算装置３１０に送る（ステップ３００３）。
４．公開演算装置３１０は、Ｃ及びＲを入力として、Ｅ’の準同型性を利用し、
【００２９】
［数８］
Ｄ＝（Ｅ’（ｒｍ−１ ｘｏｒ  ａｍ−１ ｘｏｒ  ｒｍ−１），・・・，Ｅ‘（ｒ０ ｘｏｒ  ａ０ ｘｏｒ  ｒ０）
＝（Ｅ’（ａｍ−１），・・・，Ｅ’（ａ０））
を計算し、出力する（ステップ３００４，３００５）。
【実施例４】
【００３０】
今までの実施例では、公開演算装置以外の装置については不正処理を検出できない場合がある。そのため、不正処理を通じて数値ａに関する情報を不当に引き出される恐れがある。そこで本実施例では、不正処理を検出した時点で処理を直ちに中止、中断することで、数値ａに関する情報の不当な引き出しを防ぐことを目的として、装置の不正処理を検出する方法について説明する。システム構成は、図１乃至図３の構成に検証装置が追加されるだけであるため省略する。
【００３１】
復号結果については処理正当性をゼロ知識証明する方法が幾つか知られており、非特許文献２や３でも述べられているため、復号装置の不正処理検出方法は説明を省略する。また論理演算結果についても同様に、処理正当性をゼロ知識証明する方法が非特許文献２や３で述べられているため、秘匿論理演算装置の不正処理検出方法も説明を省略する。
【００３２】
以下では、暗号乱数ビットＥ（ｒi），Ｅ’（ｒi）など、実施例１〜３で必要となる、異なる暗号化関数Ｅ，Ｅ’を用いて同一のビットを暗号化したことを、当該ビットを明かすことなく示す方法について説明する。即ち、ビットｂに対して、Ｅ（ｂ），Ｅ’（ｂ）の復号結果が等しいビットである事をゼロ知識証明する。
【００３３】
二通りのアプローチが考えられ、一つは非特許文献４で提案されている“Ｐartial  Ｐroof”を用いて、
（（Ｅ（ｂ）＝Ｅ（０））∧（Ｅ’（ｂ）＝Ｅ’（０）））∨（（Ｅ（ｂ）＝Ｅ（１））∧（Ｅ’（ｂ）＝Ｅ’（１）））
であることをｂを明かさずに証明する．
【００３４】
【非特許文献４】R．Cramer，I．Damgard，and  B．Schoenmakers，Proofs  of  partial  knowledge  and  simplified  design  of  witness  hiding  protocols，Advances  in  Cryptology−CRYPTO  ’94，Lecture  Notes  in  Computer  Science  839，pp．171−181，Springer−Verlag，1994．
【００３５】
もう一つは、ビットコミットメントと呼ばれる技術を用いてｂのコミットメントＣｏｍｍ（ｂ）を生成し、ｂがビットである事をゼロ知識証明すると同時に、コミットメントしているｂがＥ（ｂ），Ｅ’（ｂ）の復号結果と等しい事をｂを明かさずに証明する。
何れも既存技術の組合せで実現可能であるが、本実施例では前者のアプローチについて、ＥをＰaillier暗号、Ｅ’を加法準同型ＥlＧamal暗号とした場合の具体的な手続きを示す。
［記号の意味］
【００３６】
【数９】
0005578754.tif 000002
【００３７】
【数１０】
0005578754.tif 000003
検証装置は以下が成り立つか検証する。
【００３８】
【数１１】
0005578754.tif 000004
ここで、
【００３９】
【数１２】
0005578754.tif 000005
【００４０】
また、実施例１、３で必要となる、データｓが一定の範囲の値である事を証明する方法は、非特許文献１で述べられているため説明を省略する。
以上により、暗号化乱数生成装置及び置換装置が不正処理を行った場合にそれを検出できるようになる。
【実施例５】
【００４１】
本実施例では、前に述べた実施例の方法を用いて、データを明かすことなく算術演算と論理演算が混在する計算を行う例について説明する。このような例として統計処理が挙げられる。
【００４２】
ここでは、ある設問にｄ個の選択肢があるとし，選択肢毎にＹｅｓ→１，Ｎｏ→０とする。そしてＹｅｓを選択した回答者が最も多かった選択肢を求める事を考える。
回答者（回答者装置）Ｒiはｄ個の暗号文（Ｅ（ｂi,1），・・・，Ｅ（ｂi,d））（ｂi,j∈｛０，１｝）を回答として集計者（集計者装置）に送信する。
集計者は、Ｅの準同型性を利用して
（Ｅ（Ａ1），・・・，Ｅ（Ａd）＝（Ｅ（Σiｂi,1），・・・，Ｅ（Σiｂi,d））
を計算する。
次に、Ｅ（Ａj）（ｊ＝１，・・・，ｄ）について、実施例２や３等で示した方法を用いて
Ｘj＝（Ｅ’（ａj,m-1），・・・，Ｅ’（ａj,0））
を得る。但し、Ａj＝Σi=0m-1２iａj,i（ａj,i∈｛０，１｝）。
最終的に，Ｘj（ｊ＝１，・・・，ｄ）を入力とした、大小比較回路の秘匿回路計算を実行し、Ｘjが最大となるｊを得る。
ここで、例えば選択肢を選挙立候補者とすれば、最多票を獲得した立候補者のみ知る事のできる投票システムが実現される。
【００４３】
次に、Ｘ2の検定について説明する。
観測度数ｆiの期待値をｅiで表すとき、暗号化された観測度数Ｅ（ｆi）とｅiを用いて、データを明かすことなく算術演算を行い、
【００４４】
【数１３】
0005578754.tif 000006
をΠi=0lｅi倍した値の暗号文Ｅ（Ａ）＝Ｅ（Ｘ2Πi=0lｅi）を生成する。
【００４５】
次に、Ｅ（Ａ）について、実施例２や３等で示した方法を用いて
Ｘ＝（Ｅ（ａm-1，・・・，Ｅ（ａ0））
を得る。但し、Ａ＝Σi=0m-1２iａi（ａj∈｛０，１｝）。
【００４６】
最終的に、Ｅ（Ａ），Πi=0lｅi、及び棄却限界値Ｌを入力とした、大小比較回路の秘匿回路計算を実行し、Ｘ2が棄却域にあるかどうか判定する。
【００４７】
なお、図１、図３、図５等で示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図２、図４、図６等で示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００４８】
【図１】本発明の実施例１の構成図。
【図２】本発明の実施例１の処理フロー図。
【図３】本発明の実施例２の構成図。
【図４】本発明の実施例２の処理フロー図。
【図５】本発明の実施例３の構成図。
【図６】本発明の実施例３の処理フロー図。
【符号の説明】
【００４９】
１１０、２１０、３１０  公開演算装置
１２０、２２０          暗号化乱数生成装置
１３０、２３０、３３０  復号装置
２４０                  秘匿論理演算装置
３２０                  置換装置
【図１】
0005578754.tif 000007
【図２】
0005578754.tif 000008
【図３】
0005578754.tif 000009
【図４】
0005578754.tif 000010
【図５】
0005578754.tif 000011
【図６】
0005578754.tif 000012