ベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法及び暗号鍵共有システム
【課題】通信コスト及び計算コストを低減することのできるベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法、及び暗号鍵共有システムを提供する。
【解決手段】第１計算装置１００は、乱数Ｗiに基づくスカラー値と乱数Ｒjとに基づいてｎ次元ベクトルＶａをｎ次元ベクトルに線形変換し、線形変換したｎ次元ベクトルにおける各要素に対して乱数Ｍiで除算した剰余を算出し、該剰余を各要素とするｎ次元変換ベクトルＸを第２計算装置１１０に送信する変換部１０４を有し、第２計算装置１１０は、受信したｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとに基づいて内積値Ｚを算出し、該内積値Ｚを第１計算装置１００に送信する計算部１１４を有し、第１計算装置１００は、前記スカラー値の逆数と受信した内積値Ｚとに基づいてスカラー値を算出し、該スカラー値に対して乱数Ｍiで除算した剰余を算出する逆変換部１０５をさらに有する。
【解決手段】第１計算装置１００は、乱数Ｗiに基づくスカラー値と乱数Ｒjとに基づいてｎ次元ベクトルＶａをｎ次元ベクトルに線形変換し、線形変換したｎ次元ベクトルにおける各要素に対して乱数Ｍiで除算した剰余を算出し、該剰余を各要素とするｎ次元変換ベクトルＸを第２計算装置１１０に送信する変換部１０４を有し、第２計算装置１１０は、受信したｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとに基づいて内積値Ｚを算出し、該内積値Ｚを第１計算装置１００に送信する計算部１１４を有し、第１計算装置１００は、前記スカラー値の逆数と受信した内積値Ｚとに基づいてスカラー値を算出し、該スカラー値に対して乱数Ｍiで除算した剰余を算出する逆変換部１０５をさらに有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、２者間で互いにベクトルを秘匿したまま内積を計算可能なベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法及び暗号鍵共有システムに関する。
【背景技術】
【０００２】
複数のパーティーに分散されたデータを、それぞれのパーティーが秘密にしたまま、協力して様々な計算を行うプロトコル（マルチパーティープロトコル）が盛んに研究されている。マルチパーティープロトコルは、電子投票や電子契約、プライバシーを保護したデータマイニングなど、様々な分野への応用が考えられている。こうした様々な応用プロトコルを実現するための基本的なプロトコルとして、ベクトルの内積計算プロトコルがある。これは、２者（AliceとBob）がそれぞれ秘密のベクトルＶａ、Ｖｂを保持している状態で、互いに秘密ベクトルを明かすことなく、Aliceが内積値Ｖａ・Ｖｂを計算するプロトコルである。
【０００３】
内積計算プロトコルの実現方法としては、暗号化関数が準同型性を持つ公開鍵暗号であるPaillier暗号（例えば、非特許文献２参照）を利用する方法が知られている（例えば、非特許文献１参照）。具体的には以下の通りである。
【０００４】
まずAliceが秘密鍵と公開鍵のペアを生成し、自分の秘密ベクトルＶａ＝（ａ1，ａ2，…，ａn）の各要素を公開鍵により暗号化して、暗号文 Ｅ（ａ1），Ｅ（ａ2），…，Ｅ（ａn）をBobに送信する（Ｅ(・)は暗号化関数とする）。Bobはこれらの暗号文を受信し、自分の秘密ベクトルＶｂ＝（ｂ1，ｂ2，…，ｂn）を用いて、Ｅ(・)の準同型性を利用し、以下のように内積値の暗号文を計算する。
（数１）
ｅ＝（Ｅ（ａ1）b1）×（Ｅ（ａ2）b2）×…×（Ｅ（ａn）bn） ｍｏｄ Ｍ
＝Ｅ（ａ1×ｂ1＋ａ2×ｂ2＋…＋ａn×ｂn）
＝Ｅ（Ｖａ・Ｖｂ）
但し、Ｍは、例えば２０４８ビットの整数である。BobはAliceにｅを送り返す。Aliceは秘密鍵を用いてｅを復号化し、内積値Ｖａ・Ｖｂを得る。
【０００５】
一方、暗号化通信に不可欠な、暗号鍵の共有方法（鍵共有プロトコル）として、素因数分解問題の困難性に安全性の根拠を置くRSA暗号（例えば、非特許文献３参照）に基づく方式や、離散対数問題に基づくDiffie-Hellman鍵共有の方法（例えば、非特許文献４参照）が知られている。
【非特許文献１】Bart Goethals, Sven Laur, Helger Lipmaa and Taneli Mielika"inen. "On Private Scalar Product Computation for Privacy-Preserving Data Mining", The 7th Annual International Conference in Information Security and Cryptology(ICISC2004), vol. 3506 of Lecture Notes in Computer Science, pages 104-120(2004).
【非特許文献２】Pascal Paillier. "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes", In Jacques Stern, editor, Advances in Cryptology EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 223−238, Prague, Czech Republic, 2−6 May 1999. Springer-Verlag.
【非特許文献３】R.L.Rivest, A.Shamir, and L.Adelman, "Method for Obtaining Digital Signature and Public-key Cryptsystems", Communications of the ACM, Vol. 21 (2), pp.120−126. 1978.
【非特許文献４】W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol.IT-22, No.6, pp.644-654, Nov, 1976.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ベクトルの内積計算プロトコルである非特許文献１に記載の方法は、非特許文献２に記載のPaillier暗号を利用している。しかしながら、従来の方法では、通信コストと計算コストが大きいという問題がある。
【０００７】
実際、Paillier暗号において推奨されている鍵長では、暗号文のサイズが２０４８ビットであり、ベクトルがn次元の場合、通信量は ２０４８×ｎビット以上となる。また暗号化、復号化の計算では、巨大な整数を法としたべき乗計算をnに比例した回数実行する必要があり、計算コストが大きい。特に、扱うベクトルの次元nが大きい場合や、内積計算処理を頻繁に行うシステム（巨大なＤＢを対象としたデータマイニングなど）では、通信コスト、計算コストの削減が必要となるという問題点があった。
【０００８】
本発明は前記問題点に鑑みてなされたものであり、その目的とするところは、通信コスト及び計算コストを低減することのできるベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法及び暗号鍵共有システムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明は前記目的を達成するために、各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを備えるベクトル秘匿型内積計算システムにおいて、前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部と、整数である第１、第２及び第３の乱数を生成する第１生成部と、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換部とを有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部と、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算部とを有し、前記第１の計算装置は、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換部をさらに有するベクトル秘匿型内積計算システムを提案する。
【００１０】
また、本発明は前記目的を達成するために、各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを有するシステムに用いられるベクトル秘匿型内積計算方法であって、前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部を有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部を有しており、前記第１の計算装置により、整数である第１、第２及び第３の乱数を生成する第１生成ステップと、前記第１の計算装置により、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換ステップと、前記第２の計算装置により、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算ステップと、前記第１の計算装置により、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換ステップとを備えるベクトル秘匿型内積計算方法を提案する。
【００１１】
本発明によれば、第１の計算装置によって、第１の乱数に基づくｍ行ｍ列の正則行列と第２の乱数とに基づいて第１のｎ次元ベクトルがｍ行ｎ列の行列に線形変換され、線形変換した当該ｍ行ｎ列の行列における各要素に対して第３の乱数で除算した剰余が算出され、当該剰余を各要素とするｍ行ｎ列の変換行列が第１通信部により送信される。また、第２の計算装置によって、第２通信部により受信したｍ行ｎ列の変換行列と第２のｎ次元ベクトルとに基づいてｍ次元ベクトルが算出され、当該ｍ次元ベクトルが第２通信部により送信される。さらに、第１の計算装置によって、ｍ行ｍ列の正則行列の第３の乱数を法とした逆行列と第１通信部により受信したｍ次元ベクトルとに基づいてｍ次元ベクトルが算出され、当該ｍ次元ベクトルにおける所定の要素に対して第３の乱数で除算した剰余が算出される。これにより、従来と同程度の安全性を確保できるものとして、例えばｍ＝１、第１及び第３の乱数が１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１の計算装置における計算は第３の乱数を法とする掛け算であり、第２の計算装置における計算はｎ回の掛け算と足し算となる。
【発明の効果】
【００１２】
本発明によれば、従来と同程度の安全性を確保できるものとして、例えばｍ＝１、第１及び第３の乱数が１００ビットの整数である場合、通信量は第１計算装置から第２計算装置への送受信が１００×ｎビットで第２計算装置から第１計算装置への送受信が１００ビット程度となり、第１の計算装置における計算は第３の乱数を法とする掛け算であり、第２の計算装置における計算はｎ回の掛け算と足し算となる。これにより、従来のような送受信とも２０４８×ｎビット以上の通信量や２０４８ビットの数を法とするべき乗計算を必要とせず、従来よりも小さい法を用いることができ、かけ算や足し算はべき乗計算よりも計算コストが数百分の一程度でありことから、従来よりも通信コスト及び計算コストを低減することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照しながら本発明の一実施の形態を詳述する。
【００１４】
［第１実施形態］
図１乃至図３は本発明の第１実施形態を示すものである。まず、図１及び図２を用いてベクトル秘匿型内積計算システムの構成を説明する。図１は、ベクトル秘匿型内積計算システムの機能構成を説明する概略構成図である。
【００１５】
図１に示すように、ベクトル秘匿型内積計算システム１は、各要素が整数であるｎ次元ベクトルＶａ＝（Ａ1，Ａ2，…，Ａn）（ｎは正の整数）を秘匿する第１計算装置１００と、各要素が整数であるｎ次元ベクトルＶｂ＝（Ｂ1，Ｂ2，…，Ｂn）を秘匿する第２計算装置１１０とを備え、正の整数である所定数Ｑが設定される第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら通信し、第１計算装置１００が以下の式（１）で計算される剰余Ｃを算出するためのものである。
（数２）
Ｃ＝Ｖａ・Ｖｂ ｍｏｄ Ｑ
＝Ａ1Ｂ1＋Ａ2Ｂ2＋…＋ＡnＢn ｍｏｄ Ｑ …（１）
【００１６】
第１計算装置１００と第２計算装置１１０とは、ネットワークＮ１を介して互いに接続される。第１計算装置１００は、入力部１０１と、乱数生成部１０２と、一時記憶部１０３と、変換部１０４と、逆変換部１０５と、出力部１０６とから構成される。
【００１７】
入力部１０１は、前述のｎ次元ベクトルＶａが入力される。乱数生成部１０２は、後述する、整数の乱数を生成する。一時記憶部１０３は生成した乱数を一時的に記憶する。変換部１０４は、生成した乱数を用いてｎ次元ベクトルＶａの各要素値を変換して変換ベクトルＸを作成し、第２計算装置１１０に送信する。逆変換部１０５は、第２計算装置１１０から送信される後述の内積値Ｚを受信し、生成した乱数と受信した内積値Ｚとから剰余Ｃを算出する。出力部１０６は、算出された剰余Ｃを出力する。
【００１８】
第２計算装置１１０は、入力部１１１と、乱数生成部１１２と、拡張部１１３と、計算部１１４とから構成される。
【００１９】
入力部１１１は、前述のｎ次元ベクトルＶｂが入力される。乱数生成部１０２は、後述する、整数の乱数を生成する。拡張部１１３は後述するｎ次元拡張ベクトルＹを作成する。計算部１０４は、第１計算装置１００から送信されるｎ次元変換ベクトルＸを受信し、受信したｎ次元変換ベクトルＸとｎ次元拡張ベクトルＹとの内積値Ｚを計算して第１計算装置１００に送信する。
【００２０】
本実施形態では、第１計算装置１００の入力部１０１にｎ次元ベクトルＶａが入力され、第２計算装置１１０の入力部１１１にｎ次元ベクトルＶｂが入力されるが、これに限定されず、第１計算装置１００がｎ次元ベクトルＶａを生成し、第２計算装置１１０がｎ次元ベクトルＶｂを生成するようにしてもよい。
【００２１】
図２は、図１に示した第１計算装置及び第２計算装置のハードウェア構成を説明する概略構成図である。
【００２２】
図２に示すように、第１計算装置１００及び第２計算装置１１０は、それぞれＣＰＵ５００と、メモリ５０１と、ＨＤＤ５０２と、入出力装置５０３と、通信装置５０４とから構成され、ＣＰＵ５００、メモリ５０１、ＨＤＤ５０２、入出力装置５０３、及び通信装置５０４は、内部バス５０５を介して互いに接続される。
【００２３】
ＣＰＵ５００は、第１計算装置１００では図１に示した乱数生成部１０２、変換部１０４及び逆変換部１０５に対応し、第２計算装置１１０では乱数生成部１１２、拡張部１１３及び計算部１１４に対応する。メモリ５０１又はＨＤＤ５０２は、図１に示した一時記憶部１０３に対応する。入出力装置５０３は、第１計算装置１００では図１に示した入力部１０１及び出力部１０６に対応し、第２計算装置１１０では入力部１１１に対応する。通信計算装置５０４は、第１計算装置１００と第２計算装置１１０との間で情報の送受信を可能にするものであり、第１計算装置１００では図１に示した変換部１０４及び逆変換部１０５に用いられ、第２計算装置１１０では計算部１１４に用いられる。なお、第１計算装置１００のメモリ５０１又はＨＤＤ５０２は、システムパラメータとして前述の所定数Ｑ及びｎを記憶し、セキュリティパラメータとして後述する正の整数の所定数Ｒ，Ｓ，及びｐを記憶する。また、第２計算装置１１０のメモリ５０１又はＨＤＤ５０２は、システムパラメータとして前述の所定数Ｑ及びｎを記憶し、セキュリティパラメータとして後述する正の整数の所定数Ｓを記憶する。
【００２４】
次に、図３を用いてベクトル秘匿型内積計算システムの動作を説明する。図３は、第１実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【００２５】
図３に示すように、まず、第１計算装置１００の入力部１０１に前述のｎ次元ベクトルＶａが入力される（Ｓ２００）。
【００２６】
次に、乱数生成部１０２は、システムパラメータとして記憶する所定数Ｑ及びｎと、セキュリティパラメータとして記憶する所定数Ｒ，Ｓ及びｐとに対し、以下の式（２）〜（６）を満たすように、乱数Ｒj（ｊ＝１，２，…，ｎ）と、乱数Ｍi（ｉ＝１，２，…，ｐ）と、乱数Ｗi（ｉ＝１，２，…，ｐ）とを生成し、一時記憶部１０３に記憶する（Ｓ２０１）。
（数３）
Ｒ1，Ｒ2，…，Ｒn＜Ｒ …（２）
Ｍ1＞ｎＲＳＱ2 …（３）
Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ） …（４）
Ｗi＜Ｍi …（５）
ＧＣＤ（Ｗi，Ｍi）＝１ …（６）
【００２７】
ここで、ＧＣＤ（ａ，ｂ）は、ａ，ｂの最大公約数を表すものであり、式（６）を満たすためには、まず、乱数Ｍi，Ｍiをランダムに生成し、ユークリッドの互除法を用いてＧＣＤ（Ｍi，Ｍi）を計算し、これが１でない場合に、乱数Ｍi，Ｍiを再度生成する。
【００２８】
次に、変換部１０４は、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、以下の式（７）〜（９）を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を算出し、通信装置５０４により第２計算装置１１０に送信する（Ｓ２０２）。このように、Ｓ２０１の処理で生成された乱数Ｒj、Ｍi及びＷiを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒjで拡張（１次元変換）した上で、乱数Ｗiで線形変換し、乱数Ｍiで剰余を算出するので、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数４）
Ｘ1,j＝Ｒj・Ｑ＋Ａj …（７）
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す） …（８）
Ｘj＝Ｘp+1,j …（９）
【００２９】
本実施形態では、ｎ次元変換ベクトルＸからｎ次元ベクトルＶａを算出又は予測することを困難にして安全性を高めるために、式（７）によりｎ次元ベクトルＶａの各要素Ａjを拡張しているが、これに限定されず、高い安全性が要求されない場合や他の方法によって安全性を高めることができる場合には、ｎ次元ベクトルＶａの各要素Ａjを拡張しなくてもよい。また、同様の理由で、式（８）により剰余をｐ回算出しているが、所定数ｐは１であってもよい。この場合、Ｓ２０１の処理において、乱数生成部１０２は乱数Ｒjを生成せずに乱数Ｍ及びＷのみを生成し、Ｓ２０２の処理において、変換部１０４は以下の式（８）’を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を算出する。このように、Ｓ２０１の処理で生成された乱数Ｍ及びＷを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｗで線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数５）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ（ｊ＝１，２，…，ｎ） …（８）’
【００３０】
一方、第２計算装置１１０の入力部１１１に前述のｎ次元ベクトルＶｂが入力される（Ｓ２１０）。
【００３１】
次に、乱数生成部１１２は、以下の式（１０）を満たすように、乱数Ｓj（ｊ＝１，２，…，ｎ）を生成する（Ｓ２１１）。
（数６）
Ｓ1，Ｓ2，…，Ｓn＜Ｓ …（１０）
【００３２】
次に、拡張部１１３は、ｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、以下の式（１１）を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する（Ｓ２１２）。
（数７）
Ｙj＝Ｓj・Ｑ＋Ｂj …（１１）
【００３３】
なお、Ｓ２１０〜Ｓ２１２の処理は、前述のＳ２００〜Ｓ２０２の処理の前又は後、若しくは並行して行ってもよい。
【００３４】
次に、計算部１１４は、通信装置５０４により第１計算装置１００から変換ベクトルＸを受信し、以下の式（１２）を計算して内積値Ｚを通信装置５０４により第１計算装置１００に送信する（Ｓ２１３）。このように、Ｓ２１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、ｎ次元変換ベクトルＸとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数８）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn …（１２）
【００３５】
本実施形態では、前述と同様の理由で、式（１１）によりｎ次元ベクトルＶｂの各要素Ｂjを拡張しているが、これに限定されず、ｎ次元ベクトルＶｂの各要素Ｂjを拡張しなくてもよい。この場合、Ｓ２１１及びＳ２１２の処理は行わず、Ｓ２１０の処理の次に、Ｓ２１３の処理において、計算部１１４は以下の式（１２）’を計算して内積値Ｚを算出する。このように、ｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数９）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn …（１２）’
【００３６】
次に、第１計算装置１００の逆変換部１０５は、通信装置５０４により第２計算装置１１０から内積値Ｚを受信し、一時記憶部１０３に記憶された前述の乱数Ｍiと乱数Ｗiとを用いて以下の式（１３）〜（１５）を計算し、剰余Ｃを算出する（Ｓ２０３）。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１計算装置１００における計算は乱数Ｍiを法とする掛け算であり、第２計算装置１１０における計算はｎ回の掛け算と足し算となる。また、このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２）〜（１５）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
（数１０）
Ｚp+1＝Ｚ …（１３）
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す） …（１４）
Ｃ＝Ｚ1 ｍｏｄ Ｑ …（１５）
【００３７】
ここで、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）とｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、以下の式（１６）を満たすようにＱを設定すると、剰余Ｃはｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１１）
Ｑ＞ｎ・Ｎ2 …（１６）
【００３８】
本実施形態では、前述と同様の理由で、式（１４）により剰余をｐ回算出しているが、所定数ｐは１であってもよい。また、前述と同様の理由で、式（１５）により法Ｑの剰余を算出しているが、これに限定されず、法Ｑの剰余を算出しなくてもよい。この場合、Ｓ２０３の処理において、逆変換部１０５は以下の式（１４）’を計算して剰余Ｃを算出する。このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（８）’、（１２）’、（１４）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１２）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ …（１４）’
【００３９】
最後に、出力部１０６は剰余Ｃを出力する（Ｓ２０４）。
【００４０】
このように、本実施形態によれば、第１計算装置１００によって、乱数Ｗi（ｉ＝１，２，…，ｐ）に基づくスカラー値（１行１列の正則行列）と乱数Ｒj（ｊ＝１，２，…，ｎ）とに基づいてｎ次元ベクトルＶａがｎ個のスカラー値（１行ｎ列の行列）に線形変換され、線形変換した当該ｎ個のスカラー値（１行ｎ列の行列）に対して乱数Ｍi（ｉ＝１，２，…，ｐ）で除算した剰余が算出され、当該剰余を各要素とするｎ次元変換ベクトルＸ（１行ｎ列の変換行列）が通信装置５０４により送信される。また、第２計算装置１１０によって、通信装置５０４により受信したｎ次元変換ベクトルＸ（１行ｎ列の変換行列）とｎ次元ベクトルＶｂとに基づいて内積値Ｚ（１次元ベクトル）が算出され、当該内積値Ｚ（１次元ベクトル）が通信装置５０４により送信される。さらに、第１計算装置１００によって、スカラー値（１行１列の正則行列）の乱数Ｍi（ｉ＝１，２，…，ｐ）を法とした逆数（逆行列）と通信装置５０４によりにより受信した内積値Ｚ（１次元ベクトル）とに基づいてスカラー値（１次元ベクトル）が算出され、当該スカラー値（１次元ベクトル）に対して乱数Ｍi（ｉ＝１，２，…，ｐ）で除算した剰余Ｃが算出される。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１計算装置１００における計算は乱数Ｍiを法とする掛け算であり、第２計算装置１１０における計算はｎ回の掛け算と足し算となる。これにより、従来のような送受信とも２０４８×ｎビット以上の通信量や２０４８ビットの数を法とするべき乗計算を必要とせず、従来よりも小さい乱数Ｍiを法とし、べき乗計算よりも計算速度が数百分の一程度のかけ算や足し算で計算することができることから、従来よりも通信コスト及び計算コストを低減することができる。
【００４１】
また、Ｓ２０１の処理で生成された乱数Ｒj、Ｍi及びＷiを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒjで拡張（１次元変換）した上で、乱数Ｗiで線形変換し、乱数Ｍiで剰余を算出するので、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。Ｓ２１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、ｎ次元変換ベクトルＸとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２）〜（１５）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
【００４２】
また、Ｓ２０１の処理で生成された乱数Ｍ及びＷを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｗで線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。ｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（８）’、（１２）’、（１４）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００４３】
さらに、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）とｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、式（１６）を満たすようにＱを設定するので、剰余Ｃはｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００４４】
［第２実施形態］
図４は本発明の第２実施形態を示すものであり、同図は、第２実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【００４５】
第２実施形態と第１実施形態との相違点は、ｎ次元ベクトルＶａをｎ次元変換ベクトルＸに１次元変換することに代えて、ｎ次元ベクトルＶａを２行ｎ列の変換行列に２次元変換するようにしたことである。なお、本実施形態に係るベクトル秘匿型内積計算システムの機能構成及びハードウェア構成は、第１実施形態に示した図１及び図２と同様であるため、図示及びその説明を省略する。
【００４６】
まず、第１計算装置１００の入力部１０１に前述のｎ次元ベクトルＶａが入力される（Ｓ３００）。
【００４７】
次に、乱数生成部１０２は、以下の式（２０）〜（２４）を満たすように、乱数Ｒ1,j（ｊ＝１，２，…，ｎ）及びＲ2,j（ｊ＝１，２，…，ｎ）と、乱数Ｍと、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22とを生成する（Ｓ３０１）。
（数１３）
Ｒ1,j，Ｒ1,j，…，Ｒ1,n＜Ｒ …（２０）
Ｍ＞ｎＲＳＱ2 …（２１）
Ｒ2,j，Ｒ2,j，…，Ｒ2,n＜Ｍ …（２２）
Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ …（２３）
ＧＣＤ（Ｗ11・Ｗ22−Ｗ12，Ｗ21，Ｍ）＝１ …（２４）
【００４８】
ここで、式（２４）の条件を満たすためには、まずＭ，Ｗ11，Ｗ12，Ｗ21，Ｗ22をランダムに生成し、ユークリッドの互除法を用いてＧＣＤ（Ｗ11・Ｗ22−Ｗ12，Ｗ21，Ｍ）を計算し、これが１でない場合にＭ及びＷ11，Ｗ12，Ｗ21，Ｗ22を再度生成する。
【００４９】
次に、変換部１０４は、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、以下の式（２５）〜（２６）を計算して２行ｎ列の変換行列Ｘを算出し、通信装置５０４により第２計算装置１１０に送信する（Ｓ３０２）。このように、Ｓ３０１の処理で生成された乱数Ｒ1,j、Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22を用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒ1,jで拡張（１次元変換）した上で、乱数Ｒ2,jで２次元に拡張し、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22に基づく２行２列の行列で線形変換し、乱数Ｍで剰余を算出するので、第２計算装置１１０は送信された２行ｎ列の変換行列Ｘからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数１４）
【００５０】
本実施形態では、前述と同様の理由で、式（２５）によりｎ次元ベクトルＶａの各要素Ａjを拡張しているが、第１実施形態と同様に、ｎ次元ベクトルＶａの各要素Ａjを拡張しなくてもよい。この場合、Ｓ３０１の処理において、乱数生成部１０２はＲ1,jを生成せずに乱数Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22のみを生成し、Ｓ３０２の処理において、変換部１０４は以下の式（２６）’を計算して２行ｎ列の変換行列Ｘを算出する。このように、Ｓ３０１の処理で生成された乱数Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒ2,jで２次元に拡張し、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22に基づく２行２列の行列で線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信された２行ｎ列の変換行列Ｘからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数１５）
【００５１】
一方、第２計算装置１１０の入力部１１１にｎ次元ベクトルＶｂが入力される（Ｓ３１０）。
【００５２】
次に、乱数生成部１１２は、前述の式（１０）を満たすように、乱数Ｓj（ｊ＝１，２，…，ｎ）を生成する（Ｓ３１１）。
【００５３】
次に、拡張部１１３は、ｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、前述の式（１１）を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する（Ｓ３１２）。
【００５４】
なお、Ｓ３１０〜Ｓ３１２の処理は、前述のＳ３００〜Ｓ３０２の処理の前又は後、若しくは並行して行ってもよい。
【００５５】
次に、計算部１１４は、通信装置５０４により第１計算装置１００から２行ｎ列の変換行列Ｘを受信し、以下の式（２７）を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を通信装置５０４により第１計算装置１００に送信する（Ｓ３１３）。このように、Ｓ３１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、２行ｎ列の変換行列Ｘとの積である２次元ベクトルＺを算出するので、第１計算装置１００は送信された２次元ベクトルＺからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数１６）
【００５６】
本実施形態では、前述と同様の理由で、式（１１）によりｎ次元ベクトルＶｂの各要素Ｂjを拡張しているが、第１実施形態と同様に、ｎ次元ベクトルＶｂの各要素Ｂjを拡張しなくてもよい。この場合、Ｓ３１１及びＳ３１２の処理は行わず、Ｓ３１０の処理の次に、Ｓ２１３の処理において、計算部１１４は以下の式（２７）’を計算して２次元ベクトルＺを算出する。このように、２行ｎ列の変換行列Ｘとｎ次元ベクトルＶｂとの積である２次元ベクトルＺを算出するので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された２次元ベクトルＺからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数１７）
【００５７】
次に、第１計算装置１００の逆変換部１０５は、通信装置５０４により第２計算装置１１０から２次元ベクトルＺを受信し、一時記憶部１０３に記憶された前述の乱数Ｍと乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22とを用いて以下の式（２８）及び（２９）を計算し、剰余Ｃを算出する（Ｓ３０３）。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも２×１００×ｎビット程度となり、第１計算装置１００及び第２計算装置１１０における計算はそれぞれｎ回の掛け算と足し算の数倍程度となる。また、このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２０）〜（２９）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
（数１８）
【００５８】
ここで、第１実施形態と同様に、前述の式（１６）を満たすようにＱを設定すると、剰余Ｃは内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００５９】
本実施形態では、前述と同様の理由で、式（２９）により法Ｑの剰余を算出しているが、第１実施形態と同様に、法Ｑの剰余を算出しなくてもよい。この場合、Ｓ３０３の処理において、逆変換部１０５は式（２８）及び以下の式（２９）’を計算して剰余Ｃを算出する。このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２６）’、（２７）’、（２８）、（２９）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１９）
Ｃ＝Ｃ1 …（２９）’
【００６０】
最後に、出力部１０６は剰余Ｃを出力する（Ｓ３０４）。
【００６１】
このように、本実施形態によれば、ｎ次元ベクトルＶａを２行ｎ列の変換行列に２次元変換する場合であっても、第１実施形態と同様の効果を得ることができるとともに、多少の計算コストを犠牲にして更に安全性を高めることができる。
【００６２】
また、ｎ次元ベクトルＶａをｍ行ｎ列の変換行列（ｍは３以上の整数）にｍ次元変換する場合であっても、本実施形態と同様の効果を得ることができる。
【００６３】
［第３実施形態］
従来、暗号通信における暗号鍵共有プロトコルである、前述の非特許文献３及び４に記載された方法は、量子計算機によって破られることが判明している。これは、現在のコンピュータでは困難とされている素因数分解問題や離散対数問題が、量子計算機では容易に解けるためである。このため、将来的に量子計算機が実現されたとしても安全性を確保できるように、素因数分解問題や離散対数問題に依存しない新しい暗号鍵共有システムが必要とされる。
【００６４】
本発明の第３実施形態に係る暗号鍵共有システムは、前記問題点に鑑みてなされたものであり、その目的とするところは、量子計算機に対しても耐性を有する暗号鍵共有システムを提供することにある。
【００６５】
図５は本発明の第３実施形態を示すものであり、同図は、暗号鍵共有システムの機能構成を説明する概略構成図である。なお、鍵共有システムのハードウェア構成は、第１実施形態に示した図２と同様であるため、図示及びその説明を省略する。
【００６６】
図５に示すように、暗号鍵共有システム１０は、第１鍵共有装置４００と、第２鍵共有装置４１０とを備え、第１鍵共有装置４００と第２鍵共有装置４１０とは、ネットワークＮ２を介して互いに接続される。
【００６７】
第１鍵共有装置４００は、内積計算部Ａ４０１と、ベクトル生成部４０２と、内積計算部Ｂ４０３と、ハッシュ関数部４０４と、出力部４０５とから構成される。内積計算部Ａ401は、第１実施形態又は第２実施形態における第１計算装置１００と同一の機能、すなわち、入力部１０１、乱数生成部１０２、一時記憶部１０３、変換部１０４、逆変換部１０５及び出力部１０６を有する。内積計算部Ｂ４０３は、第１実施形態又は第２実施形態における第２計算装置１１０と同一の機能、すなわち、入力部１１１、乱数生成部１１２、拡張部１１３及び計算部１１４を有する。ベクトル生成部４０２は、前述のｎ次元ベクトルＶａを生成する。ハッシュ関数部４０４は、例えばＳＨＡ−１やＳＨＡ−２５６といったアルゴリズムに従い、入力値に対するハッシュ値を計算する。出力部４０５は、後述する共通鍵を出力する。
【００６８】
第２鍵共有装置４１０は、内積計算部Ｂ４１１と、ベクトル生成部４１２と、内積計算部Ａ４１３と、ハッシュ関数部４１４と、出力部４１５とから構成される。内積計算部Ｂ４１１は内積計算部Ｂ４０３と同一であり、ベクトル生成部４１２は前述のｎ次元ベクトルＶｂを生成する。内積計算部Ａ４１３は内積計算部Ａ４０１と同一であり、ハッシュ関数部４１４はハッシュ関数部４０４と同一であり、出力部４１５は、後述する共通鍵を出力する。
【００６９】
次に、暗号鍵共有システム１０の動作について説明する。
【００７０】
まず、第１鍵共有装置４００のベクトル生成部４０２は、前述のｎ次元ベクトルＶａをランダムに生成し、内積計算部Ａ４０１及び内積計算部Ｂ４０３に出力する。
【００７１】
一方、第２鍵共有装置４１０のベクトル生成部４１２は、前述のｎ次元ベクトルＶｂをランダムに生成し、内積計算部Ｂ４１１及び内積計算部Ａ４１３に出力する。
【００７２】
第１鍵共有装置４００の内積計算部Ａ４０１と第２鍵共有装置４１０の内積計算部Ｂ４１１とが通信し、内積計算部Ａ４０１は内積値Ｃ＝Ｖａ・Ｖｂを算出し、ハッシュ関数部４０４に出力する。なお、内積値Ｃの計算方法は、前述の第１実施形態又は第２実施形態と同様とする。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第１鍵共有装置４００が内積値Ｃを算出することができる。
【００７３】
同様に、第２鍵共有装置４１０の内積計算部Ａ４１３と第１鍵共有装置４００の内積計算部Ｂ４０３とが通信し、内積計算部Ａ４１３は内積値Ｃ＝Ｖａ・Ｖｂを算出し、ハッシュ関数部４１４に出力する。なお、内積計算の方法は、前述の第１実施形態又は第２実施形態と同様とする。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第２鍵共有装置４１０が内積値Ｃを算出することができる。
【００７４】
第１鍵共有装置４００のハッシュ関数部４０４は、入力された内積値Ｃのハッシュ値Ｋを算出し、出力部４０５はハッシュ値Ｋを共通鍵として出力する。これにより、素因数分解問題や離散対数問題の計算量的困難性に依存しない共通鍵（暗号鍵）を生成することができる。
【００７５】
同様に、第２鍵共有装置４１０のハッシュ関数部４１４は、入力された内積値Ｃのハッシュ値Ｋを算出し、出力部４１５はハッシュ値Ｋを共通鍵として出力する。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０はハッシュ値Ｋを共通鍵として共有することができる。
【００７６】
本実施形態では、計算した内積値Ｃのハッシュ値Ｋを共通鍵としているが、これに限定されず、他の方法で共通鍵を生成するようにしてもよいし、内積値Ｃそのものを共通鍵としてもよい。
【００７７】
このように、この暗号鍵共有システム１０によれば、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第１鍵共有装置４００が内積値Ｃを算出することができ、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第２鍵共有装置４１０が内積値Ｃを算出することができるので、第１鍵共有装置４００及び第２鍵共有装置４１０間の通信を全て盗聴されたとしても、ｎ次元ベクトルＶａ，Ｖｂが秘匿されるから、盗聴者は内積値Ｃ及びそのハッシュ値Ｋを知ることができない。これにより、共通鍵を安全に（盗聴者には計算できないように）共有することができる。また、前述の第１実施形態又は第２実施形態の方法で内積値Ｃを算出し、当該内積値Ｃ又は当該内積値Ｃのハッシュ値を共通鍵として出力するので、素因数分解問題や離散対数問題の計算量的困難性に依存しない共通鍵（暗号鍵）を生成することができる。これにより、量子計算機に対しても耐性を有する。
【００７８】
なお、本発明の構成は、前記実施形態にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加えてもよい。
【図面の簡単な説明】
【００７９】
【図１】ベクトル秘匿型内積計算システムの機能構成を説明する概略構成図である。
【図２】図１に示した第１計算装置及び第２計算装置のハードウェア構成を説明する概略構成図である。
【図３】ベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【図４】第２実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【図５】暗号鍵共有システムの機能構成を説明する概略構成図である。
【符号の説明】
【００８０】
１…ベクトル秘匿型内積計算システム、１０…暗号鍵共有システム、１００…第１計算装置、１０１…入力部、１０２…乱数生成部、１０３…一時記憶部、１０４…変換部、１０５…逆変換部、１１０…第２計算装置、１１１…入力部、１１２…乱数生成部、１１３…拡張部、１１４…計算部、４００…第１鍵共有装置、４０１…内積計算部Ａ、４０２…ベクトル生成部、４０３…内積計算部Ｂ、４０４…ハッシュ関数部、４０５…出力部、４１０…第２鍵共有装置、４１１…内積計算部Ｂ、４１２…ベクトル生成部、４１３…内積計算部Ａ、４１４…ハッシュ計算部、４１５…出力部。
【技術分野】
【０００１】
本発明は、２者間で互いにベクトルを秘匿したまま内積を計算可能なベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法及び暗号鍵共有システムに関する。
【背景技術】
【０００２】
複数のパーティーに分散されたデータを、それぞれのパーティーが秘密にしたまま、協力して様々な計算を行うプロトコル（マルチパーティープロトコル）が盛んに研究されている。マルチパーティープロトコルは、電子投票や電子契約、プライバシーを保護したデータマイニングなど、様々な分野への応用が考えられている。こうした様々な応用プロトコルを実現するための基本的なプロトコルとして、ベクトルの内積計算プロトコルがある。これは、２者（AliceとBob）がそれぞれ秘密のベクトルＶａ、Ｖｂを保持している状態で、互いに秘密ベクトルを明かすことなく、Aliceが内積値Ｖａ・Ｖｂを計算するプロトコルである。
【０００３】
内積計算プロトコルの実現方法としては、暗号化関数が準同型性を持つ公開鍵暗号であるPaillier暗号（例えば、非特許文献２参照）を利用する方法が知られている（例えば、非特許文献１参照）。具体的には以下の通りである。
【０００４】
まずAliceが秘密鍵と公開鍵のペアを生成し、自分の秘密ベクトルＶａ＝（ａ1，ａ2，…，ａn）の各要素を公開鍵により暗号化して、暗号文 Ｅ（ａ1），Ｅ（ａ2），…，Ｅ（ａn）をBobに送信する（Ｅ(・)は暗号化関数とする）。Bobはこれらの暗号文を受信し、自分の秘密ベクトルＶｂ＝（ｂ1，ｂ2，…，ｂn）を用いて、Ｅ(・)の準同型性を利用し、以下のように内積値の暗号文を計算する。
（数１）
ｅ＝（Ｅ（ａ1）b1）×（Ｅ（ａ2）b2）×…×（Ｅ（ａn）bn） ｍｏｄ Ｍ
＝Ｅ（ａ1×ｂ1＋ａ2×ｂ2＋…＋ａn×ｂn）
＝Ｅ（Ｖａ・Ｖｂ）
但し、Ｍは、例えば２０４８ビットの整数である。BobはAliceにｅを送り返す。Aliceは秘密鍵を用いてｅを復号化し、内積値Ｖａ・Ｖｂを得る。
【０００５】
一方、暗号化通信に不可欠な、暗号鍵の共有方法（鍵共有プロトコル）として、素因数分解問題の困難性に安全性の根拠を置くRSA暗号（例えば、非特許文献３参照）に基づく方式や、離散対数問題に基づくDiffie-Hellman鍵共有の方法（例えば、非特許文献４参照）が知られている。
【非特許文献１】Bart Goethals, Sven Laur, Helger Lipmaa and Taneli Mielika"inen. "On Private Scalar Product Computation for Privacy-Preserving Data Mining", The 7th Annual International Conference in Information Security and Cryptology(ICISC2004), vol. 3506 of Lecture Notes in Computer Science, pages 104-120(2004).
【非特許文献２】Pascal Paillier. "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes", In Jacques Stern, editor, Advances in Cryptology EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 223−238, Prague, Czech Republic, 2−6 May 1999. Springer-Verlag.
【非特許文献３】R.L.Rivest, A.Shamir, and L.Adelman, "Method for Obtaining Digital Signature and Public-key Cryptsystems", Communications of the ACM, Vol. 21 (2), pp.120−126. 1978.
【非特許文献４】W. Diffie and M. E. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, vol.IT-22, No.6, pp.644-654, Nov, 1976.
【発明の開示】
【発明が解決しようとする課題】
【０００６】
ベクトルの内積計算プロトコルである非特許文献１に記載の方法は、非特許文献２に記載のPaillier暗号を利用している。しかしながら、従来の方法では、通信コストと計算コストが大きいという問題がある。
【０００７】
実際、Paillier暗号において推奨されている鍵長では、暗号文のサイズが２０４８ビットであり、ベクトルがn次元の場合、通信量は ２０４８×ｎビット以上となる。また暗号化、復号化の計算では、巨大な整数を法としたべき乗計算をnに比例した回数実行する必要があり、計算コストが大きい。特に、扱うベクトルの次元nが大きい場合や、内積計算処理を頻繁に行うシステム（巨大なＤＢを対象としたデータマイニングなど）では、通信コスト、計算コストの削減が必要となるという問題点があった。
【０００８】
本発明は前記問題点に鑑みてなされたものであり、その目的とするところは、通信コスト及び計算コストを低減することのできるベクトル秘匿型内積計算システム、ベクトル秘匿型内積計算方法及び暗号鍵共有システムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明は前記目的を達成するために、各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを備えるベクトル秘匿型内積計算システムにおいて、前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部と、整数である第１、第２及び第３の乱数を生成する第１生成部と、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換部とを有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部と、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算部とを有し、前記第１の計算装置は、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換部をさらに有するベクトル秘匿型内積計算システムを提案する。
【００１０】
また、本発明は前記目的を達成するために、各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを有するシステムに用いられるベクトル秘匿型内積計算方法であって、前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部を有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部を有しており、前記第１の計算装置により、整数である第１、第２及び第３の乱数を生成する第１生成ステップと、前記第１の計算装置により、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換ステップと、前記第２の計算装置により、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算ステップと、前記第１の計算装置により、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換ステップとを備えるベクトル秘匿型内積計算方法を提案する。
【００１１】
本発明によれば、第１の計算装置によって、第１の乱数に基づくｍ行ｍ列の正則行列と第２の乱数とに基づいて第１のｎ次元ベクトルがｍ行ｎ列の行列に線形変換され、線形変換した当該ｍ行ｎ列の行列における各要素に対して第３の乱数で除算した剰余が算出され、当該剰余を各要素とするｍ行ｎ列の変換行列が第１通信部により送信される。また、第２の計算装置によって、第２通信部により受信したｍ行ｎ列の変換行列と第２のｎ次元ベクトルとに基づいてｍ次元ベクトルが算出され、当該ｍ次元ベクトルが第２通信部により送信される。さらに、第１の計算装置によって、ｍ行ｍ列の正則行列の第３の乱数を法とした逆行列と第１通信部により受信したｍ次元ベクトルとに基づいてｍ次元ベクトルが算出され、当該ｍ次元ベクトルにおける所定の要素に対して第３の乱数で除算した剰余が算出される。これにより、従来と同程度の安全性を確保できるものとして、例えばｍ＝１、第１及び第３の乱数が１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１の計算装置における計算は第３の乱数を法とする掛け算であり、第２の計算装置における計算はｎ回の掛け算と足し算となる。
【発明の効果】
【００１２】
本発明によれば、従来と同程度の安全性を確保できるものとして、例えばｍ＝１、第１及び第３の乱数が１００ビットの整数である場合、通信量は第１計算装置から第２計算装置への送受信が１００×ｎビットで第２計算装置から第１計算装置への送受信が１００ビット程度となり、第１の計算装置における計算は第３の乱数を法とする掛け算であり、第２の計算装置における計算はｎ回の掛け算と足し算となる。これにより、従来のような送受信とも２０４８×ｎビット以上の通信量や２０４８ビットの数を法とするべき乗計算を必要とせず、従来よりも小さい法を用いることができ、かけ算や足し算はべき乗計算よりも計算コストが数百分の一程度でありことから、従来よりも通信コスト及び計算コストを低減することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照しながら本発明の一実施の形態を詳述する。
【００１４】
［第１実施形態］
図１乃至図３は本発明の第１実施形態を示すものである。まず、図１及び図２を用いてベクトル秘匿型内積計算システムの構成を説明する。図１は、ベクトル秘匿型内積計算システムの機能構成を説明する概略構成図である。
【００１５】
図１に示すように、ベクトル秘匿型内積計算システム１は、各要素が整数であるｎ次元ベクトルＶａ＝（Ａ1，Ａ2，…，Ａn）（ｎは正の整数）を秘匿する第１計算装置１００と、各要素が整数であるｎ次元ベクトルＶｂ＝（Ｂ1，Ｂ2，…，Ｂn）を秘匿する第２計算装置１１０とを備え、正の整数である所定数Ｑが設定される第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら通信し、第１計算装置１００が以下の式（１）で計算される剰余Ｃを算出するためのものである。
（数２）
Ｃ＝Ｖａ・Ｖｂ ｍｏｄ Ｑ
＝Ａ1Ｂ1＋Ａ2Ｂ2＋…＋ＡnＢn ｍｏｄ Ｑ …（１）
【００１６】
第１計算装置１００と第２計算装置１１０とは、ネットワークＮ１を介して互いに接続される。第１計算装置１００は、入力部１０１と、乱数生成部１０２と、一時記憶部１０３と、変換部１０４と、逆変換部１０５と、出力部１０６とから構成される。
【００１７】
入力部１０１は、前述のｎ次元ベクトルＶａが入力される。乱数生成部１０２は、後述する、整数の乱数を生成する。一時記憶部１０３は生成した乱数を一時的に記憶する。変換部１０４は、生成した乱数を用いてｎ次元ベクトルＶａの各要素値を変換して変換ベクトルＸを作成し、第２計算装置１１０に送信する。逆変換部１０５は、第２計算装置１１０から送信される後述の内積値Ｚを受信し、生成した乱数と受信した内積値Ｚとから剰余Ｃを算出する。出力部１０６は、算出された剰余Ｃを出力する。
【００１８】
第２計算装置１１０は、入力部１１１と、乱数生成部１１２と、拡張部１１３と、計算部１１４とから構成される。
【００１９】
入力部１１１は、前述のｎ次元ベクトルＶｂが入力される。乱数生成部１０２は、後述する、整数の乱数を生成する。拡張部１１３は後述するｎ次元拡張ベクトルＹを作成する。計算部１０４は、第１計算装置１００から送信されるｎ次元変換ベクトルＸを受信し、受信したｎ次元変換ベクトルＸとｎ次元拡張ベクトルＹとの内積値Ｚを計算して第１計算装置１００に送信する。
【００２０】
本実施形態では、第１計算装置１００の入力部１０１にｎ次元ベクトルＶａが入力され、第２計算装置１１０の入力部１１１にｎ次元ベクトルＶｂが入力されるが、これに限定されず、第１計算装置１００がｎ次元ベクトルＶａを生成し、第２計算装置１１０がｎ次元ベクトルＶｂを生成するようにしてもよい。
【００２１】
図２は、図１に示した第１計算装置及び第２計算装置のハードウェア構成を説明する概略構成図である。
【００２２】
図２に示すように、第１計算装置１００及び第２計算装置１１０は、それぞれＣＰＵ５００と、メモリ５０１と、ＨＤＤ５０２と、入出力装置５０３と、通信装置５０４とから構成され、ＣＰＵ５００、メモリ５０１、ＨＤＤ５０２、入出力装置５０３、及び通信装置５０４は、内部バス５０５を介して互いに接続される。
【００２３】
ＣＰＵ５００は、第１計算装置１００では図１に示した乱数生成部１０２、変換部１０４及び逆変換部１０５に対応し、第２計算装置１１０では乱数生成部１１２、拡張部１１３及び計算部１１４に対応する。メモリ５０１又はＨＤＤ５０２は、図１に示した一時記憶部１０３に対応する。入出力装置５０３は、第１計算装置１００では図１に示した入力部１０１及び出力部１０６に対応し、第２計算装置１１０では入力部１１１に対応する。通信計算装置５０４は、第１計算装置１００と第２計算装置１１０との間で情報の送受信を可能にするものであり、第１計算装置１００では図１に示した変換部１０４及び逆変換部１０５に用いられ、第２計算装置１１０では計算部１１４に用いられる。なお、第１計算装置１００のメモリ５０１又はＨＤＤ５０２は、システムパラメータとして前述の所定数Ｑ及びｎを記憶し、セキュリティパラメータとして後述する正の整数の所定数Ｒ，Ｓ，及びｐを記憶する。また、第２計算装置１１０のメモリ５０１又はＨＤＤ５０２は、システムパラメータとして前述の所定数Ｑ及びｎを記憶し、セキュリティパラメータとして後述する正の整数の所定数Ｓを記憶する。
【００２４】
次に、図３を用いてベクトル秘匿型内積計算システムの動作を説明する。図３は、第１実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【００２５】
図３に示すように、まず、第１計算装置１００の入力部１０１に前述のｎ次元ベクトルＶａが入力される（Ｓ２００）。
【００２６】
次に、乱数生成部１０２は、システムパラメータとして記憶する所定数Ｑ及びｎと、セキュリティパラメータとして記憶する所定数Ｒ，Ｓ及びｐとに対し、以下の式（２）〜（６）を満たすように、乱数Ｒj（ｊ＝１，２，…，ｎ）と、乱数Ｍi（ｉ＝１，２，…，ｐ）と、乱数Ｗi（ｉ＝１，２，…，ｐ）とを生成し、一時記憶部１０３に記憶する（Ｓ２０１）。
（数３）
Ｒ1，Ｒ2，…，Ｒn＜Ｒ …（２）
Ｍ1＞ｎＲＳＱ2 …（３）
Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ） …（４）
Ｗi＜Ｍi …（５）
ＧＣＤ（Ｗi，Ｍi）＝１ …（６）
【００２７】
ここで、ＧＣＤ（ａ，ｂ）は、ａ，ｂの最大公約数を表すものであり、式（６）を満たすためには、まず、乱数Ｍi，Ｍiをランダムに生成し、ユークリッドの互除法を用いてＧＣＤ（Ｍi，Ｍi）を計算し、これが１でない場合に、乱数Ｍi，Ｍiを再度生成する。
【００２８】
次に、変換部１０４は、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、以下の式（７）〜（９）を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を算出し、通信装置５０４により第２計算装置１１０に送信する（Ｓ２０２）。このように、Ｓ２０１の処理で生成された乱数Ｒj、Ｍi及びＷiを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒjで拡張（１次元変換）した上で、乱数Ｗiで線形変換し、乱数Ｍiで剰余を算出するので、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数４）
Ｘ1,j＝Ｒj・Ｑ＋Ａj …（７）
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す） …（８）
Ｘj＝Ｘp+1,j …（９）
【００２９】
本実施形態では、ｎ次元変換ベクトルＸからｎ次元ベクトルＶａを算出又は予測することを困難にして安全性を高めるために、式（７）によりｎ次元ベクトルＶａの各要素Ａjを拡張しているが、これに限定されず、高い安全性が要求されない場合や他の方法によって安全性を高めることができる場合には、ｎ次元ベクトルＶａの各要素Ａjを拡張しなくてもよい。また、同様の理由で、式（８）により剰余をｐ回算出しているが、所定数ｐは１であってもよい。この場合、Ｓ２０１の処理において、乱数生成部１０２は乱数Ｒjを生成せずに乱数Ｍ及びＷのみを生成し、Ｓ２０２の処理において、変換部１０４は以下の式（８）’を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を算出する。このように、Ｓ２０１の処理で生成された乱数Ｍ及びＷを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｗで線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数５）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ（ｊ＝１，２，…，ｎ） …（８）’
【００３０】
一方、第２計算装置１１０の入力部１１１に前述のｎ次元ベクトルＶｂが入力される（Ｓ２１０）。
【００３１】
次に、乱数生成部１１２は、以下の式（１０）を満たすように、乱数Ｓj（ｊ＝１，２，…，ｎ）を生成する（Ｓ２１１）。
（数６）
Ｓ1，Ｓ2，…，Ｓn＜Ｓ …（１０）
【００３２】
次に、拡張部１１３は、ｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、以下の式（１１）を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する（Ｓ２１２）。
（数７）
Ｙj＝Ｓj・Ｑ＋Ｂj …（１１）
【００３３】
なお、Ｓ２１０〜Ｓ２１２の処理は、前述のＳ２００〜Ｓ２０２の処理の前又は後、若しくは並行して行ってもよい。
【００３４】
次に、計算部１１４は、通信装置５０４により第１計算装置１００から変換ベクトルＸを受信し、以下の式（１２）を計算して内積値Ｚを通信装置５０４により第１計算装置１００に送信する（Ｓ２１３）。このように、Ｓ２１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、ｎ次元変換ベクトルＸとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数８）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn …（１２）
【００３５】
本実施形態では、前述と同様の理由で、式（１１）によりｎ次元ベクトルＶｂの各要素Ｂjを拡張しているが、これに限定されず、ｎ次元ベクトルＶｂの各要素Ｂjを拡張しなくてもよい。この場合、Ｓ２１１及びＳ２１２の処理は行わず、Ｓ２１０の処理の次に、Ｓ２１３の処理において、計算部１１４は以下の式（１２）’を計算して内積値Ｚを算出する。このように、ｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数９）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn …（１２）’
【００３６】
次に、第１計算装置１００の逆変換部１０５は、通信装置５０４により第２計算装置１１０から内積値Ｚを受信し、一時記憶部１０３に記憶された前述の乱数Ｍiと乱数Ｗiとを用いて以下の式（１３）〜（１５）を計算し、剰余Ｃを算出する（Ｓ２０３）。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１計算装置１００における計算は乱数Ｍiを法とする掛け算であり、第２計算装置１１０における計算はｎ回の掛け算と足し算となる。また、このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２）〜（１５）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
（数１０）
Ｚp+1＝Ｚ …（１３）
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す） …（１４）
Ｃ＝Ｚ1 ｍｏｄ Ｑ …（１５）
【００３７】
ここで、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）とｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、以下の式（１６）を満たすようにＱを設定すると、剰余Ｃはｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１１）
Ｑ＞ｎ・Ｎ2 …（１６）
【００３８】
本実施形態では、前述と同様の理由で、式（１４）により剰余をｐ回算出しているが、所定数ｐは１であってもよい。また、前述と同様の理由で、式（１５）により法Ｑの剰余を算出しているが、これに限定されず、法Ｑの剰余を算出しなくてもよい。この場合、Ｓ２０３の処理において、逆変換部１０５は以下の式（１４）’を計算して剰余Ｃを算出する。このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（８）’、（１２）’、（１４）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１２）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ …（１４）’
【００３９】
最後に、出力部１０６は剰余Ｃを出力する（Ｓ２０４）。
【００４０】
このように、本実施形態によれば、第１計算装置１００によって、乱数Ｗi（ｉ＝１，２，…，ｐ）に基づくスカラー値（１行１列の正則行列）と乱数Ｒj（ｊ＝１，２，…，ｎ）とに基づいてｎ次元ベクトルＶａがｎ個のスカラー値（１行ｎ列の行列）に線形変換され、線形変換した当該ｎ個のスカラー値（１行ｎ列の行列）に対して乱数Ｍi（ｉ＝１，２，…，ｐ）で除算した剰余が算出され、当該剰余を各要素とするｎ次元変換ベクトルＸ（１行ｎ列の変換行列）が通信装置５０４により送信される。また、第２計算装置１１０によって、通信装置５０４により受信したｎ次元変換ベクトルＸ（１行ｎ列の変換行列）とｎ次元ベクトルＶｂとに基づいて内積値Ｚ（１次元ベクトル）が算出され、当該内積値Ｚ（１次元ベクトル）が通信装置５０４により送信される。さらに、第１計算装置１００によって、スカラー値（１行１列の正則行列）の乱数Ｍi（ｉ＝１，２，…，ｐ）を法とした逆数（逆行列）と通信装置５０４によりにより受信した内積値Ｚ（１次元ベクトル）とに基づいてスカラー値（１次元ベクトル）が算出され、当該スカラー値（１次元ベクトル）に対して乱数Ｍi（ｉ＝１，２，…，ｐ）で除算した剰余Ｃが算出される。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも１００×ｎビット程度となり、第１計算装置１００における計算は乱数Ｍiを法とする掛け算であり、第２計算装置１１０における計算はｎ回の掛け算と足し算となる。これにより、従来のような送受信とも２０４８×ｎビット以上の通信量や２０４８ビットの数を法とするべき乗計算を必要とせず、従来よりも小さい乱数Ｍiを法とし、べき乗計算よりも計算速度が数百分の一程度のかけ算や足し算で計算することができることから、従来よりも通信コスト及び計算コストを低減することができる。
【００４１】
また、Ｓ２０１の処理で生成された乱数Ｒj、Ｍi及びＷiを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒjで拡張（１次元変換）した上で、乱数Ｗiで線形変換し、乱数Ｍiで剰余を算出するので、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。Ｓ２１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、ｎ次元変換ベクトルＸとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２）〜（１５）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
【００４２】
また、Ｓ２０１の処理で生成された乱数Ｍ及びＷを用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｗで線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信されたｎ次元変換ベクトルＸからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。ｎ次元変換ベクトルＸとｎ次元ベクトルＶｂとの内積値Ｚを算出し、算出された内積値Ｚはスカラー値（１次元ベクトル）であるので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された内積値Ｚからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（８）’、（１２）’、（１４）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００４３】
さらに、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）とｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、式（１６）を満たすようにＱを設定するので、剰余Ｃはｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００４４】
［第２実施形態］
図４は本発明の第２実施形態を示すものであり、同図は、第２実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【００４５】
第２実施形態と第１実施形態との相違点は、ｎ次元ベクトルＶａをｎ次元変換ベクトルＸに１次元変換することに代えて、ｎ次元ベクトルＶａを２行ｎ列の変換行列に２次元変換するようにしたことである。なお、本実施形態に係るベクトル秘匿型内積計算システムの機能構成及びハードウェア構成は、第１実施形態に示した図１及び図２と同様であるため、図示及びその説明を省略する。
【００４６】
まず、第１計算装置１００の入力部１０１に前述のｎ次元ベクトルＶａが入力される（Ｓ３００）。
【００４７】
次に、乱数生成部１０２は、以下の式（２０）〜（２４）を満たすように、乱数Ｒ1,j（ｊ＝１，２，…，ｎ）及びＲ2,j（ｊ＝１，２，…，ｎ）と、乱数Ｍと、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22とを生成する（Ｓ３０１）。
（数１３）
Ｒ1,j，Ｒ1,j，…，Ｒ1,n＜Ｒ …（２０）
Ｍ＞ｎＲＳＱ2 …（２１）
Ｒ2,j，Ｒ2,j，…，Ｒ2,n＜Ｍ …（２２）
Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ …（２３）
ＧＣＤ（Ｗ11・Ｗ22−Ｗ12，Ｗ21，Ｍ）＝１ …（２４）
【００４８】
ここで、式（２４）の条件を満たすためには、まずＭ，Ｗ11，Ｗ12，Ｗ21，Ｗ22をランダムに生成し、ユークリッドの互除法を用いてＧＣＤ（Ｗ11・Ｗ22−Ｗ12，Ｗ21，Ｍ）を計算し、これが１でない場合にＭ及びＷ11，Ｗ12，Ｗ21，Ｗ22を再度生成する。
【００４９】
次に、変換部１０４は、ｎ次元ベクトルＶａの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、以下の式（２５）〜（２６）を計算して２行ｎ列の変換行列Ｘを算出し、通信装置５０４により第２計算装置１１０に送信する（Ｓ３０２）。このように、Ｓ３０１の処理で生成された乱数Ｒ1,j、Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22を用い、ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒ1,jで拡張（１次元変換）した上で、乱数Ｒ2,jで２次元に拡張し、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22に基づく２行２列の行列で線形変換し、乱数Ｍで剰余を算出するので、第２計算装置１１０は送信された２行ｎ列の変換行列Ｘからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数１４）
【００５０】
本実施形態では、前述と同様の理由で、式（２５）によりｎ次元ベクトルＶａの各要素Ａjを拡張しているが、第１実施形態と同様に、ｎ次元ベクトルＶａの各要素Ａjを拡張しなくてもよい。この場合、Ｓ３０１の処理において、乱数生成部１０２はＲ1,jを生成せずに乱数Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22のみを生成し、Ｓ３０２の処理において、変換部１０４は以下の式（２６）’を計算して２行ｎ列の変換行列Ｘを算出する。このように、Ｓ３０１の処理で生成された乱数Ｒ2,j、Ｍ及びＷ11，Ｗ12，Ｗ21，Ｗ22ｎ次元ベクトルＶａの各要素Ａjに対し、乱数Ｒ2,jで２次元に拡張し、乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22に基づく２行２列の行列で線形変換し、乱数Ｍで剰余を算出するので、各要素Ａjを拡張（１次元変換）しなくても、第２計算装置１１０は送信された２行ｎ列の変換行列Ｘからｎ次元ベクトルＶａを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶａが秘匿される。
（数１５）
【００５１】
一方、第２計算装置１１０の入力部１１１にｎ次元ベクトルＶｂが入力される（Ｓ３１０）。
【００５２】
次に、乱数生成部１１２は、前述の式（１０）を満たすように、乱数Ｓj（ｊ＝１，２，…，ｎ）を生成する（Ｓ３１１）。
【００５３】
次に、拡張部１１３は、ｎ次元ベクトルＶｂの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、前述の式（１１）を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する（Ｓ３１２）。
【００５４】
なお、Ｓ３１０〜Ｓ３１２の処理は、前述のＳ３００〜Ｓ３０２の処理の前又は後、若しくは並行して行ってもよい。
【００５５】
次に、計算部１１４は、通信装置５０４により第１計算装置１００から２行ｎ列の変換行列Ｘを受信し、以下の式（２７）を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を通信装置５０４により第１計算装置１００に送信する（Ｓ３１３）。このように、Ｓ３１１の処理で生成された乱数Ｓjを用い、ｎ次元ベクトルＶｂの各要素Ｂjに対し、乱数Ｓjで拡張（１次元変換）した上で、２行ｎ列の変換行列Ｘとの積である２次元ベクトルＺを算出するので、第１計算装置１００は送信された２次元ベクトルＺからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数１６）
【００５６】
本実施形態では、前述と同様の理由で、式（１１）によりｎ次元ベクトルＶｂの各要素Ｂjを拡張しているが、第１実施形態と同様に、ｎ次元ベクトルＶｂの各要素Ｂjを拡張しなくてもよい。この場合、Ｓ３１１及びＳ３１２の処理は行わず、Ｓ３１０の処理の次に、Ｓ２１３の処理において、計算部１１４は以下の式（２７）’を計算して２次元ベクトルＺを算出する。このように、２行ｎ列の変換行列Ｘとｎ次元ベクトルＶｂとの積である２次元ベクトルＺを算出するので、各要素Ｂjを拡張（１次元変換）しなくても、第１計算装置１００は送信された２次元ベクトルＺからｎ次元ベクトルＶｂを知ることができず、第２計算装置１１０に対してｎ次元ベクトルＶｂが秘匿される。
（数１７）
【００５７】
次に、第１計算装置１００の逆変換部１０５は、通信装置５０４により第２計算装置１１０から２次元ベクトルＺを受信し、一時記憶部１０３に記憶された前述の乱数Ｍと乱数Ｗ11，Ｗ12，Ｗ21，Ｗ22とを用いて以下の式（２８）及び（２９）を計算し、剰余Ｃを算出する（Ｓ３０３）。これにより、従来と同程度の安全性を確保できるものとして、例えば乱数Ｗi及びＭiが１００ビットの整数である場合、通信量は送受信とも２×１００×ｎビット程度となり、第１計算装置１００及び第２計算装置１１０における計算はそれぞれｎ回の掛け算と足し算の数倍程度となる。また、このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２０）〜（２９）により算出される剰余Ｃは、式（１）により算出される剰余Ｃと等しくなる。
（数１８）
【００５８】
ここで、第１実施形態と同様に、前述の式（１６）を満たすようにＱを設定すると、剰余Ｃは内積値Ｖａ・Ｖｂに等しくなる。これにより、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、正確な内積値Ｖａ・Ｖｂを算出することができる。
【００５９】
本実施形態では、前述と同様の理由で、式（２９）により法Ｑの剰余を算出しているが、第１実施形態と同様に、法Ｑの剰余を算出しなくてもよい。この場合、Ｓ３０３の処理において、逆変換部１０５は式（２８）及び以下の式（２９）’を計算して剰余Ｃを算出する。このように、第１計算装置１００及び第２計算装置１１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、式（２６）’、（２７）’、（２８）、（２９）’により算出される剰余Ｃは、ｎ次元ベクトルＶａとｎ次元ベクトルＶｂとの内積値Ｖａ・Ｖｂに等しくなるので、正確な内積値Ｖａ・Ｖｂを算出することができる。
（数１９）
Ｃ＝Ｃ1 …（２９）’
【００６０】
最後に、出力部１０６は剰余Ｃを出力する（Ｓ３０４）。
【００６１】
このように、本実施形態によれば、ｎ次元ベクトルＶａを２行ｎ列の変換行列に２次元変換する場合であっても、第１実施形態と同様の効果を得ることができるとともに、多少の計算コストを犠牲にして更に安全性を高めることができる。
【００６２】
また、ｎ次元ベクトルＶａをｍ行ｎ列の変換行列（ｍは３以上の整数）にｍ次元変換する場合であっても、本実施形態と同様の効果を得ることができる。
【００６３】
［第３実施形態］
従来、暗号通信における暗号鍵共有プロトコルである、前述の非特許文献３及び４に記載された方法は、量子計算機によって破られることが判明している。これは、現在のコンピュータでは困難とされている素因数分解問題や離散対数問題が、量子計算機では容易に解けるためである。このため、将来的に量子計算機が実現されたとしても安全性を確保できるように、素因数分解問題や離散対数問題に依存しない新しい暗号鍵共有システムが必要とされる。
【００６４】
本発明の第３実施形態に係る暗号鍵共有システムは、前記問題点に鑑みてなされたものであり、その目的とするところは、量子計算機に対しても耐性を有する暗号鍵共有システムを提供することにある。
【００６５】
図５は本発明の第３実施形態を示すものであり、同図は、暗号鍵共有システムの機能構成を説明する概略構成図である。なお、鍵共有システムのハードウェア構成は、第１実施形態に示した図２と同様であるため、図示及びその説明を省略する。
【００６６】
図５に示すように、暗号鍵共有システム１０は、第１鍵共有装置４００と、第２鍵共有装置４１０とを備え、第１鍵共有装置４００と第２鍵共有装置４１０とは、ネットワークＮ２を介して互いに接続される。
【００６７】
第１鍵共有装置４００は、内積計算部Ａ４０１と、ベクトル生成部４０２と、内積計算部Ｂ４０３と、ハッシュ関数部４０４と、出力部４０５とから構成される。内積計算部Ａ401は、第１実施形態又は第２実施形態における第１計算装置１００と同一の機能、すなわち、入力部１０１、乱数生成部１０２、一時記憶部１０３、変換部１０４、逆変換部１０５及び出力部１０６を有する。内積計算部Ｂ４０３は、第１実施形態又は第２実施形態における第２計算装置１１０と同一の機能、すなわち、入力部１１１、乱数生成部１１２、拡張部１１３及び計算部１１４を有する。ベクトル生成部４０２は、前述のｎ次元ベクトルＶａを生成する。ハッシュ関数部４０４は、例えばＳＨＡ−１やＳＨＡ−２５６といったアルゴリズムに従い、入力値に対するハッシュ値を計算する。出力部４０５は、後述する共通鍵を出力する。
【００６８】
第２鍵共有装置４１０は、内積計算部Ｂ４１１と、ベクトル生成部４１２と、内積計算部Ａ４１３と、ハッシュ関数部４１４と、出力部４１５とから構成される。内積計算部Ｂ４１１は内積計算部Ｂ４０３と同一であり、ベクトル生成部４１２は前述のｎ次元ベクトルＶｂを生成する。内積計算部Ａ４１３は内積計算部Ａ４０１と同一であり、ハッシュ関数部４１４はハッシュ関数部４０４と同一であり、出力部４１５は、後述する共通鍵を出力する。
【００６９】
次に、暗号鍵共有システム１０の動作について説明する。
【００７０】
まず、第１鍵共有装置４００のベクトル生成部４０２は、前述のｎ次元ベクトルＶａをランダムに生成し、内積計算部Ａ４０１及び内積計算部Ｂ４０３に出力する。
【００７１】
一方、第２鍵共有装置４１０のベクトル生成部４１２は、前述のｎ次元ベクトルＶｂをランダムに生成し、内積計算部Ｂ４１１及び内積計算部Ａ４１３に出力する。
【００７２】
第１鍵共有装置４００の内積計算部Ａ４０１と第２鍵共有装置４１０の内積計算部Ｂ４１１とが通信し、内積計算部Ａ４０１は内積値Ｃ＝Ｖａ・Ｖｂを算出し、ハッシュ関数部４０４に出力する。なお、内積値Ｃの計算方法は、前述の第１実施形態又は第２実施形態と同様とする。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第１鍵共有装置４００が内積値Ｃを算出することができる。
【００７３】
同様に、第２鍵共有装置４１０の内積計算部Ａ４１３と第１鍵共有装置４００の内積計算部Ｂ４０３とが通信し、内積計算部Ａ４１３は内積値Ｃ＝Ｖａ・Ｖｂを算出し、ハッシュ関数部４１４に出力する。なお、内積計算の方法は、前述の第１実施形態又は第２実施形態と同様とする。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第２鍵共有装置４１０が内積値Ｃを算出することができる。
【００７４】
第１鍵共有装置４００のハッシュ関数部４０４は、入力された内積値Ｃのハッシュ値Ｋを算出し、出力部４０５はハッシュ値Ｋを共通鍵として出力する。これにより、素因数分解問題や離散対数問題の計算量的困難性に依存しない共通鍵（暗号鍵）を生成することができる。
【００７５】
同様に、第２鍵共有装置４１０のハッシュ関数部４１４は、入力された内積値Ｃのハッシュ値Ｋを算出し、出力部４１５はハッシュ値Ｋを共通鍵として出力する。これにより、第１鍵共有装置４００及び第２鍵共有装置４１０はハッシュ値Ｋを共通鍵として共有することができる。
【００７６】
本実施形態では、計算した内積値Ｃのハッシュ値Ｋを共通鍵としているが、これに限定されず、他の方法で共通鍵を生成するようにしてもよいし、内積値Ｃそのものを共通鍵としてもよい。
【００７７】
このように、この暗号鍵共有システム１０によれば、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第１鍵共有装置４００が内積値Ｃを算出することができ、第１鍵共有装置４００及び第２鍵共有装置４１０が互いに自己の有するｎ次元ベクトルＶａ，Ｖｂを秘密にしながら、第２鍵共有装置４１０が内積値Ｃを算出することができるので、第１鍵共有装置４００及び第２鍵共有装置４１０間の通信を全て盗聴されたとしても、ｎ次元ベクトルＶａ，Ｖｂが秘匿されるから、盗聴者は内積値Ｃ及びそのハッシュ値Ｋを知ることができない。これにより、共通鍵を安全に（盗聴者には計算できないように）共有することができる。また、前述の第１実施形態又は第２実施形態の方法で内積値Ｃを算出し、当該内積値Ｃ又は当該内積値Ｃのハッシュ値を共通鍵として出力するので、素因数分解問題や離散対数問題の計算量的困難性に依存しない共通鍵（暗号鍵）を生成することができる。これにより、量子計算機に対しても耐性を有する。
【００７８】
なお、本発明の構成は、前記実施形態にのみ限定されるものではなく、本発明の要旨を逸脱しない範囲内において種々変更を加えてもよい。
【図面の簡単な説明】
【００７９】
【図１】ベクトル秘匿型内積計算システムの機能構成を説明する概略構成図である。
【図２】図１に示した第１計算装置及び第２計算装置のハードウェア構成を説明する概略構成図である。
【図３】ベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【図４】第２実施形態に係るベクトル秘匿型内積計算システムの動作を説明するフローチャートである。
【図５】暗号鍵共有システムの機能構成を説明する概略構成図である。
【符号の説明】
【００８０】
１…ベクトル秘匿型内積計算システム、１０…暗号鍵共有システム、１００…第１計算装置、１０１…入力部、１０２…乱数生成部、１０３…一時記憶部、１０４…変換部、１０５…逆変換部、１１０…第２計算装置、１１１…入力部、１１２…乱数生成部、１１３…拡張部、１１４…計算部、４００…第１鍵共有装置、４０１…内積計算部Ａ、４０２…ベクトル生成部、４０３…内積計算部Ｂ、４０４…ハッシュ関数部、４０５…出力部、４１０…第２鍵共有装置、４１１…内積計算部Ｂ、４１２…ベクトル生成部、４１３…内積計算部Ａ、４１４…ハッシュ計算部、４１５…出力部。
【特許請求の範囲】
【請求項１】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを備えるベクトル秘匿型内積計算システムにおいて、
前記第１の計算装置は、
前記第２の計算装置との間で情報を送受信可能な第１通信部と、
整数である第１、第２及び第３の乱数を生成する第１生成部と、
前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換部とを有し、
前記第２の計算装置は、
前記第１の計算装置との間で情報を送受信可能な第２通信部と、
前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算部とを有し、
前記第１の計算装置は、
前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換部をさらに有する
ことを特徴とするベクトル秘匿型内積計算システム。
【請求項２】
前記第１生成部は、前記第３の乱数としてＭと、前記第１の乱数としてＷとを生成し、
前記変換部は、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記計算部は、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、前記第１のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記内積値Ｚに対し、
（数３）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項３】
前記第１生成部は、正の整数である所定数Ｑ、Ｒ、Ｓ及びｐに対し、前記第２の乱数としてＲj（ｊ＝１，２，…，ｎ 但し、Ｒj＜Ｒ）と、前記第３の乱数としてＭi（ｉ＝１，２，…，ｐ 但し、Ｍ1＞ｎＲＳＱ2 かつ Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ））と、前記第１の乱数としてＷi（ｉ＝１，２，…，ｐ 但し、Ｗi＜Ｍi かつ ＧＣＤ（Ｗi，Ｍi）＝１）とを生成し、
前記変換部は、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数４）
Ｘ1,j＝Ｒj・Ｑ＋Ａj
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す）
Ｘj＝Ｘp+1,j
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記第２の計算装置は、
前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成部と、
前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数５）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張部とを有し、
前記計算部は、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、
（数６）
Ｚ＝Ｘ1・Ｙ1＋Ｘ2・Ｙ2＋…＋Ｘn・Ｙn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記内積値Ｚに対し、
（数７）
Ｚp+1＝Ｚ
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す）
Ｃ＝Ｚ1 ｍｏｄ Ｑ
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項４】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数８）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定する
ことを特徴とする請求項３に記載のベクトル秘匿型内積計算システム。
【請求項５】
前記第１生成部は、前記第２の乱数としてＲ2,j（ｊ＝１，２，…，ｎ）と、前記第３の乱数としてＭと、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11・Ｗ22−Ｗ12・Ｗ21≠０）とを生成し、
前記変換部は、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数９）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記計算部は、前記第２のｎ次元ベクトルＢ＝（Ｂ1，Ｂ2，…，Ｂn）に対し、
（数１０）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数１１）
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項６】
前記第１生成部は、正の整数である所定数Ｑ、Ｒ及びＳに対し、前記第２の乱数としてＲ1,j（ｊ＝１，２，…，ｎ 但し、Ｒ1,j＜Ｒ）及びＲ2,j（ｊ＝１，２，…，ｎ 但し、Ｒ2,j＜Ｍ）と、前記第３の乱数として１個のＭ（Ｍ＞ｎＳＲＱ2）と、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ かつ ＧＣＤ（Ｗ11・Ｗ22−Ｗ12・Ｗ21，Ｍ）＝１）とを生成し、
前記変換部は、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１２）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記第２の計算装置は、
前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成部と、
前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数１３）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張部とを有し、
前記算出部は、
（数１４）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数１５）
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項７】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数１６）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定する
ことを特徴とする請求項６に記載のベクトル秘匿型内積計算システム。
【請求項８】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを有するシステムに用いられるベクトル秘匿型内積計算方法であって、
前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部を有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部を有しており、
前記第１の計算装置により、整数である第１、第２及び第３の乱数を生成する第１生成ステップと、
前記第１の計算装置により、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換ステップと、
前記第２の計算装置により、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算ステップと、
前記第１の計算装置により、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換ステップとを備える
ことを特徴とするベクトル秘匿型内積計算方法。
【請求項９】
前記第１生成ステップは、前記第３の乱数としてＭと、前記第１の乱数としてＷとを生成し、
前記変換ステップは、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１７）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記計算ステップは、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、前記第１のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数１８）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記内積値Ｚに対し、
（数１９）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１０】
前記第１生成ステップは、正の整数である所定数Ｑ、Ｒ、Ｓ及びｐに対し、前記第２の乱数としてＲj（ｊ＝１，２，…，ｎ 但し、Ｒj＜Ｒ）と、前記第３の乱数としてＭi（ｉ＝１，２，…，ｐ 但し、Ｍ1＞ｎＲＳＱ2 かつ Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ））と、前記第１の乱数としてＷi（ｉ＝１，２，…，ｐ 但し、Ｗi＜Ｍi かつ ＧＣＤ（Ｗi，Ｍi）＝１）とを生成し、
前記変換ステップは、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２０）
Ｘ1,j＝Ｒj・Ｑ＋Ａj
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す）
Ｘj＝Ｘp+1,j
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記第２の計算装置により、前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成ステップと、
前記第２の計算装置により、前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２１）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張ステップとをさらに含み、
前記計算ステップは、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、
（数２２）
Ｚ＝Ｘ1・Ｙ1＋Ｘ2・Ｙ2＋…＋Ｘn・Ｙn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記内積値Ｚに対し、
（数２３）
Ｚp+1＝Ｚ
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す）
Ｃ＝Ｚ1 ｍｏｄ Ｑ
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１１】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数２４）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定するステップをさらに含む
ことを特徴とする請求項１０に記載のベクトル秘匿型内積計算方法。
【請求項１２】
前記第１生成ステップは、前記第２の乱数としてＲ2,j（ｊ＝１，２，…，ｎ）と、前記第３の乱数としてＭと、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11・Ｗ22−Ｗ12・Ｗ21≠０）とを生成し、
前記変換ステップは、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２５）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記計算ステップは、前記第２のｎ次元ベクトルＢ＝（Ｂ1，Ｂ2，…，Ｂn）に対し、
（数２６）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数２７）
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１３】
前記第１生成ステップは、正の整数である所定数Ｑ、Ｒ及びＳに対し、前記第２の乱数としてＲ1,j（ｊ＝１，２，…，ｎ 但し、Ｒ1,j＜Ｒ）及びＲ2,j（ｊ＝１，２，…，ｎ 但し、Ｒ2,j＜Ｍ）と、前記第３の乱数として１個のＭ（Ｍ＞ｎＳＲＱ2）と、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ かつ ＧＣＤ（Ｗ11・Ｗ22−Ｗ12・Ｗ21，Ｍ）＝１）とを生成し、
前記変換ステップは、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２８）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記第２の計算装置により、前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成ステップと、
前記第２の計算装置により、前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２９）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張ステップとをさらに含み、
前記算出ステップは、
（数３０）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数３１）
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１４】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数３２）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定するステップをさらに含む
ことを特徴とする請求項１３に記載のベクトル秘匿型内積計算方法。
【請求項１５】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の鍵共有装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の鍵共有装置とを備える暗号鍵共有システムにおいて、
前記第１の鍵共有装置は、
請求項８乃至１４の何れかに記載のベクトル秘匿型内積計算方法を用いて前記第１のｎ次元ベクトルと前記第２のｎ次元ベクトルとの第１内積値を算出する第１内積計算部と、
前記第１内積計算部により計算された前記第１内積値に基づいて、第１暗号鍵を生成する第１暗号鍵生成部とを有し、
前記第２の鍵共有装置は、
請求項８乃至１４の何れかに記載のベクトル秘匿型内積計算方法を用いて前記第１のｎ次元ベクトルと前記第２のｎ次元ベクトルとの第２内積値を算出する第２内積計算部と、
前記第２内積計算部により計算された前記第２内積値に基づいて、第２暗号鍵を生成する第２暗号鍵生成部とを有する
ことを特徴とする暗号鍵共有システム。
【請求項１６】
第１暗号鍵生成部は、所定のハッシュ関数を用いて前記第１内積値のハッシュ値を算出し、該ハッシュ値を前記第１暗号鍵とし、
第２暗号鍵生成部は、前記所定のハッシュ関数を用いて前記第２内積値のハッシュ値を算出し、該ハッシュ値を前記第２暗号鍵とする
ことを特徴とする請求項１５に記載の暗号鍵共有システム。
【請求項１】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを備えるベクトル秘匿型内積計算システムにおいて、
前記第１の計算装置は、
前記第２の計算装置との間で情報を送受信可能な第１通信部と、
整数である第１、第２及び第３の乱数を生成する第１生成部と、
前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換部とを有し、
前記第２の計算装置は、
前記第１の計算装置との間で情報を送受信可能な第２通信部と、
前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算部とを有し、
前記第１の計算装置は、
前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換部をさらに有する
ことを特徴とするベクトル秘匿型内積計算システム。
【請求項２】
前記第１生成部は、前記第３の乱数としてＭと、前記第１の乱数としてＷとを生成し、
前記変換部は、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記計算部は、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、前記第１のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記内積値Ｚに対し、
（数３）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項３】
前記第１生成部は、正の整数である所定数Ｑ、Ｒ、Ｓ及びｐに対し、前記第２の乱数としてＲj（ｊ＝１，２，…，ｎ 但し、Ｒj＜Ｒ）と、前記第３の乱数としてＭi（ｉ＝１，２，…，ｐ 但し、Ｍ1＞ｎＲＳＱ2 かつ Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ））と、前記第１の乱数としてＷi（ｉ＝１，２，…，ｐ 但し、Ｗi＜Ｍi かつ ＧＣＤ（Ｗi，Ｍi）＝１）とを生成し、
前記変換部は、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数４）
Ｘ1,j＝Ｒj・Ｑ＋Ａj
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す）
Ｘj＝Ｘp+1,j
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記第２の計算装置は、
前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成部と、
前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数５）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張部とを有し、
前記計算部は、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、
（数６）
Ｚ＝Ｘ1・Ｙ1＋Ｘ2・Ｙ2＋…＋Ｘn・Ｙn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記内積値Ｚに対し、
（数７）
Ｚp+1＝Ｚ
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す）
Ｃ＝Ｚ1 ｍｏｄ Ｑ
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項４】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数８）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定する
ことを特徴とする請求項３に記載のベクトル秘匿型内積計算システム。
【請求項５】
前記第１生成部は、前記第２の乱数としてＲ2,j（ｊ＝１，２，…，ｎ）と、前記第３の乱数としてＭと、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11・Ｗ22−Ｗ12・Ｗ21≠０）とを生成し、
前記変換部は、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数９）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記計算部は、前記第２のｎ次元ベクトルＢ＝（Ｂ1，Ｂ2，…，Ｂn）に対し、
（数１０）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数１１）
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項６】
前記第１生成部は、正の整数である所定数Ｑ、Ｒ及びＳに対し、前記第２の乱数としてＲ1,j（ｊ＝１，２，…，ｎ 但し、Ｒ1,j＜Ｒ）及びＲ2,j（ｊ＝１，２，…，ｎ 但し、Ｒ2,j＜Ｍ）と、前記第３の乱数として１個のＭ（Ｍ＞ｎＳＲＱ2）と、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ かつ ＧＣＤ（Ｗ11・Ｗ22−Ｗ12・Ｗ21，Ｍ）＝１）とを生成し、
前記変換部は、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１２）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記第２の計算装置は、
前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成部と、
前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数１３）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張部とを有し、
前記算出部は、
（数１４）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換部は、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数１５）
を計算してＣを算出する
ことを特徴とする請求項１に記載のベクトル秘匿型内積計算システム。
【請求項７】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数１６）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定する
ことを特徴とする請求項６に記載のベクトル秘匿型内積計算システム。
【請求項８】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の計算装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の計算装置とを有するシステムに用いられるベクトル秘匿型内積計算方法であって、
前記第１の計算装置は、前記第２の計算装置との間で情報を送受信可能な第１通信部を有し、前記第２の計算装置は、前記第１の計算装置との間で情報を送受信可能な第２通信部を有しており、
前記第１の計算装置により、整数である第１、第２及び第３の乱数を生成する第１生成ステップと、
前記第１の計算装置により、前記第１の乱数に基づくｍ行ｍ列の正則行列（ｍは正の整数）と前記第２の乱数とに基づいて前記第１のｎ次元ベクトルをｍ行ｎ列の行列に線形変換し、線形変換した該ｍ行ｎ列の行列における各要素に対して前記第３の乱数で除算した剰余を算出し、該剰余を各要素とするｍ行ｎ列の変換行列を前記第１通信部により送信する変換ステップと、
前記第２の計算装置により、前記第２通信部により受信した前記ｍ行ｎ列の変換行列と前記第２のｎ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルを前記第２通信部により送信する計算ステップと、
前記第１の計算装置により、前記ｍ行ｍ列の正則行列の前記第３の乱数を法とした逆行列と前記第１通信部により受信した前記ｍ次元ベクトルとに基づいてｍ次元ベクトルを算出し、該ｍ次元ベクトルにおける所定の要素に対して前記第３の乱数で除算した剰余を算出する逆変換ステップとを備える
ことを特徴とするベクトル秘匿型内積計算方法。
【請求項９】
前記第１生成ステップは、前記第３の乱数としてＭと、前記第１の乱数としてＷとを生成し、
前記変換ステップは、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数１７）
Ｘj＝Ｗ・Ａj ｍｏｄ Ｍ
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記計算ステップは、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、前記第１のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数１８）
Ｚ＝Ｘ1・Ｂ1＋Ｘ2・Ｂ2＋…＋Ｘn・Ｂn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記内積値Ｚに対し、
（数１９）
Ｃ＝Ｗ-1・Ｚ ｍｏｄ Ｍ
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１０】
前記第１生成ステップは、正の整数である所定数Ｑ、Ｒ、Ｓ及びｐに対し、前記第２の乱数としてＲj（ｊ＝１，２，…，ｎ 但し、Ｒj＜Ｒ）と、前記第３の乱数としてＭi（ｉ＝１，２，…，ｐ 但し、Ｍ1＞ｎＲＳＱ2 かつ Ｍi＞ｎＲＳＱ2Ｍi-1（ｉ＝２，３，…，ｐ））と、前記第１の乱数としてＷi（ｉ＝１，２，…，ｐ 但し、Ｗi＜Ｍi かつ ＧＣＤ（Ｗi，Ｍi）＝１）とを生成し、
前記変換ステップは、前記ｍとして１を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２０）
Ｘ1,j＝Ｒj・Ｑ＋Ａj
Ｘi+1,j＝Ｗj・Ｘi,j ｍｏｄ Ｍi（ｉ＝１，２，…，ｐについて繰り返す）
Ｘj＝Ｘp+1,j
を計算してｎ次元変換ベクトルＸ＝（Ｘ1，Ｘ2，…，Ｘn）を前記第１通信部により送信し、
前記第２の計算装置により、前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成ステップと、
前記第２の計算装置により、前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２１）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張ステップとをさらに含み、
前記計算ステップは、前記第２通信部により前記ｎ次元変換ベクトルＸを受信し、
（数２２）
Ｚ＝Ｘ1・Ｙ1＋Ｘ2・Ｙ2＋…＋Ｘn・Ｙn
を計算して内積値Ｚを前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記内積値Ｚに対し、
（数２３）
Ｚp+1＝Ｚ
Ｚi＝Ｗi-1・Ｚi+1 ｍｏｄ Ｍi（ｉ＝ｐ，ｐ−１，…，１について繰り返す）
Ｃ＝Ｚ1 ｍｏｄ Ｑ
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１１】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数２４）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定するステップをさらに含む
ことを特徴とする請求項１０に記載のベクトル秘匿型内積計算方法。
【請求項１２】
前記第１生成ステップは、前記第２の乱数としてＲ2,j（ｊ＝１，２，…，ｎ）と、前記第３の乱数としてＭと、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11・Ｗ22−Ｗ12・Ｗ21≠０）とを生成し、
前記変換ステップは、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２５）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記計算ステップは、前記第２のｎ次元ベクトルＢ＝（Ｂ1，Ｂ2，…，Ｂn）に対し、
（数２６）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数２７）
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１３】
前記第１生成ステップは、正の整数である所定数Ｑ、Ｒ及びＳに対し、前記第２の乱数としてＲ1,j（ｊ＝１，２，…，ｎ 但し、Ｒ1,j＜Ｒ）及びＲ2,j（ｊ＝１，２，…，ｎ 但し、Ｒ2,j＜Ｍ）と、前記第３の乱数として１個のＭ（Ｍ＞ｎＳＲＱ2）と、前記第１の乱数としてＷ11，Ｗ12，Ｗ21，Ｗ22（但し、Ｗ11，Ｗ12，Ｗ21，Ｗ22＜Ｍ かつ ＧＣＤ（Ｗ11・Ｗ22−Ｗ12・Ｗ21，Ｍ）＝１）とを生成し、
前記変換ステップは、前記ｍとして２を用い、前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）に対し、
（数２８）
を計算して２行ｎ列の変換行列Ｘを前記第１通信部により送信し、
前記第２の計算装置により、前記所定数Ｓに対し、第４の乱数としてＳj（ｊ＝１，２，…，ｎ 但し、Ｓj＜Ｓ）を生成する第２生成ステップと、
前記第２の計算装置により、前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）に対し、
（数２９）
Ｙj＝Ｓj・Ｑ＋Ｂj
を計算してｎ次元拡張ベクトルＹ＝（Ｙ1，Ｙ2，…，Ｙn）を算出する拡張ステップとをさらに含み、
前記算出ステップは、
（数３０）
を計算して２次元ベクトルＺ＝（Ｚ1，Ｚ2）を前記第２通信部により送信し、
前記逆変換ステップは、前記第１通信部により受信した前記２次元ベクトルＺに対し、
（数３１）
を計算してＣを算出する
ことを特徴とする請求項８に記載のベクトル秘匿型内積計算方法。
【請求項１４】
前記第１のｎ次元ベクトルの各要素Ａj（ｊ＝１，２，…，ｎ）と前記第２のｎ次元ベクトルの各要素Ｂj（ｊ＝１，２，…，ｎ）とにおける最大値Ｎに対し、
（数３２）
Ｑ＞ｎ・Ｎ2
を満たすように前記所定数Ｑを設定するステップをさらに含む
ことを特徴とする請求項１３に記載のベクトル秘匿型内積計算方法。
【請求項１５】
各要素が整数である第１のｎ次元ベクトル（ｎは正の整数）を秘匿する第１の鍵共有装置と、各要素が整数である第２のｎ次元ベクトルを秘匿する第２の鍵共有装置とを備える暗号鍵共有システムにおいて、
前記第１の鍵共有装置は、
請求項８乃至１４の何れかに記載のベクトル秘匿型内積計算方法を用いて前記第１のｎ次元ベクトルと前記第２のｎ次元ベクトルとの第１内積値を算出する第１内積計算部と、
前記第１内積計算部により計算された前記第１内積値に基づいて、第１暗号鍵を生成する第１暗号鍵生成部とを有し、
前記第２の鍵共有装置は、
請求項８乃至１４の何れかに記載のベクトル秘匿型内積計算方法を用いて前記第１のｎ次元ベクトルと前記第２のｎ次元ベクトルとの第２内積値を算出する第２内積計算部と、
前記第２内積計算部により計算された前記第２内積値に基づいて、第２暗号鍵を生成する第２暗号鍵生成部とを有する
ことを特徴とする暗号鍵共有システム。
【請求項１６】
第１暗号鍵生成部は、所定のハッシュ関数を用いて前記第１内積値のハッシュ値を算出し、該ハッシュ値を前記第１暗号鍵とし、
第２暗号鍵生成部は、前記所定のハッシュ関数を用いて前記第２内積値のハッシュ値を算出し、該ハッシュ値を前記第２暗号鍵とする
ことを特徴とする請求項１５に記載の暗号鍵共有システム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図２】
【図３】
【図４】
【図５】
【公開番号】特開２００９−２７２９９５（Ｐ２００９−２７２９９５Ａ）
【公開日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願番号】特願２００８−１２３１９９（Ｐ２００８−１２３１９９）
【出願日】平成２０年５月９日（２００８．５．９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２１年１１月１９日（２００９．１１．１９）
【国際特許分類】
【出願日】平成２０年５月９日（２００８．５．９）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]