(57)【要約】      （修正有）【課題】秘匿回路計算を用いて入力データを明かすことなく関数計算する場合の計算量削減を実現する。【解決手段】ｎ個の数値の集合Ｘ＝（ｘ1，・・・，ｘn）の暗号文Ｚ＝（Ｅ（ｘ1，ｒ1），・・・，Ｅ（ｘn，ｒn））（Ｅ：暗号化関数、ｒi：乱数）を入力として、Ｘの要素を秘匿したまま計算することを考える。このとき、本発明では、以下に基づいた計算を行う。１．集合｛１，・・・，ｎ｝の置換π及びＥの再暗号化により、2008176193.tif 000015を計算し（ｒi’：乱数）、暗号文Ｚの代わりに攪拌した暗号文Ｚ’を比較器ネットワークの入力とする（ステップ１）。２．各比較器を論理式表現し、入力の暗号文Ｚに対応する平文の大小関係を既存の秘匿回路計算を用いて求める（ステップ２）。【選択図】図４
2008176193.tif 000002
【特許請求の範囲】
【請求項１】
ｎ個の数値の集合Ｘ＝（ｘ1，・・・，ｘn）の暗号文Ｚ＝（Ｅ（ｘ1，ｒ1），・・・，Ｅ（ｘn，ｒn））（Ｅ：暗号化関数、ｒi：乱数）を比較器ネットワークの入力として、Ｘの要素を秘匿したまま論理演算を行う秘匿関数計算方法であって、
集合｛１，・・・，ｎ｝の置換πを選び暗号文Ｚに適用し、Ｚの要素毎に再暗号化した暗号文
【数１】
2008176193.tif 000011
を計算して、暗号文Ｚの代わりにＺを比較器ネットワークの入力とし、
比較器ネットワークは入力の暗号文に対応する平文の大小関係を平文の情報を漏らすことなく求める、
ことを特徴とする秘匿関数計算方法。
【請求項２】
請求項１記載の秘匿関数計算方法において、
暗号置換装置、公開演算装置、秘匿論理演算装置及び復号装置を用い、
暗号置換装置は、ｎ個の０以上２l未満の整数の集合Ｘ＝（ｘ1，・・・，ｘn）（ここで、ｘi＝Σj=0l-1２jｘi,j（ｘi,j∈｛０，１｝）の暗号文Ｚ＝（ｚ1，・・・，ｚn）（ここで、ｚi＝（Ｅ（ｘi,l-1,ｒi,l-1），・・・，Ｅ（ｘi,0,ｒi,0）））を入力し、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素毎に再暗号化した
【数２】
2008176193.tif 000012
を計算して出力し、
公開演算装置、秘匿論理演算装置及び復号装置は、ｉ＝１，・・・，ｎ−１の順に、
（ａ）秘匿論理演算装置は、ｚi’，ｚi+1’を入力として、大小比較論理演算をｚi’，ｚi+1’の平文の情報を漏らすことなく実行して、実行結果Ｅ（Ｂ，ｒ）を出力する、
（ｂ）復号装置は、Ｅ（Ｂ，ｒ）を入力して復号し、復号結果Ｂを出力する、
（ｃ）公開演算装置は、Ｂ＝１であればｚi’を大きい方の値の暗号文として、ｚi+1’←ｚi’としてｚi+1’を出力し、Ｂ＝０であればｚi+1’を大きい方の値の暗号文としてｚi+1’をそのまま出力する、
処理を繰り返し、
公開演算装置は、ｉ＝ｎで、ｚn’←ｚi+1’としてｚn’を出力し、復号装置はｚn’を入力して復号し、当該復号結果を出力する、
ことを特徴とする秘匿関数計算方法。
【請求項３】
請求項１記載の秘匿関数計算方法において、
暗号置換装置、公開演算装置、秘匿論理演算装置、復号装置及び暗号化乱数乗算装置を用い、
暗号置換装置は、ｎ個の０以上２l未満の整数の集合Ｘ＝（ｘ1，・・・，ｘn）（ここで、ｘi＝Σj=0l-1２jｘi,j（ｘi,j∈｛０，１｝）の暗号文Ｚ＝（ｚ1，・・・，ｚn）（ここで、ｚi＝（Ｅ（ｘi,l-1,ｒi,l-1），・・・，Ｅ（ｘi,0,ｒi,0）））を入力し、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素毎に再暗号化した
【数３】
2008176193.tif 000013
を計算して出力し、
公開演算装置、秘匿論理演算装置、復号装置及び暗号化乱数乗算装置は、ｉ＝１，・・・，ｎ−１の順に、
（ａ）秘匿論理演算装置は、ｚi’，ｚi+1’を入力として、大小比較論理演算をｚi’，ｚi+1’の平文の情報を漏らすことなく実行して、実行結果Ｇ＝（Ｅ（Ｂl-1，ｓl-1），・・・，（Ｅ（Ｂ0，ｓ0）を出力する、
（ｂ）公開演算装置は、Ｇを入力として、Ｅの準同型性を利用してＥ（Σi=0l-1Ｂi，ｓ）（ここで、ｓは適当な乱数）を計算して出力する、
（ｃ）暗号化乱数乗算装置は、Ｅ（Σi=0l-1Ｂi，ｓ）を入力として、乱数ｗを生成して、Ｅの準同型性を利用してＥ（ｗΣi=0l-1Ｂi，ｓ’）を計算して出力する、
（ｄ）復号装置は、Ｅ（ｗΣi=0l-1Ｂi，ｓ’）を入力して復号し、復号結果Ｂ’＝ｗΣi=0l-1Ｂiを出力する、
（ｅ）  公開演算装置は、Ｂ’≠０であれば、ｚi’を大きい方の値の暗号文としてｚi+1’←ｚi’としてｚi+1’を出力し、Ｂ’＝０であればｚi+1’を大きい方の値の暗号文として、ｚi+1’をそのまま出力する、
処理を繰り返し、
公開演算装置は、ｉ＝ｎで、ｚn’←ｚi+1’としてｚn’を出力し、復号装置はｚn’を入力して復号し、当該復号結果を出力する、
ことを特徴とする秘匿関数計算方法。
【請求項４】
請求項１記載の秘匿関数計算方法において、
暗号置換装置、公開演算装置、秘匿論理演算装置、復号装置及び暗号化乱数生成装置を用い、
暗号化乱数生成装置は、乱数ビットｂを生成し、それを暗号化したデータＥ（ｂ，ｒb）（ここで、ｒbは乱数）を計算して出力し、
暗号置換装置は、ｎ個の０以上２l未満の整数の集合Ｘ＝（ｘ1，・・・，ｘn）（ここで、ｘi＝Σj=0l-1２jｘi,j（ｘi,j∈｛０，１｝）の暗号文Ｚ＝（ｚ1，・・・，ｚn）（ここで、ｚi＝（Ｅ（ｘi,l-1,ｒi,l-1），・・・，Ｅ（ｘi,0,ｒi,0）））を入力し、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素毎に再暗号化した
【数４】
2008176193.tif 000014
を計算して出力し、
公開演算装置、秘匿論理演算装置及び復号装置は、ｉ＝１，・・・，ｎ−１の順に、
（ａ）秘匿論理演算装置は、ｚi’，ｚi+1’を入力として、大小比較論理演算をｚi’，ｚi+1’の平文の情報を漏らすことなく実行して、実行結果Ｇ＝（Ｅ（Ｂ，ｒ）およびＡの暗号文を得る、
（ｂ）秘匿論理演算装置は、Ｅ（Ｂ，ｒ），Ｅ（Ｂ，ｒb）、およびＡの暗号文を入力として、Ｂ∨（ｂ∧Ａ）の暗号文Ｃを計算して出力する、
（ｃ）復号装置は、Ｃを入力して復号し、復号結果Ｂ”＝Ｂ∨（ｂ∧Ａ）を出力する、
（ｄ）  公開演算装置は、Ｂ”＝１であれば、ｚi’を大きい方の値の暗号文としてｚi+1’←ｚi’としてｚi+1’を出力し、Ｂ”＝０であればｚi+1’を大きい方の値の暗号文としてｚi+1’をそのまま出力する、
処理を繰り返し、
公開演算装置は、ｉ＝ｎで、ｚn’←ｚi+1’としてｚn’を出力し、復号装置はｚn’を入力して復号し、当該復号結果を出力する、
ことを特徴とする秘匿関数計算方法。
【請求項５】
請求項１記載の秘匿関数計算方法において、比較器ネットワークの各比較器の入力の片方の数値のみ秘匿にすることを特徴とする秘匿関数計算方法。
【請求項６】
請求項１乃至５のいずれか１項に記載の秘匿関数計算方法を使用していることを特徴とする秘匿関数計算装置。
【請求項７】
請求項１乃至５のいずれか１項に記載の秘匿関数計算方法をコンピュータに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号応用技術に関するものであり、特に入力データを明かすことなく関数計算を行う技術に関する。
【背景技術】
【０００２】
入力データを秘匿したまま論理演算を行う方法は秘匿回路計算と呼ばれる。計算対象の関数を論理式で表現し、その論理式にしたがって秘匿回路計算を実行することで、入力データを秘匿したまま関数計算できるようになる。適用例として、計算対象の関数を統計演算とし、プライバシ保護の観点から、個人のデータは秘匿したまま統計データのみ得るといった方法が挙げられる。
【０００３】
非特許文献１では、加法準同型ＥlＧamal暗号を用いて入力データを明かすことなく論理演算を行う技術が提案されている。本技術を用いて、例えばｍ個の数値の集合Ａ＝（ａ1，・・・，ａm）に対して、Ａの要素を明かすことなくＡをソートすることができる。
【０００４】
【非特許文献１】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．
【発明の開示】
【発明が解決しようとする課題】
【０００５】
秘匿回路計算は論理素子毎に膨大な計算が必要となり、対象の関数について秘匿回路計算を用いて入力データを秘匿したまま計算するためには，秘匿しない場合と比べてはるかに処理時間がかかってしまう。
【０００６】
このような状況を踏まえ、本発明が解決しようとする課題は、統計処理に必要ないくつかの演算を効率良く計算できる比較器ネットワークに着目し、単純に比較器ネットワークを論理式で表現し秘匿回路計算を実行するよりも高速に計算する方法及び装置、並びにプログラムを提供することである。
【課題を解決するための手段】
【０００７】
ｎ個の数値の集合Ｘ＝（ｘ1，・・・，ｘn）の暗号文Ｚ＝（Ｅ（ｘ1，ｒ1），・・・，Ｅ（ｘn，ｒn））（Ｅ：暗号化関数、ｒi：乱数）を比較器ネットワークの入力として、Ｘの要素を秘匿したまま計算することを考える。このとき、本発明では、以下に基づいた計算を行う。
１．集合｛１，・・・，ｎ｝の置換π及びＥの再暗号化により、
【０００８】
【数１】
2008176193.tif 000003
を計算し（ｒi’：乱数）、暗号文Ｚの代わりに攪拌した暗号文Ｚ’を比較器ネットワークの入力とする（ステップ１）。
２．各比較器を論理式表現し、入力の暗号文Ｚに対応する平文の大小関係を既存の秘匿回路計算を用いて求める（ステップ２）。
【発明の効果】
【０００９】
通常の比較器の処理は、二つの値を入力し、昇順に並び替えて出力する。すなわち、入力の大小関係が露呈し、入力の秘匿性は保たれない。そのため入力の大小関係を秘匿回路計算により秘匿する必要が生じる。これに対し、ステップ１の攪拌計算は比較器ネットワークの入力の匿名化処理であり、これにより、たとえ比較器の入力の大小関係が露呈しても、集合Ｘの要素の大小関係は露呈せず、入力の秘匿性は保たれる。すなわち、入力の大小関係を秘匿回路計算により秘匿する必要はなく、この差異が処理削減につながる。したがって、当該削減効果がステップ１の攪拌計算を上回れば、単純に比較器ネットワークを論理式で表現し秘匿回路計算を実行するよりも高速に計算できることが期待できる。当該削減効果は比較器ネットワークを構成する比較器の個数に比例して増大するが、ステップ１の攪拌計算は比較器の個数とは基本的に独立である。そのため、比較器ネットワークの構成によっては既存の秘匿回路計算を単純に用いた解決方法よりも本発明が優位に成り得る。
【発明を実施するための最良の形態】
【００１０】
以下、本発明の実施の形態について図面を用いて説明する。
【００１１】
本発明は比較器ネットワーク（Comparator  Network）を用いる。比較器ネットワークは、各入力値に対応した直線と、そのうちの２つを結ぶ幾つかの比較器によって構成され、そのネットワークを通じて目的の値を出力する。例えば、入力値を昇順にソート（ソーティングネットワーク）することや、入力の中からｔ番目に大きな値を出力（セレクションネットワーク）することができる。
【００１２】
図１に７入力のソーティングネットワークの例を示す。ここで（ｘ1，・・・，ｘ7）が入力、（ｙ1，・・・，ｙ7）が出力であり、ｙi≦ｙi+1（ｉ＝１，・・・，７）となる。図１の各縦棒が比較器を意味する。すなわち、図１において、各データは横線に沿って左から右に流れ，横線と交わる各比較器は左から流れる二データを入力として、小さい方の値を右側の上位の横線に出力し、大きい方の値を右側の下位の横線に出力する。例えば、比較器ａでは、ｘ2，ｘ3を入力として、両者の小さい方の値ｍｉｎ（ｘ2，ｘ3）が上の線に、大きい方の値ｍａｘ（ｘ2，ｘ3）が下の線に出力することを示している。図１ではｘ2，ｘ3を入力とした比較器ａの出力のみ明記しているが，各比較器において同様の出力がなされ、最終的に出力ｙ1，・・・，ｙ7は、ｙ1≦ｙ2≦・・・≦ｙ7を満たす。
【００１３】
比較器の構成については、例えば、非特許文献２に示されている。ここでは、それをもとに比較器の大小比較論理演算アルゴリズムについて説明する。
【００１４】
【非特許文献２】K．Kurosawa  and  W．Ogata，Bit-slice  auction  circuit，ESORICS  2002，Lecture  Notes  in  Computer  Science  2502，pp．24-38，Springer-Verlag，2002．
【００１５】
比較器の論理演算の例が非特許文献２で次のように与えられている。
先ず準備として、ｘ，ｙ∈｛０，１｝を入力とした大小比較関数Ｂigger1（ｘ，ｙ）及び等号判定関数ＥＱ1（ｘ，ｙ）を次のように定義する。
【００１６】
【数２】
2008176193.tif 000004
ここで、
【００１７】
【数３】
2008176193.tif 000005
が成り立つ。
次に０以上２l未満の整数Ｘ，Ｙを入力とした大小比較関数
【００１８】
【数４】
2008176193.tif 000006
の論理演算を考える。
Ｘ＝Σi=0l-1２iｘi，Ｙ＝Σi=0l-1２iｙi（ｘi，ｙi∈｛０，１｝）としたとき、（ｘl−1，・・・，ｘ0），（ｙl−1，・・・，ｙ0）を入力して以下の大小比較論理演算アルゴリズムを実行する。
【００１９】
［大小比較論理演算アルゴリズム］
１．Ａ←１，Ｂ←Ｂigger1（ｘl−1，ｙl−1）とする。
２．ｉ＝ｌ−１，・・・，１の順にＡ←Ａ∧ＥＱ1（ｘi，ｙi），Ｂ←Ｂ∨（Ｂigger1（ｘi−1，ｙi−1）∧Ａ）を計算する。
３．ｉ＝０，１，・・・，ｌ−１について、
【００２０】
【数５】
2008176193.tif 000007
を計算して出力する。
上記アルゴリズムについて、Ｂiggerl（Ｘ，Ｙ）＝Σi=0l-1２iｚiが成り立つ。
【００２１】
なお、本発明は比較器ネットワークの構成には依らず、任意の比較器ネットワークに適用可能である。その理由は、本発明では入力を秘匿したまま比較器ネットワークの計算を行うための計算量削減手法として、（１）入力の各暗号文に対して一度だけ再暗号化処理および置換処理を実行、（２）比較器ネットワークを構成する各比較器の計算方法として、入力を昇順に並び替える論理式を計算する代わりに、入力の大小関係を求める論理式を計算、することを特徴としており，これらは比較器ネットワークの構成に依らず一定の処理となるためである。
【実施例１】
【００２２】
本実施例では、図２に示すように、最大値を求める単純な比較器ネットワークを例に、ｎ個の０以上２l未満の整数の集合Ｘ＝（ｘ1，・・・，ｘn）（ここで、ｘi＝Σj=0l-1２jｘi，j∈｛０，１｝）から、Ｘの要素を秘匿したままＸの最大値ｘkを求める方法について説明する。
【００２３】
図３は、本実施例の構成図であり、秘匿関数計算装置１００は、公開演算装置１１０、暗号置換装置１２０、秘匿論理演算装置１３０及び復号装置１４０によって構成される。ここで、公開演算装置１１０と秘匿論理演算装置１３０と復号装置１４０が比較器ネットワークを構成している。各装置１１０〜１４０は一体的に構成するか、あるいはネットワークを通して接続するか、いづれでもよい。公開演算装置１１０は秘密鍵や乱数を一切必要せずに与えられた処理を実行する。そのため他の装置が同一処理を再現し、公開演算装置１１０の処理正当性を検証できる。暗号置換装置１２０は、複数の暗号文を入力として、置換及び再暗号化して出力する。装置から不正に置換情報や再暗号化（攪拌）に用いた乱数を取り出す攻撃に対して耐性を高めるために装置を多重化しても良い。秘匿論理演算装置１３０は、複数のビットの暗号文を入力として論理演算結果の暗号文を出力する。装置から不正に乱数や復号鍵といった秘密情報を取り出す攻撃に対して耐性を高めるために、例えば非特許文献１で提案されている方法により、複数の装置が協力して、閾値未満の装置の秘密情報を取り出しても平文ビットに関する情報を得にくくするように論理演算を計算するようにしても良い。復号装置１４０は、内部に復号鍵を保持し、暗号文を入力として復号結果を出力する。これも、装置から不正に復号鍵を取り出す攻撃に対して耐性を高めるために、複数の装置が協力した場合に限り復号できるようにしても良い。
【００２４】
図４は本実施例の処理フロー図である。以下、図３、図４により本実施例の処理手続きを説明する。なお、Ｅは非特許文献１等で用いられている加法準同型暗号の暗号化関数とする。
１．暗号置換装置１２０は、複数の暗号文の集合Ｚ＝（ｚ1，・・・，ｚn）を入力する（ステップ１００１）。ここでｚi＝（Ｅ（ｘi,l-1，ｒi,l-1），・・・，（Ｅ（ｘi,0，ｒi,0））である。
２．暗号置換装置１２０は、Ｚについて、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素である暗号文毎に再暗号化したＺ’＝（ｚ1’，・・・，ｚn’）を計算する（ステップ１００２）。ここで
【００２５】
【数６】
2008176193.tif 000008
である。暗号置換装置１２０はＺ’を秘匿論理演算装置１３０に送る。
３．ｉ＝１，・・・，ｎ-１の順に、秘匿論理演算装置１３０、復号装置１４０及び公開演算装置１１０は以下の処理を繰り返す（ステップ１００３）。
（ａ）秘匿論理演算装置１３０は、ｚi’，ｚi+1’を入力として、大小比較論理演算アルゴリズムのステップ１，２の秘匿回路計算を実行し、実行結果Ｅ（Ｂ，ｒ）を復号装置１４０に送る。また、秘匿論理演算装置１３０はｚi’，ｚi+1’を公開演算装置１１０に送る。
（ｂ）復号装置１４０は、Ｅ（Ｂ，ｒ）を復号して、復号結果Ｂを公開演算装置１１０に送る。
（ｃ）公開演算装置１１０は、Ｂ＝１であればｚi’を大きいほうの値の暗号文として、あらたにｚi+1’←ｚi’とし、Ｂ＝０であればｚi+1’を大きい方の値の暗号文としてそのままｚi+1’←ｚi+1’とする。公開演算装置１１０は、このｚi+1’を秘匿論理演算装置１３０に送る。
４．ｉ＝ｎのとき、公開演算装置１１０はｚn’←ｚi+1’として、ｚn’を復号装置１４０に送る。復号装置１４０はｚn’を復号し、当該復号結果を最大値として出力する（ステップ１００４）。
【００２６】
以上のように、比較器の計算を大小比較論理演算アルゴリズムを秘匿回路計算で実行する場合と比べ、本実施例の方法では比較器の計算に相当する部分では入力の大小結果を求めるため、大小比較論理演算アルゴリズムのステップ３を省略することができ、処理を削減できる。
【実施例２】
【００２７】
本実施例では、実施例１の処理手続きを更に高速化する方法について説明する。本実施例でも実施例１と同様に、図２に示す単純な比較器ネットワークを例に、ｎ個の０以上２l未満の整数の集合Ｘ＝（ｘ1，・・・，ｘn）（ここで、ｘi＝Σj=0l-1２jｘi,j（ｘi,j∈｛０，１｝））から、Ｘの要素を秘匿したままＸの最大値を求めるものとする。
【００２８】
図５は、本実施例の構成図であり、秘匿関数計算装置２００は、公開演算装置２１０、暗号置換装置２２０、秘匿論理演算装置２３０、復号装置２４０、及び暗号化乱数乗算装置２５０によって構成される。ここで、公開演算装置２１０と秘匿論理演算装置２３０と復号装置２４０と暗号化乱数乗算装置２５０が比較器ネットワークを構成している。公開演算装置２１０、暗号置換装置２２０、秘匿論理演算装置２３０、復号装置２４０の機能は実施例１と基本的に同様である。暗号化乱数乗算装置２５０は、暗号文を入力として、平文に乱数を掛け合わせた暗号文を出力する機能を持つ。装置から不正に乱数を取り出す攻撃に対して耐性を高めるために装置を多重化しても良い。
【００２９】
本実施例の処理手続きの説明の前に、先の大小比較論理演算アルゴリズムのステップ２について、全体の処理を変えることなく表現を以下のように改める。
２−１  Ａl＝１，Ｂl-1＝Ｂigger1（ｘl−1，ｙl−1）とし、ｉ＝ｌ−１，・・・，１の順にＡi＝Ａi+1∧ＥＱ1（ｘi，ｙi），Ｂi-1＝Ｂigger1（ｘi-1，ｙi-1）∧Ａiを計算する。
２−２Ｂl-1∨Ｂl-2∨・・・∨Ｂ0を計算する。
【００３０】
図６は本実施例の処理フロー図である。以下、図５、図６にもとづいて本実施例の処理手続きを説明する。
１．暗号置換装置２２０は、複数の暗号文の集合Ｚ＝（ｚ1，・・・，ｚn）を入力する（ステップ２００１）。ここでｚi＝（Ｅ（ｘi,l-1，ｒi,l-1），・・・，（Ｅ（ｘi,0，ｒi,0））である。
２．暗号置換装置２２０は、Ｚについて、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素である暗号文毎に再暗号化したＺ’＝（ｚ1’，・・・，ｚn’）を計算する（ステップ２００２）。ここで
【００３１】
【数７】
2008176193.tif 000009
である。暗号置換装置２２０はＺ’を秘匿論理演算装置２３０に送る。
３．ｉ＝１，・・・，ｎ-１の順に、秘匿論理演算装置２３０、公開演算装置２１０、暗号化乗算装置２３０及び復号装置２４０は以下の処理を繰り返す（ステップ２００３）。
（ａ）秘匿論理演算装置２３０は、ｚi’，ｚi+1’を入力として、大小比較論理演算アルゴリズムのステップ１、及び改変後のステップ２-１の秘匿回路計算を実行し、実行結果Ｇ＝（Ｅ（Ｂl-1，ｓl-1），・・・，（Ｅ（Ｂ0，ｓ0）を公開演算装置２１０に送る。秘匿論理演算装置２３０はｚi’，ｚi+1’も公開演算装置２１０に送る。
（ｂ）公開演算装置２１０は、Ｇを入力として、Ｅの準同型性を利用してＥ（Σi=0l-1Ｂi，ｓ）を計算し、暗号化乱数乗算装置２５０に送る。ここで、ｓは適当な乱数である。
（ｃ）暗号化乱数乗算装置２５０は、Ｅ（Σi=0l-1Ｂi，ｓ）を入力として、乱数ｗを生成して、Ｅの準同型性を利用してＥ（ｗΣi=0l-1Ｂi，ｓ’）を計算し、復号装置２４０に送る。
（ｄ）復号装置２４０は、Ｅ（ｗΣi=0l-1Ｂi，ｓ’）を復号して、復号結果Ｂ’＝ｗΣi=0l-1Ｂiを公開演算装置２１０に送る。
（ｅ）  公開演算装置２１０は、Ｂ’≠０であれば、ｚi’を大きい方の値の暗号文として、あらたにｚi+1’←ｚi’とし、Ｂ’＝０であればｚi+1’を大きい方の値の暗号文として、そのままｚi+1’←ｚi+1’とする。公開演算装置２１０は、このｚi+1’を秘匿論理演算装置２３０に送る。
４．ｉ＝ｎのとき、公開演算装置２１０はｚn’←ｚi+1’として、ｚn’を復号装置２４０に送る。復号装置２４０はｚn’を復号し、当該復号結果を最大値として出力する（ステップ２００４）。
【００３２】
ステップ２００３（ｅ）のＢ’≠０であることと、実施例１のステップ１００３（ｃ）でＢ＝１であることは等価である。同様に、ステップ２００３（ｅ）でＢ’＝０であることと、実施例１のステップ１００３（ｃ）でＢ＝０であることは等価である。
【００３３】
以上のように、本実施例では、改変後のステップ２−２の秘匿回路計算が不要となり、処理の削減が見込める。
【実施例３】
【００３４】
実施例３では実施例１および２の方法の秘匿性を高める方法について説明する。実施例１や２の方法では、再暗号化およびランダム置換により入力を匿名化することで、各比較器の入力データの大小関係の情報が、比較器ネットワークの入力の秘匿性を損なわなくなる効果を利用して計算量を削減していた。しかし実施例１の処理中に現れる値Ｂ、および実施例２の処理中に現れる値Ｂ’は平文として現れるため、入力データに関する不要な情報が露呈する可能性がある。すなわち、入力データの平文Ｘ，Ｙに対して、Ｘ＞ＹであればＢ＝１（実施例２ではＢ’≠０）となり、そうでなければＢ＝０（実施例２ではＢ’＝０）となるため、Ｂ＝１（実施例２ではＢ’≠０）であればＸ≠Ｙであることが分かってしまう。本実施例では、このような比較器ネットワークの最終出力以外の不要な情報の露呈を防ぐ方法について説明する。簡単に言えば、Ｘ＝Ｙであれば、Ｂ（実施例２ではＢ’）は乱数ビット（実施例２では１／２の確率でＢ’＝０）となるような操作を追加する。以降、実施例１に基づいて具体的な手続きを示す。
【００３５】
図７は本実施例の構成図であり、秘匿計算装置３００は、公開演算装置３１０、暗号置換装置３２０、秘匿論理演算装置３３０、復号装置３４０及び暗号化乱数生成装置３５０によって構成される。ここで、公開演算装置３１０と秘匿論理演算装置３３０と復号装置３４０と暗号乱数生成装置３５０が比較器ネットワークを構成している。゜
【００３６】
公開演算装置３１０は秘密鍵や乱数を一切必要せずに与えられた処理を実行する。そのため他の装置が同一処理を再現し、公開演算装置３１０の処理正当性を検証できる。暗号置換装置３２０は、複数の暗号文を入力として、置換及び再暗号化して出力する。装置から不正に置換情報や再暗号化に用いた乱数を取り出す攻撃に対して耐性を高めるために装置を多重化しても良い。暗号化乱数生成装置３５０は、１ビットの乱数を生成し、それを暗号化して出力する。暗号化乱数生成装置３５０の内部状態を得ない限りは当該乱数を知ることができない。当該乱数の秘匿性を高めるために、複数の装置が協力して１ビットの乱数の暗号文を生成し、当該全ての装置の内部状態を得ない限りは当該乱数を知ることができないようにしても良い。また、当該暗号文が正しく１ビットデータを暗号化したものであることをゼロ知識証明を用いて当該装置が証明することで、当該装置の不正行為を防止しても良い。これらの１ビットの乱数の暗号文の生成方法に関しては以下の非特許文献３で説明されているためここでは省略する。
【００３７】
【非特許文献３】B．Schoenmakers  and  P．Tuy1s，Effcient  binary  conversion  for  Paillier  encrypted  values，EUROCRYPT  2006，LNCS  4004，PP．522-537，Springer-Verlag，2006．
【００３８】
秘匿論理演算装置３３０は、複数のビットの暗号文を入力として論理演算結果の暗号文を出力する。装置から不正に乱数や復号鍵といった秘密情報を取り出す攻撃に対して耐性を高めるために、例えば非特許文献１で提案されている方法により、複数の装置が協力して、開催未満の装置の秘密情報を取り出しても平文ビットに関する情報を得にくくするように論理演算を計算するようにしても良い。復号装置３４０は、内部に復号鍵を保持し、暗号文を入力として復号結果を出力する。装置から不正に復号鍵を取り出す攻撃に対して耐性を高めるために、複数の装置が協力した場合に限り復号できるようにしても良い。
【００３９】
図８は本実施例の処理フロー図である。以下、図７、図８にもとづいて本実施例の処理手続きを説明する。なお、Ｅは非特許文献１等で用いられている加法準同型暗号の暗号化関数とする。
０．あらかじめ暗号化乱数生成装置３５０は、乱数ビットｂを生成し、それを暗号化したデータＥ（ｂ，ｒb）を計算し、秘匿論理演算装置３３０に送る（ステップ３０００）。ここでｒbは乱数である。
１．暗号置換装置３２０は、複数の暗号文の集合Ｚ＝（ｚ1，・・・，ｚn）を入力する（ステップ３００１）。ここでｚi＝（Ｅ（ｘi,l-1，ｒi,l-1），・・・，（Ｅ（ｘi,0，ｒi,0））である。
２．暗号置換装置３２０は、Ｚについて、集合｛１，・・・，ｎ｝の置換πを一つ選びＺに適用し、Ｚの要素である暗号文毎に再暗号化したＺ’＝（ｚ1’，・・・，ｚn’）を計算する（ステップ３００２）。ここで
【００４０】
【数８】
2008176193.tif 000010
である。暗号置換装置１２０はＺ’を秘匿論理演算装置３３０に送る。
３．ｉ＝１，・・・，ｎ-１の順に、秘匿論理演算装置３３０、復号装置３４０及び公開演算装置３１０は以下の処理を繰り返す（ステップ３００３）。
（ａ）秘匿論理演算装置３３０は、ｚi’，ｚi+1’を入力として、先の大小比較論理演算アルゴリズムのステップ１、２の秘匿回路計算を実行し、実行結果Ｇ＝（Ｅ（Ｂ，ｒ）およびＡの暗号文を得る。なお、秘匿論理演算装置３３０はｚi’，ｚi+1’を公開演算装置３１０に送る。
（ｂ）さらに、秘匿論理演算装置３３０は、Ｅ（Ｂ，ｒ），Ｅ（Ｂ，ｒb）およびＡの暗号文を入力として秘匿回路計算を実行し、Ｂ∨（ｂ∧Ａ）の暗号文Ｃを計算する。秘匿論理演算装置３３０は、このＣを復号装置３４０に送る。
（ｃ）復号装置３４０は、Ｃを復号して、復号結果Ｂ”＝Ｂ∨（ｂ∧Ａ）を公開演算装置３１０に送る。
（ｄ）  公開演算装置３１０は、Ｂ”＝１であれば、ｚi’を大きい方の値の暗号文として、あらたにｚi+1’←ｚi’とし、Ｂ”＝０であればｚi+1’を大きい方の値の暗号文として、そのままｚi+1’←ｚi+1’とする。公開演算装置３１０は、このｚi+1’を秘匿論理演算装置３３０に送る。
４．ｉ＝ｎのとき、公開演算装置３１０はｚn’←ｚi+1’として、ｚn’を復号装置３４０に送る。復号装置３４０はｚn’を復号し、当該復号結果を最大値として出力する（ステップ３００４）。
【００４１】
比較器の入力である暗号文ｚi’，ｚi+1’について、それらを復号したデータが等しければ、Ｂ＝０となり、かつ、当該データが等しい場合に限りＡ＝１となる。すなわち、当該データが異なる場合はＡ＝０であるからＢ＝Ｂ”となり、等しい場合はＢ＝０かつＢ”＝Ｂ∨ｂであるからＢ”＝ｂとなることが分かる。したがって、実施例１では当該データが等しければＢ＝０を出力していたのに対し、本実施例ではＢの代わりにＢ”を出力するため、当該データが等しい場合は乱数ビットｂを出力することになる。また当該データが異なる場合は実施例１の出力と等しい。以上により不要な情報の露呈を防ぐことができることが分かる。
【００４２】
以上、実施例１に基づいた具体的な手続きを述べたが、本実施例で述べた方法の特徴は、暗号化乱数生成装置３４０によって生成された乱数ビットの暗号文を利用して，比較器の入力となる暗号文に対応する平文が同値のとき、当該乱数ビットが出力されるようにしたことであり、実施例２に対しても特別な処理をすることなく同様に適用できるため、実施例２に基づいた具体的な手続きの説明は省略する。
【実施例４】
【００４３】
最後に実施例４として、図９で示すような比較器ネットワークにおいて、Ｌ以外の入力を秘匿したまま計算する方法について説明する。図９の比較器ネットワークは、各入力がＬり大きいかどうか判定するためのものである。実施例１〜３と異なる点は、入力の一部（本実施例ではＬ）は秘匿しなくて良しことである。これにより、以下で示すように全ての入力を秘匿する場合に比べ計算量の削減が見込める。
【００４４】
なお、本実施例で用いる加法準同型暗号Ｅは、ｘ，ｙの暗号文Ｅ（ｘ，ｒ），Ｅ（ｙ，ｓ）および定数ｃに対して、
Ｅ（ｘ，ｒ）×Ｅ（ｙ，ｓ）＝Ｅ（ｘ＋ｙ，ｔ），
Ｅ（ｘ，ｒ）／Ｅ（ｙ，ｓ）＝Ｅ（ｘ−ｙ，ｕ），
Ｅ（ｘ，ｒ）c＝Ｅ（ｘｃ，ｖ）
を満たす性質であるとする（ｒ，ｓ，ｔ，ｕ，ｖ：適当な乱数）。このような性質を満たす暗号として、Paillier暗号などが知られている。
【００４５】
以下では実施例１に基づき説明する。本実施例における装置構成は実施例１同様として良い。手続きも実施例１と大部分は等しくなるが、実施例１のステップ１００３中の（ａ）のみ異なる。具体的には、ステップ１００３中の（ａ）の処理のうち、大小比較論理演算アルゴリズムのステップ２のＥＱ（ｘi，ｙi）およびＢigger1（ｘi-1，・・・，ｙi-1）の演算方法が異なる。実施例１ではＥＱ（ｘi，ｙi）＝２ｘiｙi−ｘi−ｙi＋１およびＢigger1（ｘi-1，ｙi-1）＝−ｘiｙi＋ｘiの計算は秘匿回路計算で行うとしているが、いまＬ＝Σi=0l-1２iｙiとしたとき、ｙiは明かしてよいことにより秘匿回路計算が不要となる。
【００４６】
具体的には、実施例１のステップ１００３中の（ａ）のＥＱ（ｘi，ｙi）の計算において、秘匿論理演算装置（他の任意の装置でも良い）が以下を行う。
［入力］  Ｅ（ｘi，ｙi），ｙi（ｒi；乱数）
［出力］  ＥＱ（ｘi，ｙi）＝２ｘiｙi−ｘi−ｙi＋１
１．１−ｙiの暗号文Ｅ（１−ｙi，ｗ）を計算する（ｗ：乱数）。
２．Ｃ＝（Ｅ（（ｘi，ｙi）2ｙi／Ｅ（ｘi，ｒi））×Ｅ（１−ｙi，ｗ）を計算する。
【００４７】
上記の計算について、Ｅの加法準岡型性により、Ｃは２ｘiｙi−ｘi−ｙi＋１の暗号文、すなわちＥＱ（ｘi，ｙi）の暗号文となっていることが分かる。Ｂigger1（ｘi-1，ｙi-1）＝−ｘiｙi＋ｘiの計算についても明らかに加法準同型性により同様に行うことができる。
【００４８】
以上、４つの実施例について述べたが、本発明により、比較器ネットワークを利用した計算について入力データを秘匿したまま従来の方法よりも効率良く処理することができるようになる。比較器ネットワークを利用した計算の例としては、先に述べたソート、最大値導出、範囲指定、その他、中央値や第１四分位数導出などが挙げられる。これらの計算は統計処理などでしばしば用いられることから、本発明は、個人から提供されるデータは秘匿し、かつ複数の個人データから得られる統計データのみ得る場合などに有効である。
【００４９】
なお、図３、図５、図７などで示した装置における各部の一部もしくは全部の処理機能をコンピュータのプログラムで構成し、そのプログラムをコンピュータを用いて実行して本発明を実現することができること、あるいは、図４、図６、図８などで示した処理手順をコンピュータのプログラムで構成し、そのプログラムをコンピュータに実行させることができることは言うまでもない。また、コンピュータでその処理機能を実現するためのプログラム、あるいは、コンピュータにその処理手順を実行させるためのプログラムを、そのコンピュータが読み取り可能な記録媒体、例えば、ＦＤ、ＭＯ、ＲＯＭ、メモリカード、ＣＤ、ＤＶＤ、リムーバブルディスクなどに記録して、保存したり、提供したりすることができるとともに、インターネット等のネットワークを通してそのプログラムを配布したりすることが可能である。
【図面の簡単な説明】
【００５０】
【図１】比較器ネットワークの一例を示す図。
【図２】比較器ネットワークの他の一例を示す図。
【図３】本発明の実施例１の構成図。
【図４】実施例１の処理フロー図。
【図５】本発明の実施例２の構成図。
【図６】実施例２の処理フロー図。
【図７】本発明の実施例３の構成図。
【図８】実施例３の処理フロー図。
【図９】比較器ネットワークの更に他の一例を示す図。
【符号の説明】
【００５１】
１１０、２１０、３１０  公開演算装置
１２０、２２０、３２０  暗号置換装置
１３０、２３０、３３０  秘匿論理演算装置
１４０、２４０、３４０  復号装置
２５０  暗号化乱数乗算装置
３５０  暗号化乱数生成装置
【図１】
2008176193.tif 000016
【図２】
2008176193.tif 000017
【図３】
2008176193.tif 000018
【図４】
2008176193.tif 000019
【図５】
2008176193.tif 000020
【図６】
2008176193.tif 000021
【図７】
2008176193.tif 000022
【図８】
2008176193.tif 000023
【図９】
2008176193.tif 000024