鍵生成装置、鍵生成方法、プログラム及び記録媒体
【課題】実用的な準同型暗号方式を実現する。
【解決手段】任意値生成部１１６が、絶対値が所定値以上となるｎ個（ｎは正の整数）の任意値λｉ（ｉ＝０，．．，ｎ−１）を生成する。暗号鍵生成部１１７は、これらを用いて、ｎ個の任意値λｉ（ｉ＝０，．．，ｎ−１）の離散フーリエ変換結果に対応するｎ個の要素をｖｉ（ｉ＝０，．．，ｎ−１）とした場合における、ｎ×ｎの巡回行列ｒｏｔ（ｖ）に対して定まるｎ×ｎの行列を、準同型暗号方式の暗号鍵として生成する。
【解決手段】任意値生成部１１６が、絶対値が所定値以上となるｎ個（ｎは正の整数）の任意値λｉ（ｉ＝０，．．，ｎ−１）を生成する。暗号鍵生成部１１７は、これらを用いて、ｎ個の任意値λｉ（ｉ＝０，．．，ｎ−１）の離散フーリエ変換結果に対応するｎ個の要素をｖｉ（ｉ＝０，．．，ｎ−１）とした場合における、ｎ×ｎの巡回行列ｒｏｔ（ｖ）に対して定まるｎ×ｎの行列を、準同型暗号方式の暗号鍵として生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、準同型暗号方式の暗号鍵を生成する技術に関する。
【背景技術】
【０００２】
準同型暗号（homomorphic encryption）方式とは、ある平文集合に演算を施して得られる暗号文を、その平文集合に属する各々の平文の暗号文から構成できる、という性質を持つ暗号方式である。例えば、平文集合Sに属する平文M1,M2∈Sとし、加法及び乗法について準同型な準同型暗号方式の暗号化関数をEncとすると、以下の式(1)(2)の性質が成り立つ。
【０００３】
Enc(M1+M2)=Enc(M1)+Enc(M2) …(1)
Enc(M1・M2)=Enc(M1)・Enc(M2) …(2)
準同型暗号方式を用いれば、暗号文どうしの加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。例えば、データを準同型暗号方式で暗号化しておけば、１以上の演算ゲート（以下「ゲート」）から構成される任意の演算回路（以下「回路」）にデータを入力して演算結果を得る計算を、暗号文のまま行うことができる。この性質はプログラム秘匿やデータ秘匿において非常に重要である。そのため、準同型暗号方式を構成する研究が長年行われてきた。しかしながら、加法及び乗法について準同型な準同型暗号方式の構成に成功したと認められる研究はいまだなく、近年はこのような準同型暗号方式が存在するかどうかの研究が主題であった。このような中、任意の深さの回路に適用可能で加法及び乗法について準同型な準同型暗号方式が存在することを主張する画期的な論文が発表された（非特許文献１）。なお、回路の深さとは、その回路の入力ゲートから出力ゲートまでのゲート数の最大値を意味する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】C. Gentry., "Fully Homomorphic encryption using ideal lattices", STOC 2009, pp. 169-178, 2009
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１では、十分な鍵長を確保して十分な演算時間を費やすならば理論的に機能する準同型暗号方式が存在することのみが示されるにとどまり、準同型暗号方式の実用的な構成方法は明らかにされていない。すなわち、非特許文献１の準同型暗号方式は、各平文にそれぞれ対応する暗号文間の演算結果と、各平文間の演算結果に対する暗号文との間に許容範囲内の誤差があったとしても、前者の暗号文間の演算結果を復号した結果が、後者の演算結果に対する暗号文を復号した結果と等しくなるように構成されている。そして、非特許文献１には、大きな鍵長の暗号鍵を用いることで上記の誤差を許容範囲内に収め、準同型暗号方式を構成することが示されている。ところが、非特許文献１の準同型暗号方式には、回路の深さが深くなるにつれて上記の誤差が蓄積されて大きくなる性質がある。そのため、非特許文献１の準同型暗号方式を実用的に用いるためには、回路の深さと誤差との関係について具体的な評価を行い、誤差が許容範囲を超える前に誤差を再び小さくするといった処理を行う必要がある。しかしながら、非特許文献１に開示された内容では誤差を再び小さくする処理を行うことができる鍵長や、その処理の手数は膨大と考えられ、実用的な程度にはいたっていない。
【課題を解決するための手段】
【０００６】
本発明では、回路の深さと誤差との関係を評価し、その評価結果を暗号化処理や復号処理に反映させるというアプローチではなく、鍵生成処理の時点で所望の範囲に誤差を収めることが可能な暗号鍵を生成しておくというアプローチをとる。すなわち、本発明の鍵生成処理では、絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成し、n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【０００７】
【数１】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力する。
【発明の効果】
【０００８】
本発明で生成された暗号鍵を用いた場合の上記誤差の範囲は、任意値λiが採りうる範囲に依存する。よって、回路の深さに応じた適切な範囲から任意値λiを選択することで、容易に実用的な準同型暗号方式を構成することができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態のセキュリティシステムの全体構成を説明するための図。
【図２】実施形態のセキュリティシステムの全体構成を説明するための図。
【図３】実施形態の鍵生成装置の構成を説明するための図。
【図４】実施形態の鍵生成処理を説明するための図。
【図５】第２実施形態の鍵情報生成部の構成を説明するための図。
【図６】第２実施形態のステップＳ２５の詳細を説明するための図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して本発明の実施形態を説明する。
【００１１】
〔定義〕
まず、本形態で用いる基本的な用語を定義する。
【００１２】
＜格子(lattice)＞
格子とは、Zn中の離散的な加法的部分群を意味する。格子は、Zn中の線形独立な基底b0,b2,...,bn-1∈Znの線形結合で表現される。なお、Znはn次元（nは整数）の整数からなる整数環である。また、基底を並べたn×nの行列B=(b0,b2,...,bn-1)を基底行列と呼ぶ。
【００１３】
＜イデアル格子(ideal lattice)＞
格子がイデアル格子であるとは、その格子と加群として同型な剰余環R=Z[x]/f(x)のイデアルが存在することである。なお、Z[x]は整数係数多項式環であり、f(x)は最高次の係数が１である（monicな）次数nの整数係数一変数多項式である。また、剰余環Rのイデアルとは、剰余環Rの加法的部分群であり、その元に対して剰余環Rの元を左右どちらから掛けても、その演算結果が当該加法的部分群の元となるものを意味する（両側イデアルと呼ぶ場合もある）。また、剰余環Rのイデアルとして最も単純なものは剰余環Rの１つの元を用いて生成される単項イデアルである。
【００１４】
＜巡回行列(circulant matrix)＞
巡回行列（「循環行列」とも呼ばれる）とは、各行ベクトルが1つ前の行ベクトルの要素を1つ巡回させたように構成された行列である。
【００１５】
剰余環Rの１つの元
V=v0+v1・x+...+vn-1・xn-1 mod f(x)
で生成される単項イデアルの元は、V, V・x,..., V・xn-1の線形結合で書ける。ただし、ベクトルv=T(v0,v1,...,vn-1)∈Znとし、T(α)をαの転置とする。本形態では、この生成系のベクトルv=T(v0,v1,...,vn-1)∈Znを並べた巡回行列を巡回行列rot(v)と表現する。特に、f(x)=xn-1のとき、巡回行列rot(v)は以下のようになる。
【００１６】
【数２】
f(x)=xn-1のとき、巡回行列rot(v)は基底行列Bとなる。
【００１７】
＜半開基本平行体（half-open parallelepiped）＞
基底行列Bに対して、
P(B)={B・T(x0,x1,...,xn-1)|-1/2≦xi≦1/2}2 …(4)
を半開基本並行体と呼ぶ。
【００１８】
＜格子による剰余＞
基底行列Bに対応する基底で構成される格子をL(B)と表現する。ベクトルt∈Znについて、t-t'∈L(B)かつt'∈P(B)を満たすベクトルt'∈Znを
t mod B …(5)
と表現し、基底行列Bとベクトルtに対してベクトルt'を求める演算をtのBによる剰余と呼ぶ。
【００１９】
＜ノルム＞
ベクトルαのユークリッドノルム（Euclid norm）を‖α‖と表現する。また、n次正方行列Αのスペクトルノルム（spectral norm）を‖Α‖を表現する。‖Α‖は、任意のn次元ベクトルXに対し、以下のように定義される。
【００２０】
【数３】
また、n次正方行列Αのフロベニウスノルム（frobenius norm）を‖Α‖Fを表現する。‖Α‖Fは、Αのi行j列の要素をαij(0≦i,j＜n)とした場合に（A=(αij)0≦i,j＜n）、以下のように定義される。
【００２１】
【数４】
また、n次正方行列Αの随伴行列をΑ*とし、λ|max|(Α*・Α)をΑ*・Αの固有値の絶対値の最大値とし、λ|min|(Α*・Α)をΑ*・Αの固有値の絶対値の最小値と表現する。この場合、
【００２２】
【数５】
となることがよく知られている。また、
‖Α‖≦‖Α‖F …(9)
を満たすことがよく知られている。
【００２３】
〔非特許文献１の準同型暗号方式〕
次に、本形態の前提となる非特許文献１の準同型暗号方式（以下「Gentry方式」）の一例を示す。
【００２４】
まず、剰余環R=Z[x]/f(x)を定める。以下では、f(x)=xn-1の場合を例示する。また、I=(2Z)nとし、(2Z)nに属する線形独立なベクトルである基底からなる基底行列をBIとし、平文空間PをP∈P(BI)∩Znとする。さらにn次元のベクトルs=T(2,0,...,0)を定める。また、この例では、回路Copeを構成するゲートの集合をΓ=(+I, ×I)とする。ただし、この例の「+I」は、Zn上の二項加算を行いmod BIを計算するゲートを意味し、この例の「×I」は、Zn上の二項乗算を行いmod BIを計算するゲートを意味する。
【００２５】
＜鍵生成＞
Iと互いに素なベクトルv=T(v0,v1,...,vn-1)∈Znを選択し、その巡回行列rot(v)を秘密鍵Bskとする。さらに、秘密鍵Bskのエルミート標準形（Hermite Normal Form）である行列を公開鍵Bpkとする。なお、エルミート標準形とは、正則な正方整数行列に対して整数上の行基本変形を施して得られる上三角行列である。エルミート標準形が効率的に計算できることはよく知られている（例えば、「H. Cohen., "A course in computational algebraic number theory", GTM138, Springer, 1996」参照）。
【００２６】
＜暗号化＞
平文π∈Pに対して以下の処理が行われる。
【００２７】
(1)ユークリッド・ノルム‖r‖がL以下となるようにr∈Znをランダムに選ぶ。なお、Ｌはセキュリティパラメータである。
【００２８】
(2)φ'=π+r×s …(10)
を計算する。ただし、r×sは、rを係数とする多項式とsを係数とする多項式との乗算を意味する。
【００２９】
(3)φ=φ'mod Bpk …(11)
を暗号文とする。
【００３０】
＜復号＞
暗号文φ∈P(Bpk)∩Znに対し、以下の処理が行われる。
【００３１】
(1)φ'=φ mod Bsk …(12)
(2)π=φ mod BI …(13)
を平文とする。
【００３２】
＜評価＞
平文π1,...,πq∈P（qは正の整数）に対応する暗号文の組(φ1,...,φq)と回路Copeに対し、以下の処理が行われる。
【００３３】
(1) 回路Copeのゲート+I, ×Iをそれぞれ+J, ×Jに置き換えた回路Cope'を用い、Cope'(φ1,...,φq)を計算する。ただし、「+J」は、Zn上の二項加算を行いmod Bpkを計算するゲートを意味し、この例の「×J」は、Zn上の二項乗算を行いmod Bpkを計算するゲートを意味する。また、Cope'(φ1,...,φq)は、暗号文の組(φ1,...,φq)を回路Cope'に入力して得られる回路Cope'からの出力値を示す。
【００３４】
Cope'(φ1,...,φq)∈P(Bpk)∩Znをφとして式(12)(13)によって復号された値と、Cope(φ1,...,φq)とが等しくなる確率が圧倒的であるとき、準同型暗号方式の要件を満たすと判定される。非特許文献１の[THEOREM 8]には、2≦γxの場合に回路の深さdが以下の式(14)の条件を満たすとき、この準同型暗号方式の要件が満たされることが示されている。
【００３５】
【数６】
【００３６】
【数７】
ρDec=sup{ρ∈RE>0|Bρ⊂P(Bsk)} …(16)
Bρ={t∈REn|‖t‖<ρ} …(17)
である。なお、
【００３７】
【数８】
は、αの条件を満たすβの中で最大のものを意味する。また、sup{α}は集合αの上限を示し、RE>0は0よりも大きい実数を示し、REnはn次元の実数からなる実数環である。また、γxは任意のZnの元u,v∈Znに対して、
‖u×v‖≦γx・‖u‖・‖v‖ …(18)
となる最小の値を意味する。特に、f(x)=xn-1の場合には、
γx=√n …(19)
となる。なお、式(18)の演算子「×」の意味は式(10)と同様である。
【００３８】
また、
(b0*,...,bn-1*)={(Bsk)-1}* …(20)
とおくと、
【００３９】
【数９】
を満たす。なお、α*はαのエルミート共役（随伴作用素）を意味する。また、行列βに対するβ-1は、行列βの逆行列を意味する。
【００４０】
〔本形態の原理〕
以上を前提とし、本形態の原理について説明する。
【００４１】
式(20)のようにおいた場合、式(6)のスペクトルノルムの定義から、
【００４２】
【数１０】
の関係が成り立つ。また、式(7)のフロベニウスノルムの定義、及び式(9)の関係から、
【００４３】
【数１１】
の関係が成り立つ。よって、式(22)(23)から
【００４４】
【数１２】
の関係が成り立つ。また、式(8)より、
【００４５】
【数１３】
の関係が成り立つ。なお、式(25)の変形は、n×nの正則行列Aの固有値が逆行列A-1の固有値の逆数となることに基づく。なお、正則行列Aの固有方程式はf(t)=det(A-t・I)=0となり、その根tが固有値となる。ただし、det(α)は行列αの行列式であり、Iは単位行列である。また、逆行列A-1の固有方程式はg(t)=det(A-1-t・I)=det(t・A-1)・det((1/t)・I-A)=0となる。したがって、逆行列A-1の固有方程式はg(t)={(-t)n/det(A)}・f(1/t)=0となる。よって、正則行列Aの固有値は、正則行列Aの逆行列A-1の固有値の逆数となる。
【００４６】
式(24)(25)から
【００４７】
【数１４】
の関係が成り立ち、さらには、
【００４８】
【数１５】
の関係が成り立つ。さらに、式(21)より、
【００４９】
【数１６】
の関係が成り立つ。なお、秘密鍵Bskが対角化可能な行列である場合、
【００５０】
【数１７】
の関係が成り立つ。よって、秘密鍵Bskが対角化可能な行列である場合、式(28)(29)から、
【００５１】
【数１８】
の関係が成り立つ。これより、秘密鍵Bskが対角化可能な行列である場合、ρDecの範囲を制御するためには、秘密鍵Bskの固有値を制御すればよいことが分る。
【００５２】
一方、式(14)から、
【００５３】
【数１９】
の関係が成り立つ。
【００５４】
特に、f(x)=xn-1の場合にはγx=√n（式(19)）を満たすから、式(31)は以下のように変形できる。
【００５５】
2d・log2(√n・ρEnc)≦log2ρDec …(32)
よって、f(x)=xn-1の場合には、
【００５６】
【数２０】
の要件を満たせば、準同型暗号方式の要件が満たされることになる。
【００５７】
ここで、式(33)の要件を満たすようにρDecの範囲を制御することを考える。秘密鍵Bskが対角化可能な行列である場合、前述の式(30)の関係から
【００５８】
【数２１】
の関係を満たす場合には必ず式(33)を満たす。よって、秘密鍵Bskの各固有値λ(Bsk)の絶対値|λ(Bsk)|が
【００５９】
【数２２】
の関係を満たすように秘密鍵Bskが生成されれば、深さdの回路に対して必ず準同型暗号方式の要件が満たされることになる。また、例えば、暗号文への総当り攻撃に対する安全性を確保するために、
ρEnc≦n …(36)
とするのであれば、秘密鍵Bskの各固有値λ(Bsk)の絶対値|λ(Bsk)|が
【００６０】
【数２３】
の関係を満たすように秘密鍵Bskが生成されれば、深さdの回路に対して必ず準同型暗号方式の要件が満たされることになる。
【００６１】
以上に例示したように、秘密鍵Bskの各固有値λ(Bsk)の範囲を制御することで、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式を構築できる。本形態では、絶対値が所定値以上となるn個の任意値λi(i=0,..,n-1)を選択し、それらを固有値とする巡回行列rot(v)を生成して秘密鍵Bskを生成する。
【００６２】
まず、ωを１の原始n乗根とし、i行j列の要素をωi・j(0≦i,j＜n)とするn×nの行列を
W=(ωi・j)0≦i,j＜n …(38)
とする。この行列Wは離散フーリエ変換行列（discrete Fourier transform matrix）である。このとき、n×nの任意の巡回行列Cは、離散フーリエ変換行列Wで対角化可能である。すなわち、n×nの任意の巡回行列Cの各固有値が対角成分に並ぶn×nの対角行列をΛとした場合、
C=W・Λ・W-1 …(39)
の関係が成り立つ。これは、絶対値が所定値以上となる（例えば、λ(Bsk)=λi(i=0,..,n-1)とした式(35)や(37)を満たす）n個の任意値λi(i=0,..,n-1)を選択し、それらを固有値λi(i=0,..,n-1)とし、各固有値λi(i=0,..,n-1)が対角成分に並ぶn×nの対角行列Λを生成し、式(39)によって巡回行列Cを生成することによって、深さdの回路に対して必ず準同型暗号方式の要件を満たすような暗号鍵を生成できることを示している。
【００６３】
しかし、一般に、原始n乗根ωは複素数体の元であり、式(39)で生成された巡回行列Cの要素は複素数体の元となる。このように生成された巡回行列Cは、Gentry方式の秘密鍵Bskとして用いることはできない。前述のように、Gentry方式の秘密鍵Bskとして用いることができる巡回行列は、整数要素の行列（整数要素行列）である必要があるからである。よって、本形態では、n,ωを2のべき乗からなる整数とし、
m=ωn/2+1 …(40)
とおく。このとき、ωはmを法とする剰余環Z/mZにおいて１の原始n乗根となる。このような制約のもと式(39)で生成された巡回行列Cの要素は剰余環Z/mZの元となり、それらを整数に写像することで得られる（例えば、巡回行列Cの要素を整数とみなして得られる）n×nの巡回行列は、巡回行列rot(v)（式(3)）となる。このような巡回行列rot(v)は、Gentry方式の秘密鍵Bskとして用いることができる。さらに、このように生成された秘密鍵Bskのエルミート標準形を公開鍵Bpkとすることができる。これにより、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式の秘密鍵Bskと公開鍵Bpkとの鍵ペアが生成できる。
【００６４】
また、本形態では、式(39)をそのまま計算して上述の秘密鍵Bsk及び公開鍵Bpkを求めるよりも高速に、同様な性質を持つ秘密鍵Bsk及び公開鍵Bpkを求める方法を提供する。以下にそのことを説明する。
【００６５】
上述の離散フーリエ変換行列Wの逆行列W-1のi行j列の要素はω-i・j/nとなる。つまり、離散フーリエ変換行列Wの逆行列は
W-1=(ω-i・j/n)0≦i,j＜n …(41)
となる。また、各固有値λi(i=0,..,n-1)が対角成分に並ぶn×nの対角行列Λのi行j列の要素はλi・δi,jとなる。なお、δi,jはクロネッカーのデルタ（Kronecker delta）関数であり、i=jのときδi,j=1となり、i≠jのときδi,j=0となる関数である。よって、W・Λ・W-1のi行g行（0≦i,g＜n）の要素(W・Λ・W-1)i,gは
【００６６】
【数２４】
となる。クロネッカーのデルタ関数δi,jの性質から、式(42)は
【００６７】
【数２５】
と変形できる。前述のように、式(43)は巡回行列Cのi行g列の要素となる。
【００６８】
一方、T(λ0,...,λn-1)を離散フーリエ変換した結果をT(v'0,...,v'n-1)とすると、
【００６９】
【数２６】
の関係が成り立つ。また、T(v'0,...,v'n-1)から構成される巡回行列C'のi行g列の要素は、
【００７０】
【数２７】
となる。よって、式(43)(45)より、
C'=n・(W・Λ・W-1) …(46)
の関係が成り立つ。
【００７１】
ここで、T(λ0,...,λn-1)を離散フーリエ変換し、それによって得られたT(v'0,...,v'n-1)から巡回行列C'を構成するための演算量は、W・Λ・W-1の演算量よりも小さい。また、式(46)の巡回行列C'の各固有値はn・λi(i∈{0,...,N-1})となり、それぞれ、W・Λ・W-1の各固有値λi(i∈{0,...,N-1})よりも大きい。よって、巡回行列C'の各要素を整数に写像することで得られる（例えば、回行列C'の要素を整数とみなして得られる）n×nの巡回行列をGentry方式の秘密鍵Bskとし、秘密鍵Bskのエルミート標準形を公開鍵Bpkとしても、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式が実現できる。また、式(46)の巡回行列C'を1/n倍した行列を用いて秘密鍵Bskや公開鍵Bpkを生成しても同様な効果を得ることができる。また、例えば、
【００７２】
【数２８】
又は、
【００７３】
【数２９】
の関係を満たすように選択されたT(λ0,...,λn-1)を離散フーリエ変換し、それによって得られたT(v'0,...,v'n-1)から巡回行列C'を生成し、それから秘密鍵Bskや公開鍵Bpkを生成しても同様な効果を得ることができる。
【００７４】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
【００７５】
＜全体構成＞
図１は、実施形態のセキュリティシステムの全体構成を説明するための図である。
【００７６】
図１に例示するように、第１実施形態のセキュリティシステム１は、鍵生成装置１１と、暗号化装置１２−１〜Ｑ（Ｑは正の整数）と、復号装置１３とを有し、これらはネットワークを通じて通信可能に構成されている。
【００７７】
鍵生成装置１１は、Gentry方式の秘密鍵Bskと公開鍵Bpkとを生成する装置である。
【００７８】
暗号化装置１２−１〜Ｑは、それぞれ、平文π1,...,πq∈Pに対してGentry方式の暗号化処理を行いて暗号文φ1,...,φqを生成する公知の装置である。また、少なくとも一部の暗号化装置１２−１〜Ｑは、各暗号文φ1,...,φqを回路Copeに入力して暗号文Cope(φ1,...,φq)を生成する機能を備える。
【００７９】
復号装置１３は、暗号文Cope(φ1,...,φq)が入力され、それらにGentry方式の復号処理を施し、平文π1,...,πq∈Pを回路Copeに入力して得られる演算結果Cope(π1,...,πq)を出力する公知の装置である。
【００８０】
暗号化装置１２−１〜Ｑ及び復号装置１３は公知の装置であるため、以下では鍵生成装置１１の構成のみを説明する。
【００８１】
＜鍵生成装置１１の構成＞
図２は、実施形態の鍵生成装置の構成を説明するための図である。また、図３は、実施形態の鍵情報生成部の構成を説明するための図である。
【００８２】
図２に例示するように、本形態の鍵生成装置１１は、入力部１１１と、記憶部１１２と、制御部１１３と、設定部１１４，１１５と、任意値生成部１１６と、鍵情報生成部１１７とを有する。また、図３に例示するように、本形態の鍵情報生成部１１７は、離散フーリエ変換部１１７ａと、巡回行列生成部１１７ｂと、秘密鍵生成部１１７ｃと、公開鍵生成部１１７ｄとを有する。
【００８３】
鍵生成装置１１は、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)等からなる公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて構成される特別な装置である。入力部１１１は、例えば、入力インタフェースや入力ポートなどであり、記憶部１１２は、例えば、RAM、キャッシュメモリ、レジスタ、ハードディスク装置等から構成される記憶領域である。また、制御部１１３、設定部１１４，１１５、任意値生成部１１６及び鍵情報生成部１１７は、CPUに所定のプログラムが読み込まれて構成される処理部である。また、処理部の少なくとも一部が集積回路によって構成されてもよい。
【００８４】
＜鍵生成処理＞
次に、本形態の鍵生成処理を説明する。
【００８５】
図４（Ａ）（Ｂ）は、実施形態の鍵生成処理を説明するための図である。
【００８６】
鍵生成装置１１は、制御部１１３の制御のもと、以下の鍵生成処理を実行する。
【００８７】
図４（Ａ）に例示するように、まず、鍵生成装置１１（図２）の入力部１１１に、セキュリティパラメータである正の整数n,κと、回路Copeの深さを示す正の整数dとが入力され、これらが記憶部１１２に格納される。本形態の整数nは2のべき乗からなる。また、安全性の観点から、κは{2・log2(2・η-1)}/2以上の自然数であることが望ましい。なお、本形態では、準同型暗号方式の暗号鍵を生成するために、絶対値が所定値以上となるn個の任意値λi(i=0,...,n-1)を生成するが（後述）、この「所定値」が2・ηに相当する。
【００８８】
次に、設定部１１４に整数n,dが入力され、設定部１１４がこれらに対応するηを設定して記憶部１１２に格納する（ステップＳ１２）。
【００８９】
［ηの設定方法の例示］
本形態の設定部１１４は、例えば、
【００９０】
【数３０】
の演算によってηを設定する。なお、式(10)(15)に示したように、ρEncはn次元ベクトルφ'の最大値である。ρEncは、例えば定数として設定部１１４に設定されている。また、式(49)の代わりに、設定部１１４が、
【００９１】
【数３１】
の演算によってηを設定してもよい。また、ρEnc≦nなのであれば、設定部１１４が、以下の何れかの演算によってηを設定してもよい。
【００９２】
【数３２】
その他、式(49)〜(52)で定まる値よりも大きな値をηとしてもよい。例えば、式(49)〜(52)で定まる値の定数倍をηとしてもよい（［ηの設定方法の例示］の説明終わり）。
【００９３】
次に、設定部１１５に整数κが入力される。設定部１１５は、
ω=2κ …(53)
m=ωn/2+1 …(54)
の演算によってmを設定し、記憶部１１２に格納する（ステップＳ１３）。
【００９４】
次に、上記のように設定されたパラメータを用いて暗号鍵の生成が行われる。なお、ステップＳ１１からＳ１３の処理は毎回実行される必要はない。n,κ,d,m,ηの値に変化がないのであれば、以前に行われたステップＳ１１からＳ１３の処理で設定されたn,κ,d,m,ηを用いて暗号鍵の生成が実行されてもよい。また、ステップＳ１１からＳ１３の処理で設定されるパラメータが入力部１１１に入力され、暗号鍵の生成に用いられてもよい。
【００９５】
暗号鍵の生成を行う場合、まず、任意値生成部１１６にηとmとnが入力される。任意値生成部１１６は、絶対値が2・η（所定値）以上m未満となるn個の任意値λi(i=0,..,n-1)を生成し、記憶部１１２に格納する（ステップＳ１４）。なお、演算効率の面から、任意値λiの絶対値はm未満であることが望ましい。しかし、m未満という制約を外し、絶対値が2・η以上となるn個の任意値λi(i=0,..,n-1)が選択される構成でもよい。
【００９６】
次に、暗号鍵生成部１１７にn個の任意値λi(i=0,..,n-1)が入力される。暗号鍵生成部１１７は、n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【００９７】
【数３３】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として生成する（ステップＳ１５）。本形態では、準同型暗号方式の秘密鍵Bskと公開鍵Bpkとが生成される。以下に、ステップＳ１５の詳細を例示する。
【００９８】
［ステップＳ１５の詳細の例示］
図４（Ｂ）に例示するように、本形態のステップＳ１５では、まず、暗号鍵生成部１１７（図３）の離散フーリエ変換部１１７ａに、mとn個の任意値λi(i=0,..,n-1)とが入力される。離散フーリエ変換部１１７ａは、以下のように、mを法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施し、n個の要素v'i∈Z/mZ (i=0,..,n-1)を生成する。なお、Wは離散フーリエ変換行列である。
【００９９】
T(v'0,..,v'n-1)=W・T(λ0,..,λn-1) …(56)
さらに、離散フーリエ変換部１１７ａは、n個の要素v'i∈Z/mZ (i=0,..,n-1)を整数に写像したn個の要素vi∈Z (i=0,..,n-1)を生成する。なお、要素vi∈Z (i=0,..,n-1)の例は、要素v'i∈Z/mZ (i=0,..,n-1)を整数とみなした値、要素v'i∈Z/mZ (i=0,..,n-1)を整数とみなした値の定数倍値、その他、要素v'i∈Z/mZ (i=0,..,n-1)から整数へ単写した値などである。また、n個の要素vi∈Z (i=0,..,n-1)は、「n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素」に相当し、m=ωn/2+1を法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい。生成されたn個の要素vi∈Z (i=0,..,n-1)は、記憶部１１２に格納される（ステップＳ１５１）。
【０１００】
次に、巡回行列生成部１１７ｂに、生成されたn個の要素vi(i=0,..,n-1)が入力される。巡回行列生成部１１７ｂは、n個の要素viを用い、式(55)の巡回行列rot(v)を生成し、記憶部１１２に格納する（ステップＳ１５２）。
【０１０１】
次に、秘密鍵生成部１１７ｃに、巡回行列rot(v)が入力される。秘密鍵生成部１１７ｃは、巡回行列rot(v)を秘密鍵Bskとする。或いは、密鍵生成部１１７ｃは、巡回行列rot(v)の像であるn×nの整数要素行列を秘密鍵Bskとしてもよい。なお、当該整数要素行列の固有値の絶対値の最小値は、巡回行列rot(v)の固有値の絶対値の最小値以上であるこのような整数要素行列の例は、巡回行列rot(v)の各要素を整数倍した行列などである。また、その他、巡回行列rot(v)を特定可能な情報を秘密鍵Bskとして生成してもよい。以上のように生成された秘密鍵Bskは、記憶部１１２に格納される（ステップＳ１５３）。
【０１０２】
次に、公開鍵生成部１１７ｄに秘密鍵Bskが入力される。公開鍵生成部１１７ｄは、秘密鍵Bskを用い、上記の巡回行列rot(v)のエルミート標準形、又は、上記の整数要素行列のエルミート標準形を、公開鍵Bpkとして生成する。例えば、公開鍵生成部１１７ｄは、秘密鍵Bskのエルミート標準形を公開鍵Bpkとして生成する。生成された公開鍵Bpkは、記憶部１１２に格納される（ステップＳ１５３）。以上の処理により、深さdの回路に対して準同型暗号方式の要件を満たすGentry方式の秘密鍵Bskと公開鍵Bpkとの鍵ペアが生成された（［ステップＳ１５の詳細の例示］の説明終わり）。
【０１０３】
次に、出力部１１８に秘密鍵Bskと公開鍵Bpkとが入力され、出力部１１８がこれらを出力する（ステップＳ１６）。出力された公開鍵Bpkは、例えば、ネットワーク経由で各暗号化装置１２−１〜Ｑに送られる。また、出力された秘密鍵Bskは、例えば、暗号化された通信路などを用いて復号装置１３に送られる。
【０１０４】
〔第２実施形態〕
次に、本発明の第２実施形態と説明する。本形態は第１実施形態の変形例であり、n個の任意値λi(i=0,..,n-1)を対角成分に持つn×nの対角行列Λと、離散フーリエ変換行列Wと、その逆行列W-1とを用い、式(55)の巡回行列rot(v)を生成する。以下では、第１実施形態との相違点を中心に説明する。
【０１０５】
＜全体構成＞
図１を用いて第２実施形態のキュリティシステム２の全体構成を説明する。なお、第１実施形態と共通する部分については、第１実施形態と同じ参照番号を利用し、説明を省略する。図１に例示するように、第２実施形態のセキュリティシステム２は、鍵生成装置２１と、暗号化装置１２−１〜Ｑ（Ｑは正の整数）と、復号装置１３とを有し、これらはネットワークを通じて通信可能に構成されている。
【０１０６】
＜鍵生成装置２１の構成＞
本形態の鍵生成装置２１も、例えば、公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて構成される特別な装置である。図２に例示するように、本形態の鍵生成装置２１は、入力部１１１と、記憶部１１２と、制御部１１３と、設定部１１４，１１５と、任意値生成部１１６と、鍵情報生成部２１７とを有する。
【０１０７】
図５は、第２実施形態の鍵情報生成部２１７の構成を説明するための図である。図５に例示するように、本形態の鍵情報生成部２１７は、巡回行列生成部２１７ｂと、秘密鍵生成部１１７ｃと、公開鍵生成部１１７ｄとを有する。
【０１０８】
＜鍵生成処理＞
次に、図４（Ａ）を用い、本形態の鍵生成処理を説明する。
【０１０９】
鍵生成装置２１は、制御部１１３の制御のもと、以下の鍵生成処理を実行する。
【０１１０】
まず、第１実施形態と同様に、ステップＳ１１〜Ｓ１４の処理が実行される。ただし、本形態のステップＳ１２で設定されるηは、例えば、式(49)(51)で定まる値、又は、式(49)(51)で定まる値よりも大きな値であることが望ましい。
【０１１１】
次に、暗号鍵生成部２１７にn個の任意値λi(i=0,..,n-1)が入力される。暗号鍵生成部２１７は、n個の任意値λi(i=0,..,n-1)に離散フーリエ変換を施して得られるn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列rot(v)（式(55)）に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として生成する（ステップＳ２５）。本形態では、準同型暗号方式の秘密鍵Bskと公開鍵Bpkとが生成される。以下に、ステップＳ２５の詳細を例示する。
【０１１２】
［ステップＳ２５の詳細の例示］
図６は、第２実施形態のステップＳ２５の詳細を説明するための図である。
【０１１３】
図６に例示するように、本形態のステップＳ２５では、巡回行列生成部１１７ｂ（図５）に、mとn個の任意値λi(i=0,..,n-1)とが入力される。巡回行列生成部１１７ｂは、n個の任意値λi(i=0,..,n-1)を対角成分に持つn×nの対角行列Λと、離散フーリエ変換行列Wと、その逆行列W-1とを用い、剰余環Z/mZ上で、
rot'(v)=W・Λ・W-1 …(57)
の演算を行い、剰余環Z/mZの元を要素に持つ、n×nの巡回行列rot'(v)を生成する。次に、巡回行列生成部１１７ｂは、巡回行列rot'(v)の各要素を整数に写像したn×nの巡回行列rot(v)を生成する。なお、この場合のn×nの巡回行列rot(v)の要素の例は、巡回行列rot'(v)の要素を整数とみなした値、巡回行列rot'(v)の要素を整数とみなした値の定数倍値、その他、巡回行列rot'(v)の要素から整数へ単写した値などである。また、巡回行列rot(v)の要素は、「n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素」に相当し、m=ωn/2+1を法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい。生成されたn×nの巡回行列rot(v)は、記憶部１１２に格納される（ステップＳ２５２）。
【０１１４】
その後、第１実施形態と同様、ステップＳ１５３，Ｓ１５４の処理が実行される（［ステップＳ２５の詳細の例示］の説明終わり）。
【０１１５】
その後、第１実施形態と同様、ステップＳ１６の処理が実行される。
【０１１６】
〔その他の変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１実施形態では、ステップＳ１５１で、n個の要素v'i∈Z/mZ (i=0,..,n-1)を整数に写像したn個の要素vi∈Z (i=0,..,n-1)を生成し、ステップＳ１５２で、n個の要素viを用いて式(55)の巡回行列rot(v)を生成することとした。しかし、ステップＳ１５１でn個の要素v'i∈Z/mZ (i=0,..,n-1)をそのまま出力し、ステップＳ１５２で、n個の要素v'i∈Z/mZを用いて巡回行列rot'(v)を生成し、巡回行列rot'(v)の要素を整数に写像することで式(55)の巡回行列rot(v)を生成してもよい。
【０１１７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１２３】
１，２ セキュリティシステム
１１、２１ 鍵生成装置
【技術分野】
【０００１】
本発明は、暗号技術に関し、特に、準同型暗号方式の暗号鍵を生成する技術に関する。
【背景技術】
【０００２】
準同型暗号（homomorphic encryption）方式とは、ある平文集合に演算を施して得られる暗号文を、その平文集合に属する各々の平文の暗号文から構成できる、という性質を持つ暗号方式である。例えば、平文集合Sに属する平文M1,M2∈Sとし、加法及び乗法について準同型な準同型暗号方式の暗号化関数をEncとすると、以下の式(1)(2)の性質が成り立つ。
【０００３】
Enc(M1+M2)=Enc(M1)+Enc(M2) …(1)
Enc(M1・M2)=Enc(M1)・Enc(M2) …(2)
準同型暗号方式を用いれば、暗号文どうしの加算や乗算により、暗号文を復号することなく、加算や乗算を行った演算結果の暗号文を得ることができる。例えば、データを準同型暗号方式で暗号化しておけば、１以上の演算ゲート（以下「ゲート」）から構成される任意の演算回路（以下「回路」）にデータを入力して演算結果を得る計算を、暗号文のまま行うことができる。この性質はプログラム秘匿やデータ秘匿において非常に重要である。そのため、準同型暗号方式を構成する研究が長年行われてきた。しかしながら、加法及び乗法について準同型な準同型暗号方式の構成に成功したと認められる研究はいまだなく、近年はこのような準同型暗号方式が存在するかどうかの研究が主題であった。このような中、任意の深さの回路に適用可能で加法及び乗法について準同型な準同型暗号方式が存在することを主張する画期的な論文が発表された（非特許文献１）。なお、回路の深さとは、その回路の入力ゲートから出力ゲートまでのゲート数の最大値を意味する。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】C. Gentry., "Fully Homomorphic encryption using ideal lattices", STOC 2009, pp. 169-178, 2009
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、非特許文献１では、十分な鍵長を確保して十分な演算時間を費やすならば理論的に機能する準同型暗号方式が存在することのみが示されるにとどまり、準同型暗号方式の実用的な構成方法は明らかにされていない。すなわち、非特許文献１の準同型暗号方式は、各平文にそれぞれ対応する暗号文間の演算結果と、各平文間の演算結果に対する暗号文との間に許容範囲内の誤差があったとしても、前者の暗号文間の演算結果を復号した結果が、後者の演算結果に対する暗号文を復号した結果と等しくなるように構成されている。そして、非特許文献１には、大きな鍵長の暗号鍵を用いることで上記の誤差を許容範囲内に収め、準同型暗号方式を構成することが示されている。ところが、非特許文献１の準同型暗号方式には、回路の深さが深くなるにつれて上記の誤差が蓄積されて大きくなる性質がある。そのため、非特許文献１の準同型暗号方式を実用的に用いるためには、回路の深さと誤差との関係について具体的な評価を行い、誤差が許容範囲を超える前に誤差を再び小さくするといった処理を行う必要がある。しかしながら、非特許文献１に開示された内容では誤差を再び小さくする処理を行うことができる鍵長や、その処理の手数は膨大と考えられ、実用的な程度にはいたっていない。
【課題を解決するための手段】
【０００６】
本発明では、回路の深さと誤差との関係を評価し、その評価結果を暗号化処理や復号処理に反映させるというアプローチではなく、鍵生成処理の時点で所望の範囲に誤差を収めることが可能な暗号鍵を生成しておくというアプローチをとる。すなわち、本発明の鍵生成処理では、絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成し、n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【０００７】
【数１】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力する。
【発明の効果】
【０００８】
本発明で生成された暗号鍵を用いた場合の上記誤差の範囲は、任意値λiが採りうる範囲に依存する。よって、回路の深さに応じた適切な範囲から任意値λiを選択することで、容易に実用的な準同型暗号方式を構成することができる。
【図面の簡単な説明】
【０００９】
【図１】実施形態のセキュリティシステムの全体構成を説明するための図。
【図２】実施形態のセキュリティシステムの全体構成を説明するための図。
【図３】実施形態の鍵生成装置の構成を説明するための図。
【図４】実施形態の鍵生成処理を説明するための図。
【図５】第２実施形態の鍵情報生成部の構成を説明するための図。
【図６】第２実施形態のステップＳ２５の詳細を説明するための図。
【発明を実施するための形態】
【００１０】
以下、図面を参照して本発明の実施形態を説明する。
【００１１】
〔定義〕
まず、本形態で用いる基本的な用語を定義する。
【００１２】
＜格子(lattice)＞
格子とは、Zn中の離散的な加法的部分群を意味する。格子は、Zn中の線形独立な基底b0,b2,...,bn-1∈Znの線形結合で表現される。なお、Znはn次元（nは整数）の整数からなる整数環である。また、基底を並べたn×nの行列B=(b0,b2,...,bn-1)を基底行列と呼ぶ。
【００１３】
＜イデアル格子(ideal lattice)＞
格子がイデアル格子であるとは、その格子と加群として同型な剰余環R=Z[x]/f(x)のイデアルが存在することである。なお、Z[x]は整数係数多項式環であり、f(x)は最高次の係数が１である（monicな）次数nの整数係数一変数多項式である。また、剰余環Rのイデアルとは、剰余環Rの加法的部分群であり、その元に対して剰余環Rの元を左右どちらから掛けても、その演算結果が当該加法的部分群の元となるものを意味する（両側イデアルと呼ぶ場合もある）。また、剰余環Rのイデアルとして最も単純なものは剰余環Rの１つの元を用いて生成される単項イデアルである。
【００１４】
＜巡回行列(circulant matrix)＞
巡回行列（「循環行列」とも呼ばれる）とは、各行ベクトルが1つ前の行ベクトルの要素を1つ巡回させたように構成された行列である。
【００１５】
剰余環Rの１つの元
V=v0+v1・x+...+vn-1・xn-1 mod f(x)
で生成される単項イデアルの元は、V, V・x,..., V・xn-1の線形結合で書ける。ただし、ベクトルv=T(v0,v1,...,vn-1)∈Znとし、T(α)をαの転置とする。本形態では、この生成系のベクトルv=T(v0,v1,...,vn-1)∈Znを並べた巡回行列を巡回行列rot(v)と表現する。特に、f(x)=xn-1のとき、巡回行列rot(v)は以下のようになる。
【００１６】
【数２】
f(x)=xn-1のとき、巡回行列rot(v)は基底行列Bとなる。
【００１７】
＜半開基本平行体（half-open parallelepiped）＞
基底行列Bに対して、
P(B)={B・T(x0,x1,...,xn-1)|-1/2≦xi≦1/2}2 …(4)
を半開基本並行体と呼ぶ。
【００１８】
＜格子による剰余＞
基底行列Bに対応する基底で構成される格子をL(B)と表現する。ベクトルt∈Znについて、t-t'∈L(B)かつt'∈P(B)を満たすベクトルt'∈Znを
t mod B …(5)
と表現し、基底行列Bとベクトルtに対してベクトルt'を求める演算をtのBによる剰余と呼ぶ。
【００１９】
＜ノルム＞
ベクトルαのユークリッドノルム（Euclid norm）を‖α‖と表現する。また、n次正方行列Αのスペクトルノルム（spectral norm）を‖Α‖を表現する。‖Α‖は、任意のn次元ベクトルXに対し、以下のように定義される。
【００２０】
【数３】
また、n次正方行列Αのフロベニウスノルム（frobenius norm）を‖Α‖Fを表現する。‖Α‖Fは、Αのi行j列の要素をαij(0≦i,j＜n)とした場合に（A=(αij)0≦i,j＜n）、以下のように定義される。
【００２１】
【数４】
また、n次正方行列Αの随伴行列をΑ*とし、λ|max|(Α*・Α)をΑ*・Αの固有値の絶対値の最大値とし、λ|min|(Α*・Α)をΑ*・Αの固有値の絶対値の最小値と表現する。この場合、
【００２２】
【数５】
となることがよく知られている。また、
‖Α‖≦‖Α‖F …(9)
を満たすことがよく知られている。
【００２３】
〔非特許文献１の準同型暗号方式〕
次に、本形態の前提となる非特許文献１の準同型暗号方式（以下「Gentry方式」）の一例を示す。
【００２４】
まず、剰余環R=Z[x]/f(x)を定める。以下では、f(x)=xn-1の場合を例示する。また、I=(2Z)nとし、(2Z)nに属する線形独立なベクトルである基底からなる基底行列をBIとし、平文空間PをP∈P(BI)∩Znとする。さらにn次元のベクトルs=T(2,0,...,0)を定める。また、この例では、回路Copeを構成するゲートの集合をΓ=(+I, ×I)とする。ただし、この例の「+I」は、Zn上の二項加算を行いmod BIを計算するゲートを意味し、この例の「×I」は、Zn上の二項乗算を行いmod BIを計算するゲートを意味する。
【００２５】
＜鍵生成＞
Iと互いに素なベクトルv=T(v0,v1,...,vn-1)∈Znを選択し、その巡回行列rot(v)を秘密鍵Bskとする。さらに、秘密鍵Bskのエルミート標準形（Hermite Normal Form）である行列を公開鍵Bpkとする。なお、エルミート標準形とは、正則な正方整数行列に対して整数上の行基本変形を施して得られる上三角行列である。エルミート標準形が効率的に計算できることはよく知られている（例えば、「H. Cohen., "A course in computational algebraic number theory", GTM138, Springer, 1996」参照）。
【００２６】
＜暗号化＞
平文π∈Pに対して以下の処理が行われる。
【００２７】
(1)ユークリッド・ノルム‖r‖がL以下となるようにr∈Znをランダムに選ぶ。なお、Ｌはセキュリティパラメータである。
【００２８】
(2)φ'=π+r×s …(10)
を計算する。ただし、r×sは、rを係数とする多項式とsを係数とする多項式との乗算を意味する。
【００２９】
(3)φ=φ'mod Bpk …(11)
を暗号文とする。
【００３０】
＜復号＞
暗号文φ∈P(Bpk)∩Znに対し、以下の処理が行われる。
【００３１】
(1)φ'=φ mod Bsk …(12)
(2)π=φ mod BI …(13)
を平文とする。
【００３２】
＜評価＞
平文π1,...,πq∈P（qは正の整数）に対応する暗号文の組(φ1,...,φq)と回路Copeに対し、以下の処理が行われる。
【００３３】
(1) 回路Copeのゲート+I, ×Iをそれぞれ+J, ×Jに置き換えた回路Cope'を用い、Cope'(φ1,...,φq)を計算する。ただし、「+J」は、Zn上の二項加算を行いmod Bpkを計算するゲートを意味し、この例の「×J」は、Zn上の二項乗算を行いmod Bpkを計算するゲートを意味する。また、Cope'(φ1,...,φq)は、暗号文の組(φ1,...,φq)を回路Cope'に入力して得られる回路Cope'からの出力値を示す。
【００３４】
Cope'(φ1,...,φq)∈P(Bpk)∩Znをφとして式(12)(13)によって復号された値と、Cope(φ1,...,φq)とが等しくなる確率が圧倒的であるとき、準同型暗号方式の要件を満たすと判定される。非特許文献１の[THEOREM 8]には、2≦γxの場合に回路の深さdが以下の式(14)の条件を満たすとき、この準同型暗号方式の要件が満たされることが示されている。
【００３５】
【数６】
【００３６】
【数７】
ρDec=sup{ρ∈RE>0|Bρ⊂P(Bsk)} …(16)
Bρ={t∈REn|‖t‖<ρ} …(17)
である。なお、
【００３７】
【数８】
は、αの条件を満たすβの中で最大のものを意味する。また、sup{α}は集合αの上限を示し、RE>0は0よりも大きい実数を示し、REnはn次元の実数からなる実数環である。また、γxは任意のZnの元u,v∈Znに対して、
‖u×v‖≦γx・‖u‖・‖v‖ …(18)
となる最小の値を意味する。特に、f(x)=xn-1の場合には、
γx=√n …(19)
となる。なお、式(18)の演算子「×」の意味は式(10)と同様である。
【００３８】
また、
(b0*,...,bn-1*)={(Bsk)-1}* …(20)
とおくと、
【００３９】
【数９】
を満たす。なお、α*はαのエルミート共役（随伴作用素）を意味する。また、行列βに対するβ-1は、行列βの逆行列を意味する。
【００４０】
〔本形態の原理〕
以上を前提とし、本形態の原理について説明する。
【００４１】
式(20)のようにおいた場合、式(6)のスペクトルノルムの定義から、
【００４２】
【数１０】
の関係が成り立つ。また、式(7)のフロベニウスノルムの定義、及び式(9)の関係から、
【００４３】
【数１１】
の関係が成り立つ。よって、式(22)(23)から
【００４４】
【数１２】
の関係が成り立つ。また、式(8)より、
【００４５】
【数１３】
の関係が成り立つ。なお、式(25)の変形は、n×nの正則行列Aの固有値が逆行列A-1の固有値の逆数となることに基づく。なお、正則行列Aの固有方程式はf(t)=det(A-t・I)=0となり、その根tが固有値となる。ただし、det(α)は行列αの行列式であり、Iは単位行列である。また、逆行列A-1の固有方程式はg(t)=det(A-1-t・I)=det(t・A-1)・det((1/t)・I-A)=0となる。したがって、逆行列A-1の固有方程式はg(t)={(-t)n/det(A)}・f(1/t)=0となる。よって、正則行列Aの固有値は、正則行列Aの逆行列A-1の固有値の逆数となる。
【００４６】
式(24)(25)から
【００４７】
【数１４】
の関係が成り立ち、さらには、
【００４８】
【数１５】
の関係が成り立つ。さらに、式(21)より、
【００４９】
【数１６】
の関係が成り立つ。なお、秘密鍵Bskが対角化可能な行列である場合、
【００５０】
【数１７】
の関係が成り立つ。よって、秘密鍵Bskが対角化可能な行列である場合、式(28)(29)から、
【００５１】
【数１８】
の関係が成り立つ。これより、秘密鍵Bskが対角化可能な行列である場合、ρDecの範囲を制御するためには、秘密鍵Bskの固有値を制御すればよいことが分る。
【００５２】
一方、式(14)から、
【００５３】
【数１９】
の関係が成り立つ。
【００５４】
特に、f(x)=xn-1の場合にはγx=√n（式(19)）を満たすから、式(31)は以下のように変形できる。
【００５５】
2d・log2(√n・ρEnc)≦log2ρDec …(32)
よって、f(x)=xn-1の場合には、
【００５６】
【数２０】
の要件を満たせば、準同型暗号方式の要件が満たされることになる。
【００５７】
ここで、式(33)の要件を満たすようにρDecの範囲を制御することを考える。秘密鍵Bskが対角化可能な行列である場合、前述の式(30)の関係から
【００５８】
【数２１】
の関係を満たす場合には必ず式(33)を満たす。よって、秘密鍵Bskの各固有値λ(Bsk)の絶対値|λ(Bsk)|が
【００５９】
【数２２】
の関係を満たすように秘密鍵Bskが生成されれば、深さdの回路に対して必ず準同型暗号方式の要件が満たされることになる。また、例えば、暗号文への総当り攻撃に対する安全性を確保するために、
ρEnc≦n …(36)
とするのであれば、秘密鍵Bskの各固有値λ(Bsk)の絶対値|λ(Bsk)|が
【００６０】
【数２３】
の関係を満たすように秘密鍵Bskが生成されれば、深さdの回路に対して必ず準同型暗号方式の要件が満たされることになる。
【００６１】
以上に例示したように、秘密鍵Bskの各固有値λ(Bsk)の範囲を制御することで、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式を構築できる。本形態では、絶対値が所定値以上となるn個の任意値λi(i=0,..,n-1)を選択し、それらを固有値とする巡回行列rot(v)を生成して秘密鍵Bskを生成する。
【００６２】
まず、ωを１の原始n乗根とし、i行j列の要素をωi・j(0≦i,j＜n)とするn×nの行列を
W=(ωi・j)0≦i,j＜n …(38)
とする。この行列Wは離散フーリエ変換行列（discrete Fourier transform matrix）である。このとき、n×nの任意の巡回行列Cは、離散フーリエ変換行列Wで対角化可能である。すなわち、n×nの任意の巡回行列Cの各固有値が対角成分に並ぶn×nの対角行列をΛとした場合、
C=W・Λ・W-1 …(39)
の関係が成り立つ。これは、絶対値が所定値以上となる（例えば、λ(Bsk)=λi(i=0,..,n-1)とした式(35)や(37)を満たす）n個の任意値λi(i=0,..,n-1)を選択し、それらを固有値λi(i=0,..,n-1)とし、各固有値λi(i=0,..,n-1)が対角成分に並ぶn×nの対角行列Λを生成し、式(39)によって巡回行列Cを生成することによって、深さdの回路に対して必ず準同型暗号方式の要件を満たすような暗号鍵を生成できることを示している。
【００６３】
しかし、一般に、原始n乗根ωは複素数体の元であり、式(39)で生成された巡回行列Cの要素は複素数体の元となる。このように生成された巡回行列Cは、Gentry方式の秘密鍵Bskとして用いることはできない。前述のように、Gentry方式の秘密鍵Bskとして用いることができる巡回行列は、整数要素の行列（整数要素行列）である必要があるからである。よって、本形態では、n,ωを2のべき乗からなる整数とし、
m=ωn/2+1 …(40)
とおく。このとき、ωはmを法とする剰余環Z/mZにおいて１の原始n乗根となる。このような制約のもと式(39)で生成された巡回行列Cの要素は剰余環Z/mZの元となり、それらを整数に写像することで得られる（例えば、巡回行列Cの要素を整数とみなして得られる）n×nの巡回行列は、巡回行列rot(v)（式(3)）となる。このような巡回行列rot(v)は、Gentry方式の秘密鍵Bskとして用いることができる。さらに、このように生成された秘密鍵Bskのエルミート標準形を公開鍵Bpkとすることができる。これにより、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式の秘密鍵Bskと公開鍵Bpkとの鍵ペアが生成できる。
【００６４】
また、本形態では、式(39)をそのまま計算して上述の秘密鍵Bsk及び公開鍵Bpkを求めるよりも高速に、同様な性質を持つ秘密鍵Bsk及び公開鍵Bpkを求める方法を提供する。以下にそのことを説明する。
【００６５】
上述の離散フーリエ変換行列Wの逆行列W-1のi行j列の要素はω-i・j/nとなる。つまり、離散フーリエ変換行列Wの逆行列は
W-1=(ω-i・j/n)0≦i,j＜n …(41)
となる。また、各固有値λi(i=0,..,n-1)が対角成分に並ぶn×nの対角行列Λのi行j列の要素はλi・δi,jとなる。なお、δi,jはクロネッカーのデルタ（Kronecker delta）関数であり、i=jのときδi,j=1となり、i≠jのときδi,j=0となる関数である。よって、W・Λ・W-1のi行g行（0≦i,g＜n）の要素(W・Λ・W-1)i,gは
【００６６】
【数２４】
となる。クロネッカーのデルタ関数δi,jの性質から、式(42)は
【００６７】
【数２５】
と変形できる。前述のように、式(43)は巡回行列Cのi行g列の要素となる。
【００６８】
一方、T(λ0,...,λn-1)を離散フーリエ変換した結果をT(v'0,...,v'n-1)とすると、
【００６９】
【数２６】
の関係が成り立つ。また、T(v'0,...,v'n-1)から構成される巡回行列C'のi行g列の要素は、
【００７０】
【数２７】
となる。よって、式(43)(45)より、
C'=n・(W・Λ・W-1) …(46)
の関係が成り立つ。
【００７１】
ここで、T(λ0,...,λn-1)を離散フーリエ変換し、それによって得られたT(v'0,...,v'n-1)から巡回行列C'を構成するための演算量は、W・Λ・W-1の演算量よりも小さい。また、式(46)の巡回行列C'の各固有値はn・λi(i∈{0,...,N-1})となり、それぞれ、W・Λ・W-1の各固有値λi(i∈{0,...,N-1})よりも大きい。よって、巡回行列C'の各要素を整数に写像することで得られる（例えば、回行列C'の要素を整数とみなして得られる）n×nの巡回行列をGentry方式の秘密鍵Bskとし、秘密鍵Bskのエルミート標準形を公開鍵Bpkとしても、所望の深さdの回路に対して準同型暗号方式の要件を満たすGentry方式が実現できる。また、式(46)の巡回行列C'を1/n倍した行列を用いて秘密鍵Bskや公開鍵Bpkを生成しても同様な効果を得ることができる。また、例えば、
【００７２】
【数２８】
又は、
【００７３】
【数２９】
の関係を満たすように選択されたT(λ0,...,λn-1)を離散フーリエ変換し、それによって得られたT(v'0,...,v'n-1)から巡回行列C'を生成し、それから秘密鍵Bskや公開鍵Bpkを生成しても同様な効果を得ることができる。
【００７４】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
【００７５】
＜全体構成＞
図１は、実施形態のセキュリティシステムの全体構成を説明するための図である。
【００７６】
図１に例示するように、第１実施形態のセキュリティシステム１は、鍵生成装置１１と、暗号化装置１２−１〜Ｑ（Ｑは正の整数）と、復号装置１３とを有し、これらはネットワークを通じて通信可能に構成されている。
【００７７】
鍵生成装置１１は、Gentry方式の秘密鍵Bskと公開鍵Bpkとを生成する装置である。
【００７８】
暗号化装置１２−１〜Ｑは、それぞれ、平文π1,...,πq∈Pに対してGentry方式の暗号化処理を行いて暗号文φ1,...,φqを生成する公知の装置である。また、少なくとも一部の暗号化装置１２−１〜Ｑは、各暗号文φ1,...,φqを回路Copeに入力して暗号文Cope(φ1,...,φq)を生成する機能を備える。
【００７９】
復号装置１３は、暗号文Cope(φ1,...,φq)が入力され、それらにGentry方式の復号処理を施し、平文π1,...,πq∈Pを回路Copeに入力して得られる演算結果Cope(π1,...,πq)を出力する公知の装置である。
【００８０】
暗号化装置１２−１〜Ｑ及び復号装置１３は公知の装置であるため、以下では鍵生成装置１１の構成のみを説明する。
【００８１】
＜鍵生成装置１１の構成＞
図２は、実施形態の鍵生成装置の構成を説明するための図である。また、図３は、実施形態の鍵情報生成部の構成を説明するための図である。
【００８２】
図２に例示するように、本形態の鍵生成装置１１は、入力部１１１と、記憶部１１２と、制御部１１３と、設定部１１４，１１５と、任意値生成部１１６と、鍵情報生成部１１７とを有する。また、図３に例示するように、本形態の鍵情報生成部１１７は、離散フーリエ変換部１１７ａと、巡回行列生成部１１７ｂと、秘密鍵生成部１１７ｃと、公開鍵生成部１１７ｄとを有する。
【００８３】
鍵生成装置１１は、例えば、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)等からなる公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて構成される特別な装置である。入力部１１１は、例えば、入力インタフェースや入力ポートなどであり、記憶部１１２は、例えば、RAM、キャッシュメモリ、レジスタ、ハードディスク装置等から構成される記憶領域である。また、制御部１１３、設定部１１４，１１５、任意値生成部１１６及び鍵情報生成部１１７は、CPUに所定のプログラムが読み込まれて構成される処理部である。また、処理部の少なくとも一部が集積回路によって構成されてもよい。
【００８４】
＜鍵生成処理＞
次に、本形態の鍵生成処理を説明する。
【００８５】
図４（Ａ）（Ｂ）は、実施形態の鍵生成処理を説明するための図である。
【００８６】
鍵生成装置１１は、制御部１１３の制御のもと、以下の鍵生成処理を実行する。
【００８７】
図４（Ａ）に例示するように、まず、鍵生成装置１１（図２）の入力部１１１に、セキュリティパラメータである正の整数n,κと、回路Copeの深さを示す正の整数dとが入力され、これらが記憶部１１２に格納される。本形態の整数nは2のべき乗からなる。また、安全性の観点から、κは{2・log2(2・η-1)}/2以上の自然数であることが望ましい。なお、本形態では、準同型暗号方式の暗号鍵を生成するために、絶対値が所定値以上となるn個の任意値λi(i=0,...,n-1)を生成するが（後述）、この「所定値」が2・ηに相当する。
【００８８】
次に、設定部１１４に整数n,dが入力され、設定部１１４がこれらに対応するηを設定して記憶部１１２に格納する（ステップＳ１２）。
【００８９】
［ηの設定方法の例示］
本形態の設定部１１４は、例えば、
【００９０】
【数３０】
の演算によってηを設定する。なお、式(10)(15)に示したように、ρEncはn次元ベクトルφ'の最大値である。ρEncは、例えば定数として設定部１１４に設定されている。また、式(49)の代わりに、設定部１１４が、
【００９１】
【数３１】
の演算によってηを設定してもよい。また、ρEnc≦nなのであれば、設定部１１４が、以下の何れかの演算によってηを設定してもよい。
【００９２】
【数３２】
その他、式(49)〜(52)で定まる値よりも大きな値をηとしてもよい。例えば、式(49)〜(52)で定まる値の定数倍をηとしてもよい（［ηの設定方法の例示］の説明終わり）。
【００９３】
次に、設定部１１５に整数κが入力される。設定部１１５は、
ω=2κ …(53)
m=ωn/2+1 …(54)
の演算によってmを設定し、記憶部１１２に格納する（ステップＳ１３）。
【００９４】
次に、上記のように設定されたパラメータを用いて暗号鍵の生成が行われる。なお、ステップＳ１１からＳ１３の処理は毎回実行される必要はない。n,κ,d,m,ηの値に変化がないのであれば、以前に行われたステップＳ１１からＳ１３の処理で設定されたn,κ,d,m,ηを用いて暗号鍵の生成が実行されてもよい。また、ステップＳ１１からＳ１３の処理で設定されるパラメータが入力部１１１に入力され、暗号鍵の生成に用いられてもよい。
【００９５】
暗号鍵の生成を行う場合、まず、任意値生成部１１６にηとmとnが入力される。任意値生成部１１６は、絶対値が2・η（所定値）以上m未満となるn個の任意値λi(i=0,..,n-1)を生成し、記憶部１１２に格納する（ステップＳ１４）。なお、演算効率の面から、任意値λiの絶対値はm未満であることが望ましい。しかし、m未満という制約を外し、絶対値が2・η以上となるn個の任意値λi(i=0,..,n-1)が選択される構成でもよい。
【００９６】
次に、暗号鍵生成部１１７にn個の任意値λi(i=0,..,n-1)が入力される。暗号鍵生成部１１７は、n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【００９７】
【数３３】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として生成する（ステップＳ１５）。本形態では、準同型暗号方式の秘密鍵Bskと公開鍵Bpkとが生成される。以下に、ステップＳ１５の詳細を例示する。
【００９８】
［ステップＳ１５の詳細の例示］
図４（Ｂ）に例示するように、本形態のステップＳ１５では、まず、暗号鍵生成部１１７（図３）の離散フーリエ変換部１１７ａに、mとn個の任意値λi(i=0,..,n-1)とが入力される。離散フーリエ変換部１１７ａは、以下のように、mを法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施し、n個の要素v'i∈Z/mZ (i=0,..,n-1)を生成する。なお、Wは離散フーリエ変換行列である。
【００９９】
T(v'0,..,v'n-1)=W・T(λ0,..,λn-1) …(56)
さらに、離散フーリエ変換部１１７ａは、n個の要素v'i∈Z/mZ (i=0,..,n-1)を整数に写像したn個の要素vi∈Z (i=0,..,n-1)を生成する。なお、要素vi∈Z (i=0,..,n-1)の例は、要素v'i∈Z/mZ (i=0,..,n-1)を整数とみなした値、要素v'i∈Z/mZ (i=0,..,n-1)を整数とみなした値の定数倍値、その他、要素v'i∈Z/mZ (i=0,..,n-1)から整数へ単写した値などである。また、n個の要素vi∈Z (i=0,..,n-1)は、「n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素」に相当し、m=ωn/2+1を法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい。生成されたn個の要素vi∈Z (i=0,..,n-1)は、記憶部１１２に格納される（ステップＳ１５１）。
【０１００】
次に、巡回行列生成部１１７ｂに、生成されたn個の要素vi(i=0,..,n-1)が入力される。巡回行列生成部１１７ｂは、n個の要素viを用い、式(55)の巡回行列rot(v)を生成し、記憶部１１２に格納する（ステップＳ１５２）。
【０１０１】
次に、秘密鍵生成部１１７ｃに、巡回行列rot(v)が入力される。秘密鍵生成部１１７ｃは、巡回行列rot(v)を秘密鍵Bskとする。或いは、密鍵生成部１１７ｃは、巡回行列rot(v)の像であるn×nの整数要素行列を秘密鍵Bskとしてもよい。なお、当該整数要素行列の固有値の絶対値の最小値は、巡回行列rot(v)の固有値の絶対値の最小値以上であるこのような整数要素行列の例は、巡回行列rot(v)の各要素を整数倍した行列などである。また、その他、巡回行列rot(v)を特定可能な情報を秘密鍵Bskとして生成してもよい。以上のように生成された秘密鍵Bskは、記憶部１１２に格納される（ステップＳ１５３）。
【０１０２】
次に、公開鍵生成部１１７ｄに秘密鍵Bskが入力される。公開鍵生成部１１７ｄは、秘密鍵Bskを用い、上記の巡回行列rot(v)のエルミート標準形、又は、上記の整数要素行列のエルミート標準形を、公開鍵Bpkとして生成する。例えば、公開鍵生成部１１７ｄは、秘密鍵Bskのエルミート標準形を公開鍵Bpkとして生成する。生成された公開鍵Bpkは、記憶部１１２に格納される（ステップＳ１５３）。以上の処理により、深さdの回路に対して準同型暗号方式の要件を満たすGentry方式の秘密鍵Bskと公開鍵Bpkとの鍵ペアが生成された（［ステップＳ１５の詳細の例示］の説明終わり）。
【０１０３】
次に、出力部１１８に秘密鍵Bskと公開鍵Bpkとが入力され、出力部１１８がこれらを出力する（ステップＳ１６）。出力された公開鍵Bpkは、例えば、ネットワーク経由で各暗号化装置１２−１〜Ｑに送られる。また、出力された秘密鍵Bskは、例えば、暗号化された通信路などを用いて復号装置１３に送られる。
【０１０４】
〔第２実施形態〕
次に、本発明の第２実施形態と説明する。本形態は第１実施形態の変形例であり、n個の任意値λi(i=0,..,n-1)を対角成分に持つn×nの対角行列Λと、離散フーリエ変換行列Wと、その逆行列W-1とを用い、式(55)の巡回行列rot(v)を生成する。以下では、第１実施形態との相違点を中心に説明する。
【０１０５】
＜全体構成＞
図１を用いて第２実施形態のキュリティシステム２の全体構成を説明する。なお、第１実施形態と共通する部分については、第１実施形態と同じ参照番号を利用し、説明を省略する。図１に例示するように、第２実施形態のセキュリティシステム２は、鍵生成装置２１と、暗号化装置１２−１〜Ｑ（Ｑは正の整数）と、復号装置１３とを有し、これらはネットワークを通じて通信可能に構成されている。
【０１０６】
＜鍵生成装置２１の構成＞
本形態の鍵生成装置２１も、例えば、公知のコンピュータ又は専用のコンピュータに所定のプログラムが読み込まれて構成される特別な装置である。図２に例示するように、本形態の鍵生成装置２１は、入力部１１１と、記憶部１１２と、制御部１１３と、設定部１１４，１１５と、任意値生成部１１６と、鍵情報生成部２１７とを有する。
【０１０７】
図５は、第２実施形態の鍵情報生成部２１７の構成を説明するための図である。図５に例示するように、本形態の鍵情報生成部２１７は、巡回行列生成部２１７ｂと、秘密鍵生成部１１７ｃと、公開鍵生成部１１７ｄとを有する。
【０１０８】
＜鍵生成処理＞
次に、図４（Ａ）を用い、本形態の鍵生成処理を説明する。
【０１０９】
鍵生成装置２１は、制御部１１３の制御のもと、以下の鍵生成処理を実行する。
【０１１０】
まず、第１実施形態と同様に、ステップＳ１１〜Ｓ１４の処理が実行される。ただし、本形態のステップＳ１２で設定されるηは、例えば、式(49)(51)で定まる値、又は、式(49)(51)で定まる値よりも大きな値であることが望ましい。
【０１１１】
次に、暗号鍵生成部２１７にn個の任意値λi(i=0,..,n-1)が入力される。暗号鍵生成部２１７は、n個の任意値λi(i=0,..,n-1)に離散フーリエ変換を施して得られるn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列rot(v)（式(55)）に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として生成する（ステップＳ２５）。本形態では、準同型暗号方式の秘密鍵Bskと公開鍵Bpkとが生成される。以下に、ステップＳ２５の詳細を例示する。
【０１１２】
［ステップＳ２５の詳細の例示］
図６は、第２実施形態のステップＳ２５の詳細を説明するための図である。
【０１１３】
図６に例示するように、本形態のステップＳ２５では、巡回行列生成部１１７ｂ（図５）に、mとn個の任意値λi(i=0,..,n-1)とが入力される。巡回行列生成部１１７ｂは、n個の任意値λi(i=0,..,n-1)を対角成分に持つn×nの対角行列Λと、離散フーリエ変換行列Wと、その逆行列W-1とを用い、剰余環Z/mZ上で、
rot'(v)=W・Λ・W-1 …(57)
の演算を行い、剰余環Z/mZの元を要素に持つ、n×nの巡回行列rot'(v)を生成する。次に、巡回行列生成部１１７ｂは、巡回行列rot'(v)の各要素を整数に写像したn×nの巡回行列rot(v)を生成する。なお、この場合のn×nの巡回行列rot(v)の要素の例は、巡回行列rot'(v)の要素を整数とみなした値、巡回行列rot'(v)の要素を整数とみなした値の定数倍値、その他、巡回行列rot'(v)の要素から整数へ単写した値などである。また、巡回行列rot(v)の要素は、「n個の任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素」に相当し、m=ωn/2+1を法とする剰余環Z/mZ上の離散フーリエ変換をn個の任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい。生成されたn×nの巡回行列rot(v)は、記憶部１１２に格納される（ステップＳ２５２）。
【０１１４】
その後、第１実施形態と同様、ステップＳ１５３，Ｓ１５４の処理が実行される（［ステップＳ２５の詳細の例示］の説明終わり）。
【０１１５】
その後、第１実施形態と同様、ステップＳ１６の処理が実行される。
【０１１６】
〔その他の変形例〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第１実施形態では、ステップＳ１５１で、n個の要素v'i∈Z/mZ (i=0,..,n-1)を整数に写像したn個の要素vi∈Z (i=0,..,n-1)を生成し、ステップＳ１５２で、n個の要素viを用いて式(55)の巡回行列rot(v)を生成することとした。しかし、ステップＳ１５１でn個の要素v'i∈Z/mZ (i=0,..,n-1)をそのまま出力し、ステップＳ１５２で、n個の要素v'i∈Z/mZを用いて巡回行列rot'(v)を生成し、巡回行列rot'(v)の要素を整数に写像することで式(55)の巡回行列rot(v)を生成してもよい。
【０１１７】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１１８】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１１９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２０】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１２２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１２３】
１，２ セキュリティシステム
１１、２１ 鍵生成装置
【特許請求の範囲】
【請求項１】
絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成する任意値生成部と、
n個の前記任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【数３４】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力する暗号鍵生成部と、
を有する鍵生成装置。
【請求項２】
請求項１の鍵生成装置であって、
前記任意値生成部は、
dを正の整数とし、φ'をn次元ベクトルとし、Bpkをn×nの行列からなる公開鍵とし、φ' mod Bpkを暗号文とし、当該n次元ベクトルφ'の最大値をρEncとし、
【数３５】
とした場合に、絶対値が2・η以上となる前記任意値λi(i=0,..,n-1)を生成する、
ことを特徴とする鍵生成装置。
【請求項３】
請求項１又は２の鍵生成装置であって、
前記任意値生成部は、
dを正の整数とし、
【数３６】
とした場合に、絶対値が2・η以上となる前記任意値λi(i=0,..,n-1)を生成する、
ことを特徴とする鍵生成装置。
【請求項４】
請求項１から３の何れかの鍵生成装置であって、
前記整数nは2のべき乗からなり、
前記要素vi(i=0,..,n-1)は、m=ωn/2+1（ωは2のべき乗からなる整数）を法とする剰余環Z/mZ上の離散フーリエ変換をn個の前記任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい、
ことを特徴とする鍵生成装置。
【請求項５】
請求項４の鍵生成装置であって、
ω=2κであり、
κは、{2・log2(2・η-1)}/2以上の自然数であり、
前記ηは、dを正の整数とし、φ'をn次元ベクトルとし、Bpkをn×nの行列からなる公開鍵とし、φ' mod Bpkを暗号文とし、当該n次元ベクトルφ'の最大値をρEncとした場合における、
【数３７】
の何れかである、
ことを特徴とする鍵生成装置。
【請求項６】
請求項１から５の何れかの鍵生成装置であって、
前記暗号鍵生成部は、
n個の前記任意値λi(i=0,..,n-1)に離散フーリエ変換を施し、前記要素v i(i=0,..,n-1)を生成する離散フーリエ変換部と、
前記要素vi(i=0,..,n-1)を用い、前記巡回行列rot(v)を生成する巡回行列生成部と、を含む、ことを特徴とする鍵生成装置。
【請求項７】
請求項１から６の何れかの鍵生成装置であって、
前記鍵情報は、準同型暗号方式の秘密鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列を、前記秘密鍵として出力する秘密鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項８】
請求項１から７の何れかの鍵生成装置であって、
前記鍵情報は、準同型暗号方式の公開鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)のエルミート標準形、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列のエルミート標準形を、前記公開鍵として出力する公開鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項９】
請求項１から５の何れかの鍵生成装置であって、
前記暗号鍵生成部は、
n個の前記任意値λi(i=0,..,n-1)を対角成分とするn×nの対角行列をΛとし、n×nの離散フーリエ変換行列をWとし、当該離散フーリエ変換行列Wの逆行列をW-1とした場合における、n×nの巡回行列rot'(v)=W・Λ・W-1を用い、前記巡回行列rot(v)を生成する巡回行列生成部を含む、ことを特徴とする鍵生成装置。
【請求項１０】
請求項９の鍵生成装置であって、
前記鍵情報は、準同型暗号方式の秘密鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列を、前記秘密鍵として出力する秘密鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項１１】
請求項９又は１０の鍵生成装置であって、
前記鍵情報は、準同型暗号方式の公開鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)のエルミート標準形、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列のエルミート標準形を、前記公開鍵として出力する公開鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項１２】
任意値生成部が、絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成するステップと、
暗号鍵生成部が、n個の前記任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【数３８】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力するステップと、
を有する鍵生成方法。
【請求項１３】
請求項１から１１の何れかの鍵生成装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項１３のプログラムを格納したコンピュータ読取可能な記録媒体。
【請求項１】
絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成する任意値生成部と、
n個の前記任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【数３４】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力する暗号鍵生成部と、
を有する鍵生成装置。
【請求項２】
請求項１の鍵生成装置であって、
前記任意値生成部は、
dを正の整数とし、φ'をn次元ベクトルとし、Bpkをn×nの行列からなる公開鍵とし、φ' mod Bpkを暗号文とし、当該n次元ベクトルφ'の最大値をρEncとし、
【数３５】
とした場合に、絶対値が2・η以上となる前記任意値λi(i=0,..,n-1)を生成する、
ことを特徴とする鍵生成装置。
【請求項３】
請求項１又は２の鍵生成装置であって、
前記任意値生成部は、
dを正の整数とし、
【数３６】
とした場合に、絶対値が2・η以上となる前記任意値λi(i=0,..,n-1)を生成する、
ことを特徴とする鍵生成装置。
【請求項４】
請求項１から３の何れかの鍵生成装置であって、
前記整数nは2のべき乗からなり、
前記要素vi(i=0,..,n-1)は、m=ωn/2+1（ωは2のべき乗からなる整数）を法とする剰余環Z/mZ上の離散フーリエ変換をn個の前記任意値λi(i=0,..,n-1)に対して施すことで得られる剰余環Z/mZの要素を整数に写像した値と等しい、
ことを特徴とする鍵生成装置。
【請求項５】
請求項４の鍵生成装置であって、
ω=2κであり、
κは、{2・log2(2・η-1)}/2以上の自然数であり、
前記ηは、dを正の整数とし、φ'をn次元ベクトルとし、Bpkをn×nの行列からなる公開鍵とし、φ' mod Bpkを暗号文とし、当該n次元ベクトルφ'の最大値をρEncとした場合における、
【数３７】
の何れかである、
ことを特徴とする鍵生成装置。
【請求項６】
請求項１から５の何れかの鍵生成装置であって、
前記暗号鍵生成部は、
n個の前記任意値λi(i=0,..,n-1)に離散フーリエ変換を施し、前記要素v i(i=0,..,n-1)を生成する離散フーリエ変換部と、
前記要素vi(i=0,..,n-1)を用い、前記巡回行列rot(v)を生成する巡回行列生成部と、を含む、ことを特徴とする鍵生成装置。
【請求項７】
請求項１から６の何れかの鍵生成装置であって、
前記鍵情報は、準同型暗号方式の秘密鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列を、前記秘密鍵として出力する秘密鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項８】
請求項１から７の何れかの鍵生成装置であって、
前記鍵情報は、準同型暗号方式の公開鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)のエルミート標準形、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列のエルミート標準形を、前記公開鍵として出力する公開鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項９】
請求項１から５の何れかの鍵生成装置であって、
前記暗号鍵生成部は、
n個の前記任意値λi(i=0,..,n-1)を対角成分とするn×nの対角行列をΛとし、n×nの離散フーリエ変換行列をWとし、当該離散フーリエ変換行列Wの逆行列をW-1とした場合における、n×nの巡回行列rot'(v)=W・Λ・W-1を用い、前記巡回行列rot(v)を生成する巡回行列生成部を含む、ことを特徴とする鍵生成装置。
【請求項１０】
請求項９の鍵生成装置であって、
前記鍵情報は、準同型暗号方式の秘密鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列を、前記秘密鍵として出力する秘密鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項１１】
請求項９又は１０の鍵生成装置であって、
前記鍵情報は、準同型暗号方式の公開鍵を含み、
前記暗号鍵生成部は、前記巡回行列rot(v)のエルミート標準形、又は、前記巡回行列rot(v)の像であるn×nの整数要素行列のエルミート標準形を、前記公開鍵として出力する公開鍵生成部を含み、
前記整数要素行列の固有値の絶対値の最小値は、前記巡回行列rot(v)の固有値の絶対値の最小値以上である、
ことを特徴とする鍵生成装置。
【請求項１２】
任意値生成部が、絶対値が所定値以上となるn個（nは正の整数）の任意値λi(i=0,..,n-1)を生成するステップと、
暗号鍵生成部が、n個の前記任意値λi(i=0,..,n-1)の離散フーリエ変換結果に対応するn個の要素をv i(i=0,..,n-1)とした場合における、n×nの巡回行列
【数３８】
に対して定まるn×nの行列を、準同型暗号方式の暗号鍵として出力するステップと、
を有する鍵生成方法。
【請求項１３】
請求項１から１１の何れかの鍵生成装置としてコンピュータを機能させるためのプログラム。
【請求項１４】
請求項１３のプログラムを格納したコンピュータ読取可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図２】
【図３】
【図４】
【図５】
【図６】
【公開番号】特開２０１１−１４５５１２（Ｐ２０１１−１４５５１２Ａ）
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願番号】特願２０１０−６７１１（Ｐ２０１０−６７１１）
【出願日】平成２２年１月１５日（２０１０．１．１５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成２３年７月２８日（２０１１．７．２８）
【国際特許分類】
【出願日】平成２２年１月１５日（２０１０．１．１５）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]