暗号化数値二進変換システム、暗号化数値二進変換方法、暗号化数値二進変換プログラム
【課題】Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値の二進数表記の桁ごとに暗号化すること。
【解決手段】本発明は、１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムに適用される。本発明の暗号化数値二進変換システム２０は、先ず、関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成する。次に、Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求める。次に、π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める。最後に、Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める。
【解決手段】本発明は、１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムに適用される。本発明の暗号化数値二進変換システム２０は、先ず、関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成する。次に、Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求める。次に、π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める。最後に、Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、ある数値の暗号文を入力として、当該数値を復元する事無く、当該数値を二進数表記した桁ごとに暗号化した暗号文を生成する技術に関する。
【背景技術】
【０００２】
非特許文献１では、Ｐａｉｌｌｉｅｒ暗号によって暗号化された数値に対して、当該数値を明かす事無く、当該数値を二進数表記した桁ごとに暗号化した暗号文を生成する方法が開示されている。
【０００３】
また、二進数表記した数値を桁ごとに暗号化することで、当該数値の任意の論理演算を、当該数値を明かすこと無く実行可能とする方法も知られている（例えば、非特許文献２）。このような論理演算は、秘匿回路計算と称されている。
【０００４】
従って、非特許文献１に開示された方法を用いれば、数値の暗号文を入力として秘匿回路計算が実行できるようになる。これにより、秘匿回路計算の入力を提供する装置（入力提供装置）は、数値の暗号文のみを計算、保存すれば良く、当該数値を二進数表記した桁ごとの暗号文を計算、保存する必要が無くなる。
【０００５】
そのため、非特許文献１に開示された方法は、入力提供装置が計算資源やメモリ資源に乏しい場合に特に有効な方法となる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】B. Schoenmakers and P. Tuyls, Efficient binary conversion for Paillier encrypted values, Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science 4004, pp. 522-537, Springer-Verlag, 2006.
【非特許文献２】G. Yamamoto, K. Chida, A. Nasciment, K. Suzuki, and S. Uchiyama, Efficient, non-optimistic secure circuit evaluation based on the ElGamal encryption, WISA 2005, Lecture Notes in Computer Science, pp. 328-343, Springer-Verlag, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献２に開示された方法は、Ｅｌ Ｇａｍａｌ暗号によって数値を二進数表記の桁ごとに暗号化したものに対して秘匿回路計算を実現している。
【０００８】
一方、非特許文献１に開示された方法は、Ｐａｉｌｌｉｅｒ暗号によって暗号化された暗号文を対象としている。
【０００９】
そのため、非特許文献１に開示された方法を用いることで実現されるのは、Ｐａｉｌｌｉｅｒ暗号によって数値を二進数表記の桁ごとに暗号化したものに対する秘匿回路計算となる。
【００１０】
しかし、Ｐａｉｌｌｉｅｒ暗号は、Ｅｌ Ｇａｍａｌ暗号と比べて、暗号文のサイズや復号処理、ゼロ知識証明等に要する計算量が多いため、秘匿回路計算におけるデータサイズや計算量が増大してしまうという課題がある。
【００１１】
そこで、本発明の目的は、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値の二進数表記の桁ごとに暗号化することができる暗号化数値二進変換システム、暗号化数値二進変換方法、暗号化数値二進変換プログラムを提供することである。
【課題を解決するための手段】
【００１２】
本発明の第１の暗号化数値二進変換システムは、
１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成し、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求め、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求めることを特徴とする。
【００１３】
本発明の第２の暗号化数値二進変換システムは、
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成し、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求め、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求めることを特徴とする。
【発明の効果】
【００１４】
本発明は、楕円曲線の有理点群を利用したＥｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値の二進数表記の桁ごとに暗号化を行う。Ｅｌ Ｇａｍａｌ暗号は、Ｐａｉｌｌｉｅｒ暗号と比べて、暗号文のサイズや復号処理、ゼロ知識証明等に要する計算量が小さくすむことが期待できる。
【００１５】
そのため、本発明は、非特許文献１に開示された方法と比べて、秘匿回路計算におけるデータサイズ削減や計算量削減が見込めるという効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施例１，２の暗号化数値二進変換システムの構成を説明する図である。
【図２】本発明の実施例１の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【図３】本発明の実施例２の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【図４】本発明の実施例３の暗号化数値二進変換システムの構成を説明する図である。
【図５】本発明の実施例３の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１７】
図１に示すように、本実施例の暗号化数値二進変換システム２０は、暗号化数値二進変換装置２１Ａ，２１Ｂを有し、ある数値の暗号文を入力として秘匿回路計算を実行するための当該数値の二進数表記の桁ごとの暗号文を生成する。
【００１８】
なお、図１において、１以上の入力提供装置１０は、秘匿回路計算の入力となる、ある数値の暗号文を暗号化数値二進変換システム２０に提供する。また、１以上の秘匿回路計算装置３０は、暗号化数値二進変換システム２０にて生成された二進数表記の桁ごとの暗号文を基に秘匿回路計算を実行する。
【００１９】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂにおいて、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成するための処理手順について説明する。
【００２０】
最初に、Ｅｌ Ｇａｍａｌ暗号の構成例について説明しておく。
【００２１】
Ｅｌ Ｇａｍａｌ暗号の場合、ｇを素数位数ｑの乗法群Ｇの生成元とし、ｇ，ｑ，Ｇを公開情報としたとき、先ず、鍵ペア（ｘ，ｙ＝ｇx）を生成する。ここで、ｘは０以上ｑ未満の整数からなる秘密鍵であり、ｙは公開鍵である。ここでは、暗号化数値二進変換装置２１Ｂが当該鍵ペアを生成し、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとする。
【００２２】
次に、Ｅ（・）をＥｌ Ｇａｍａｌ暗号の暗号化関数としたとき、Ｇの元ｚの暗号文をＥ（ｚ）＝（Ａ，Ｂ）＝（ｇr，ｚ×ｙr）とする。ここで、ｒは０以上ｑ未満の乱数である。復号に秘密鍵ｘを用いることで、復号処理の結果ｚ＝Ｂ／Ａxを得ることができる。なお、ｚを０以上ｑ未満の整数としたいときは、Ｅ（ｚ）＝（ｇr，ｙr+z）としても良い。非特許文献２に開示された方法では、この形式のＥ（ｚ）を用いている。ただし、この形式の場合、上記の復号処理の結果はｙzとなり、ｙzからｚを求める必要がある。ｚの候補数が多くなるとｙzからｚを求めることは一般に困難となるため、ｚの候補数は予め少なく設定することが望ましい。
【００２３】
本発明では、非特許文献２に開示された方法とＥ（ｚ）の形式が同様であることを前提とし、以降説明の簡略化のため、入力提供装置１０は単一とし、当該入力提供装置１０がＥ（ｚ）を生成し、暗号化数値二進変換装置２１Ａに送信するものとする。なお、ｚは０（＝ａ）以上２t−１（＝ｂ）以下の整数とする（ｔは適当な自然数）。
【００２４】
すなわち、本発明が解決しようとする課題は、ｚを二進数表記したときの下位ｊ＋１桁目をｚjと表記したとき、ｚを復元すること無く、Ｅ（ｚ）から、Ｅ（ｚt-1），・・・，Ｅ（ｚ0）を生成することである。
【００２５】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂの処理手順の概略を、図２を用いて説明する。
【００２６】
先ず、暗号化数値二進変換装置２１Ａは、ステップＡ１において、Ｅ（ｚ）を受信すると、ステップＡ２において、ある関数Ｆによって０から２t−１までの各整数ｉに対応するデータＦ（ｉ）、及び、Ｅ（Ｆ（ｚ））を生成し、ｉに対してある置換関数πを作用させることで得られる２t個のデータ（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を、Ｅ（Ｆ（ｚ））とともに暗号化数値二進変換装置２１Ｂに送信する。
【００２７】
次に、（π（ｉ）：Ｆ（ｉ））及びＥ（Ｆ（ｚ））を受信した暗号化数値二進変換装置２１Ｂは、ステップＡ３において、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）を取得し、（π（ｉ）：Ｆ（ｉ））からＦ（ｚ）と一致するＦ（ｉ）を探索し、対応するπ（ｉ）を取得し、ステップＡ４において、π（ｉ）をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成し、Ｅ（ｗj）を暗号化数値二進変換装置２１Ａに送信する。
【００２８】
最後に、Ｅ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を受信した暗号化数値二進変換装置２１Ａは、ステップＡ５において、Ｅ（ｗj）に対してπ-1を作用させ、Ｅ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。
【００２９】
上記の各処理について具体例を与える。
【００３０】
先ず、Ｆとして、例えば、０以上ｑ未満の整数ｕを用いて、Ｆ（ｉ）＝ｙ(i+1)uとする。この場合、暗号化数値二進変換装置２１Ａは、Ｅ（ｚ）から、Ｅ（Ｆ（ｚ））＝（（ｇr）u，（ｙr+z）u×ｙu）が計算可能となる。また、Ｆは、暗号化数値二進変換装置２１Ａ以外はＦ（ｉ）からｉを求めることが困難となるようにする必要がある。そして、πとして、例えば、二進数表記でｔ桁の数値ｖを用いて
【００３１】
【数１】
【００３２】
とする。ここで、
【００３３】
【数２】
【００３４】
はｉを二進数表記し、ｉとｖを各桁ごとにＸＯＲ演算した結果を並べたものとする。
【００３５】
すると、暗号化数値二進変換装置２１Ｂは、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）＝ｙ(z+1)uを得ることができ、（π（ｉ）：Ｆ（ｉ））のＦ（ｉ）の中からＦ（ｚ）と一致するものを探索し、対応する
【００３６】
【数３】
【００３７】
を得ることができる。したがって、
【００３８】
【数４】
【００３９】
となり（ｖjはｖの二進数表記の下位ｊ＋１桁目）、ｖjを所持している暗号化数値二進変換装置２１Ａは、Ｅ（ｗj）に対してπ-1を作用させた結果となる、
【００４０】
【数５】
【００４１】
（ｊ＝０，１，・・・，ｔ−１）を得ることができる。ここで、Ｅ（１−ｗj）は、Ｅ（ｗj）から生成できることが知られており、例えば、非特許文献２にも開示されていることから、ここでは生成方法は省略する。
【００４２】
以上により、暗号化数値二進変換装置２１Ａは、Ｅ（ｚj）を得ることができ、得られたＥ（ｚj）を秘匿回路計算装置３０に送信する。１以上からなる秘匿回路計算装置３０は、例えば、非特許文献２に開示された方法により秘匿回路計算を実行する。なお、非特許文献２に開示された方法によれば秘匿回路計算装置３０は２以上を必要とする。
【００４３】
以上、本実施例では、Ｆやπについて具体例を与えたが、勿論これに限るものではない。例えば、本実施例では、（π（ｉ）：Ｆ（ｉ））を（π（ｉ）：Ｈａｓｈ（Ｆ（ｉ）））とし（Ｈａｓｈ（・）は適当なハッシュ関数）、暗号化数値二進変換装置２１Ｂは、Ｆ（ｚ）をＨａｓｈ（Ｆ（ｚ））に変換してからＨａｓｈ（Ｆ（ｉ））との一致探索を行うとしても良い。また、πとしてπ（ｉ）＝ｚ＋ｖ等としても良い。この場合、Ｅ（ｗj）からＥ（ｚj）を求めるためには、非特許文献１にしたがえば、暗号化数値二進変換装置２１Ａ，２１Ｂが協力する必要がある。
【００４４】
また、本実施例では、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとしたが、非特許文献２に開示された方法のように、ｘを暗号化数値二進変換装置２１Ａ，２１Ｂが分散所持するものとしても良い。この場合、いま、暗号化数値二進変換装置２１Ａ，２１Ｂがそれぞれ分散された秘密鍵ｘA，ｘBを所持するものとすると、暗号化数値二進変換装置２１ＡはＥ（Ｆ（ｚ））に対してｘAを用いて部分的に復号したものを暗号化数値二進変換装置２１Ｂに送信し、それを受信した暗号化数値二進変換装置２１Ｂは、ｘBを用いてＥ（Ｆ（ｚ））を完全に復号することができる。
【００４５】
また、本実施例では、秘匿回路計算装置３０を２つとし、それぞれ暗号化数値二進変換装置２１Ａ，２１Ｂと同一の装置として構成しても良い。この場合、上述の秘密鍵の分散所持は、非特許文献２の秘匿回路計算で必要となるため、このようにすることが望ましい。
【００４６】
更に、本実施例では、暗号化数値二進変換システム２０を２つの暗号化数値二進変換装置２１Ａ，２１Ｂで構成したが、１つの暗号化数値二進変換装置で構成しても良い。
【実施例２】
【００４７】
本実施例の暗号化数値二進変換システム２０は、実施例１と比べて、構成自体は同様であるが、暗号化数値二進変換装置２１Ａ，２１Ｂにおいて、Ｅ（ｚj）が正しくｚの二進数表記における桁ごとの暗号文となっているかどうか検証を行う点が異なる。
【００４８】
なお、ここでは、実施例１の処理手順に基づき、
【００４９】
【数６】
【００５０】
とし（ｕ，ｕ′は適当な乱数）、入力提供装置１０の処理は同様とし、秘匿回路計算装置３０は非特許文献２に開示された方法により秘匿回路計算を実行するものとする。
【００５１】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂの処理手順を、図３を用いて説明する。
説明する。
【００５２】
先ず、暗号化数値二進変換装置２１Ａは、ステップＢ１において、Ｅ（ｚ）を受信すると、ステップＢ２において、０から２t−１までの各整数ｉに対応するデータＦ（ｉ）＝ｙiu+u′、及びＥ（Ｆ（ｚ））を生成し、２t個のデータ
【００５３】
【数７】
【００５４】
（ｉ＝０，１，・・・，２t−１）を、Ｅ（Ｆ（ｚ））とともに暗号化数値二進変換装置Ｂに送信する。
【００５５】
次に、
【００５６】
【数８】
【００５７】
及びＥ（Ｆ（ｚ））を受信した暗号化数値二進変換装置２１Ｂは、ステップＢ３において、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）を取得し、
【００５８】
【数９】
【００５９】
からＦ（ｚ）と一致するＦ（ｉ）を探索し、対応する
【００６０】
【数１０】
【００６１】
を取得し、ステップＢ４において、
【００６２】
【数１１】
【００６３】
をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成する。また、ステップＢ４においては、更に、暗号化数値二進変換装置２１Ｂは、Ｅ（ｗj）の復号結果ｗjが０または１のどちらかであることを示すためにゼロ知識証明による証明情報を生成し、Ｅ（ｗj）及び当該証明情報を暗号化数値二進変換装置２１Ａに送信する。
【００６４】
次に、Ｅ（ｗj）（ｊ＝０，１，・・・，ｔ−１）及び当該証明情報を受信した暗号化数値二進変換装置２１Ａは、ステップＢ５において、当該証明情報を検証し、正しいと判断した場合は、Ｅ（ｗj）からＥ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。一方、当該証明情報が不正と判断した場合は、暗号化数値二進変換装置２１Ａは、以降の処理を行わない等、例外的措置をとる。なお、暗号化数値二進変換装置２１Ａは、Ｅ（ｚj）を正しく生成したとは限らないため、Ｅ（ｚj）をＥ（ｚ′j）と表記する。
【００６５】
最後に、暗号化数値二進変換装置２１Ａ，２１Ｂは、ステップＢ６において、Ｅ（ｚ′j）から
【００６６】
【数１２】
【００６７】
を計算し、
【００６８】
【数１３】
【００６９】
の復号結果とＥ（ｚ）の復号結果とが等しいかどうか、それぞれの暗号文を復号すること無く検証する。等しければＥ（ｚ′j）は正しく生成されていることになる。
【００７０】
当該検証方法として、例えば、暗号化数値二進変換装置２１Ａは、１以上ｑ未満の乱数ａを生成し、
【００７１】
【数１４】
【００７２】
から
【００７３】
【数１５】
【００７４】
を計算し、同様に暗号化数値二進変換装置２１Ｂは、１以上ｑ未満の乱数ｂを生成し、
【００７５】
【数１６】
【００７６】
から
【００７７】
【数１７】
【００７８】
を計算する。
【００７９】
次に、暗号化数値二進変換装置２１Ａ，２１Ｂは、
【００８０】
【数１８】
【００８１】
から
【００８２】
【数１９】
【００８３】
を計算し、
【００８４】
【数２０】
【００８５】
を復号し、復号結果が０であれば
【００８６】
【数２１】
【００８７】
の復号結果とＥ（ｚ）の復号結果が等しいと判断する。その理由は、ｚと
【００８８】
【数２２】
【００８９】
が等しければ、
【００９０】
【数２３】
【００９１】
の復号結果はａ，ｂにかかわらず０となり、異なれば当該復号結果が０になることは、ａ，ｂが乱数であることからその確率が低くなるためである。なお、例えば、
【００９２】
【数２４】
【００９３】
から
【００９４】
【数２５】
【００９５】
を計算することはＥ（・）の準同型性により可能であることが非特許文献２等で開示されている。具体的には、Ｅ（ｚ）＝（Ａ，Ｂ），Ｅ（ｚ′）＝（Ａ′，Ｂ′）としたとき、（ＡＡ′，ＢＢ′）＝Ｅ（ｚ＋ｚ′）となり、また、整数ｃに対して（Ａc，Ｂc）＝Ｅ（ｃｚ）となることが知られているため、このような処理を実行すれば良い。
【実施例３】
【００９６】
図４に示すように、本実施例の暗号化数値二進変換システム２０は、実施例１，２と比べて、３つの暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃを有する点が異なる。
【００９７】
なお、図３では、暗号化数値二進変換装置の数を３と固定しているが、本実施例は、４つ以上であっても同様の処理が可能である。
【００９８】
ここでは、入力提供装置１０の処理は実施例１と同様とし、秘匿回路計算装置３０は非特許文献２に開示された方法により秘匿回路計算を実行するものとする。
【００９９】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃの処理手順の概略を、図５を用いて説明する。
【０１００】
ここでは、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、秘密鍵ｘを分散所持し、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃの全装置が処理した場合に限り、Ｅ（・）によって暗号化された暗号文を復号できるものとし、また、０から２t−１までの各整数ｉの暗号文Ｅ（ｉ）を生成する。
【０１０１】
先ず、暗号化数値二進変換装置２１Ａは、ステップＣ１において、Ｅ（ｚ）を受信する。
【０１０２】
すると、暗号化数値二進変換装置２１Ａは、ステップＣ２において、ある関数ＦAによってＥ（ｉ）を変換したＦA（Ｅ（ｉ））を生成し、ｉにある置換関数πAを作用させることで得られる２t個のデータ（πA（ｉ）：ＦA（Ｅ（ｉ）））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ｂに送信する。
【０１０３】
次に、（πA（ｉ）：ＦA（Ｅ（ｉ）））（ｉ＝０，１，・・・，２t−１）を受信した暗号化数値二進変換装置２１Ｂは、ある関数ＦBによってＦA（Ｅ（ｉ））を変換したＦB（ＦA（Ｅ（ｉ）））を生成し、πA（ｉ）にある置換関数πBを作用させることで得られる２t個のデータ（πB（πA（ｉ））：ＦB（ＦA（Ｅ（ｉ））））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ｃに送信する。
【０１０４】
次に、（πB（πA（ｉ））：ＦB（ＦA（Ｅ（ｉ））））（ｉ＝０，１，・・・，２t−１）を受信した暗号化数値二進変換装置２１Ｃは、ある関数ＦCによってＦB（ＦA（Ｅ（ｉ）））を変換したＦC（ＦB（ＦA（Ｅ（ｉ））））を生成し、πB（πA（ｉ））にある置換関数πCを作用させることで得られる２t個のデータ（πC（πB（πA（ｉ）））：ＦC（ＦB（ＦA（Ｅ（ｉ）））））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ａ，２１Ｂに送信する。
【０１０５】
次に、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、ステップＣ３において、当該ＦC（ＦB（ＦA（Ｅ（ｉ））））に対応するｉとＥ（ｚ）に対応するｚとの一致探索を行い、対応するπC（πB（πA（ｉ）））を得る。そして、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、ステップＣ４において、πC（πB（πA（ｉ）））をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成する。
【０１０６】
最後に、ステップＣ５において、Ｅ（ｗj）に対して暗号化数値二進変換装置２１Ｃ，２１Ｂ，２１Ａの順に、それぞれが
【０１０７】
【数２６】
【０１０８】
を作用させ、Ｅ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。
【０１０９】
上記の各処理について具体例を与える。
【０１１０】
先ず、ＦA，ＦB，ＦCとして、例えば、非特許文献２に開示されたような再暗号化手法がある。すなわち、ある数値ｚの暗号文Ｅ（ｚ）＝（ｇr，ｙr+z）に対し、０以上ｑ未満の乱数ｓを用いて、（ｇr+s，ｙr+s+z）＝（ｇrｇs，ｙr+zｙs）を計算し、これをＥ（ｚ）に置き換える。数値ｚを変えること無く暗号文が変化するため、置換関数を作用させることで（ｇr，ｙr+z）と（ｇr+s，ｙr+s+z）との対応関係を秘匿することが可能となる。ＦC（ＦB（ＦA（Ｅ（ｉ））））に対応するｉと、Ｅ（ｚ）に対応するｚとの一致探索は、ＦA，ＦB，ＦCを上述の再暗号化手法とすることで、Ｅ（πC（πB（πA（ｉ））））とＥ（ｚ）の復号結果との一致探索となるため、実施例２で示したような方法を用いれば良い。なお、πA，πB，πCや
【０１１１】
【数２７】
【０１１２】
の作用は実施例１と同様で良く、その説明は省略する。
【０１１３】
以上により、暗号化数値二進変換システム２０を３つ以上の暗号化数値二進変換装置で構成した場合でも、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成することが可能となる。
【０１１４】
以上、本発明を実施例を参照して説明したが、本発明は上記実施例に限定されものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１１５】
例えば、実施例３に、実施例２で示されたＥ（ｚj）の検証方法を適用しても良い。
【０１１６】
また、実施例１，２，３では、暗号化数値二進変換システム２０を複数の暗号化数値二進変換装置で構成したが、１つの暗号化数値二進変換装置で構成しても良い。更に、この場合、その暗号化数値二進変換装置にて行われる暗号化数値二進変換方法を、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１７】
１０ 入力提供装置
２０ 暗号化数値二進変換システム
２１Ａ，２１Ｂ，２１Ｃ 暗号化数値二進変換装置
３０ 秘匿回路計算装置
【技術分野】
【０００１】
本発明は、暗号応用技術に関し、特に、ある数値の暗号文を入力として、当該数値を復元する事無く、当該数値を二進数表記した桁ごとに暗号化した暗号文を生成する技術に関する。
【背景技術】
【０００２】
非特許文献１では、Ｐａｉｌｌｉｅｒ暗号によって暗号化された数値に対して、当該数値を明かす事無く、当該数値を二進数表記した桁ごとに暗号化した暗号文を生成する方法が開示されている。
【０００３】
また、二進数表記した数値を桁ごとに暗号化することで、当該数値の任意の論理演算を、当該数値を明かすこと無く実行可能とする方法も知られている（例えば、非特許文献２）。このような論理演算は、秘匿回路計算と称されている。
【０００４】
従って、非特許文献１に開示された方法を用いれば、数値の暗号文を入力として秘匿回路計算が実行できるようになる。これにより、秘匿回路計算の入力を提供する装置（入力提供装置）は、数値の暗号文のみを計算、保存すれば良く、当該数値を二進数表記した桁ごとの暗号文を計算、保存する必要が無くなる。
【０００５】
そのため、非特許文献１に開示された方法は、入力提供装置が計算資源やメモリ資源に乏しい場合に特に有効な方法となる。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】B. Schoenmakers and P. Tuyls, Efficient binary conversion for Paillier encrypted values, Advances in Cryptology - EUROCRYPT 2006, Lecture Notes in Computer Science 4004, pp. 522-537, Springer-Verlag, 2006.
【非特許文献２】G. Yamamoto, K. Chida, A. Nasciment, K. Suzuki, and S. Uchiyama, Efficient, non-optimistic secure circuit evaluation based on the ElGamal encryption, WISA 2005, Lecture Notes in Computer Science, pp. 328-343, Springer-Verlag, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献２に開示された方法は、Ｅｌ Ｇａｍａｌ暗号によって数値を二進数表記の桁ごとに暗号化したものに対して秘匿回路計算を実現している。
【０００８】
一方、非特許文献１に開示された方法は、Ｐａｉｌｌｉｅｒ暗号によって暗号化された暗号文を対象としている。
【０００９】
そのため、非特許文献１に開示された方法を用いることで実現されるのは、Ｐａｉｌｌｉｅｒ暗号によって数値を二進数表記の桁ごとに暗号化したものに対する秘匿回路計算となる。
【００１０】
しかし、Ｐａｉｌｌｉｅｒ暗号は、Ｅｌ Ｇａｍａｌ暗号と比べて、暗号文のサイズや復号処理、ゼロ知識証明等に要する計算量が多いため、秘匿回路計算におけるデータサイズや計算量が増大してしまうという課題がある。
【００１１】
そこで、本発明の目的は、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値の二進数表記の桁ごとに暗号化することができる暗号化数値二進変換システム、暗号化数値二進変換方法、暗号化数値二進変換プログラムを提供することである。
【課題を解決するための手段】
【００１２】
本発明の第１の暗号化数値二進変換システムは、
１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成し、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求め、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求めることを特徴とする。
【００１３】
本発明の第２の暗号化数値二進変換システムは、
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成し、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求め、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求めることを特徴とする。
【発明の効果】
【００１４】
本発明は、楕円曲線の有理点群を利用したＥｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値の二進数表記の桁ごとに暗号化を行う。Ｅｌ Ｇａｍａｌ暗号は、Ｐａｉｌｌｉｅｒ暗号と比べて、暗号文のサイズや復号処理、ゼロ知識証明等に要する計算量が小さくすむことが期待できる。
【００１５】
そのため、本発明は、非特許文献１に開示された方法と比べて、秘匿回路計算におけるデータサイズ削減や計算量削減が見込めるという効果が得られる。
【図面の簡単な説明】
【００１６】
【図１】本発明の実施例１，２の暗号化数値二進変換システムの構成を説明する図である。
【図２】本発明の実施例１の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【図３】本発明の実施例２の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【図４】本発明の実施例３の暗号化数値二進変換システムの構成を説明する図である。
【図５】本発明の実施例３の暗号化数値二進変換システムによる暗号化数値二進変換方法を説明するフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１７】
図１に示すように、本実施例の暗号化数値二進変換システム２０は、暗号化数値二進変換装置２１Ａ，２１Ｂを有し、ある数値の暗号文を入力として秘匿回路計算を実行するための当該数値の二進数表記の桁ごとの暗号文を生成する。
【００１８】
なお、図１において、１以上の入力提供装置１０は、秘匿回路計算の入力となる、ある数値の暗号文を暗号化数値二進変換システム２０に提供する。また、１以上の秘匿回路計算装置３０は、暗号化数値二進変換システム２０にて生成された二進数表記の桁ごとの暗号文を基に秘匿回路計算を実行する。
【００１９】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂにおいて、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成するための処理手順について説明する。
【００２０】
最初に、Ｅｌ Ｇａｍａｌ暗号の構成例について説明しておく。
【００２１】
Ｅｌ Ｇａｍａｌ暗号の場合、ｇを素数位数ｑの乗法群Ｇの生成元とし、ｇ，ｑ，Ｇを公開情報としたとき、先ず、鍵ペア（ｘ，ｙ＝ｇx）を生成する。ここで、ｘは０以上ｑ未満の整数からなる秘密鍵であり、ｙは公開鍵である。ここでは、暗号化数値二進変換装置２１Ｂが当該鍵ペアを生成し、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとする。
【００２２】
次に、Ｅ（・）をＥｌ Ｇａｍａｌ暗号の暗号化関数としたとき、Ｇの元ｚの暗号文をＥ（ｚ）＝（Ａ，Ｂ）＝（ｇr，ｚ×ｙr）とする。ここで、ｒは０以上ｑ未満の乱数である。復号に秘密鍵ｘを用いることで、復号処理の結果ｚ＝Ｂ／Ａxを得ることができる。なお、ｚを０以上ｑ未満の整数としたいときは、Ｅ（ｚ）＝（ｇr，ｙr+z）としても良い。非特許文献２に開示された方法では、この形式のＥ（ｚ）を用いている。ただし、この形式の場合、上記の復号処理の結果はｙzとなり、ｙzからｚを求める必要がある。ｚの候補数が多くなるとｙzからｚを求めることは一般に困難となるため、ｚの候補数は予め少なく設定することが望ましい。
【００２３】
本発明では、非特許文献２に開示された方法とＥ（ｚ）の形式が同様であることを前提とし、以降説明の簡略化のため、入力提供装置１０は単一とし、当該入力提供装置１０がＥ（ｚ）を生成し、暗号化数値二進変換装置２１Ａに送信するものとする。なお、ｚは０（＝ａ）以上２t−１（＝ｂ）以下の整数とする（ｔは適当な自然数）。
【００２４】
すなわち、本発明が解決しようとする課題は、ｚを二進数表記したときの下位ｊ＋１桁目をｚjと表記したとき、ｚを復元すること無く、Ｅ（ｚ）から、Ｅ（ｚt-1），・・・，Ｅ（ｚ0）を生成することである。
【００２５】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂの処理手順の概略を、図２を用いて説明する。
【００２６】
先ず、暗号化数値二進変換装置２１Ａは、ステップＡ１において、Ｅ（ｚ）を受信すると、ステップＡ２において、ある関数Ｆによって０から２t−１までの各整数ｉに対応するデータＦ（ｉ）、及び、Ｅ（Ｆ（ｚ））を生成し、ｉに対してある置換関数πを作用させることで得られる２t個のデータ（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を、Ｅ（Ｆ（ｚ））とともに暗号化数値二進変換装置２１Ｂに送信する。
【００２７】
次に、（π（ｉ）：Ｆ（ｉ））及びＥ（Ｆ（ｚ））を受信した暗号化数値二進変換装置２１Ｂは、ステップＡ３において、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）を取得し、（π（ｉ）：Ｆ（ｉ））からＦ（ｚ）と一致するＦ（ｉ）を探索し、対応するπ（ｉ）を取得し、ステップＡ４において、π（ｉ）をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成し、Ｅ（ｗj）を暗号化数値二進変換装置２１Ａに送信する。
【００２８】
最後に、Ｅ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を受信した暗号化数値二進変換装置２１Ａは、ステップＡ５において、Ｅ（ｗj）に対してπ-1を作用させ、Ｅ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。
【００２９】
上記の各処理について具体例を与える。
【００３０】
先ず、Ｆとして、例えば、０以上ｑ未満の整数ｕを用いて、Ｆ（ｉ）＝ｙ(i+1)uとする。この場合、暗号化数値二進変換装置２１Ａは、Ｅ（ｚ）から、Ｅ（Ｆ（ｚ））＝（（ｇr）u，（ｙr+z）u×ｙu）が計算可能となる。また、Ｆは、暗号化数値二進変換装置２１Ａ以外はＦ（ｉ）からｉを求めることが困難となるようにする必要がある。そして、πとして、例えば、二進数表記でｔ桁の数値ｖを用いて
【００３１】
【数１】
【００３２】
とする。ここで、
【００３３】
【数２】
【００３４】
はｉを二進数表記し、ｉとｖを各桁ごとにＸＯＲ演算した結果を並べたものとする。
【００３５】
すると、暗号化数値二進変換装置２１Ｂは、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）＝ｙ(z+1)uを得ることができ、（π（ｉ）：Ｆ（ｉ））のＦ（ｉ）の中からＦ（ｚ）と一致するものを探索し、対応する
【００３６】
【数３】
【００３７】
を得ることができる。したがって、
【００３８】
【数４】
【００３９】
となり（ｖjはｖの二進数表記の下位ｊ＋１桁目）、ｖjを所持している暗号化数値二進変換装置２１Ａは、Ｅ（ｗj）に対してπ-1を作用させた結果となる、
【００４０】
【数５】
【００４１】
（ｊ＝０，１，・・・，ｔ−１）を得ることができる。ここで、Ｅ（１−ｗj）は、Ｅ（ｗj）から生成できることが知られており、例えば、非特許文献２にも開示されていることから、ここでは生成方法は省略する。
【００４２】
以上により、暗号化数値二進変換装置２１Ａは、Ｅ（ｚj）を得ることができ、得られたＥ（ｚj）を秘匿回路計算装置３０に送信する。１以上からなる秘匿回路計算装置３０は、例えば、非特許文献２に開示された方法により秘匿回路計算を実行する。なお、非特許文献２に開示された方法によれば秘匿回路計算装置３０は２以上を必要とする。
【００４３】
以上、本実施例では、Ｆやπについて具体例を与えたが、勿論これに限るものではない。例えば、本実施例では、（π（ｉ）：Ｆ（ｉ））を（π（ｉ）：Ｈａｓｈ（Ｆ（ｉ）））とし（Ｈａｓｈ（・）は適当なハッシュ関数）、暗号化数値二進変換装置２１Ｂは、Ｆ（ｚ）をＨａｓｈ（Ｆ（ｚ））に変換してからＨａｓｈ（Ｆ（ｉ））との一致探索を行うとしても良い。また、πとしてπ（ｉ）＝ｚ＋ｖ等としても良い。この場合、Ｅ（ｗj）からＥ（ｚj）を求めるためには、非特許文献１にしたがえば、暗号化数値二進変換装置２１Ａ，２１Ｂが協力する必要がある。
【００４４】
また、本実施例では、秘密鍵ｘは暗号化数値二進変換装置２１Ｂが所持するものとしたが、非特許文献２に開示された方法のように、ｘを暗号化数値二進変換装置２１Ａ，２１Ｂが分散所持するものとしても良い。この場合、いま、暗号化数値二進変換装置２１Ａ，２１Ｂがそれぞれ分散された秘密鍵ｘA，ｘBを所持するものとすると、暗号化数値二進変換装置２１ＡはＥ（Ｆ（ｚ））に対してｘAを用いて部分的に復号したものを暗号化数値二進変換装置２１Ｂに送信し、それを受信した暗号化数値二進変換装置２１Ｂは、ｘBを用いてＥ（Ｆ（ｚ））を完全に復号することができる。
【００４５】
また、本実施例では、秘匿回路計算装置３０を２つとし、それぞれ暗号化数値二進変換装置２１Ａ，２１Ｂと同一の装置として構成しても良い。この場合、上述の秘密鍵の分散所持は、非特許文献２の秘匿回路計算で必要となるため、このようにすることが望ましい。
【００４６】
更に、本実施例では、暗号化数値二進変換システム２０を２つの暗号化数値二進変換装置２１Ａ，２１Ｂで構成したが、１つの暗号化数値二進変換装置で構成しても良い。
【実施例２】
【００４７】
本実施例の暗号化数値二進変換システム２０は、実施例１と比べて、構成自体は同様であるが、暗号化数値二進変換装置２１Ａ，２１Ｂにおいて、Ｅ（ｚj）が正しくｚの二進数表記における桁ごとの暗号文となっているかどうか検証を行う点が異なる。
【００４８】
なお、ここでは、実施例１の処理手順に基づき、
【００４９】
【数６】
【００５０】
とし（ｕ，ｕ′は適当な乱数）、入力提供装置１０の処理は同様とし、秘匿回路計算装置３０は非特許文献２に開示された方法により秘匿回路計算を実行するものとする。
【００５１】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂの処理手順を、図３を用いて説明する。
説明する。
【００５２】
先ず、暗号化数値二進変換装置２１Ａは、ステップＢ１において、Ｅ（ｚ）を受信すると、ステップＢ２において、０から２t−１までの各整数ｉに対応するデータＦ（ｉ）＝ｙiu+u′、及びＥ（Ｆ（ｚ））を生成し、２t個のデータ
【００５３】
【数７】
【００５４】
（ｉ＝０，１，・・・，２t−１）を、Ｅ（Ｆ（ｚ））とともに暗号化数値二進変換装置Ｂに送信する。
【００５５】
次に、
【００５６】
【数８】
【００５７】
及びＥ（Ｆ（ｚ））を受信した暗号化数値二進変換装置２１Ｂは、ステップＢ３において、Ｅ（Ｆ（ｚ））を復号してＦ（ｚ）を取得し、
【００５８】
【数９】
【００５９】
からＦ（ｚ）と一致するＦ（ｉ）を探索し、対応する
【００６０】
【数１０】
【００６１】
を取得し、ステップＢ４において、
【００６２】
【数１１】
【００６３】
をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成する。また、ステップＢ４においては、更に、暗号化数値二進変換装置２１Ｂは、Ｅ（ｗj）の復号結果ｗjが０または１のどちらかであることを示すためにゼロ知識証明による証明情報を生成し、Ｅ（ｗj）及び当該証明情報を暗号化数値二進変換装置２１Ａに送信する。
【００６４】
次に、Ｅ（ｗj）（ｊ＝０，１，・・・，ｔ−１）及び当該証明情報を受信した暗号化数値二進変換装置２１Ａは、ステップＢ５において、当該証明情報を検証し、正しいと判断した場合は、Ｅ（ｗj）からＥ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。一方、当該証明情報が不正と判断した場合は、暗号化数値二進変換装置２１Ａは、以降の処理を行わない等、例外的措置をとる。なお、暗号化数値二進変換装置２１Ａは、Ｅ（ｚj）を正しく生成したとは限らないため、Ｅ（ｚj）をＥ（ｚ′j）と表記する。
【００６５】
最後に、暗号化数値二進変換装置２１Ａ，２１Ｂは、ステップＢ６において、Ｅ（ｚ′j）から
【００６６】
【数１２】
【００６７】
を計算し、
【００６８】
【数１３】
【００６９】
の復号結果とＥ（ｚ）の復号結果とが等しいかどうか、それぞれの暗号文を復号すること無く検証する。等しければＥ（ｚ′j）は正しく生成されていることになる。
【００７０】
当該検証方法として、例えば、暗号化数値二進変換装置２１Ａは、１以上ｑ未満の乱数ａを生成し、
【００７１】
【数１４】
【００７２】
から
【００７３】
【数１５】
【００７４】
を計算し、同様に暗号化数値二進変換装置２１Ｂは、１以上ｑ未満の乱数ｂを生成し、
【００７５】
【数１６】
【００７６】
から
【００７７】
【数１７】
【００７８】
を計算する。
【００７９】
次に、暗号化数値二進変換装置２１Ａ，２１Ｂは、
【００８０】
【数１８】
【００８１】
から
【００８２】
【数１９】
【００８３】
を計算し、
【００８４】
【数２０】
【００８５】
を復号し、復号結果が０であれば
【００８６】
【数２１】
【００８７】
の復号結果とＥ（ｚ）の復号結果が等しいと判断する。その理由は、ｚと
【００８８】
【数２２】
【００８９】
が等しければ、
【００９０】
【数２３】
【００９１】
の復号結果はａ，ｂにかかわらず０となり、異なれば当該復号結果が０になることは、ａ，ｂが乱数であることからその確率が低くなるためである。なお、例えば、
【００９２】
【数２４】
【００９３】
から
【００９４】
【数２５】
【００９５】
を計算することはＥ（・）の準同型性により可能であることが非特許文献２等で開示されている。具体的には、Ｅ（ｚ）＝（Ａ，Ｂ），Ｅ（ｚ′）＝（Ａ′，Ｂ′）としたとき、（ＡＡ′，ＢＢ′）＝Ｅ（ｚ＋ｚ′）となり、また、整数ｃに対して（Ａc，Ｂc）＝Ｅ（ｃｚ）となることが知られているため、このような処理を実行すれば良い。
【実施例３】
【００９６】
図４に示すように、本実施例の暗号化数値二進変換システム２０は、実施例１，２と比べて、３つの暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃを有する点が異なる。
【００９７】
なお、図３では、暗号化数値二進変換装置の数を３と固定しているが、本実施例は、４つ以上であっても同様の処理が可能である。
【００９８】
ここでは、入力提供装置１０の処理は実施例１と同様とし、秘匿回路計算装置３０は非特許文献２に開示された方法により秘匿回路計算を実行するものとする。
【００９９】
以下、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃの処理手順の概略を、図５を用いて説明する。
【０１００】
ここでは、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、秘密鍵ｘを分散所持し、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃの全装置が処理した場合に限り、Ｅ（・）によって暗号化された暗号文を復号できるものとし、また、０から２t−１までの各整数ｉの暗号文Ｅ（ｉ）を生成する。
【０１０１】
先ず、暗号化数値二進変換装置２１Ａは、ステップＣ１において、Ｅ（ｚ）を受信する。
【０１０２】
すると、暗号化数値二進変換装置２１Ａは、ステップＣ２において、ある関数ＦAによってＥ（ｉ）を変換したＦA（Ｅ（ｉ））を生成し、ｉにある置換関数πAを作用させることで得られる２t個のデータ（πA（ｉ）：ＦA（Ｅ（ｉ）））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ｂに送信する。
【０１０３】
次に、（πA（ｉ）：ＦA（Ｅ（ｉ）））（ｉ＝０，１，・・・，２t−１）を受信した暗号化数値二進変換装置２１Ｂは、ある関数ＦBによってＦA（Ｅ（ｉ））を変換したＦB（ＦA（Ｅ（ｉ）））を生成し、πA（ｉ）にある置換関数πBを作用させることで得られる２t個のデータ（πB（πA（ｉ））：ＦB（ＦA（Ｅ（ｉ））））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ｃに送信する。
【０１０４】
次に、（πB（πA（ｉ））：ＦB（ＦA（Ｅ（ｉ））））（ｉ＝０，１，・・・，２t−１）を受信した暗号化数値二進変換装置２１Ｃは、ある関数ＦCによってＦB（ＦA（Ｅ（ｉ）））を変換したＦC（ＦB（ＦA（Ｅ（ｉ））））を生成し、πB（πA（ｉ））にある置換関数πCを作用させることで得られる２t個のデータ（πC（πB（πA（ｉ）））：ＦC（ＦB（ＦA（Ｅ（ｉ）））））（ｉ＝０，１，・・・，２t−１）を暗号化数値二進変換装置２１Ａ，２１Ｂに送信する。
【０１０５】
次に、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、ステップＣ３において、当該ＦC（ＦB（ＦA（Ｅ（ｉ））））に対応するｉとＥ（ｚ）に対応するｚとの一致探索を行い、対応するπC（πB（πA（ｉ）））を得る。そして、暗号化数値二進変換装置２１Ａ，２１Ｂ，２１Ｃは、ステップＣ４において、πC（πB（πA（ｉ）））をｔ桁の二進数表記としたときの下位ｊ＋１桁目をｗjと表記したとき、ｊ＝０，１，・・・，ｔ−１についてＥ（ｗj）を生成する。
【０１０６】
最後に、ステップＣ５において、Ｅ（ｗj）に対して暗号化数値二進変換装置２１Ｃ，２１Ｂ，２１Ａの順に、それぞれが
【０１０７】
【数２６】
【０１０８】
を作用させ、Ｅ（ｚj）（ｊ＝０，１，・・・，ｔ−１）を得る。
【０１０９】
上記の各処理について具体例を与える。
【０１１０】
先ず、ＦA，ＦB，ＦCとして、例えば、非特許文献２に開示されたような再暗号化手法がある。すなわち、ある数値ｚの暗号文Ｅ（ｚ）＝（ｇr，ｙr+z）に対し、０以上ｑ未満の乱数ｓを用いて、（ｇr+s，ｙr+s+z）＝（ｇrｇs，ｙr+zｙs）を計算し、これをＥ（ｚ）に置き換える。数値ｚを変えること無く暗号文が変化するため、置換関数を作用させることで（ｇr，ｙr+z）と（ｇr+s，ｙr+s+z）との対応関係を秘匿することが可能となる。ＦC（ＦB（ＦA（Ｅ（ｉ））））に対応するｉと、Ｅ（ｚ）に対応するｚとの一致探索は、ＦA，ＦB，ＦCを上述の再暗号化手法とすることで、Ｅ（πC（πB（πA（ｉ））））とＥ（ｚ）の復号結果との一致探索となるため、実施例２で示したような方法を用いれば良い。なお、πA，πB，πCや
【０１１１】
【数２７】
【０１１２】
の作用は実施例１と同様で良く、その説明は省略する。
【０１１３】
以上により、暗号化数値二進変換システム２０を３つ以上の暗号化数値二進変換装置で構成した場合でも、Ｅｌ Ｇａｍａｌ暗号で暗号化された数値に対して、当該数値を明かすこと無く、当該数値を二進数表記の桁ごとに暗号化した暗号文を生成することが可能となる。
【０１１４】
以上、本発明を実施例を参照して説明したが、本発明は上記実施例に限定されものではない。本発明の構成や詳細には、本発明の範囲内で当業者が理解し得る様々な変更をすることができる。
【０１１５】
例えば、実施例３に、実施例２で示されたＥ（ｚj）の検証方法を適用しても良い。
【０１１６】
また、実施例１，２，３では、暗号化数値二進変換システム２０を複数の暗号化数値二進変換装置で構成したが、１つの暗号化数値二進変換装置で構成しても良い。更に、この場合、その暗号化数値二進変換装置にて行われる暗号化数値二進変換方法を、コンピュータに実行させるためのプログラムに適用しても良い。また、そのプログラムを記憶媒体に格納することも可能であり、ネットワークを介して外部に提供することも可能である。
【符号の説明】
【０１１７】
１０ 入力提供装置
２０ 暗号化数値二進変換システム
２１Ａ，２１Ｂ，２１Ｃ 暗号化数値二進変換装置
３０ 秘匿回路計算装置
【特許請求の範囲】
【請求項１】
１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成し、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求め、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める、暗号化数値二進変換システム。
【請求項２】
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成し、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求め、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求める、暗号化数値二進変換システム。
【請求項３】
Ｅ（ｗj）の復号結果ｗjについてのゼロ知識証明による証明情報を生成し、
証明情報が正しい場合にＥ（ｚj）を求め、更に、Ｅ（ｚj）から
【数１】
を計算し復号した復号結果とＥ（ｚ）の復号結果とが等しいかどうかを検証する、請求項１または２に記載の暗号化数値二進変換システム。
【請求項４】
１または２個の暗号化数値二進変換手段を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換方法であって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成する第１ステップと、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求める第２ステップと、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める第３ステップと、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める第４ステップと、を有する暗号化数値二進変換方法。
【請求項５】
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換手段を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換方法であって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成する第１ステップと、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求める第２ステップと、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める第３ステップと、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求める第４ステップと、を有する暗号化数値二進変換方法。
【請求項６】
前記第３ステップでは、更に、Ｅ（ｗj）の復号結果ｗjについてのゼロ知識証明による証明情報を生成し、
前記第４ステップでは、証明情報が正しい場合にＥ（ｚj）を求め、
更に、Ｅ（ｚj）から
【数２】
を計算し復号した復号結果とＥ（ｚ）の復号結果とが等しいかどうかを検証する第５ステップを有する、請求項４または５に記載の暗号化数値二進変換方法。
【請求項７】
請求項４から６のいずれか１項に記載の暗号化数値二進変換方法をコンピュータに実行させるための暗号化数値二進変換プログラム。
【請求項１】
１または２個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成し、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求め、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める、暗号化数値二進変換システム。
【請求項２】
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換装置を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換システムであって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成し、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求め、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求め、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求める、暗号化数値二進変換システム。
【請求項３】
Ｅ（ｗj）の復号結果ｗjについてのゼロ知識証明による証明情報を生成し、
証明情報が正しい場合にＥ（ｚj）を求め、更に、Ｅ（ｚj）から
【数１】
を計算し復号した復号結果とＥ（ｚ）の復号結果とが等しいかどうかを検証する、請求項１または２に記載の暗号化数値二進変換システム。
【請求項４】
１または２個の暗号化数値二進変換手段を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換方法であって、
関数Ｆ及び置換関数πを用いて、（π（ｉ）：Ｆ（ｉ））（ｉ＝０，１，・・・，２t−１）を生成する第１ステップと、
Ｆ（ｚ）とＦ（ｉ）との対応関係を基にπ（ｉ）を求める第２ステップと、
π（ｉ）をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める第３ステップと、
Ｅ（ｗj）に対してπ-1を作用させてＥ（ｚj）を求める第４ステップと、を有する暗号化数値二進変換方法。
【請求項５】
Ｎ（Ｎは３以上の整数）個の暗号化数値二進変換手段を用いて、Ｅｌ Ｇａｍａｌ暗号の暗号化関数をＥ（・）とし、ａ≦ｚ≦ｂとなる整数ｚの暗号文をＥ（ｚ）としたとき、Ｅ（ｚ）を入力として、ｚをｔ桁の二進数表記とした桁ごとの暗号文を求める暗号化数値二進変換方法であって、
関数Ｆn及び置換関数πn（ｎ＝１，・・・，Ｎ）を用いて、（πN（πN-1（・・・（π1（ｉ））））：ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ））））））（ｉ＝０，１，・・・，２t−１）を生成する第１ステップと、
ＦN（ＦN-1（・・・（Ｆ1（Ｅ（ｉ）））））に対応するｉとＥ（ｚ）に対応するｚとの対応関係を基にπN（πN-1（・・・（π1（ｉ））））を求める第２ステップと、
πN（πN-1（・・・（π1（ｉ））））をｔ桁の二進数表記とした桁ごとに暗号化してＥ（ｗj）（ｊ＝０，１，・・・，ｔ−１）を求める第３ステップと、
Ｅ（ｗj）に対してπn-1を作用させてＥ（ｚj）を求める第４ステップと、を有する暗号化数値二進変換方法。
【請求項６】
前記第３ステップでは、更に、Ｅ（ｗj）の復号結果ｗjについてのゼロ知識証明による証明情報を生成し、
前記第４ステップでは、証明情報が正しい場合にＥ（ｚj）を求め、
更に、Ｅ（ｚj）から
【数２】
を計算し復号した復号結果とＥ（ｚ）の復号結果とが等しいかどうかを検証する第５ステップを有する、請求項４または５に記載の暗号化数値二進変換方法。
【請求項７】
請求項４から６のいずれか１項に記載の暗号化数値二進変換方法をコンピュータに実行させるための暗号化数値二進変換プログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２０１０−１６４８９７（Ｐ２０１０−１６４８９７Ａ）
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願番号】特願２００９−８９６８（Ｐ２００９−８９６８）
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２２年７月２９日（２０１０．７．２９）
【国際特許分類】
【出願日】平成２１年１月１９日（２００９．１．１９）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]