暗号化数値二進変換システム及び方法とプログラム
【課題】第１及び第２の暗号化数値二進変換装置を備える暗号文を生成する暗号化数値二進変換システムで、ある数値の暗号文を二進表記した桁ごとに暗号化する際の計算量を抑える手段を提供する。
【解決手段】本発明は、置換関数π、π′、π′′、π′′′をそれぞれ用いて、ラベルつきハッシュ値を得、各ラベルつきハッシュ値から対応するラベルを求めて、それぞれの各ビットを暗号化し、これらにπ-1・π′′′-1，π′-1、π′′-1を作用させて、El Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行う。
【解決手段】本発明は、置換関数π、π′、π′′、π′′′をそれぞれ用いて、ラベルつきハッシュ値を得、各ラベルつきハッシュ値から対応するラベルを求めて、それぞれの各ビットを暗号化し、これらにπ-1・π′′′-1，π′-1、π′′-1を作用させて、El Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、ある数値の暗号文を入力として、当該数値を復元することなく、当該数値を二進表記した桁ごとに暗号化した暗号文を生成する技術に関する。
【背景技術】
【０００２】
非特許文献１では、楕円曲線の有理点群を利用したEl Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行う方法が提案されている。
【０００３】
また、二進数表記した数値を桁ごとに暗号化することで、当該数値の任意の論理演算を当該数値を明かすことなく実行可能とする方法も知られている（例えば、非特許文献２）。このような論理演算は、秘匿回路計算と称されている。
【０００４】
El Gamal暗号は、Paillier暗号と比べて、暗号文のサイズや復号処理、零知識証明などに要する計算量が小さく済むことが期待され、Paillier暗号を用いた従来の方法と比べるとデータサイズ削減や計算量削減が見込めるという効果が得られる。
【非特許文献１】千田、五十嵐、高橋、”エルガマル暗号に適したバイナリ変換マルチパーティプロトコル”、SCIS2009。
【非特許文献２】G. Yamamoto, K. Chida, A. Nasciment, K. Suzuki, and S. Uchiyama, ′′Efficient、 non-optimistic secure circuit evaluation based on the El Gamal encryption,′′ WISA2005, LNCS, pp. 328[343, Springer-Verlag, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１の第４．３節の方法によれば、El Gamal暗号で暗号化された数値をｔビットとすると、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行うために2t回以上の群演算およびハッシュ演算が必要となる。非特許文献１ではその他の方法も記されているが、何れも第４．３節の方法より演算量が大きい。したがって、ｔが小さな場合には利用することができるが、ｔが大きな場合には実際に利用することが困難となるという問題がある。
【０００６】
本発明は、非特許文献１の方法よりも計算量を抑える手段を提供する。
【課題を解決するための手段】
【０００７】
Ｅ（ ）をEl Gamal暗号の暗号化関数とする。ｚを0以上2t−1以下の整数とする。ｔを偶数とする。Ｇ，ｑ，ｙをEl Gamal 暗号のパラメータとする。Ｆ（ ）を群Ｇに写すハッシュ関数とする。
【０００８】
このとき、先ず、暗号化数値二進変換装置Ａは以下を実行する。
S1. Ｅ（ｚ）を受信する。
S2. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S3. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S4. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S5.
【０００９】
【数１】
を生成する。特にＣiはラベルｉと対応付けておく。
S6. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S7. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置Ｂに送信する。
【００１０】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S8. ＤAを復号し、ＤB=yz-uを得る。
S9. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S10. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S11. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置Ａに送信する。
【００１１】
次に、暗号化数値二進変換装置Ａは以下を実行する。
S12. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S13. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S14. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置Ｂに送信する。
【００１２】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S15. Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S16. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S17. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置Ａに送信する。
【００１３】
最後に、暗号化数値二進変換装置Ａ、Ｂは以下を実行する。
S18. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００１４】
【数２】
を得る。
S19.
【数３】
を暗号化する。
S20.
【００１５】
【数４】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
【発明の効果】
【００１６】
本発明によれば、群演算はおよそ２(t+4)/2回で済む。全体の計算量を大まかに比較すると、本発明はｔ≧１８であれば非特許文献１の方法よりも計算量が少ない。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施例の構成を示すブロック図である。
【図２】本発明の実施例の動作を示すフローチャートである。
【図３】本発明の実施例の動作を示すフローチャートである。
【図４】本発明の実施例の動作を示すフローチャートである。
【実施例１】
【００１８】
次に、本発明の実施例について説明する。
【００１９】
図１は本発明による一実施例の構成を示すブロック図である。
【００２０】
図１に示すように、本実施例の暗号化数値二進変換システム２０は、暗号化数値二進変換装置２１Ａ、２１Ｂを有し、ある数値の暗号文を入力として秘匿回路計算を実行するための当該数値の二進数表記の桁ごとの暗号文を生成する。なお、図１において、１以上の入力提供装置１０は、秘匿回路計算装置３０の入力となる、ある数値の暗号文を暗号化数値二進変換システム２０に提供する。
【００２１】
また、１以上の秘匿回路計算装置３０は、暗号化数値二進変換システム２０にて生成された二進数表記の桁ごとの暗号文を基に秘匿回路計算を実行する。
【００２２】
以下、非特許文献１の第４．３節で記されている、暗号化数値二進変換装置２１Ａ、２１Ｂにおいて、El Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成するための処理手順について説明する。
【００２３】
最初に、El Gamal暗号の構成例について説明しておく。
【００２４】
El Gamal暗号の場合、ｇを素数位数ｑの乗法群Ｇの生成元とし、ｇ、ｑ、Ｇを公開情報としたとき、先ず、鍵ペア（ｘ，ｙ＝ｇx）を生成する。ここで、ｘは０以上ｑ未満の整数からなる秘密鍵であり、ｙは公開鍵である。ここでは、暗号化数値二進変換装置２１Ｂが当該鍵ペアを生成し、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとする。
【００２５】
次に、Ｅ（ ）をEl Gamal暗号の暗号化関数としたとき、Ｇの元ｚの暗号文をＥ（z）=（Ａ，Ｂ）＝（ｇr，ｚ×ｙr）とする。ここで、ｒは０以上ｑ未満の乱数である。復号に秘密鍵ｘを用いることで、復号処理の結果ｚ＝Ｂ／Ａxを得ることができる。なお、ｚを０以上ｑ未満の整数としたいときは、Ｅ（z）=（Ａ，Ｂ）＝（ｇr，ｙr+z）としても良い。非特許文献１および２に開示された方法では、この形式のＥ（ｚ）を用いている。ただし、この形式の場合、上記の復号処理の結果はｙzとなり、ｙzからｚを求める必要がある。ｚの候補数が多くなるとｙzからｚを求めることは一般に困難となるため、ｚの候補数はあらかじめ少なく設定することが望ましい。
【００２６】
本発明では、非特許文献１および２に開示された方法とＥ（ｚ）の形式が同様であることを前提とし、以降説明の簡略化のため、入力提供装置１０は単一とし、当該入力提供装置１０がＥ（ｚ）を生成し、暗号化数値二進変換装置２１Ａに送信するものとする。なお、Ｚは０（＝ａ）以上２t−１（＝ｂ）以下の整数とする（ｔは２t＜ｑを満たす適当な自然数）。
【００２７】
すなわち、非特許文献１では、ｚを二進数表記したときの下位ｊ＋１桁目をｚjと表記したとき、ｚを復元することなく、Ｅ（ｚ）から、Ｅ（ｚt-1），・・・，Ｅ（ｚ0）を生成している。
【００２８】
以下、暗号化数値二進変換装置２１A、２１Ｂの処理手順について、図２を参照して説明する。
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S101. Ｅ（ｚ）を受信する。
S102. ０以上ｑ未満の整数ｕ，ｖを選ぶ。
S103. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｕｚ＋ｖ）を計算する。
S104. Ｅ（ｕｚ＋ｖ）の部分復号結果ＤAを計算する。
S105. Ｃi=Ｈａｓｈ（ｙui+v）（ｉ＝０，・・・，2t−１）を生成するＨａｓｈ（ ）はハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S106. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S107. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００２９】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S108. ＤAを復号し、ＤB=yuz+vを得る。
S109. Ｃi=＝Ｈａｓｈ（ＤB）となるＣiを探索し、対応するラベルπ（Ｉ）＝（π（ｚ））を得る。
S110.
【００３０】
【数５】
を暗号化する。
S111.
【００３１】
【数６】
を暗号化数値二進変換装置２１Ｂに送信する。
【００３２】
最後に暗号化数値二進変換装置２１Ａは
S112.
【００３３】
【数７】
にπ-1を作用させてＥ（ｚi）を得る。
【００３４】
上記の手続きは、ｔが小さくない場合、S105の計算量が最も大きくなると考えられる。具体的には、S105では2t回の乗算およびハッシュ演算を実行する。
【００３５】
次に、本発明の処理手順について、図３を参照して説明する。なお説明の簡略化のため、ｔは偶数とする。
【００３６】
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S201. Ｅ（ｚ）を受信する。
S202. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S203. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S204. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S205.
【００３７】
【数８】
を生成する（Ｆ（ ）は群Ｇに写すハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S206. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S207. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００３８】
次に暗号化数値二進変換装置Ｂは以下を実行する。
S208. ＤAを復号し、ＤB=yz-uを得る。
S209. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S210. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S211. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置２１Ａに送信する。
【００３９】
次に、暗号化数値二進変換装置２１Ａは以下を実行する。
S212. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S213. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S214. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置２１Ｂに送信する。
【００４０】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S215. Ｃ′′′i＝CivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S216. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S217. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置２１Ａに送信する。
【００４１】
最後に暗号化数値二進変換装置２１Ａ、２１Ｂは以下を実行する。
S218. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００４２】
【数９】
を得る。
S219.
【００４３】
【数１０】
を暗号化する。
S220.
【００４４】
【数１１】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
【００４５】
いまS220が手続き終了、即ち
【００４６】
【数１２】
が成り立つことを示す。S218からＣ′′′I＝Ｃ′′Jであることが分かる。また、S215，S205からＣ′′′I＝ＣIvB＝
【００４７】
【数１３】
，S212，S209からＣ′′J＝Ｃ′JvA＝Ｆ（ｙu-z+J）vBvAであることがわかる。したがって、Ｃ′′′I＝Ｃ′′J⇒
【００４８】
【数１４】
＝Ｆ（ｙu-z+J）がいえ、Ｆの衝突困難性を仮定すれば、ｕ−Ｉ２t/2＝ｕ−ｚ＋Ｊ（mod q）
が成り立つ。すなわち、
【００４９】
【数１５】
となり、式（１）が示せた。
【００５０】
最後に、本発明と非特許文献１の第４．３節の方法との大まかな計算量比較を行う。前にも述べたとおり、ｔが小さくない場合、S105の計算量が最も大きくなると考えられ、S105では２t回の乗算およびハッシュ演算を実行する。
【００５１】
一方、本発明では、S205、S209、S212、S215の計算量が大きく、合わせて、2(t+4)/2+２回のべき乗演算、２(t+2)/2−２回の乗算、および、２(t+2)/2回のハッシュ演算を実行する。
【００５２】
乗算とハッシュ演算の計算量を同程度とみなす。また、べき乗演算の計算量は、Binary Methodの利用を仮定するとして、１．５｜ｑ｜回の乗算と同程度とみなす。ここで｜ｑ｜はｑのビット長を表すものとする。すると、｜ｑ｜＝１６０としたとき、本発明と非特許文献１の第４．３節の方法の計算量の比は大まかに２４０×（２(t+4)/2＋２）＋２(t+2)/2−２＋２(t+2)/2：２t+1と見積もることができる。すなわち、ｔ≧１８であれば本発明の方が計算量が少なく済む。
【実施例２】
【００５３】
実施例１では、暗号化数値二進変換装置２１Ａ、２１Ｂのどちらか一方が誤った処理を実行しても、その事実を判別することが難しい場合がある。これは暗号文のランダム性により、出力された暗号文が正しい暗号文なのか誤った暗号文なのか判別することが一般に困難であるためである。本実施例では、非特許文献１の第４．４節の方法に倣い、実施例１における本発明を拡張し、当該判別を可能とする方法について図４を参照して説明する。
【００５４】
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S301. Ｅ（ｚ）を受信する。
S302. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S303. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S304. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S305.
【００５５】
【数１６】
を生成する。（Ｆ（ ）は群Ｇに写すハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S306. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S307. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００５６】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S308. ＤAを復号し、ＤB=yz-uを得る。
S309. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S310. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S311. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置２１Ａに送信する。
【００５７】
次に、暗号化数値二進変換装置２１Ａは以下を実行する。
S312. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S313. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S314. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置２１Ｂに送信する。
【００５８】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S315. Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S316. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S317. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置２１Ａに送信する。
【００５９】
最後に、暗号化数値二進変換装置２１Ａ、２１Ｂは以下を実行する。
S318. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００６０】
【数１７】
を得る。
S319.
【００６１】
【数１８】
を暗号化する。
S320.
【００６２】
【数１９】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
S321. 零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認する。
S322. Ｅ（ｚ）の復号結果と
【００６３】
【数２０】
の復号結果が等しいことを確認する。
【００６４】
上記手続は、S301からS320は実施例１で説明したS201からS220の手続きと同一である。したがって、以降ではS321およびS322について詳しく説明する。
【００６５】
例えば置換関数πとして
【００６６】
【数２１】
を考える。ここで，ｗはｔビットの乱数とする。π′，π′′，π′′′も同様に、それぞれ
【００６７】
【数２２】
とする。すると例えば
【００６８】
【数２３】
が成り立つ。ここでｗ′k，ｗ′′kはそれぞれ暗号化数値二進変換装置B、A が生成した乱数ビットであり、他の装置には知られない値である。即ち、例えばS320の処理は以下とみなすことができる。
【００６９】
１．暗号化数値二進変換装置２１Ｂは
【００７０】
【数２４】
を受信する。
【００７１】
２．暗号化数値二進変換装置２１Ｂはｗ′ｋを用いて
【００７２】
【数２５】
を計算し、暗号化数値二進変換装置２１Ａに送信する。
【００７３】
３．暗号化数値二進変換装置２１Ａはｗ′′ｋを用いてＥ（ｚk）を計算し、暗号化数値二進変換装置２１Ｂに送信する。
【００７４】
上記の2、３の計算方法は、例えば非特許文献２に詳しく説明されている。また上記処理に応じて、例えばS321の処理は以下とみなすことができる。
【００７５】
１．暗号化数値二進変換装置２１ＢはS320の入出力
【００７６】
【数２６】
について、S310で生成したｗ′ｋを作用させた関係であることを零知識証明する。
２．暗号化数値二進変換装置２１Ａは当該暗号化数値二進変換装置２１Ｂの零知識証明が正しいことを確認する。
３．暗号化数値二進変換装置２１ＡはS320の入出力
【００７７】
【数２７】
について、S313で生成したｗ′′ｋを作用させた関係であることを零知識証明する。
４．暗号化数値二進変換装置２１Ｂは当該暗号化数値二進変換装置２１Ａの零知識証明が正しいことを確認する。
【００７８】
上記零知識証明もまた、例えば非特許文献２に詳しく説明されている。
【００７９】
最後にS322の具体例を説明する。
【００８０】
S322では、ｚ＝ｚ′であることを確認できれば良い。しかし本来の目的である、ｚを明かすことなく、Ｅ（ｚ）からｚの二進数表記の桁ごとの暗号文を生成するためには、Ｅ（ｚ）やＥ（ｚ′）を単純に復号することはできない。そこで、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ）、Ｅ（ｚ′）から、Ｅ（ｚ−ｚ′）を計算し、この復号結果が０であるかどうか確認することを考える。例えば、本技術分野で良く知られるテクニックとして以下の手続きが考えられる。
【００８１】
１．暗号化数値二進変換装置２１Aは０以上ｑ未満の乱数ｓを生成し、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ−ｚ′）からＥ（ｓ′（ｚ−ｚ′））を計算し、これを暗号化数値二進変換装置２１Ｂに送信する。
【００８２】
２．暗号化数値二進変換装置２１Ｂは同様に０以上ｑ未満の乱数ｓ′を生成し、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ−ｚ′）からＥ（ｓ′（ｚ−ｚ′））を計算し、これを暗号化数値二進変換装置２１Ａに送信する。
【００８３】
３．暗号化数値二進変換装置２１Ａ、２１ＢはＥ（ ）の加法準同型性を利用して、Ｅ（ｓ（ｚ−ｚ′）），Ｅ（ｓ′（ｚ−ｚ′））からＥ（（ｓ＋ｓ′）（ｚ−ｚ′））を計算し、これを復号して(ｓ＋ｓ′）（ｚ−ｚ′）を得、当該復号結果が０であればｚ−ｚ′と判断し、そうでなければｚ−ｚ′≠０と判断する。
【００８４】
上記手続において、実際(ｓ＋ｓ′）（ｚ−ｚ′）ｍｏｄ ｑ＝０であれば、ｓ＋ｓ′ｍｏｄ ｑ＝０となる場合を除いてｚ−ｚ′ｍｏｄ ｑ＝０が成り立つ。いま、０≦ｚ，ｚ′＜２t＜ｑであるから、ｚ−ｚ′＝０がいえる。ｑはEl Gamal暗号の安全性の理由から一般に十分大きくとり、ｓ，ｓ′は乱数であることから、ｓ＋ｓ′ｍｏｄ ｑ＝０となる可能性は無視できる。また同様の議論により、(ｓ＋ｓ′）（ｚ−ｚ′）ｍｏｄ ｑ＝０であればｚ−ｚ′≠０がいえる。
【００８５】
なお、暗号化数値二進変換システム２０を構成する暗号化数値二進変換装置２１Ａ、２１Ｂは、キーボード、マウス、受信装置等の入力装置、CPUなどの制御装置、ROM、RAM、HDDなどの記憶装置、ディスプレイ、プリンタ、送信装置などの出力装置からなる一般的なコンピュータシステムにより構成されるものである。
【００８６】
入力提供装置１０からの入力、秘匿回路計算装置３０への出力、暗号化数値二進変換装置２１Ａ、２１Ｂ間でのデータの送受信は入力装置、出力装置により行われる。また、各ステップを実行することは、ROM、RAM、HDDに格納されているプログラムに則って行われるものである。
【００８７】
また、ROM、RAM、HDD内に格納されるプログラムは、CD-ROM、DVD-ROM、フロッピーディスク、USBメモリなどの読み取り可能な記録媒体からこれらの入力装置を介して移入される形態やインターネットなどのネットワークを介して受信装置より移入される形態がある。本発明によるシステムはこれらのプログラムにより一般的なコンピュータシステム上に構築されるものであり、本発明にはこれらのプログラムや該プログラムを格納した記録媒体が含まれる。
【符号の説明】
【００８８】
１０ 入力提供装置
２０ 暗号化数値二進変換システム
２１Ａ、２１Ｂ 暗号化数値二進変換装置
３０ 秘匿回路計算装置
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、ある数値の暗号文を入力として、当該数値を復元することなく、当該数値を二進表記した桁ごとに暗号化した暗号文を生成する技術に関する。
【背景技術】
【０００２】
非特許文献１では、楕円曲線の有理点群を利用したEl Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行う方法が提案されている。
【０００３】
また、二進数表記した数値を桁ごとに暗号化することで、当該数値の任意の論理演算を当該数値を明かすことなく実行可能とする方法も知られている（例えば、非特許文献２）。このような論理演算は、秘匿回路計算と称されている。
【０００４】
El Gamal暗号は、Paillier暗号と比べて、暗号文のサイズや復号処理、零知識証明などに要する計算量が小さく済むことが期待され、Paillier暗号を用いた従来の方法と比べるとデータサイズ削減や計算量削減が見込めるという効果が得られる。
【非特許文献１】千田、五十嵐、高橋、”エルガマル暗号に適したバイナリ変換マルチパーティプロトコル”、SCIS2009。
【非特許文献２】G. Yamamoto, K. Chida, A. Nasciment, K. Suzuki, and S. Uchiyama, ′′Efficient、 non-optimistic secure circuit evaluation based on the El Gamal encryption,′′ WISA2005, LNCS, pp. 328[343, Springer-Verlag, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１の第４．３節の方法によれば、El Gamal暗号で暗号化された数値をｔビットとすると、当該数値を明かすことなく、当該数値の二進数表記の桁ごとに暗号化を行うために2t回以上の群演算およびハッシュ演算が必要となる。非特許文献１ではその他の方法も記されているが、何れも第４．３節の方法より演算量が大きい。したがって、ｔが小さな場合には利用することができるが、ｔが大きな場合には実際に利用することが困難となるという問題がある。
【０００６】
本発明は、非特許文献１の方法よりも計算量を抑える手段を提供する。
【課題を解決するための手段】
【０００７】
Ｅ（ ）をEl Gamal暗号の暗号化関数とする。ｚを0以上2t−1以下の整数とする。ｔを偶数とする。Ｇ，ｑ，ｙをEl Gamal 暗号のパラメータとする。Ｆ（ ）を群Ｇに写すハッシュ関数とする。
【０００８】
このとき、先ず、暗号化数値二進変換装置Ａは以下を実行する。
S1. Ｅ（ｚ）を受信する。
S2. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S3. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S4. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S5.
【０００９】
【数１】
を生成する。特にＣiはラベルｉと対応付けておく。
S6. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S7. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置Ｂに送信する。
【００１０】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S8. ＤAを復号し、ＤB=yz-uを得る。
S9. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S10. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S11. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置Ａに送信する。
【００１１】
次に、暗号化数値二進変換装置Ａは以下を実行する。
S12. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S13. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S14. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置Ｂに送信する。
【００１２】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S15. Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S16. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S17. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置Ａに送信する。
【００１３】
最後に、暗号化数値二進変換装置Ａ、Ｂは以下を実行する。
S18. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００１４】
【数２】
を得る。
S19.
【数３】
を暗号化する。
S20.
【００１５】
【数４】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
【発明の効果】
【００１６】
本発明によれば、群演算はおよそ２(t+4)/2回で済む。全体の計算量を大まかに比較すると、本発明はｔ≧１８であれば非特許文献１の方法よりも計算量が少ない。
【図面の簡単な説明】
【００１７】
【図１】本発明の実施例の構成を示すブロック図である。
【図２】本発明の実施例の動作を示すフローチャートである。
【図３】本発明の実施例の動作を示すフローチャートである。
【図４】本発明の実施例の動作を示すフローチャートである。
【実施例１】
【００１８】
次に、本発明の実施例について説明する。
【００１９】
図１は本発明による一実施例の構成を示すブロック図である。
【００２０】
図１に示すように、本実施例の暗号化数値二進変換システム２０は、暗号化数値二進変換装置２１Ａ、２１Ｂを有し、ある数値の暗号文を入力として秘匿回路計算を実行するための当該数値の二進数表記の桁ごとの暗号文を生成する。なお、図１において、１以上の入力提供装置１０は、秘匿回路計算装置３０の入力となる、ある数値の暗号文を暗号化数値二進変換システム２０に提供する。
【００２１】
また、１以上の秘匿回路計算装置３０は、暗号化数値二進変換システム２０にて生成された二進数表記の桁ごとの暗号文を基に秘匿回路計算を実行する。
【００２２】
以下、非特許文献１の第４．３節で記されている、暗号化数値二進変換装置２１Ａ、２１Ｂにおいて、El Gamal暗号で暗号化された数値に対して、当該数値を明かすことなく、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成するための処理手順について説明する。
【００２３】
最初に、El Gamal暗号の構成例について説明しておく。
【００２４】
El Gamal暗号の場合、ｇを素数位数ｑの乗法群Ｇの生成元とし、ｇ、ｑ、Ｇを公開情報としたとき、先ず、鍵ペア（ｘ，ｙ＝ｇx）を生成する。ここで、ｘは０以上ｑ未満の整数からなる秘密鍵であり、ｙは公開鍵である。ここでは、暗号化数値二進変換装置２１Ｂが当該鍵ペアを生成し、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとする。
【００２５】
次に、Ｅ（ ）をEl Gamal暗号の暗号化関数としたとき、Ｇの元ｚの暗号文をＥ（z）=（Ａ，Ｂ）＝（ｇr，ｚ×ｙr）とする。ここで、ｒは０以上ｑ未満の乱数である。復号に秘密鍵ｘを用いることで、復号処理の結果ｚ＝Ｂ／Ａxを得ることができる。なお、ｚを０以上ｑ未満の整数としたいときは、Ｅ（z）=（Ａ，Ｂ）＝（ｇr，ｙr+z）としても良い。非特許文献１および２に開示された方法では、この形式のＥ（ｚ）を用いている。ただし、この形式の場合、上記の復号処理の結果はｙzとなり、ｙzからｚを求める必要がある。ｚの候補数が多くなるとｙzからｚを求めることは一般に困難となるため、ｚの候補数はあらかじめ少なく設定することが望ましい。
【００２６】
本発明では、非特許文献１および２に開示された方法とＥ（ｚ）の形式が同様であることを前提とし、以降説明の簡略化のため、入力提供装置１０は単一とし、当該入力提供装置１０がＥ（ｚ）を生成し、暗号化数値二進変換装置２１Ａに送信するものとする。なお、Ｚは０（＝ａ）以上２t−１（＝ｂ）以下の整数とする（ｔは２t＜ｑを満たす適当な自然数）。
【００２７】
すなわち、非特許文献１では、ｚを二進数表記したときの下位ｊ＋１桁目をｚjと表記したとき、ｚを復元することなく、Ｅ（ｚ）から、Ｅ（ｚt-1），・・・，Ｅ（ｚ0）を生成している。
【００２８】
以下、暗号化数値二進変換装置２１A、２１Ｂの処理手順について、図２を参照して説明する。
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S101. Ｅ（ｚ）を受信する。
S102. ０以上ｑ未満の整数ｕ，ｖを選ぶ。
S103. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｕｚ＋ｖ）を計算する。
S104. Ｅ（ｕｚ＋ｖ）の部分復号結果ＤAを計算する。
S105. Ｃi=Ｈａｓｈ（ｙui+v）（ｉ＝０，・・・，2t−１）を生成するＨａｓｈ（ ）はハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S106. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S107. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００２９】
次に、暗号化数値二進変換装置Ｂは以下を実行する。
S108. ＤAを復号し、ＤB=yuz+vを得る。
S109. Ｃi=＝Ｈａｓｈ（ＤB）となるＣiを探索し、対応するラベルπ（Ｉ）＝（π（ｚ））を得る。
S110.
【００３０】
【数５】
を暗号化する。
S111.
【００３１】
【数６】
を暗号化数値二進変換装置２１Ｂに送信する。
【００３２】
最後に暗号化数値二進変換装置２１Ａは
S112.
【００３３】
【数７】
にπ-1を作用させてＥ（ｚi）を得る。
【００３４】
上記の手続きは、ｔが小さくない場合、S105の計算量が最も大きくなると考えられる。具体的には、S105では2t回の乗算およびハッシュ演算を実行する。
【００３５】
次に、本発明の処理手順について、図３を参照して説明する。なお説明の簡略化のため、ｔは偶数とする。
【００３６】
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S201. Ｅ（ｚ）を受信する。
S202. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S203. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S204. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S205.
【００３７】
【数８】
を生成する（Ｆ（ ）は群Ｇに写すハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S206. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S207. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００３８】
次に暗号化数値二進変換装置Ｂは以下を実行する。
S208. ＤAを復号し、ＤB=yz-uを得る。
S209. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S210. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S211. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置２１Ａに送信する。
【００３９】
次に、暗号化数値二進変換装置２１Ａは以下を実行する。
S212. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S213. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S214. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置２１Ｂに送信する。
【００４０】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S215. Ｃ′′′i＝CivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S216. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S217. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置２１Ａに送信する。
【００４１】
最後に暗号化数値二進変換装置２１Ａ、２１Ｂは以下を実行する。
S218. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００４２】
【数９】
を得る。
S219.
【００４３】
【数１０】
を暗号化する。
S220.
【００４４】
【数１１】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
【００４５】
いまS220が手続き終了、即ち
【００４６】
【数１２】
が成り立つことを示す。S218からＣ′′′I＝Ｃ′′Jであることが分かる。また、S215，S205からＣ′′′I＝ＣIvB＝
【００４７】
【数１３】
，S212，S209からＣ′′J＝Ｃ′JvA＝Ｆ（ｙu-z+J）vBvAであることがわかる。したがって、Ｃ′′′I＝Ｃ′′J⇒
【００４８】
【数１４】
＝Ｆ（ｙu-z+J）がいえ、Ｆの衝突困難性を仮定すれば、ｕ−Ｉ２t/2＝ｕ−ｚ＋Ｊ（mod q）
が成り立つ。すなわち、
【００４９】
【数１５】
となり、式（１）が示せた。
【００５０】
最後に、本発明と非特許文献１の第４．３節の方法との大まかな計算量比較を行う。前にも述べたとおり、ｔが小さくない場合、S105の計算量が最も大きくなると考えられ、S105では２t回の乗算およびハッシュ演算を実行する。
【００５１】
一方、本発明では、S205、S209、S212、S215の計算量が大きく、合わせて、2(t+4)/2+２回のべき乗演算、２(t+2)/2−２回の乗算、および、２(t+2)/2回のハッシュ演算を実行する。
【００５２】
乗算とハッシュ演算の計算量を同程度とみなす。また、べき乗演算の計算量は、Binary Methodの利用を仮定するとして、１．５｜ｑ｜回の乗算と同程度とみなす。ここで｜ｑ｜はｑのビット長を表すものとする。すると、｜ｑ｜＝１６０としたとき、本発明と非特許文献１の第４．３節の方法の計算量の比は大まかに２４０×（２(t+4)/2＋２）＋２(t+2)/2−２＋２(t+2)/2：２t+1と見積もることができる。すなわち、ｔ≧１８であれば本発明の方が計算量が少なく済む。
【実施例２】
【００５３】
実施例１では、暗号化数値二進変換装置２１Ａ、２１Ｂのどちらか一方が誤った処理を実行しても、その事実を判別することが難しい場合がある。これは暗号文のランダム性により、出力された暗号文が正しい暗号文なのか誤った暗号文なのか判別することが一般に困難であるためである。本実施例では、非特許文献１の第４．４節の方法に倣い、実施例１における本発明を拡張し、当該判別を可能とする方法について図４を参照して説明する。
【００５４】
先ず、暗号化数値二進変換装置２１Ａは以下を実行する。
S301. Ｅ（ｚ）を受信する。
S302. ０以上ｑ未満の整数ｕ，ｖAを選ぶ。
S303. Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算する。
S304. Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算する。
S305.
【００５５】
【数１６】
を生成する。（Ｆ（ ）は群Ｇに写すハッシュ関数）。特にＣiはラベルｉと対応付けておく。
S306. 置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得る。
S307. ＤA及び<π（ｉ）：Ｃi>を暗号化数値二進変換装置２１Ｂに送信する。
【００５６】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S308. ＤAを復号し、ＤB=yz-uを得る。
S309. Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′jはラベルｊと対応付けておく。
S310. 置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得る。
S311. <π′（ｊ）：Ｃ′j>を暗号化数値二進変換装置２１Ａに送信する。
【００５７】
次に、暗号化数値二進変換装置２１Ａは以下を実行する。
S312. Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておく。
S313. 置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得る。
S314. ＜π′′（π′（ｊ））：Ｃ′′j＞を暗号化数値二進変換装置２１Ｂに送信する。
【００５８】
次に、暗号化数値二進変換装置２１Ｂは以下を実行する。
S315. Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成する。特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておく。
S316. 置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得る。
S317. ＜π′′′（π（ｉ））：Ｃ′′′i＞を暗号化数値二進変換装置２１Ａに送信する。
【００５９】
最後に、暗号化数値二進変換装置２１Ａ、２１Ｂは以下を実行する。
S318. Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【００６０】
【数１７】
を得る。
S319.
【００６１】
【数１８】
を暗号化する。
S320.
【００６２】
【数１９】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得る。
S321. 零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認する。
S322. Ｅ（ｚ）の復号結果と
【００６３】
【数２０】
の復号結果が等しいことを確認する。
【００６４】
上記手続は、S301からS320は実施例１で説明したS201からS220の手続きと同一である。したがって、以降ではS321およびS322について詳しく説明する。
【００６５】
例えば置換関数πとして
【００６６】
【数２１】
を考える。ここで，ｗはｔビットの乱数とする。π′，π′′，π′′′も同様に、それぞれ
【００６７】
【数２２】
とする。すると例えば
【００６８】
【数２３】
が成り立つ。ここでｗ′k，ｗ′′kはそれぞれ暗号化数値二進変換装置B、A が生成した乱数ビットであり、他の装置には知られない値である。即ち、例えばS320の処理は以下とみなすことができる。
【００６９】
１．暗号化数値二進変換装置２１Ｂは
【００７０】
【数２４】
を受信する。
【００７１】
２．暗号化数値二進変換装置２１Ｂはｗ′ｋを用いて
【００７２】
【数２５】
を計算し、暗号化数値二進変換装置２１Ａに送信する。
【００７３】
３．暗号化数値二進変換装置２１Ａはｗ′′ｋを用いてＥ（ｚk）を計算し、暗号化数値二進変換装置２１Ｂに送信する。
【００７４】
上記の2、３の計算方法は、例えば非特許文献２に詳しく説明されている。また上記処理に応じて、例えばS321の処理は以下とみなすことができる。
【００７５】
１．暗号化数値二進変換装置２１ＢはS320の入出力
【００７６】
【数２６】
について、S310で生成したｗ′ｋを作用させた関係であることを零知識証明する。
２．暗号化数値二進変換装置２１Ａは当該暗号化数値二進変換装置２１Ｂの零知識証明が正しいことを確認する。
３．暗号化数値二進変換装置２１ＡはS320の入出力
【００７７】
【数２７】
について、S313で生成したｗ′′ｋを作用させた関係であることを零知識証明する。
４．暗号化数値二進変換装置２１Ｂは当該暗号化数値二進変換装置２１Ａの零知識証明が正しいことを確認する。
【００７８】
上記零知識証明もまた、例えば非特許文献２に詳しく説明されている。
【００７９】
最後にS322の具体例を説明する。
【００８０】
S322では、ｚ＝ｚ′であることを確認できれば良い。しかし本来の目的である、ｚを明かすことなく、Ｅ（ｚ）からｚの二進数表記の桁ごとの暗号文を生成するためには、Ｅ（ｚ）やＥ（ｚ′）を単純に復号することはできない。そこで、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ）、Ｅ（ｚ′）から、Ｅ（ｚ−ｚ′）を計算し、この復号結果が０であるかどうか確認することを考える。例えば、本技術分野で良く知られるテクニックとして以下の手続きが考えられる。
【００８１】
１．暗号化数値二進変換装置２１Aは０以上ｑ未満の乱数ｓを生成し、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ−ｚ′）からＥ（ｓ′（ｚ−ｚ′））を計算し、これを暗号化数値二進変換装置２１Ｂに送信する。
【００８２】
２．暗号化数値二進変換装置２１Ｂは同様に０以上ｑ未満の乱数ｓ′を生成し、Ｅ（ ）の加法準同型性を利用して、Ｅ（ｚ−ｚ′）からＥ（ｓ′（ｚ−ｚ′））を計算し、これを暗号化数値二進変換装置２１Ａに送信する。
【００８３】
３．暗号化数値二進変換装置２１Ａ、２１ＢはＥ（ ）の加法準同型性を利用して、Ｅ（ｓ（ｚ−ｚ′）），Ｅ（ｓ′（ｚ−ｚ′））からＥ（（ｓ＋ｓ′）（ｚ−ｚ′））を計算し、これを復号して(ｓ＋ｓ′）（ｚ−ｚ′）を得、当該復号結果が０であればｚ−ｚ′と判断し、そうでなければｚ−ｚ′≠０と判断する。
【００８４】
上記手続において、実際(ｓ＋ｓ′）（ｚ−ｚ′）ｍｏｄ ｑ＝０であれば、ｓ＋ｓ′ｍｏｄ ｑ＝０となる場合を除いてｚ−ｚ′ｍｏｄ ｑ＝０が成り立つ。いま、０≦ｚ，ｚ′＜２t＜ｑであるから、ｚ−ｚ′＝０がいえる。ｑはEl Gamal暗号の安全性の理由から一般に十分大きくとり、ｓ，ｓ′は乱数であることから、ｓ＋ｓ′ｍｏｄ ｑ＝０となる可能性は無視できる。また同様の議論により、(ｓ＋ｓ′）（ｚ−ｚ′）ｍｏｄ ｑ＝０であればｚ−ｚ′≠０がいえる。
【００８５】
なお、暗号化数値二進変換システム２０を構成する暗号化数値二進変換装置２１Ａ、２１Ｂは、キーボード、マウス、受信装置等の入力装置、CPUなどの制御装置、ROM、RAM、HDDなどの記憶装置、ディスプレイ、プリンタ、送信装置などの出力装置からなる一般的なコンピュータシステムにより構成されるものである。
【００８６】
入力提供装置１０からの入力、秘匿回路計算装置３０への出力、暗号化数値二進変換装置２１Ａ、２１Ｂ間でのデータの送受信は入力装置、出力装置により行われる。また、各ステップを実行することは、ROM、RAM、HDDに格納されているプログラムに則って行われるものである。
【００８７】
また、ROM、RAM、HDD内に格納されるプログラムは、CD-ROM、DVD-ROM、フロッピーディスク、USBメモリなどの読み取り可能な記録媒体からこれらの入力装置を介して移入される形態やインターネットなどのネットワークを介して受信装置より移入される形態がある。本発明によるシステムはこれらのプログラムにより一般的なコンピュータシステム上に構築されるものであり、本発明にはこれらのプログラムや該プログラムを格納した記録媒体が含まれる。
【符号の説明】
【００８８】
１０ 入力提供装置
２０ 暗号化数値二進変換システム
２１Ａ、２１Ｂ 暗号化数値二進変換装置
３０ 秘匿回路計算装置
【特許請求の範囲】
【請求項１】
第１及び第２の暗号化数値二進変換装置を備え、Ｅ（ ）をEl Gamal暗号の暗号化関数とし、ｚを0以上2t−1以下の整数とし、ｔを偶数とし、Ｇ，ｑ，ｙをEl Gamal暗号のパラメータとし、Ｆ（ ）を群Ｇに写すハッシュ関数として、ある数値の暗号文を二進表記した桁ごとに暗号化した暗号文を生成する暗号化数値二進変換システムであって、
前記第１の暗号化数値二進変換装置は、
Ｅ（ｚ）を受信し、
０以上ｑ未満の整数ｕ，ｖAを選び、
Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算し、
Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算し、
【数１】
を生成し、特にＣiはラベルｉと対応付けておき、
置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得、
ＤA及び<π（ｉ）：Ｃi>を前記第２の暗号化数値二進変換装置Ｂに送信し、
前記第２の暗号化数値二進変換装置は、
ＤAを復号し、ＤB=yz-uを得、
Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′jはラベルｊと対応付けておき、
置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得、
<π′（ｊ）：Ｃ′j>を前記第１の暗号化数値二進変換装置Ａに送信し、
前記第１の暗号化数値二進変換装置は、
Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておき、
置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得、
＜π′′（π′（ｊ））：Ｃ′′j＞を前記第２の暗号化数値二進変換装置に送信し、
前記第２の暗号化数値二進変換装置は、
Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておき、
置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得、
＜π′′′（π（ｉ））：Ｃ′′′i＞を前記第１の暗号化数値二進変換装置に送信し、
前記第１及び第２の暗号化数値二進変換装置は、
Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【数２】
を得、
【数３】
を暗号化し、
【数４】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得ることを特徴とする暗号化数値二進変換システム。
【請求項２】
請求項１記載の暗号化数値二進変換システムにおいて、
前記第１及び第２の暗号化数値二進変換装置は、さらに、零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認し、
Ｅ（ｚ）の復号結果と
【数５】
の復号結果が等しいことを確認する暗号化数値二進変換システム。
【請求項３】
第１及び第２の暗号化数値二進変換装置を備える暗号文を生成する暗号化数値二進変換システムで、ある数値の暗号文を二進表記した桁ごとに暗号化する暗号化数値二進変換方法であって、
Ｅ（ ）をEl Gamal暗号の暗号化関数とし、ｚを0以上2t−1以下の整数とし、ｔを偶数とし、Ｇ，ｑ，ｙをEl Gamal暗号のパラメータとし、Ｆ（ ）を群Ｇに写すハッシュ関数として、
前記第１の暗号化数値二進変換装置が行う、
Ｅ（ｚ）を受信するステップと、
０以上ｑ未満の整数ｕ，ｖAを選ぶステップと、
Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算するステップと、
Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算するステップと、
【数６】
を生成し、特にＣiはラベルｉと対応付けておくステップと、
置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得るステップと、
ＤA及び<π（ｉ）：Ｃi>を前記第２の暗号化数値二進変換装置に送信するステップと、
前記第２の暗号化数値二進変換装置Ｂが行う、
ＤAを復号し、ＤB=yz-uを得るステップと、
Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′jはラベルｊと対応付けておくステップと、
置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得るステップと、
<π′（ｊ）：Ｃ′j>を前記第１の暗号化数値二進変換装置に送信するステップと、
前記第１の暗号化数値二進変換装置が行う、
Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておくステップと、
置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得るステップと、
＜π′′（π′（ｊ））：Ｃ′′j＞を前記第２の暗号化数値二進変換装置に送信するステップと、
前記第２の暗号化数値二進変換装置が行う、
Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておくステップと、
置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得るステップと、
＜π′′′（π（ｉ））：Ｃ′′′i＞を前記第１の暗号化数値二進変換装置に送信するステップと、
前記第１及び第２の暗号化数値二進変換装置が行う、
Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【数７】
を得るステップと、
【数８】
を暗号化するステップと、
【数９】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得るステップと、を有する暗号化数値二進変換方法。
【請求項４】
請求項３記載の暗号化数値二進変換方法において、前記第１及び第２の暗号化数値二進変換装置が行う、
零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認するステップと、
Ｅ（ｚ）の復号結果と
【数１０】
の復号結果が等しいことを確認するステップと、をさらに有する暗号化数値二進変換方法。
【請求項５】
請求項３または請求項４記載の暗号化数値二進変換方法をコンピュータに実行させるプログラム。
【請求項１】
第１及び第２の暗号化数値二進変換装置を備え、Ｅ（ ）をEl Gamal暗号の暗号化関数とし、ｚを0以上2t−1以下の整数とし、ｔを偶数とし、Ｇ，ｑ，ｙをEl Gamal暗号のパラメータとし、Ｆ（ ）を群Ｇに写すハッシュ関数として、ある数値の暗号文を二進表記した桁ごとに暗号化した暗号文を生成する暗号化数値二進変換システムであって、
前記第１の暗号化数値二進変換装置は、
Ｅ（ｚ）を受信し、
０以上ｑ未満の整数ｕ，ｖAを選び、
Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算し、
Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算し、
【数１】
を生成し、特にＣiはラベルｉと対応付けておき、
置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得、
ＤA及び<π（ｉ）：Ｃi>を前記第２の暗号化数値二進変換装置Ｂに送信し、
前記第２の暗号化数値二進変換装置は、
ＤAを復号し、ＤB=yz-uを得、
Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′jはラベルｊと対応付けておき、
置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得、
<π′（ｊ）：Ｃ′j>を前記第１の暗号化数値二進変換装置Ａに送信し、
前記第１の暗号化数値二進変換装置は、
Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておき、
置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得、
＜π′′（π′（ｊ））：Ｃ′′j＞を前記第２の暗号化数値二進変換装置に送信し、
前記第２の暗号化数値二進変換装置は、
Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておき、
置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得、
＜π′′′（π（ｉ））：Ｃ′′′i＞を前記第１の暗号化数値二進変換装置に送信し、
前記第１及び第２の暗号化数値二進変換装置は、
Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【数２】
を得、
【数３】
を暗号化し、
【数４】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得ることを特徴とする暗号化数値二進変換システム。
【請求項２】
請求項１記載の暗号化数値二進変換システムにおいて、
前記第１及び第２の暗号化数値二進変換装置は、さらに、零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認し、
Ｅ（ｚ）の復号結果と
【数５】
の復号結果が等しいことを確認する暗号化数値二進変換システム。
【請求項３】
第１及び第２の暗号化数値二進変換装置を備える暗号文を生成する暗号化数値二進変換システムで、ある数値の暗号文を二進表記した桁ごとに暗号化する暗号化数値二進変換方法であって、
Ｅ（ ）をEl Gamal暗号の暗号化関数とし、ｚを0以上2t−1以下の整数とし、ｔを偶数とし、Ｇ，ｑ，ｙをEl Gamal暗号のパラメータとし、Ｆ（ ）を群Ｇに写すハッシュ関数として、
前記第１の暗号化数値二進変換装置が行う、
Ｅ（ｚ）を受信するステップと、
０以上ｑ未満の整数ｕ，ｖAを選ぶステップと、
Ｅ（ ）の加法準同型性を利用してＥ（ｚ）からＥ（ｚ−ｕ）を計算するステップと、
Ｅ（ｚ−ｕ）の部分復号結果ＤAを計算するステップと、
【数６】
を生成し、特にＣiはラベルｉと対応付けておくステップと、
置換関数πを選び、ｉ→π（ｉ）としてラベル付きハッシュ値<π（ｉ）：Ｃi>を得るステップと、
ＤA及び<π（ｉ）：Ｃi>を前記第２の暗号化数値二進変換装置に送信するステップと、
前記第２の暗号化数値二進変換装置Ｂが行う、
ＤAを復号し、ＤB=yz-uを得るステップと、
Ｃ′j＝Ｆ（yu-z+j）vB（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′jはラベルｊと対応付けておくステップと、
置換関数π′を選び、ｊ→π′（ｊ）としてラベル付きハッシュ値<π′（ｊ）：Ｃ′j>を得るステップと、
<π′（ｊ）：Ｃ′j>を前記第１の暗号化数値二進変換装置に送信するステップと、
前記第１の暗号化数値二進変換装置が行う、
Ｃ′′j＝Ｃ′jvA（ｊ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′jはラベルπ′（ｊ）と対応付けておくステップと、
置換関数π′′を選び、π′（ｊ）→π′′（π′（ｊ））としてラベル付きハッシュ値＜π′′（π′（ｊ））：Ｃ′′j＞を得るステップと、
＜π′′（π′（ｊ））：Ｃ′′j＞を前記第２の暗号化数値二進変換装置に送信するステップと、
前記第２の暗号化数値二進変換装置が行う、
Ｃ′′′i＝ＣivB（ｉ＝０，・・・，２t/2−１）を生成し、特に、Ｃ′′′iはラベルπ（ｉ）と対応付けておくステップと、
置換関数π′′′を選び、π（ｉ）→π′′′（π（ｉ））としてラベル付きハッシュ値＜π′′′（π（ｉ））：Ｃ′′′i＞を得るステップと、
＜π′′′（π（ｉ））：Ｃ′′′i＞を前記第１の暗号化数値二進変換装置に送信するステップと、
前記第１及び第２の暗号化数値二進変換装置が行う、
Ｃ′′′I＝Ｃ′′JとなるＣ′′′I，Ｃ′′Jを探し、対応するラベル
【数７】
を得るステップと、
【数８】
を暗号化するステップと、
【数９】
を作用させてＥ（Ｉk），Ｅ（Ｊk）を得るステップと、を有する暗号化数値二進変換方法。
【請求項４】
請求項３記載の暗号化数値二進変換方法において、前記第１及び第２の暗号化数値二進変換装置が行う、
零知識証明を用いて、Ｅ（Ｉk），Ｅ（Ｊk）がそれぞれ正しくπ-1・π′′′-1，π′-1・π′′-1を作用させた結果であることを確認するステップと、
Ｅ（ｚ）の復号結果と
【数１０】
の復号結果が等しいことを確認するステップと、をさらに有する暗号化数値二進変換方法。
【請求項５】
請求項３または請求項４記載の暗号化数値二進変換方法をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１１−１３５４４（Ｐ２０１１−１３５４４Ａ）
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願番号】特願２００９−１５８７９２（Ｐ２００９−１５８７９２）
【出願日】平成２１年７月３日（２００９．７．３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年１月２０日（２０１１．１．２０）
【国際特許分類】
【出願日】平成２１年７月３日（２００９．７．３）
【公序良俗違反の表示】
（特許庁注：以下のものは登録商標）
１．フロッピー
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]