(57)【特許請求の範囲】
【請求項１】
暗号処理装置と暗号演算装置と分析装置とを備えるシステムであって、
前記暗号処理装置は、
第１のベクトルを記憶する記憶部と、
前記第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する生成部と、
前記第１の暗号化多項式を表す暗号情報を前記暗号演算装置へ送信する送信部とを含み、
前記暗号演算装置は、前記第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成し、前記第３の暗号化多項式を表す暗号情報を前記分析装置へ送信し、
前記分析装置は、前記第３の暗号化多項式を復号して第３の多項式を生成し、前記第３の多項式の所定部分の変数に２を代入することで、前記第１のベクトルと前記第２のベクトルとの演算結果を求めることを特徴とするシステム。
【請求項２】
前記生成部は、前記第１のベクトルの要素を複数のビットを含むビット列に変換し、２つの要素に対応する２つのビット列の間に、複数の０を表すビット値を含むビット列を挿入することで、前記第１のバイナリベクトルを生成することを特徴とする請求項１記載のシステム。
【請求項３】
前記複数の０を表すビット値を含む前記ビット列のビット数は、前記複数のビットを含む前記ビット列のビット数ｄと等しく、前記第３の多項式の前記所定部分は、前記第３の多項式に含まれる２（ｄ−１）次以下の次数の項に対応し、前記演算結果は、前記第１のベクトルと前記第２のベクトルとの内積であることを特徴とする請求項２記載のシステム。
【請求項４】
暗号処理装置が、第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する工程と、
前記暗号処理装置が、前記第１の暗号化多項式を表す暗号情報を暗号演算装置へ送信する工程と、
前記暗号演算装置が、前記第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する工程と、
前記暗号演算装置が、前記第３の暗号化多項式を表す暗号情報を分析装置へ送信する工程と、
前記分析装置が、前記第３の暗号化多項式を復号して第３の多項式を生成する工程と、
前記分析装置が、前記第３の多項式の所定部分の変数に２を代入することで、前記第１のベクトルと前記第２のベクトルとの演算結果を求める工程と、
を備えることを特徴とする暗号処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号処理装置、暗号処理方法、及び暗号処理プログラムに関する。
【背景技術】
【０００２】
現在、個人情報及び機密情報を保護する規制が強化される一方で、それらの情報を利用したサービスの市場が拡大しつつある。このようなサービスとしては、例えば、スマートフォンから取得できる個人ユーザの位置情報等を活用したサービスが挙げられる。
【０００３】
そこで、個人情報又は機密情報を保護したままで、情報の利活用ができる秘匿化技術が注目されている。秘匿化技術の中には、データ種別又はサービス要件に応じて暗号技術又は統計技術を用いる方法がある。
【０００４】
暗号技術を用いた秘匿化技術として、準同型暗号技術が知られている。準同型暗号技術は、暗号化と復号とで一対の異なる鍵を用いる公開鍵暗号方式の１つであり、暗号化したままでデータ操作が可能となる機能を有する。例えば、加算及び乗算に関する準同型暗号の暗号化関数Ｅは、平文ｍ１及び平文ｍ２に対して、次式のような性質を持つ。
Ｅ（ｍ１）＋Ｅ（ｍ２）＝Ｅ（ｍ１＋ｍ２）      （１）
Ｅ（ｍ１）＊Ｅ（ｍ２）＝Ｅ（ｍ１＊ｍ２）      （２）
【０００５】
式（１）は、加算に対して準同型であることを表し、式（２）は、乗算に対して準同型であることを表す。このように、準同型暗号技術によれば、２つ以上の暗号文を対象に加算、乗算等に対応する操作を行うことで、暗号文を復号することなく、元の平文同士に対して加算、乗算等を行った演算結果の暗号文を得ることができる。
【０００６】
このような準同型暗号の性質は、電子投票、電子現金等の分野、及び近年ではクラウド・コンピューティングの分野において利用されることが期待されている。加算又は乗算に関する準同型暗号としては、乗算のみ可能なRivest Shamir Adleman（ＲＳＡ）暗号、加算のみ可能なAdditive ElGamal暗号等が知られている。
【０００７】
また、２００９年には、式（１）及び式（２）を満たす、加算と乗算の両方が可能な準同型暗号が提案されている（例えば、非特許文献１を参照）。非特許文献１では、準同型暗号の理論的な実現方法のみしか示されておらず、実用的な構成法は明らかにされていない。しかし、近年では、加算と乗算の両方が可能な準同型暗号の実用的な構成法も提案されている（例えば、非特許文献２を参照）。
【０００８】
準同型暗号を利用した秘匿距離計算において、暗号ベクトルデータのサイズと秘匿距離計算の時間の両方を削減する暗号処理装置も知られている（例えば、特許文献１を参照）。この暗号処理装置は、第１のベクトルから第１の変換多項式を用いて第１の多項式を得るとともに、第２のベクトルから第２の変換多項式を用いて第２の多項式を得る。次に、暗号処理装置は、第１のベクトルの秘匿距離に関する第１の重みと、第２のベクトルの秘匿距離に関する第２の重みとを得る。
【０００９】
次に、暗号処理装置は、第１の多項式、第２の多項式、第１の重み、及び第２の重みのそれぞれを準同型暗号方式を用いて暗号化し、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、及び第２の暗号化重みを得る。そして、暗号処理装置は、第１の暗号化多項式、第２の暗号化多項式、第１の暗号化重み、及び第２の暗号化重みから、第１のベクトルと第２のベクトルの秘匿距離の暗号化に対応する暗号化秘匿距離を得る。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】特開２０１４−１２６８６５号公報
【非特許文献】
【００１１】
【非特許文献１】C. Gentry, “Fully Homomorphic Encryption Using Ideal Lattices”, STOC 2009, pp. 169-178, 2009.
【非特許文献２】K. Lauter, M. Naehrig, V. Vaikuntanathan, “Can Homomorphic Encryption be Practical?”, In ACM workshop on Cloud Computing Security Workshop-CCSW 2011, ACM, pp. 113-124, 2011.
【発明の概要】
【発明が解決しようとする課題】
【００１２】
特許文献１の暗号処理装置を適用することで、２つのベクトルの各要素を暗号化して乗算する方法よりも効率的に、２つのベクトルの間の内積又は距離を計算することができる。しかしながら、２つのベクトルの各要素の値が大きくなると、準同型暗号により生成される暗号化多項式のサイズも大きくなるため、準同型暗号の処理性能が低下すると考えられる。
【００１３】
なお、かかる問題は、２つのベクトルの間の内積又は距離を求める場合に限らず、２つのベクトルの他の演算結果を求める場合においても生ずるものである。
【００１４】
１つの側面において、本発明は、暗号化多項式を用いた暗号演算によって２つのベクトルの演算結果を効率よく求めることを目的とする。
【課題を解決するための手段】
【００１５】
１つの案では、暗号処理装置は、記憶部、生成部、及び送信部を含む。
記憶部は、第１のベクトルを記憶する。生成部は、第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する。送信部は、第１の暗号化多項式を表す暗号情報を暗号演算装置へ送信する。
【００１６】
暗号演算装置は、第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する。第３の暗号化多項式を復号して得られる第３の多項式の所定部分の変数に２を代入することで、第１のベクトルと第２のベクトルとの演算結果が得られる。
【発明の効果】
【００１７】
実施形態によれば、暗号化多項式を用いた暗号演算によって２つのベクトルの演算結果を効率よく求めることができる。
【図面の簡単な説明】
【００１８】
【図１】暗号処理装置の機能的構成図である。
【図２】暗号処理のフローチャートである。
【図３】統計システムの構成図である。
【図４】暗号処理の具体例を示すフローチャートである。
【図５】情報処理装置の構成図である。
【発明を実施するための形態】
【００１９】
以下、図面を参照しながら、実施形態を詳細に説明する。
非特許文献２の３．２節には、準同型暗号の実用的な構成法について記載されている。この構成法では、まず、暗号鍵生成において、主に３つの鍵生成パラメータ（ｎ，ｑ，ｔ）が用いられる。ｎは２冪の整数であり、格子次元と呼ばれる。ｑは素数であり、ｔは素数ｑよりも小さい整数である。
【００２０】
暗号鍵生成の手順として、まず、秘密鍵として各係数が非常に小さいｎ−１次多項式ｓｋがランダムに生成される。各係数の大きさは、あるパラメータσにより制限される。次に、各係数がｑより小さいｎ−１次多項式ａ１と、各係数が非常に小さいｎ−１次多項式ｅとがランダムに生成される。そして、次式の多項式ａ０が計算され、多項式の組（ａ０，ａ１）が公開鍵ｐｋとして定義される。
【００２１】
ａ０＝−（ａ１＊ｓｋ＋ｔ＊ｅ）      （１１）
【００２２】
ただし、多項式ａ０の計算では、ｎ次以上の多項式に対してｘn＝−１，ｘn+1＝−ｘ，．．．を適用することで、絶えずｎ次より小さい次数の多項式が計算される。さらに、多項式に含まれる各項の係数としては、その係数を素数ｑで除算したときの剰余が用いられる。このような多項式演算を行う空間は、学術的にはＲq：＝Ｆq［ｘ］／（ｘn＋１）と表されることが多い。
【００２３】
次に、各係数がｔより小さいｎ−１次多項式で表される平文データｍと公開鍵ｐｋとに対して、各係数が非常に小さい３つのｎ−１次多項式ｕ、ｆ、及びｇがランダムに生成され、平文データｍの暗号データＥｎｃ（ｍ，ｐｋ）が次式により定義される。
【００２４】
Ｅｎｃ（ｍ，ｐｋ）＝（ｃ０，ｃ１）      （１２）
ｃ０＝ａ０＊ｕ＋ｔ＊ｇ＋ｍ              （１３）
ｃ１＝ａ１＊ｕ＋ｔ＊ｆ                  （１４）
【００２５】
多項式ｃ０及び多項式ｃ１の計算においても、空間Ｒq上の多項式演算が用いられる。このとき、暗号データＥｎｃ（ｍ１，ｐｋ）＝（ｃ０，ｃ１）と暗号データＥｎｃ（ｍ２，ｐｋ）＝（ｄ０，ｄ１）とに対する暗号加算は、次式により計算される。
【００２６】
Ｅｎｃ（ｍ１，ｐｋ）＋Ｅｎｃ（ｍ２，ｐｋ）
＝（ｃ０＋ｄ０，ｃ１＋ｄ１）                    （１５）
【００２７】
また、暗号データＥｎｃ（ｍ１，ｐｋ）と暗号データＥｎｃ（ｍ２，ｐｋ）とに対する暗号乗算は、次式により計算される。
【００２８】
Ｅｎｃ（ｍ１，ｐｋ）＊Ｅｎｃ（ｍ２，ｐｋ）
＝（ｃ０＊ｄ０，ｃ０＊ｄ１＋ｃ１＊ｄ０，ｃ１＊ｄ１）      （１６）
【００２９】
式（１６）の暗号乗算を行うと、暗号データが２次元ベクトルから３次元ベクトルに変化する。暗号乗算を複数回繰り返すと、乗算結果の暗号データの要素はさらに増加する。
【００３０】
次に、復号処理について説明する。複数回の暗号乗算等の操作により要素が増加した暗号データｃ＝（ｃ０，ｃ１，ｃ２，．．．）に対して、秘密鍵ｓｋを用いて次式の復号結果Ｄｅｃ（ｃ，ｓｋ）を計算することで、暗号データｃが復号される。
【００３１】
Ｄｅｃ（ｃ，ｓｋ）
＝［ｃ０＋ｃ１＊ｓｋ＋ｃ２＊ｓｋ2＋・・・］q  ｍｏｄ  ｔ      （１７）
【００３２】
式（１７）において、［ｆ（ｘ）］q  ｍｏｄ  ｔは、多項式ｆ（ｘ）の各係数ｚiを［ｚi］ｑ  ｍｏｄ  ｔに置き換えた多項式を表す。整数ｚに対する［ｚ］qの値は、ｚをｑで除算したときの剰余ｗを用いて、次式により定義される。
【００３３】
［ｚ］q＝ｗ      （ｗ＜ｑ／２の場合）      （１８）
［ｚ］q＝ｗ−ｑ  （ｗ≧ｑ／２の場合）      （１９）
【００３４】
したがって、［ｚ］qの値域は［−ｑ／２，ｑ／２）となる。また、ａ  ｍｏｄ  ｔは、整数ａをｔで除算したときの剰余を表す。
【００３５】
例えば、（ｎ，ｑ，ｔ）＝（４，１０３３，２０）の場合、秘密鍵ｓｋ、公開鍵ｐｋ、及び暗号データＥｎｃ（ｍ，ｐｋ）の簡単な例として、以下のような多項式が挙げられる。
【００３６】
ｓｋ＝Ｍｏｄ（Ｍｏｄ（４，１０３３）＊ｘ3＋Ｍｏｄ（４，１０３３）＊ｘ2
＋Ｍｏｄ（１，１０３３）＊ｘ，ｘ4＋１）                      （２０）
ｐｋ＝（ａ０，ａ１）                      （２１）
ａ０＝Ｍｏｄ（Ｍｏｄ（８８５，１０３３）＊ｘ3
＋Ｍｏｄ（５１９，１０３３）＊ｘ2＋Ｍｏｄ（６２１，１０３３）＊ｘ
＋Ｍｏｄ（３２７，１０３３），ｘ4＋１）                      （２２）
ａ１＝Ｍｏｄ（Ｍｏｄ（６６１，１０３３）＊ｘ3
＋Ｍｏｄ（６２５，１０３３）＊ｘ2＋Ｍｏｄ（８６１，１０３３）＊ｘ
＋Ｍｏｄ（３１１，１０３３），ｘ4＋１）                      （２３）
Ｅｎｃ（ｍ，ｐｋ）＝（ｃ０，ｃ１）                      （２４）
ｍ＝３＋２ｘ＋２ｘ2＋２ｘ3                      （２５）
ｃ０＝Ｍｏｄ（Ｍｏｄ（８２２，１０３３）＊ｘ3
＋Ｍｏｄ（１０１６，１０３３）＊ｘ2＋Ｍｏｄ（２９２，１０３３）＊ｘ
＋Ｍｏｄ（２４３，１０３３），ｘ4＋１）                      （２６）
ｃ１＝Ｍｏｄ（Ｍｏｄ（８４０，１０３３）＊ｘ3
＋Ｍｏｄ（２７５，１０３３）＊ｘ2＋Ｍｏｄ（６２８，１０３３）＊ｘ
＋Ｍｏｄ（９１１，１０３３），ｘ4＋１）                      （２７）
【００３７】
式（２０）〜式（２７）において、Ｍｏｄ（ａ，ｑ）は、整数ａを素数ｑで除算したときの剰余を表し、Ｍｏｄ（ｆ（ｘ），ｘ4＋１）は、多項式ｆ（ｘ）を多項式ｘ4＋１で除算したときの剰余（多項式）を表す。例えば、ｆ（ｘ）＝ｘ4に対するＭｏｄ（ｆ（ｘ），ｘ4＋１）は、ｆ（ｘ）＝−１に対するＭｏｄ（ｆ（ｘ），ｘ4＋１）と等しく、ｆ（ｘ）＝ｘ5に対するＭｏｄ（ｆ（ｘ），ｘ4＋１）は、ｆ（ｘ）＝−ｘに対するＭｏｄ（ｆ（ｘ），ｘ4＋１）と等しい。
【００３８】
ｎ−１次以下の２つの多項式ｆ（ｘ）及びｇ（ｘ）に対する２つの暗号データＥｎｃ（ｆ（ｘ），ｐｋ）及びＥｎｃ（ｇ（ｘ），ｐｋ）は、加算及び乗算に関して、次式のような性質を持つ。
【００３９】
Ｅｎｃ（ｆ（ｘ），ｐｋ）＋Ｅｎｃ（ｇ（ｘ），ｐｋ）
＝Ｅｎｃ（ｆ（ｘ）＋ｇ（ｘ），ｐｋ）                    （３１）
Ｅｎｃ（ｆ（ｘ），ｐｋ）＊Ｅｎｃ（ｇ（ｘ），ｐｋ）
＝Ｅｎｃ（ｆ（ｘ）＊ｇ（ｘ），ｐｋ）                    （３２）
【００４０】
さらに、特許文献１の暗号処理装置によれば、ベクトルデータを多項式変換により１つの多項式で表現し、その多項式を準同型暗号により暗号化することで、処理時間や暗号データのサイズが大幅に改善される。
【００４１】
この暗号処理装置では、例えば、次のような２つのｎ次元ベクトルが入力データとして用いられる。
【００４２】
Ａ＝（ａ0，ａ2，．．．，ａn-1）      （４１）
Ｂ＝（ｂ0，ｂ2，．．．，ｂn-1）      （４２）
【００４３】
２つのベクトルを暗号化したままで２つのベクトルの間の内積又は距離を高速に計算するために、例えば、次のような昇順変換と降順変換の２種類の多項式変換が用いられる。
【００４４】
［昇順変換］
【数１】
0006413743.tif 000002
【００４５】
［降順変換］
【数２】
0006413743.tif 000003
【００４６】
多項式ｐｍ１（Ａ）及び多項式ｐｍ２（Ｂ）は、変数ｘの多項式である。多項式ｐｍ１（Ａ）及び多項式ｐｍ２（Ｂ）を準同型暗号により暗号化すると、暗号化多項式Ｅ（ｐｍ１（Ａ））及び暗号化多項式Ｅ（ｐｍ２（Ｂ））が生成される。
【００４７】
Ｅ（ｐｍ１（Ａ））＝Ｅｎｃ（ｐｍ１（Ａ），ｐｋ）      （４５）
Ｅ（ｐｍ２（Ｂ））＝Ｅｎｃ（ｐｍ２（Ｂ），ｐｋ）      （４６）
【００４８】
暗号化多項式Ｅ（ｐｍ１（Ａ））及び暗号化多項式Ｅ（ｐｍ２（Ｂ））を乗算すると、暗号化したままで乗算ｐｍ１（Ａ）＊ｐｍ２（Ｂ）が行われる。そして、乗算結果Ｅ（ｐｍ１（Ａ））＊Ｅ（ｐｍ２（Ｂ））を復号すると、復号結果の多項式に含まれる定数項は、次式のような値になる。
【００４９】
【数３】
0006413743.tif 000004
【００５０】
式（４７）は、ベクトルＡとベクトルＢの内積を表している。この方法によれば、ベクトルＡとベクトルＢの各要素を暗号化して乗算する方法よりも効率的に、内積を計算することができる。ベクトルＡとベクトルＢの内積はこれらのベクトルの間の相関を表すため、内積計算を統計システムに対して適用することが可能である。
【００５１】
例えば、２つのクライアント端末がそれぞれデータＤＡ及びデータＤＢを保持しており、お互いのデータを公開することなくデータＤＡとデータＤＢとの間の相関を求めたい場合がある。
【００５２】
この場合、まず、２つのクライアント端末が、それぞれ、データＤＡ及びデータＤＢをベクトルＡ及びベクトルＢに変換して、暗号化多項式Ｅ（ｐｍ１（Ａ））及び暗号化多項式Ｅ（ｐｍ２（Ｂ））を生成し、クラウド内の暗号演算サーバへ送信する。次に、暗号演算サーバが、暗号化多項式Ｅ（ｐｍ１（Ａ））及び暗号化多項式Ｅ（ｐｍ２（Ｂ））を乗算して暗号乗算結果を生成し、第３者機関の分析サーバへ送信する。そして、分析サーバが、秘密鍵で暗号乗算結果を復号して、復号結果の多項式からベクトルＡとベクトルＢの内積を求め、その内積に基づいて、データＤＡとデータＤＢとの間の相関分析を行う。
【００５３】
しかしながら、ベクトルＡの各要素ａiとベクトルＢの各要素ｂiの値が大きくなると、式（４７）の内積も巨大な値になると考えられる。例えば、ａi及びｂiが１６ビットの値である場合、内積はｎ個の３２ビットの値の和という巨大な値になる。内積が巨大な値になる場合、内積が準同型暗号の鍵生成パラメータｔよりも小さくなるように、ｔも巨大な値に設定され、式（１３）及び式（１４）の暗号化多項式のサイズが大きくなるため、準同型暗号の処理性能が低下する。
【００５４】
図１は、実施形態の暗号処理装置の機能的構成例を示している。図１の暗号処理装置１０１は、記憶部１１１、生成部１１２、及び送信部１１３を含む。
【００５５】
記憶部１１１は、第１のベクトルを記憶する。生成部１１２は、第１のベクトルを用いて第１の暗号化多項式を生成し、送信部１１３は、第１の暗号化多項式を表す暗号情報を暗号演算装置へ送信する。
【００５６】
図２は、図１の暗号処理装置１０１が行う暗号処理の例を示すフローチャートである。まず、生成部１１２は、第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する（ステップ２０１）。そして、送信部１１３は、第１の暗号化多項式を表す暗号情報を暗号演算装置へ送信する（ステップ２０２）。
【００５７】
暗号演算装置は、第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する。第３の暗号化多項式を復号して得られる第３の多項式の所定部分の変数に２を代入することで、第１のベクトルと第２のベクトルとの演算結果が得られる。
【００５８】
このような暗号処理装置１０１によれば、暗号化多項式を用いた暗号演算によって２つのベクトルの演算結果を効率よく求めることができる。
【００５９】
図３は、図１の暗号処理装置１０１を適用した統計システムの構成例を示している。図３の統計システムは、端末装置３０１、端末装置３０２、暗号演算装置３０３、及び分析装置３０４を含む。暗号演算装置３０３と、端末装置３０１、端末装置３０２、及び分析装置３０４とは、通信ネットワークにより接続されており、暗号演算装置３０３は、クラウド上に設けられる。端末装置３０１及び端末装置３０２の各々は、図１の暗号処理装置１０１に対応する。
【００６０】
この例では、相関分析を行う分析者の分析装置３０４が、準同型暗号の公開鍵と秘密鍵とを生成し、公開鍵の情報のみを公開する。これにより、端末装置３０１、端末装置３０２、及び暗号演算装置３０３は、公開鍵を知ることが可能になる。そこで、端末装置３０１及び端末装置３０２は、保持しているベクトルの情報を公開鍵により暗号化し、暗号情報のみを暗号演算装置３０３へ送信する。
【００６１】
暗号演算装置３０３は、端末装置３０１及び端末装置３０２から受信した暗号情報を用いて暗号演算を行い、暗号演算結果のみを分析装置３０４へ送信する。通信ネットワーク上の情報はすべて暗号化されているため、ベクトルの情報が暗号演算装置３０３に漏洩することはない。
【００６２】
端末装置３０１は、記憶部３１１、生成部３１２、及び送信部３１３を含む。記憶部３１１は、データＤＡを表すベクトルＶＡを記憶する。生成部３１２は、ベクトルＶＡをバイナリベクトルＵＡに変換し、バイナリベクトルＵＡと公開鍵とを用いて暗号化多項式Ｅ（ｐｍ１（ＵＡ））を生成する。送信部３１３は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））を表す暗号情報を暗号演算装置３０３へ送信する。
【００６３】
端末装置３０２は、記憶部３２１、生成部３２２、及び送信部３２３を含む。記憶部３２１は、データＤＢを表すベクトルＶＢを記憶する。生成部３２２は、ベクトルＶＢをバイナリベクトルＵＢに変換し、バイナリベクトルＵＢと公開鍵とを用いて暗号化多項式Ｅ（ｐｍ２（ＵＢ））を生成する。送信部３２３は、暗号化多項式Ｅ（ｐｍ２（ＵＢ））を表す暗号情報を暗号演算装置３０３へ送信する。
【００６４】
データＤＡ及びデータＤＢは、例えば、テキストデータ、画像データ、音声データ等である。テキストデータは、例えば、店舗等で顧客が購入した商品の識別情報、個数、価格等を表す購買履歴データであってもよい。画像データは、例えば、カメラにより撮影された被写体の画像であってもよい。音声データは、例えば、音声レコーダにより録音された人間、動物、又は物体の音声であってもよい。
【００６５】
端末装置３０１及び端末装置３０２は、例えば、データＤＡ及びデータＤＢから抽出した特徴情報を特徴ベクトルに変換することで、ベクトルＶＡ及びベクトルＶＢを生成することができる。また、暗号化多項式を表す暗号情報としては、例えば、暗号化多項式の各項が有する係数を用いることができる。
【００６６】
暗号演算装置３０３は、受信部３３１、生成部３３２、及び送信部３３３を含む。受信部３３１は、端末装置３０１から暗号化多項式Ｅ（ｐｍ１（ＵＡ））を表す暗号情報を受信し、端末装置３０２から暗号化多項式Ｅ（ｐｍ２（ＵＢ））を表す暗号情報を受信する。生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））と暗号化多項式Ｅ（ｐｍ２（ＵＢ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を生成する。送信部３３３は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を表す暗号情報を分析装置３０４へ送信する。
【００６７】
分析装置３０４は、受信部３４１及び分析部３４２を含む。受信部３４１は、暗号演算装置３０３から暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を表す暗号情報を受信する。分析部３４２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を秘密鍵により復号して、多項式ｐｍ１（ＵＡ）＊ｐｍ２（ＵＢ）を生成し、生成した多項式の所定部分の変数に２を代入することで、ベクトルＶＡとベクトルＶＢの内積を求める。そして、分析部３４２は、その内積に基づいて、データＤＡとデータＤＢとの間の相関分析のための統計処理を行って、処理結果を出力する。
【００６８】
次に、図３の統計システムにおける暗号処理の具体例について説明する。この暗号処理では、例えば、次のような２つのｋ次元ベクトルがベクトルＶＡ及びベクトルＶＢとして用いられる。
【００６９】
ＶＡ＝（ａ0，ａ2，．．．，ａk-1）      （５１）
ＶＢ＝（ｂ0，ｂ2，．．．，ｂk-1）      （５２）
【００７０】
端末装置３０１の生成部３１２及び端末装置３０２の生成部３２２は、ベクトルＶＡ及びベクトルＶＢの各要素を、次式のようなバイナリ変換によりバイナリ値に変換する。
【００７１】
【数４】
0006413743.tif 000005
【００７２】
ただし、ｄは２以上の整数であり、要素ａi及び要素ｂiは、２d未満の整数であると仮定する。式（５３）のａi(u) 及び式（５４）のｂi(u) は、０又は１のバイナリ値である。このバイナリ変換により、ベクトルＶＡ及びベクトルＶＢは、次式のようなｋｄ次元のバイナリベクトルに変換される。
【００７３】
ＶＡ→（ａ0(0)，ａ0(1)，．．．，ａ0(d-1)，ａ1(0)，ａ1(1)，．．．，ａ1(d-1)，．．．，
ａk-1(0)，ａk-1(1)，．．．，ａk-1(d-1)）                      （５５）
ＶＢ→（ｂ0(0)，ｂ0(1)，．．．，ｂ0(d-1)，ｂ1(0)，ｂ1(1)，．．．，ｂ1(d-1)，．．．，
ｂk-1(0)，ｂk-1(1)，．．．，ｂk-1(d-1)）                      （５６）
【００７４】
次に、生成部３１２は、式（５５）のバイナリベクトルの要素ａi(d-1) の後にｄ個の０を挿入して、２ｋｄ次元のバイナリベクトルＵＡを生成し、生成部３２２は、式（５６）のバイナリベクトルの要素ｂi(d-1) の後にｄ個の０を挿入して、２ｋｄ次元のバイナリベクトルＵＢを生成する。
【００７５】
ＵＡ＝（ａ0(0)，ａ0(1)，．．．，ａ0(d-1)，０，０，．．．，０，
ａ1(0)，ａ1(1)，．．．，ａ1(d-1)，０，０，．．．，０，．．．，
ａk-1(0)，ａk-1(1)，．．．，ａk-1(d-1)，０，０，．．．，０）  （５７）
ＵＢ＝（ｂ0(0)，ｂ0(1)，．．．，ｂ0(d-1)，０，０，．．．，０，
ｂ1(0)，ｂ1(1)，．．．，ｂ1(d-1)，０，０，．．．，０，．．．，
ｂk-1(0)，ｂk-1(1)，．．．，ｂk-1(d-1)，０，０，．．．，０）  （５８）
【００７６】
バイナリベクトルＵＡ及びバイナリベクトルＵＢは、それぞれ、式（４１）のベクトルＡ及び式（４２）のベクトルＢとして用いられる。次に、生成部３１２及び生成部３２２は、バイナリベクトルＵＡ及びバイナリベクトルＵＢを用いて、式（４３）及び式（４４）により、多項式ｐｍ１（ＵＡ）及び多項式ｐｍ２（ＵＢ）を生成する。
【００７７】
【数５】
0006413743.tif 000006
【００７８】
この場合、ｎ＝２ｋｄである。式（６０）は、式（５９）の多項式Ａi（ｘ）を表し、式（６２）は、式（６１）の多項式Ｂi（ｘ）を表す。生成部３１２及び生成部３２２は、式（４５）及び式（４６）により、暗号化多項式Ｅ（ｐｍ１（ＵＡ））及び暗号化多項式Ｅ（ｐｍ２（ＵＢ））を生成する。
【００７９】
暗号演算装置３０３の生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））と暗号化多項式Ｅ（ｐｍ２（ＵＢ））とを乗算する。式（３１）及び式（３２）に示したように、準同型暗号による暗号演算処理において、２つの多項式ｆ（ｘ）及びｇ（ｘ）に対する加算及び乗算は、次式のような性質を持つ。
【００８０】
Ｅ（ｆ（ｘ））＋Ｅ（ｇ（ｘ））＝Ｅ（ｆ（ｘ）＋ｇ（ｘ））      （７１）
Ｅ（ｆ（ｘ））＊Ｅ（ｇ（ｘ））＝Ｅ（ｆ（ｘ）＊ｇ（ｘ））      （７２）
【００８１】
そこで、以下では、Ｅ（ｐｍ１（ＵＡ））とＥ（ｐｍ２（ＵＢ））の乗算をｐｍ１（ＵＡ）とｐｍ２（ＵＢ）の乗算に置き換えて、生成部３３２が行う暗号演算を説明する。式（５９）のｐｍ１（ＵＡ）と式（６１）のｐｍ２（ＵＢ）とを乗算すると、次のような多項式が得られる。
【００８２】
【数６】
0006413743.tif 000007
【００８３】
式（７４）は、式（７３）の多項式Ｐ１（ｘ）を表す。式（７４）の計算では、ｘn＝−１が適用されている。多項式Ｐ１（ｘ）は、２（ｄ−１）次の多項式であり、多項式Ｐ２（ｘ）は、２ｄ次以上の項を含む多項式である。暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））は、暗号化多項式Ｅ（Ｐ１（ｘ）＋Ｐ２（ｘ））と等価になる。
【００８４】
分析装置３０４の分析部３４２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を復号して、多項式Ｐ１（ｘ）＋Ｐ２（ｘ）を生成する。そして、分析部３４２は、得られた多項式のうち、０次から２（ｄ−１）次までの項を含む部分であるＰ１（ｘ）の変数ｘに２を代入することで、Ｐ１（２）の値を計算する。
【００８５】
【数７】
0006413743.tif 000008
【００８６】
式（７５）が示すように、得られたＰ１（２）の値は、ベクトルＶＡとベクトルＶＢの内積を表している。ベクトルＶＡ及びベクトルＶＢを、式（５７）及び式（５８）のようなバイナリベクトルＵＡ及びバイナリベクトルＵＢに変換することで、復号結果に式（７４）の多項式Ｐ１（ｘ）が現れる仕組みになっている。そして、Ｐ１（ｘ）にｘ＝２を代入することで、ベクトルＶＡとベクトルＶＢの内積が得られる。
【００８７】
このような暗号処理によれば、鍵生成パラメータｔの値は、多項式Ｐ１（ｘ）に含まれる各項の係数よりも大きな値に設定すればよい。具体的には、ベクトルＶＡ及びベクトルＶＢの要素数ｋと、各要素の最大ビット数ｄとに対して、鍵生成パラメータｔの値をｔ＞ｋｄを満たすように設定すればよいことが分かる。これに対して、ベクトルＶＡ及びベクトルＶＢのバイナリ変換を行わずに、暗号化多項式Ｅ（ｐｍ１（ＶＡ））と暗号化多項式Ｅ（ｐｍ２（ＶＢ））とを乗算する場合は、鍵生成パラメータｔに対する条件は、ｔ＞ｍ＊２＾（２ｄ）となる。
【００８８】
例えば、ｋ＝１０００、ｄ＝１６と設定して、Ｅ（ｐｍ１（ＶＡ））＊Ｅ（ｐｍ２（ＶＢ））を計算する場合、ｔの値は１０００＊２＾３２より大きくなる。これに対して、バイナリベクトルＵＡ及びバイナリベクトルＵＢを用いて、Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を計算する場合、ｔの値は１６０００より大きければ十分である。このｔの値は、非特許文献２の準同型暗号にとって十分に実用的なレベルである。
【００８９】
このように、ベクトルをバイナリ変換してから暗号化多項式を生成することで、大きな値を要素に持つベクトルに対して、暗号化多項式のサイズを増大させることなく、特許文献１と同様の一括暗号化方式を適用できるようになる。具体的には、１回の暗号乗算により、大きな値を要素に持つベクトルを暗号化したままで、効率よく内積を計算することが可能になる。
【００９０】
分析装置３０４は、ベクトルＡとベクトルＢの内積だけでなく、内積に基づく様々な統計値を計算することができる。分析装置３０４は、内積に基づく類似度（例えば、コサイン類似度）又は内積に基づく相違度（例えば、ハミング距離、ユークリッド距離等）を計算してもよい。
【００９１】
図４は、図３の統計システムにおける暗号処理の例を示すフローチャートである。この暗号処理において、分析装置３０４は、ベクトルＶＡとベクトルＶＢの内積を用いて、ベクトルＶＡとベクトルＶＢの共分散ｃｏｖ（ＶＡ，ＶＢ）及び相関係数ｒ（ＶＡ，ＶＢ）を計算する。共分散ｃｏｖ（ＶＡ，ＶＢ）及び相関係数ｒ（ＶＡ，ＶＢ）は、ベクトルＶＡの要素の平均ｍVA及び標準偏差ｓVAと、ベクトルＶＢの要素の平均ｍVB及び標準偏差ｓVBとを用いて、次式により計算される。
【００９２】
【数８】
0006413743.tif 000009
【００９３】
まず、端末装置３０１の生成部３１２は、データＤＡからベクトルＶＡを生成し（ステップ４１１）、ベクトルＶＡの各要素をバイナリ変換して、式（５５）のバイナリベクトルを生成する（ステップ４１２）。次に、生成部３１２は、式（５５）のバイナリベクトルの要素ａi(d-1) の後にｄ個の０を挿入して、式（５７）のバイナリベクトルＵＡを生成する（ステップ４１３）。
【００９４】
次に、生成部３１２は、式（４３）及び式（４４）を用いて、バイナリベクトルＵＡを多項式ｐｍ１（ＵＡ）及び多項式ｐｍ２（ＵＡ）に変換する（ステップ４１４）。そして、生成部３１２は、多項式ｐｍ１（ＵＡ）及び多項式ｐｍ２（ＵＡ）を公開鍵により暗号化して、暗号化多項式Ｅ（ｐｍ１（ＵＡ））及び暗号化多項式Ｅ（ｐｍ２（ＵＡ））を生成する。送信部３１３は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））を表す暗号情報と、暗号化多項式Ｅ（ｐｍ２（ＵＡ））を表す暗号情報とを、暗号演算装置３０３へ送信する（ステップ４１５）。
【００９５】
一方、端末装置３０２の生成部３２２は、データＤＢからベクトルＶＢを生成し（ステップ４２１）、ベクトルＶＢの各要素をバイナリ変換して、式（５６）のバイナリベクトルを生成する（ステップ４２２）。次に、生成部３２２は、式（５６）のバイナリベクトルの要素ｂi(d-1) の後にｄ個の０を挿入して、式（５８）のバイナリベクトルＵＢを生成する（ステップ４２３）。
【００９６】
次に、生成部３２２は、式（４３）及び式（４４）を用いて、バイナリベクトルＵＢを多項式ｐｍ１（ＵＢ）及び多項式ｐｍ２（ＵＢ）に変換する（ステップ４２４）。そして、生成部３２２は、多項式ｐｍ１（ＵＢ）及び多項式ｐｍ２（ＵＢ）を公開鍵により暗号化して、暗号化多項式Ｅ（ｐｍ１（ＵＢ））及び暗号化多項式Ｅ（ｐｍ２（ＵＢ））を生成する。送信部３２３は、暗号化多項式Ｅ（ｐｍ１（ＵＢ））を表す暗号情報と、暗号化多項式Ｅ（ｐｍ２（ＵＢ））を表す暗号情報とを、暗号演算装置３０３へ送信する（ステップ４２５）。
【００９７】
暗号演算装置３０３の生成部３３２は、まず、すべての要素が１であるｋ次元のベクトルＶＣを、式（５５）及び式（５７）と同様にしてバイナリ変換することで、２ｋｄ次元のバイナリベクトルＵＣを生成する（ステップ４３１）。
【００９８】
ＶＣ＝（１，１，．．．，１）      （９１）
ＶＣ→（１，０，．．．，０，１，０，．．．，０，．．．，
１，０，．．．，０）                              （９２）
ＵＣ＝（１，０，．．．，０，０，０，．．．，０，
１，０，．．．，０，０，０，．．．，０，．．．，
１，０，．．．，０，０，０，．．．，０）      （９３）
【００９９】
次に、生成部３３２は、式（４３）及び式（４４）を用いて、バイナリベクトルＵＣを多項式ｐｍ１（ＵＣ）及び多項式ｐｍ２（ＵＣ）に変換する。そして、生成部３３２は、多項式ｐｍ１（ＵＣ）及び多項式ｐｍ２（ＵＣ）を公開鍵により暗号化して、暗号化多項式Ｅ（ｐｍ１（ＵＣ））及び暗号化多項式Ｅ（ｐｍ２（ＵＣ））を生成する。
【０１００】
次に、生成部３３２は、次のような５種類の暗号乗算を行って、５つの乗算結果を生成する（ステップ４３２）。
【０１０１】
（１）生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））と暗号化多項式Ｅ（ｐｍ２（ＵＣ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＣ））を生成する。
【０１０２】
（２）生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＣ））と暗号化多項式Ｅ（ｐｍ２（ＵＢ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＣ））＊Ｅ（ｐｍ２（ＵＢ））を生成する。
【０１０３】
（３）生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））と暗号化多項式Ｅ（ｐｍ２（ＵＡ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＡ））を生成する。
【０１０４】
（４）生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＢ））と暗号化多項式Ｅ（ｐｍ２（ＵＢ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＢ））＊Ｅ（ｐｍ２（ＵＢ））を生成する。
【０１０５】
（５）生成部３３２は、暗号化多項式Ｅ（ｐｍ１（ＵＡ））と暗号化多項式Ｅ（ｐｍ２（ＵＢ））とを乗算して、乗算結果の暗号化多項式Ｅ（ｐｍ１（ＵＡ））＊Ｅ（ｐｍ２（ＵＢ））を生成する。
【０１０６】
そして、送信部３３３は、各乗算結果の暗号化多項式を表す暗号情報を分析装置３０４へ送信する（ステップ４３３）。
【０１０７】
分析装置３０４の分析部３４２は、５つの乗算結果の暗号化多項式を秘密鍵により復号して、５つの復号結果の多項式を生成する（ステップ４４１）。次に、分析部３４２は、各復号結果の多項式に含まれる項のうち、２（ｄ−１）次より大きな次数の項を除く、２（ｄ−１）次の多項式の部分にｘ＝２を代入することで、次のような５種類の内積を計算する（ステップ４４２）。
【０１０８】
（ａ）ベクトルＶＡとベクトルＶＣの内積
（ｂ）ベクトルＶＣとベクトルＶＢの内積
（ｃ）ベクトルＶＡとベクトルＶＡの内積
（ｄ）ベクトルＶＢとベクトルＶＢの内積
（ｅ）ベクトルＶＡとベクトルＶＢの内積
【０１０９】
ベクトルＶＡとベクトルＶＣの内積は、式（８１）の右辺に現れるベクトルＶＡの要素の総和を表し、ベクトルＶＣとベクトルＶＢの内積は、式（８２）の右辺に現れるベクトルＶＢの要素の総和を表す。
【０１１０】
ベクトルＶＡとベクトルＶＡの内積は、式（８３）の右辺に現れるベクトルＶＡの要素の二乗和を表し、ベクトルＶＢとベクトルＶＢの内積は、式（８４）の右辺に現れるベクトルＶＢの要素の二乗和を表す。ベクトルＶＡとベクトルＶＢの内積は、式（８５）の右辺に現れ、式（７４）の多項式Ｐ１（ｘ）にｘ＝２を代入することで計算される。
【０１１１】
分析部３４２は、５種類の内積と式（８１）〜式（８６）とを用いて、ベクトルＶＡとベクトルＶＢの共分散ｃｏｖ（ＶＡ，ＶＢ）及び相関係数ｒ（ＶＡ，ＶＢ）を計算する統計処理を行い、処理結果を出力する（ステップ４４３）。
【０１１２】
このような暗号処理によれば、大きな値を要素に持つベクトルに対して暗号化多項式のサイズを増大させることなく、５種類の暗号乗算により、効率よく共分散及び相関係数を計算することが可能になる。
【０１１３】
図１の暗号処理装置１０１及び図３の統計システムの構成は一例に過ぎず、暗号処理装置の用途や条件に応じて一部の構成要素を省略又は変更してもよい。例えば、図３の統計システムにおいて、端末装置３０１又は端末装置３０２のいずれか一方を用いて、ベクトルＶＡ及びベクトルＶＢを生成し、Ｅ（ｐｍ１（ＵＡ））、Ｅ（ｐｍ２（ＵＡ））、Ｅ（ｐｍ１（ＵＢ））、及びＥ（ｐｍ２（ＵＢ））を生成してもよい。この場合、他方の端末装置を省略することができる。
【０１１４】
図２及び図４のフローチャートは一例に過ぎず、暗号処理装置又は統計システムの構成や条件に応じて一部の処理を省略又は変更してもよい。例えば、図４の暗号処理において、Ｅ（ｐｍ１（ＵＣ））及びＥ（ｐｍ２（ＵＣ））があらかじめ生成されている場合は、ステップ４３１の処理を省略することができる。
【０１１５】
図４のステップ４４３において、分析装置３０４は、ベクトルＶＡとベクトルＶＢの内積のみに基づく処理結果を生成してもよい。この場合、分析装置３０４は、ステップ４４２において、ベクトルＶＡとベクトルＶＣの内積、ベクトルＶＣとベクトルＶＢの内積、ベクトルＶＡとベクトルＶＡの内積、及びベクトルＶＢとベクトルＶＢの内積の計算を省略することができる。
【０１１６】
また、端末装置３０１は、ステップ４１４において、Ｅ（ｐｍ２（ＵＡ））の生成を省略することができ、端末装置３０２は、ステップ４２４において、Ｅ（ｐｍ１（ＵＢ））の生成を省略することができる。暗号演算装置３０３は、ステップ４３１の処理を省略することができ、ステップ４３２において、Ｅ（ｐｍ１（ＵＡ））とＥ（ｐｍ２（ＵＢ））との乗算以外の４つの暗号乗算を省略することができる。
【０１１７】
式（１）〜式（９３）は一例に過ぎず、他の定式化を用いてもよい。例えば、式（７３）の多項式に含まれる２（ｄ−１）次の多項式の代わりに、他の部分の多項式からベクトルＶＡとベクトルＶＢの内積が得られるような定式化を用いてもよい。
【０１１８】
図１及び図３の暗号処理装置１０１、端末装置３０１、端末装置３０２、暗号演算装置３０３、及び分析装置３０４は、例えば、ハードウェア回路として実装することができる。この場合、暗号処理装置１０１の各構成要素を個別の回路として実装してもよく、複数の構成要素を１つの集積回路として実装してもよい。
【０１１９】
暗号処理装置１０１、端末装置３０１、端末装置３０２、暗号演算装置３０３、及び分析装置３０４は、図５に示すような情報処理装置（コンピュータ）を用いて実現することも可能である。
【０１２０】
図５の情報処理装置は、Central Processing Unit（ＣＰＵ）５０１、メモリ５０２、入力装置５０３、出力装置５０４、補助記憶装置５０５、媒体駆動装置５０６、及びネットワーク接続装置５０７を含む。これらの構成要素はバス５０８により互いに接続されている。
【０１２１】
メモリ５０２は、例えば、Read Only Memory（ＲＯＭ）、Random Access Memory（ＲＡＭ）、フラッシュメモリ等の半導体メモリである。メモリ５０２は、暗号処理装置１０１、端末装置３０１、端末装置３０２、暗号演算装置３０３、又は分析装置３０４が行う処理のためのプログラム及びデータを格納する。メモリ５０２は、図１の記憶部１１１、図３の記憶部３１１、又は記憶部３２１として用いることができる。
【０１２２】
情報処理装置が暗号処理装置１０１である場合、ＣＰＵ５０１は、例えば、メモリ５０２を利用してプログラムを実行することにより、生成部１１２として動作し、暗号処理を行う。
【０１２３】
情報処理装置が端末装置３０１である場合、ＣＰＵ５０１は、例えば、メモリ５０２を利用してプログラムを実行することにより、生成部３１２として動作し、暗号処理を行う。情報処理装置が端末装置３０２である場合、ＣＰＵ５０１は、例えば、メモリ５０２を利用してプログラムを実行することにより、生成部３２２として動作し、暗号処理を行う。
【０１２４】
情報処理装置が暗号演算装置３０３である場合、ＣＰＵ５０１は、例えば、メモリ５０２を利用してプログラムを実行することにより、生成部３３２として動作する。情報処理装置が分析装置３０４である場合、ＣＰＵ５０１は、例えば、メモリ５０２を利用してプログラムを実行することにより、分析部３４２として動作する。
【０１２５】
入力装置５０３は、例えば、キーボード、ポインティングデバイス等であり、ユーザ又はオペレータからの指示や情報の入力に用いられる。出力装置５０４は、例えば、表示装置、プリンタ、スピーカ等であり、ユーザ又はオペレータへの問い合わせや処理結果の出力に用いられる。処理結果は、分析装置３０４による統計処理の結果であってもよい。
【０１２６】
補助記憶装置５０５は、例えば、磁気ディスク装置、光ディスク装置、光磁気ディスク装置、テープ装置等である。補助記憶装置５０５は、ハードディスクドライブ又はフラッシュメモリであってもよい。情報処理装置は、補助記憶装置５０５にプログラム及びデータを格納しておき、それらをメモリ５０２にロードして使用することができる。補助記憶装置５０５は、図１の記憶部１１１、図３の記憶部３１１、又は記憶部３２１として用いることができる。
【０１２７】
媒体駆動装置５０６は、可搬型記録媒体５０９を駆動し、その記録内容にアクセスする。可搬型記録媒体５０９は、メモリデバイス、フレキシブルディスク、光ディスク、光磁気ディスク等である。可搬型記録媒体５０９は、Compact Disk Read Only Memory（ＣＤ−ＲＯＭ）、Digital Versatile Disk（ＤＶＤ）、Universal Serial Bus（ＵＳＢ）メモリ等であってもよい。ユーザ又はオペレータは、この可搬型記録媒体５０９にプログラム及びデータを格納しておき、それらをメモリ５０２にロードして使用することができる。
【０１２８】
このように、プログラム及びデータを格納するコンピュータ読み取り可能な記録媒体は、メモリ５０２、補助記憶装置５０５、及び可搬型記録媒体５０９のような、物理的な（非一時的な）記録媒体である。
【０１２９】
ネットワーク接続装置５０７は、Local Area Network（ＬＡＮ）、インターネット等の通信ネットワークに接続され、通信に伴うデータ変換を行う通信インタフェースである。情報処理装置は、ネットワーク接続装置５０７を介して外部の装置からプログラム及びデータを受信し、それらをメモリ５０２にロードして使用することができる。ネットワーク接続装置５０７は、図１の送信部１１３、図３の送信部３１３、送信部３２３、受信部３３１、送信部３３３、又は受信部３４１として用いることができる。
【０１３０】
なお、情報処理装置が図５のすべての構成要素を含む必要はなく、用途や条件に応じて一部の構成要素を省略することも可能である。例えば、ユーザ又はオペレータからの指示や情報の入力を行わない場合は、入力装置５０３を省略してもよく、ユーザ又はオペレータへの問い合わせや処理結果の出力を行わない場合は、出力装置５０４を省略してもよい。情報処理装置が可搬型記録媒体５０９にアクセスしない場合は、媒体駆動装置５０６を省略してもよい。
【０１３１】
開示の実施形態とその利点について詳しく説明したが、当業者は、特許請求の範囲に明確に記載した本発明の範囲から逸脱することなく、様々な変更、追加、省略をすることができるであろう。
【０１３２】
図１乃至図５を参照しながら説明した実施形態に関し、さらに以下の付記を開示する。
（付記１）
第１のベクトルを記憶する記憶部と、
前記第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する生成部と、
前記第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する暗号演算装置へ、前記第１の暗号化多項式を表す暗号情報を送信する送信部とを備え、
前記第３の暗号化多項式を復号して得られる第３の多項式の所定部分の変数に２を代入することで、前記第１のベクトルと前記第２のベクトルとの演算結果が得られることを特徴とする暗号処理装置。
（付記２）
前記生成部は、前記第１のベクトルの要素を複数のビットを含むビット列に変換し、２つの要素に対応する２つのビット列の間に、複数の０を表すビット値を含むビット列を挿入することで、前記第１のバイナリベクトルを生成することを特徴とする付記１記載の暗号処理装置。
（付記３）
前記複数の０を表すビット値を含む前記ビット列のビット数は、前記複数のビットを含む前記ビット列のビット数ｄと等しく、前記第３の多項式の前記所定部分は、前記第３の多項式に含まれる２（ｄ−１）次以下の次数の項に対応し、前記演算結果は、前記第１のベクトルと前記第２のベクトルとの内積であることを特徴とする付記２に記載の暗号処理装置。
（付記４）
暗号処理装置が、第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する工程と、
前記暗号処理装置が、前記第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する暗号演算装置へ、前記第１の暗号化多項式を表す暗号情報を送信する工程とを備え、
前記第３の暗号化多項式を復号して得られる第３の多項式の所定部分の変数に２を代入することで、前記第１のベクトルと前記第２のベクトルとの演算結果が得られることを特徴とする暗号処理方法。
（付記５）
前記第１の暗号化多項式を生成する工程は、前記第１のベクトルの要素を複数のビットを含むビット列に変換し、２つの要素に対応する２つのビット列の間に、複数の０を表すビット値を含むビット列を挿入することで、前記第１のバイナリベクトルを生成することを特徴とする付記４記載の暗号処理方法。
（付記６）
前記複数の０を表すビット値を含む前記ビット列のビット数は、前記複数のビットを含む前記ビット列のビット数ｄと等しく、前記第３の多項式の前記所定部分は、前記第３の多項式に含まれる２（ｄ−１）次以下の次数の項に対応し、前記演算結果は、前記第１のベクトルと前記第２のベクトルとの内積であることを特徴とする付記５に記載の暗号処理方法。
（付記７）
暗号処理をコンピュータに実行させる暗号処理プログラムであって、
前記暗号処理は、
第１のベクトルの要素をバイナリ変換した第１のバイナリベクトルに対応する第１の多項式を暗号化して、第１の暗号化多項式を生成する工程と、
前記第１の暗号化多項式と、第２のベクトルの要素をバイナリ変換した第２のバイナリベクトルに対応する第２の多項式を暗号化して生成される、第２の暗号化多項式とを乗算して、第３の暗号化多項式を生成する暗号演算装置へ、前記第１の暗号化多項式を表す暗号情報を送信する工程とを備え、
前記第３の暗号化多項式を復号して得られる第３の多項式の所定部分の変数に２を代入することで、前記第１のベクトルと前記第２のベクトルとの演算結果が得られることを特徴とする暗号処理プログラム。
（付記８）
前記第１の暗号化多項式を生成する工程は、前記第１のベクトルの要素を複数のビットを含むビット列に変換し、２つの要素に対応する２つのビット列の間に、複数の０を表すビット値を含むビット列を挿入することで、前記第１のバイナリベクトルを生成することを特徴とする付記７記載の暗号処理プログラム。
（付記９）
前記複数の０を表すビット値を含む前記ビット列のビット数は、前記複数のビットを含む前記ビット列のビット数ｄと等しく、前記第３の多項式の前記所定部分は、前記第３の多項式に含まれる２（ｄ−１）次以下の次数の項に対応し、前記演算結果は、前記第１のベクトルと前記第２のベクトルとの内積であることを特徴とする付記８に記載の暗号処理プログラム。
【符号の説明】
【０１３３】
１０１  暗号処理装置
１１１、３１１、３２１  記憶部
１１２、３１２、３２２、３３２  生成部
１１３、３１３、３２３、３３３  送信部
３０１、３０２  端末装置
３０３  暗号演算装置
３０４  分析装置
３３１、３４１  受信部
３４２  分析部
５０１  ＣＰＵ
５０２  メモリ
５０３  入力装置
５０４  出力装置
５０５  補助記憶装置
５０６  媒体駆動装置
５０７  ネットワーク接続装置
５０８  バス
５０９  可搬型記録媒体
【図１】
0006413743.tif 000010
【図２】
0006413743.tif 000011
【図３】
0006413743.tif 000012
【図４】
0006413743.tif 000013
【図５】
0006413743.tif 000014