(57)【特許請求の範囲】
【請求項１】
暗号化装置であって、
乱数ｒを生成する乱数生成部と、
前記乱数ｒに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2を生成する第１暗号化部と、
前記乱数ｒと前記暗号文C2との組を衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力して得られる、Smax（Smax≧1）個の関数値HS(ｒ,C2)(S=1,...,Smax)を生成する関数演算部と、
巡回群GTの元である共通鍵Kを生成する共通鍵生成部と、
前記共通鍵Kを用いて共通鍵暗号方式によって前記乱数ｒを暗号化して暗号文C(Ψ+1)を生成する第２暗号化部と、
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)、C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)、及び前記暗号文C(Ψ+1)を含む暗号文C1を生成する第３暗号化部と、を有し、
Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、n(ψ)が1以上の整数であり、ζ(ψ)が0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上n(0)+ζ(0)以下の定数であり、eψのそれぞれが巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力として前記巡回群GTの１個の元を出力する非退化な双線形写像であり、iが１以上n(ψ)+ζ(ψ)以下の整数であり、bi(ψ)が前記巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、bi*(ψ)が前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、δ(i,j)がクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数τ,τ'に対してeψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)が満たされ、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルであり、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が前記関数値HS(ｒ,C2)(S=1,...,Smax)の何れかに対応する、暗号化装置。
【請求項２】
請求項１の暗号化装置であって、
前記乱数ｒに応じたバイナリ系列は、前記乱数ｒにランダム関数を作用させた関数値である、暗号化装置。
【請求項３】
請求項１の暗号化装置であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化装置。
【請求項４】
請求項２の暗号化装置であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化装置。
【請求項５】
請求項１から４の何れかの暗号化装置であって、
前記定数τ,τ'、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ,C2)(S=1,...,Smax)、及びυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、暗号化装置。
【請求項６】
請求項１から４の何れかの暗号化装置であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2(0),υ4(0),υn(λ)+1(λ),...,υ3・n(λ)(λ)が零元であり、K=gTτ・τ'・υ'∈GT、υ'=υ3(0)であり、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)のそれぞれがH1(ｒ,C2),...,HSmax(ｒ,C2)の何れかである、暗号化装置。
【請求項７】
請求項６の暗号化装置であって、
前記定数τ,τ'、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ,C2)(S=1,...,Smax)、及びυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、暗号化装置。
【請求項８】
復号装置であって、
SE=Σμ∈SETconst(μ)・share(μ)（μ∈SET）を満たす係数const(μ)が存在する場合に、第１鍵情報D*(0)、第２鍵情報D*(λ)、及び、入力された暗号文C'(0)、C'(λ)を用いて、共通鍵
【数２１】
0005466763.tif 000022
を生成する共通鍵生成部と、
前記共通鍵K'を用い、入力された暗号文C'(Ψ+1)を復号して復号値r'を生成する第１復号部と、
前記復号値r'と入力された暗号文C2'との組を衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力して得られる、Smax（Smax≧1）個の関数値HS(ｒ',C2')(S=1,...,Smax)を生成する関数演算部と、
前記暗号文C'(0),C'(λ)と、暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0), C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)と、が一致しない場合に復号を拒絶する判定部と、を有し、
υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が前記関数値HS(ｒ',C2')(S=1,...,Smax)の何れかに対応し、
Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、ζ(ψ)が0以上の整数であり、λが1以上Ψ以下の整数であり、n(ψ)が1以上の整数であり、Iが2以上n(0)+ζ(0)以下の定数であり、eψのそれぞれが巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力として巡回群GTの１個の元を出力する非退化な双線形写像であり、iが１以上n(ψ)+ζ(ψ)以下の整数であり、bi(ψ)が前記巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、bi*(ψ)が前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、δ(i,j)がクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数τ,τ'に対してeψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)が満たされ、v(λ)→=(v1(λ),...,vn(λ)(λ))がv1(λ),...,vn(λ)(λ)を要素とするn(λ)次元ベクトルであり、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルであり、ラベルLAB(λ)（λ=1,...,Ψ）が前記n(λ)次元ベクトルv(λ)→又は前記n(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表す情報であり、LAB(λ)=v(λ)→は、LAB(λ)が前記n(λ)次元ベクトルv(λ)→を表すことを意味し、LAB(λ)=¬v(λ)→は、LAB(λ)が前記n(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表すことを意味し、share(λ)(λ=1,...,Ψ)が秘密情報SEを秘密分散して得らたシェア情報を表し、前記第１鍵情報がD*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、SETが{LAB(λ)=v(λ)→}∧{v(λ)→・w(λ)→=0}又は{LAB(λ)=¬v(λ)→}∧{v(λ)→・w(λ)→≠0}を満たすλの集合を表す、復号装置。
【請求項９】
請求項８の復号装置であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、復号装置。
【請求項１０】
請求項９の復号装置であって、
前記要素v1(λ),...,vn(λ)(λ)、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ',C2')(S=1,...,Smax)、及びυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、復号装置。
【請求項１１】
請求項８の復号装置であって、
前記要素v1(λ),...,vn(λ)(λ)、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ',C2')(S=1,...,Smax)、及びυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、復号装置。
【請求項１２】
請求項８から１１の何れかの復号装置であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2''(0),υ4''(0),υn(λ)+1''(λ),...,υ3・n(λ)''(λ)が零元であり、K'=gTτ・τ'・υ'''∈GT、υ'''=υ3''(0)であり、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)のそれぞれがH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れかであり、前記第１鍵情報がD*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)である、復号装置。
【請求項１３】
請求項１２の復号装置であって、
前記復号値r'に応じたバイナリ系列は、前記復号値r'にランダム関数を作用させた関数値である、復号装置。
【請求項１４】
請求項８から１１の何れかの復号装置であって、
前記暗号文C'(0)及びC'(λ)と、暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0)及びC''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)と、が一致する場合に、前記復号値r'に応じたバイナリ系列と入力されたバイナリ系列の暗号文C2'との排他的論理和である復号値M'を生成する第２復号部をさらに有する、復号装置。
【請求項１５】
請求項１４の復号装置であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2''(0),υ4''(0),υn(λ)+1''(λ),...,υ3・n(λ)''(λ)が零元であり、K'=gTτ・τ'・υ'''∈GT、υ'''=υ3''(0)であり、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)のそれぞれがH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れかであり、前記第１鍵情報がD*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)である、復号装置。
【請求項１６】
請求項１５の復号装置であって、
前記復号値r'に応じたバイナリ系列は、前記復号値r'にランダム関数を作用させた関数値である、復号装置。
【請求項１７】
暗号化方法であって、
乱数生成部が、乱数ｒを生成するステップと、
第１暗号化部が、前記乱数ｒに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2を生成するステップと、
関数演算部が、前記乱数ｒと前記暗号文C2との組を衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力して得られる、Smax（Smax≧1）個の関数値HS(ｒ,C2)(S=1,...,Smax)を生成するステップと、
共通鍵生成部が、巡回群GTの元である共通鍵Kを生成するステップと、
第２暗号化部が、前記共通鍵Kを用いて共通鍵暗号方式によって前記乱数ｒを暗号化して暗号文C(Ψ+1)を生成するステップと、
第３暗号化部が、C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)、C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)、及び前記暗号文C(Ψ+1)を含む暗号文C1を生成するステップと、を有し、
Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、n(ψ)が1以上の整数であり、ζ(ψ)が0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上n(0)+ζ(0)以下の定数であり、eψのそれぞれが巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力として前記巡回群GTの１個の元を出力する非退化な双線形写像であり、iが１以上n(ψ)+ζ(ψ)以下の整数であり、bi(ψ)が前記巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、bi*(ψ)が前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、δ(i,j)がクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数τ,τ'に対してeψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)が満たされ、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルであり、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が前記関数値HS(ｒ,C2)(S=1,...,Smax)の何れかにに対応する、暗号化方法。
【請求項１８】
請求項１７の暗号化方法であって、
前記乱数ｒに応じたバイナリ系列は、前記乱数ｒにランダム関数を作用させた関数値である、暗号化方法。
【請求項１９】
請求項１７の暗号化方法であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化方法。
【請求項２０】
請求項１８の暗号化方法であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、暗号化方法。
【請求項２１】
請求項１７から２０の何れかの暗号化方法であって、
前記定数τ,τ'、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ,C2)(S=1,...,Smax)、及びυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、暗号化方法。
【請求項２２】
請求項１７から２０の何れかの暗号化方法であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2(0),υ4(0),υn(λ)+1(λ),...,υ3・n(λ)(λ)が零元であり、K=gTτ・τ'・υ'∈GT、υ'=υ3(0)であり、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)のそれぞれがH1(ｒ,C2),...,HSmax(ｒ,C2)の何れかである、暗号化方法。
【請求項２３】
請求項２２の暗号化方法であって、
前記定数τ,τ'、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ,C2)(S=1,...,Smax)、及びυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、暗号化方法。
【請求項２４】
復号方法であって、
SE=Σμ∈SETconst(μ)・share(μ)（μ∈SET）を満たす係数const(μ)が存在する場合に、共通鍵生成部が、第１鍵情報D*(0)、第２鍵情報D*(λ)、及び、入力された暗号文C'(0)、C'(λ)を用いて、共通鍵
【数２２】
0005466763.tif 000023
を生成するステップと、
第１復号部が、前記共通鍵K'を用い、入力された暗号文C'(Ψ+1)を復号して復号値r'を生成するステップと、
関数演算部が、前記復号値r'と入力された暗号文C2'との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力してSmax（Smax≧1）個の関数値HS(ｒ',C2')(S=1,...,Smax)を生成するステップと、
判定部が、前記暗号文C'(0),C'(λ)と、暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0), C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)と、が一致しない場合に復号を拒絶するステップと、を有し、
υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が前記関数値HS(ｒ',C2')(S=1,...,Smax)の何れかに対応し、
Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、ζ(ψ)が0以上の整数であり、λが1以上Ψ以下の整数であり、n(ψ)が1以上の整数であり、Iが2以上n(0)+ζ(0)以下の定数であり、eψのそれぞれが巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力として巡回群GTの１個の元を出力する非退化な双線形写像であり、iが１以上n(ψ)+ζ(ψ)以下の整数であり、bi(ψ)が前記巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、bi*(ψ)が前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、δ(i,j)がクロネッカーのデルタ関数であり、前記巡回群GTの生成元gT及び定数τ,τ'に対してeψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)が満たされ、v(λ)→=(v1(λ),...,vn(λ)(λ))がv1(λ),...,vn(λ)(λ)を要素とするn(λ)次元ベクトルであり、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルであり、ラベルLAB(λ)（λ=1,...,Ψ）が前記n(λ)次元ベクトルv(λ)→又は前記n(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表す情報であり、LAB(λ)=v(λ)→は、LAB(λ)が前記n(λ)次元ベクトルv(λ)→を表すことを意味し、LAB(λ)=¬v(λ)→は、LAB(λ)が前記n(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表すことを意味し、share(λ)(λ=1,...,Ψ)が秘密情報SEを秘密分散して得らたシェア情報を表し、前記第１鍵情報がD*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、SETが{LAB(λ)=v(λ)→}∧{v(λ)→・w(λ)→=0}又は{LAB(λ)=¬v(λ)→}∧{v(λ)→・w(λ)→≠0}を満たすλの集合を表す、復号方法。
【請求項２５】
請求項２４の復号方法であって、
前記衝突困難な関数HSの少なくとも一部はランダム関数である、復号方法。
【請求項２６】
請求項２５の復号方法であって、
前記要素v1(λ),...,vn(λ)(λ)、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ',C2')(S=1,...,Smax)、及びυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、復号方法。
【請求項２７】
請求項２４の復号方法であって、
前記要素v1(λ),...,vn(λ)(λ)、前記要素w1(λ),...,wn(λ)(λ)、前記関数値HS(ｒ',C2')(S=1,...,Smax)、及びυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))が有限体Fqの元であり、
前記巡回群G1及びG2の位数のそれぞれが前記有限体Fqの位数q(q≧1)と等しい、復号方法。
【請求項２８】
請求項２４から２７の何れかの復号方法であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2''(0),υ4''(0),υn(λ)+1''(λ),...,υ3・n(λ)''(λ)が零元であり、K'=gTτ・τ'・υ'''∈GT、υ'''=υ3''(0)であり、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)のそれぞれがH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れかであり、前記第１鍵情報がD*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)である、復号方法。
【請求項２９】
請求項２８の復号方法であって、
前記復号値r'に応じたバイナリ系列は、前記復号値r'にランダム関数を作用させた関数値である、復号方法。
【請求項３０】
請求項２４から２７の何れかの復号方法であって、
前記暗号文C'(0)及びC'(λ)と、暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0)及びC''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)と、が一致する場合に、前記復号値r'に応じたバイナリ系列と入力されたバイナリ系列の暗号文C2'との排他的論理和である復号値M'を生成する第２復号部をさらに有する、復号方法。
【請求項３１】
請求項３０の復号方法であって、
ζ(λ)=3・n(λ)、I=5、Smax=3+Σλ=1Ψn(λ)であり、υ2''(0),υ4''(0),υn(λ)+1''(λ),...,υ3・n(λ)''(λ)が零元であり、K'=gTτ・τ'・υ'''∈GT、υ'''=υ3''(0)であり、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)のそれぞれがH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れかであり、前記第１鍵情報がD*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)であり、LAB(λ)=v(λ)→となるλに対する前記第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する前記第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)である、復号方法。
【請求項３２】
請求項３１の復号方法であって、
前記復号値r'に応じたバイナリ系列は、前記復号値r'にランダム関数を作用させた関数値である、復号方法。
【請求項３３】
請求項１の暗号化装置としてコンピュータを機能させるためのプログラム。
【請求項３４】
請求項１の暗号化装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項３５】
請求項８の復号装置としてコンピュータを機能させるためのプログラム。
【請求項３６】
請求項８の復号装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティ技術に関し、特に暗号技術に関する。
【背景技術】
【０００２】
暗号研究分野の一つに、選択暗号文攻撃に対して安全な（CCA-Secure：Chosen Ciphertext Attacks - Secure )暗号方式（CCA安全な暗号方式）がある。特に近年、一般に選択平文攻撃(CPA: Chosen Plaintext Attack)に対する安全性しか持たないIDベース暗号(IBE: Identity-based Encryption)方式（例えば、非特許文献１参照）に基づきCCA安全な暗号方式を構成しようとする研究が盛んである。例えば、非特許文献２では、CHK変換方式が提案されている。CHK変換方式では、CPA安全な任意のIDベース暗号方式に基づいてCCA安全な暗号方式を構築するためにOne-Time 署名が用いられる。例えば、非特許文献３では、BK変換方式が提案されている。BK変換方式では、CPA安全な任意のIDベース暗号方式に基づいてCCA安全な暗号方式を構築するために、メッセージ認証子（MAC: Message Authentication Code）とビットコミットメント方式とが用いられる。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】D.Boneh, M. Franklin, "Identity based encryption from the Weil pairing," Crypto 2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp.213-229, 2001.
【非特許文献２】R. Canetti, S. Halevi, J. Katz, “Chosen-Ciphertext Security from Identity-Based Encryption,” Proc. of EUROCRYPT’04, LNCS 3027, pp. 207-222, 2004.
【非特許文献３】D. Boneh, J. Katz, “Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption,” Proc. of CT-RSA’05, LNCS 3376, pp. 87-103, 2005.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上述したCHK変換方式に基づいて生成された暗号文は、暗号化された平文と当該暗号化された平文のOne-Time署名と当該One-Time署名を検証するための署名鍵とを含む。そのため、CHK変換方式に基づいて生成される暗号文の暗号文空間は、暗号化された平文のための空間だけではなく、One-Time署名や署名鍵のための空間を含む。上述したBK変換方式に基づいて生成された暗号文は、暗号化された平文とメッセージ認証子とビットコミットメント列とを含む。そのため、BK変換方式に基づいて生成される暗号文の暗号文空間は、暗号化された平文のための空間だけではなく、メッセージ認証子やビットコミットメント列のための空間を含む。すなわち、CHK変換方式やBK変換方式に基づいて生成される暗号文空間は、CCA安全性を向上させるためのみに割り当てられた2次元の空間を含む。しかしながら、暗号文空間のサイズが大きくなるほど演算量やデータ量が増加するため、暗号文空間のサイズはできるだけ小さいほうが望ましい。【０００５】
また、IDベース暗号方式では、暗号化を行う者が、暗号化を行う前に復号を行う者のIDを取得しておかなければならない。これに対し、暗号化を行う者が復号を行う者を特定することなく暗号文を生成でき、所望の条件に合致した者が当該暗号文を復号できる方式を構成できれば便利である。【０００６】
本発明はこのような点に鑑みてなされたものであり、利便性が高く、CCA安全性の向上のための付加的な暗号文空間なしにCCA安全性を向上できる暗号方式を提供する。
【課題を解決するための手段】
【０００７】
本発明の暗号化では、乱数ｒが生成され、乱数ｒに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2が生成される。乱数ｒと暗号文C2との組が衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力されてSmax（Smax≧1）個の関数値HS(ｒ,C2)(S=1,...,Smax)が生成される。巡回群GTの元である共通鍵Kが生成され、共通鍵Kを用いて共通鍵暗号方式によって乱数ｒを暗号化して暗号文C(Ψ+1)が生成される。C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)、C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)、及び暗号文C(Ψ+1)を含む暗号文C1が生成される。【０００８】
ここで、Ψが1以上の整数であり、ψが0以上Ψ以下の整数であり、n(ψ)が1以上の整数であり、ζ(ψ)が0以上の整数であり、λが1以上Ψ以下の整数であり、Iが2以上n(0)+ζ(0)以下の定数であり、eψのそれぞれが巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力として巡回群GTの１個の元を出力する非退化な双線形写像であり、iが１以上n(ψ)+ζ(ψ)以下の整数であり、bi(ψ)が巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、bi*(ψ)が巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルであり、δ(i,j)がクロネッカーのデルタ関数であり、巡回群GTの生成元gT及び定数τ,τ'に対してeψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)が満たされ、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルである。υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ,C2)(S=1,...,Smax)の何れかに対応する。【０００９】
本発明の復号では、SE=Σμ∈SETconst(μ)・share(μ)（μ∈SET）を満たす係数const(μ)が存在する場合に、第１鍵情報D*(0)、第２鍵情報D*(λ)、及び、入力された暗号文C'(0)、C'(λ)を用いて、以下のように共通鍵K'が生成される。
【数１】
0005466763.tif 000002
共通鍵K'を用い、入力された暗号文C'(Ψ+1)が復号されて復号値r'が生成される。復号値r'と入力された暗号文C2'との組が衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力されてSmax（Smax≧1）個の関数値HS(ｒ',C2')(S=1,...,Smax)が生成される。暗号文C'(0),C'(λ)と暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0),C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)とそれぞれが一致しない場合に復号が拒絶される。【００１０】
ただし、v(λ)→=(v1(λ),...,vn(λ)(λ))がv1(λ),...,vn(λ)(λ)を要素とするn(λ)次元ベクトルであり、w(λ)→=(w1(λ),...,wn(λ)(λ))がw1(λ),...,wn(λ)(λ)を要素とするn(λ)次元ベクトルであり、ラベルLAB(λ)（λ=1,...,Ψ）がn(λ)次元ベクトルv(λ)→又はn(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表す情報であり、「LAB(λ)=v(λ)→」はLAB(λ)がn(λ)次元ベクトルv(λ)→を表すことを意味し、「LAB(λ)=¬v(λ)→」はn(λ)次元ベクトルv(λ)→の否定¬v(λ)→を表すことを意味し、share(λ)(λ=1,...,Ψ)が秘密情報SEを秘密分散して得られたシェア情報を表し、第１鍵情報がD*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)であり、LAB(λ)=v(λ)→となるλに対する第２鍵情報がD*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、LAB(λ)=¬v(λ)→となるλに対する第２鍵情報がD*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)であり、SETが{LAB(λ)=v(λ)→}∧{v(λ)→・w(λ)→=0}又は{LAB(λ)=¬v(λ)→}∧{v(λ)→・w(λ)→≠0}を満たすλの集合を表す。υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ',C2')(S=1,...,Smax)の何れかに対応する。
【発明の効果】
【００１１】
本発明では、暗号文C'(0),C'(λ)と暗号文C''(0),C''(λ)とがそれぞれ一致しない場合に復号を拒絶することとしたためCCA安全性が向上する。本発明では、CCA安全性を向上させるための付加的な暗号文空間が不要である。本発明は、暗号化を行う者が復号を行う者を特定することなく暗号文を生成でき、所望の条件に合致した者が当該暗号文を復号できる。
このように本発明では、利便性が高く、CCA安全性の向上のための付加的な暗号文空間なしにCCA安全性を向上できる。
【図面の簡単な説明】
【００１２】
【図１】図１は、標準形論理式を表現する木構造データを例示する図である。
【図２】図２は、標準形論理式を表現する木構造データを例示する図である。
【図３】図３は、本形態の暗号システムを例示するためのブロック図である。
【図４】図４は、本形態の暗号化装置を例示するためのブロック図である。
【図５】図５は、本形態の復号装置を例示するためのブロック図である。
【図６】図６は、本形態の鍵生成装置を例示するためのブロック図である。
【図７】図７は、本形態の鍵生成処理を例示するための図である。
【図８】図８は、本形態の暗号化処理を例示するための図である。
【図９】図９は、本形態の復号処理を例示するための図である。
【図１０】図１０は、図９のステップ４３の処理を例示するための図である。
【発明を実施するための形態】
【００１３】
本発明を実施するための形態を説明する。
〔定義〕
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」である。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
【００１４】
∧：∧は論理積（ＡＮＤ）を表す論理記号である。
∨：∨は論理和（ＯＲ）を表す論理記号である。
¬：¬は否定（ＮＯＴ）を表す論理記号である。
命題変数：命題変数は命題の「真」,「偽」（"false","true"）を要素とする集合｛真，偽｝上の変数である。すなわち、命題変数の定義域は「真」,「偽」を要素とする集合である。命題変数及び命題変数の否定を総称してリテラル（literal）と呼ぶ。
論理式：論理式とは数理論理学における命題を表す式を意味する。具体的には「真」及び「偽」は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。
【００１５】
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
0*：0*は*個の0からなる列を表す。
1*：1*は*個の１からなる列を表す。
{0,1}*：{0,1}*は任意ビット長のバイナリ系列を表す。{0,1}*の一例は、整数0及び1からなる系列である。しかし、{0,1}*は整数0及び1からなる系列に限定されない。{0,1}*は位数2の有限体又はその拡大体と同義である。
{0,1}ζ：{0,1}ζはビット長ζ（ζ∈Z, ζ>0）のバイナリ系列を表す。{0,1}ζの一例は、ζ個の整数0及び1からなる系列である。しかし、{0,1}ζは整数0及び1からなる系列に限定されない。{0,1}ζは位数2の有限体（ζ=1の場合）又はそれをζ次拡大した拡大体（ζ>1の場合）と同義である。
(+):(+)はバイナリ系列間の排他的論理和演算子を表す。例えば、10110011(+)11100001=01010010を満たす。
【００１６】
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。有限体Fqが素体である場合の演算は、例えば、位数qを法とする剰余演算によって容易に構成できる。有限体Fqが拡大体である場合の演算は、例えば、既約多項式を法とする剰余演算によって容易に構成できる。有限体Fqの具体的な構成方法は、例えば、参考文献１「ISO/IEC 18033-2: Information technology - Security techniques - Encryption algorithms - Part 2: Asymmetric ciphers」に開示されている。
0F：0Fは有限体Fqの加法単位元（零元）を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0Fを満たす。
【００１７】
E：Eは有限体Fq上で定義された楕円曲線を表す。楕円曲線Eは、以下に示すアフィン（affine）座標上のWeierstrass方程式を満たすx,y∈Fqからなる点(x,y)の集合と無限遠点と呼ばれる特別な点Ｏとを含む集合である。
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6
ただし、a1,a2,a3,a4,a6∈Fqを満たす。
楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算＋が定義され、楕円曲線E上の任意の１点に対して逆元演算と呼ばれる単項演算−が定義される。楕円曲線E上の有理点からなる有限集合が楕円加算に関して群をなすこと、楕円加算を用いて楕円スカラー倍算と呼ばれる演算が定義できること、及びコンピュータ上での楕円加算などの楕円演算の具体的な演算方法はよく知られている（例えば、参考文献１、参考文献２「RFC 5091: Identity-Based Cryptography Standard (IBCS) #1: Supersingular Curve Implementations of the BF and BB1 Cryptosystems」、参考文献３「イアン・Ｆ・ブラケ、ガディエル・セロッシ、ナイジェル・Ｐ・スマート＝著、「楕円曲線暗号」、出版＝ピアソン・エデュケーション、ISBN4-89471-431-0」等参照）。
【００１８】
楕円曲線E上の有理点からなる有限集合は位数p(p≧1)の部分群を持つ。例えば、楕円曲線E上の有理点からなる有限集合の要素数が＃Eであり、pが＃Eを割り切る大きい素数であるとすると、楕円曲線Eのp等分点からなる有限集合E[p]は、楕円曲線E上の有理点からなる有限集合の部分群を構成する。楕円曲線Eのp等分点とは、楕円曲線E上の点Aのうち、楕円曲線E上での楕円スカラー倍算値p・Aがp・A＝Ｏを満たす点を意味する。
【００１９】
G1, G2,GT：G1, G2, GTはそれぞれ位数qの巡回群を表す。巡回群G1, G2の具体例は、楕円曲線Eのp等分点からなる有限集合E[p]やその部分群である。G1=G2であってもよいしG1≠G2であってもよい。巡回群GTの具体例は、有限体Fqを基礎体とする拡大体を構成する有限集合である。その一例は、有限体Fqの代数閉包における１のｐ乗根からなる有限集合である。巡回群G1, G2,GTの位数と有限体Fqの位数とが同一である場合にはより安全性が高い。
【００２０】
本形態では、巡回群G1, G2上で定義された演算を加法的に表現し、巡回群GT上で定義された演算を乗法的に表現する。例えば、χ∈Fq及びΩ∈G1に対するχ・Ω∈G1は、Ω∈G1に対して巡回群G1で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G1に対するΩ1+Ω2∈G1は、Ω1∈G1とΩ2∈G1とを被演算子として巡回群G1で定義された演算を行うことを意味する。同様に、例えば、χ∈Fq及びΩ∈G2に対するχ・Ω∈G2は、Ω∈G2に対して巡回群G2で定義された演算をχ回施すことを意味し、Ω1, Ω2∈G2に対するΩ1+Ω2∈G2は、Ω1∈G2とΩ2∈G2とを被演算子として巡回群G2で定義された演算を行うことを意味する。一方、χ∈Fq及びΩ∈GTに対するΩχ∈GTは、例えば、Ω∈GTに対して巡回群GTで定義された演算をχ回施すことを意味し、Ω1,Ω2∈GTに対するΩ1・Ω2∈GTは、Ω1∈GTとΩ2∈GTとを被演算子として巡回群GTで定義された演算を行うことを意味する。
【００２１】
Ψ：Ψは1以上の整数を表す。
ψ：ψは0以上Ψ以下の整数ψ=0,...,Ψを表す。
λ：λは1以上Ψ以下の整数λ=1,...,Ψを表す。
n(ψ)：n(ψ)は予め定められた1以上の整数を表す。
ζ(ψ)：ζ(ψ)は予め定められた0以上の整数を表す。
G1n(ψ)+ζ(ψ)：G1n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積を表す。
G2n(ψ)+ζ(ψ)：G2n(ψ)+ζ(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積を表す。
g1, g2, gT：g1, g2, gTはそれぞれ巡回群G1, G2, GTの生成元を表す。
V(ψ)：V(ψ)はn(ψ)+ζ(ψ)個の巡回群G1の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。
V*(ψ)：V*(ψ)はn(ψ)+ζ(ψ)個の巡回群G2の直積からなるn(ψ)+ζ(ψ)次元のベクトル空間を表す。 
【００２２】
eψ：eψは直積G1n(ψ)+ζ(ψ)と直積G2n(ψ)+ζ(ψ)との直積G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)を巡回群GTに写す非退化な双線形写像（bilinear map）を表す。双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ(β=1,...,n(ψ)+ζ(ψ))と巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))とを入力とし、巡回群GTの１個の元を出力する。
eψ：G1n(ψ)+ζ(ψ)×G2n(ψ)+ζ(ψ)→GT          …(1)
双線形写像eψは以下の性質を満たす。
［双線形性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)及びν，κ∈Fqについて以下の関係を満たす。
eψ(ν・Γ1,κ・Γ2)=eψ(Γ1,Γ2)ν・κ          …(2)
［非退化性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆる
Γ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)          …(3)
についてeψ(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【００２３】
本形態では、以下のような、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を用いて双線形写像eψを構成する。
Pair:G1×G2→GT          …(4)
本形態の双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ (β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1,...,γn(ψ)+ζ(ψ))と、巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1*,...,γn(ψ)+ζ(ψ)*)との入力に対し、巡回群GTの１個の元を出力する。
eψ：Πβ=1n(ψ)+ζ(ψ)Pair(γβ, γβ*)          …(5)
双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像Pairは、以下の性質を満たす。
［双線形性］双線形写像Pairは、すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(6)
［非退化性］双線形写像Pairは、すべての
Ω1∈G1，Ω2∈G2          …(7)
を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆるΩ1∈G1，Ω2∈G2についてPair(Ω1,Ω2)を効率的に計算するアルゴリズムが存在する。
【００２４】
双線形写像Pairの具体例は、WeilペアリングやTateペアリングなどのペアリング演算を行うための関数である（例えば、参考文献４「Alfred. J. Menezes，ELLIPTIC CURVE PUBLIC KEY CRYPTOSYSTEMS， KLUWER ACADEMIC PUBLISHERS， ISBN0-7923-9368-6，pp. 61-81」等参照）。楕円曲線Eの種類に応じ、Tateペアリングなどのペアリング演算を行うための関数と所定の関数phiを組み合わせた変更ペアリング関数e(Ω1,phi(Ω2))（Ω1∈G1，Ω2∈G2）を双線形写像Pairとして用いてもよい（例えば、参考文献２等参照）。ペアリング演算をコンピュータ上で行うためのアルゴリズムとしては、周知のMiller のアルゴリズム（参考文献５「V. S. Miller, “Short Programs for functions on Curves,”1986，インターネット＜http://crypto.stanford.edu/miller/miller.pdf＞」などが存在する。ペアリング演算を効率的に行うための楕円曲線や巡回群の構成方法はよく知られている（例えば、参考文献２、参考文献６「A. Miyaji, M. Nakabayashi, S.Takano, "New explicit conditions of elliptic curve Traces for FR-Reduction," IEICE Trans. Fundamentals, vol. E84-A, no05, pp. 1234-1243, May 2001」、参考文献７「P.S.L.M. Barreto, B. Lynn, M. Scott, "Constructing elliptic curves with prescribed embedding degrees," Proc. SCN '2002, LNCS 2576, pp.257-267, Springer-Verlag. 2003」、参考文献８「R. Dupont, A. Enge, F. Morain, "Building curves with arbitrary small MOV degree over finite prime fields," http://eprint.iacr.org/2002/094/」等参照）。
【００２５】
ai(ψ)(i=1,...,n(ψ)+ζ(ψ))：ai(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai(ψ)の一例は、κ1・g1∈G1をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G1の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1(ψ)=(κ1・g1,0,0,...,0)
a2(ψ)=(0,κ1・g1,0,...,0)          …(8)
...
an(ψ)+ζ(ψ)(ψ)=(0,0,0,...,κ1・g1)
ここで、κ1は加法単位元0F以外の有限体Fqの元からなる定数であり、κ1∈Fqの具体例はκ1=1Fである。基底ベクトルai(ψ)は直交基底であり、巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai(ψ)は前述のベクトル空間V(ψ)を張る。
【００２６】
ai*(ψ)(i=1,...,n(ψ)+ζ(ψ))：ai*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。基底ベクトルai*(ψ)の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn(ψ)+ζ(ψ)-1個の要素を巡回群G2の単位元（加法的に「0」と表現）とするn(ψ)+ζ(ψ)次元の基底ベクトルである。この場合、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の各要素をそれぞれ列挙して表現すると、以下のようになる。
a1*(ψ)=(κ2・g2,0,0,...,0)
a2*(ψ)=(0,κ2・g2,0,...,0)          …(9)
...
an(ψ)+ζ(ψ)*(ψ)=(0,0,0,...,κ2・g2)
ここで、κ2は加法単位元0F以外の有限体Fqの元からなる定数であり、κ2∈Fqの具体例はκ2=1Fである。基底ベクトルai*(ψ)は直交基底であり、巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルai*(ψ)は前述のベクトル空間V*(ψ)を張る。
【００２７】
なお、基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について
eψ(ai(ψ), aj*(ψ))=gTτ・δ(i,j)           …(10)
を満たす。すなわち、i=jの場合には、式(5)(6)の関係より、以下の関係が満たされる。
eψ(ai(ψ), aj*(ψ))
= Pair(κ1・g1,κ2・g2)・Pair(0, 0)・...・Pair(0, 0)
= Pair(g1, g2)κ1・κ2・Pair(g1, g2)0・0・...・Pair(g1, g2)0・0
= Pair(g1, g2)κ1・κ2=gTτ
上付き添え字κ1，κ2はそれぞれκ1，κ2を表す。一方、i≠jの場合には、eψ(ai(ψ), aj*(ψ))=Πi=1n(ψ)+ζ(ψ) Pair(ai(ψ), aj*(ψ))の右辺は、Pair(κ1・g1,κ2・g2)を含まず、Pair(κ1・g1,0)と Pair(0,κ2・g2)とPair(0,0)との積になる。さらに、式(6)の関係からPair(g1, 0)=Pair(0, g2)=Pair(g1, g2)0を満たす。そのため、i≠jの場合には、以下の関係が満たされる。
eψ(ai(ψ), aj*(ψ))=eψ(g1, g2)0=gT0
【００２８】
特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=1Fの場合）、以下の関係が満たされる。
e(ai(ψ), aj*(ψ))=gTδ(i,j)           …(11)
gT0=1は巡回群GTの単位元であり、gT1=gTは巡回群GTの生成元である。基底ベクトルai(ψ)と基底ベクトルai*(ψ)とは双対正規直交基底であり、ベクトル空間V(ψ)とベクトル空間V*(ψ)とは、双線形写像を構成可能な双対ベクトル空間〔双対ペアリングベクトル空間（DPVS:Dual Paring Vector space)〕である。
【００２９】
A(ψ)：A(ψ)は、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、行列A(ψ)は以下のようになる。
【数２】
0005466763.tif 000003
【００３０】
A*(ψ)：A*(ψ)は、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、行列A*(ψ)は以下のようになる。
【数３】
0005466763.tif 000004
【００３１】
X(ψ)：X(ψ)は有限体Fqの元を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。行列X(ψ)は基底ベクトルai(ψ)の座標変換に用いられる。行列X(ψ)のi行j列(i=1,...,n(ψ)+ζ(ψ),j=1,...,n(ψ)+ζ(ψ))の要素をχi,j(ψ)∈Fqとすると、行列X(ψ)は以下のようになる。
【数４】
0005466763.tif 000005
なお、行列X(ψ)の各要素χi,j(ψ)を変換係数と呼ぶ。
【００３２】
X *(ψ)：行列X*(ψ)と行列X(ψ)とはX*(ψ)=τ'・(X(ψ)-1)Tの関係を満たす。ただし、τ'∈Fqは有限体Fqに属する任意の定数であり、例えば、τ'=1Fである。X*(ψ)は基底ベクトルai*(ψ)の座標変換に用いられる。行列X*(ψ)のi行j列の要素をχi,j*(ψ)∈Fqとすると、行列Ｘ*(ψ)は以下のようになる。
【数５】
0005466763.tif 000006
なお、行列Ｘ*(ψ)の各要素χi,j*(ψ)を変換係数と呼ぶ。
【００３３】
この場合、n(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の単位行列をI(ψ)とするとX(ψ)・(X*(ψ))T=τ'・I(ψ)を満たす。すなわち、単位行列を以下のように定義する。
【数６】
0005466763.tif 000007
これについて以下が満たされる。
【数７】
0005466763.tif 000008
【００３４】
ここで、以下のようなn(ψ)+ζ(ψ)次元ベクトルを定義する。
χi→(ψ)=(χi,1(ψ),...,χi,n(ψ)+ζ(ψ)(ψ))          …(18)
χj→*(ψ)=(χj,1*(ψ),...,χj,n(ψ)+ζ(ψ)*(ψ))       …(19)
すると、式(17)の関係から、n(ψ)+ζ(ψ)次元ベクトルχi→(ψ)とχj→*(ψ)との内積は、以下のようになる。
χi→(ψ)・χj→*(ψ)=τ'・δ(i,j)          …(20)
【００３５】
bi(ψ)：bi(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi(ψ)は行列X(ψ)を用いて基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi(ψ)は、以下の演算によって得られる。
bi(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j(ψ)・aj(ψ)          …(21)
例えば、基底ベクトルaj(ψ)(j=1,...,n(ψ)+ζ(ψ))が式(8)によって表現される場合、基底ベクトルbi(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi(ψ)=(χi,1(ψ)・κ1・g1,χi,2(ψ)・κ1・g1,
...,χi,n(ψ)+ζ(ψ)(ψ)・κ1・g1)      …(22)
巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ)は前述のベクトル空間V(ψ)を張る。
【００３６】
bi*(ψ)：bi*(ψ)は巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi*(ψ)は行列X*(ψ)を用いて基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi*(ψ)は、以下の演算によって得られる。
bi*(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j*(ψ)・aj*(ψ)          …(23)
例えば、基底ベクトルaj*(ψ) (j=1,...,n(ψ)+ζ(ψ))が式(9)によって表現される場合、基底ベクトルbi*(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*(ψ)=(χi,1*(ψ)・κ2・g2 ,χi,2*(ψ)・κ2・g2,
...,χi,n(ψ)+ζ(ψ)*(ψ)・κ2・g2)    …(24)
巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)は前述のベクトル空間V*(ψ)を張る。
【００３７】
なお、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について以下の関係を満たす。
eψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)          …(25)
すなわち、式(5)(20)(22)(24)の関係から、以下の関係が満たされる。
【数８】
0005466763.tif 000009
特にτ=κ1・κ2=1F（例えば、κ1=κ2=1F）及びτ'=1Fである場合、以下の関係が満たされる。
eψ(bi(ψ), bj*(ψ))=gTδ(i,j)          …(26)
基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、双対ペアリングベクトル空間（ベクトル空間V(ψ)とベクトル空間V*(ψ)）の双対正規直交基底である。
なお、式(25)の関係を満たすのであれば、式(8)(9)で例示したもの以外の基底ベクトルai(ψ)及びai*(ψ)や、式(21)(23)で例示したもの以外の基底ベクトルbi(ψ)及びbi*(ψ)を用いてもよい。
【００３８】
B(ψ)：B(ψ)は基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列である。B(ψ)=X(ψ)・A(ψ)を満たす。例えば、基底ベクトルbi(ψ)が式(22)によって表現される場合、行列B(ψ)は以下のようになる。
【数９】
0005466763.tif 000010
【００３９】
B*(ψ)：B*(ψ)は基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。B*(ψ)=X*(ψ)・A*(ψ)を満たす。例えば、基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(24)によって表現される場合、行列B*(ψ)は以下のようになる。
【数１０】
0005466763.tif 000011
【００４０】
v(λ)→：v(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
v(λ)→=(v1(λ),...,vn(λ)(λ))∈Fqn(λ)          …(29)
vμ(λ)：vμ(λ)はn(λ)次元ベクトルv(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
w(λ)→：w(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
w(λ)→=(w1(λ),...,wn(λ)(λ))∈Fqn(λ)          …(30)
wμ(λ)：wμ(λ)はn(λ)次元ベクトルw(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
【００４１】
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。
EncK(M)：EncK(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
DecK(C)：DecK(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【００４２】
衝突困難な関数：「衝突困難な関数」とは、十分大きなセキュリティパラメータsecに対して以下の条件を満たす関数h、又は、関数hとみなせる関数を表す。
Pr[A(h)=(x,y)|h(x)=h(y)∧x≠y]<ε(sec)
ただし、Pr[・]は事象[・]の確率であり、A(h)は関数hに対してh(x)=h(y)を満たす値x,y（x≠y）を算出する確率的多項式時間アルゴリズムであり、ε(sec)はセキュリティパラメータsecについての多項式である。衝突困難な関数の例は、参考文献１に開示された「cryptographic hash function」などのハッシュ関数である。
【００４３】
ランダム関数：「ランダム関数」とは、集合Φζの部分集合φζに属する関数、又は、当該部分集合φζに属する関数とみなせる関数を表す。ただし、集合Φζは集合{0,1}ζの元を集合{0,1}ζの元へ写すすべての関数の集合である。任意の確率的多項式時間アルゴリズムは、集合Φζと部分集合φζとを区別できない。ランダム関数の例は、上述のようなハッシュ関数である。
単射関数：「単射関数」とは、その定義域に属する互いに異なる元の像をその値域に属する同一の元に写像することがない関数、又は、その定義域に属する互いに異なる元の像をその値域に属する同一の元に写像することがない関数とみなせる関数を表す。すなわち「単射関数」は、その定義域に属する元をその値域に属する何れかの元に一対一で写像する関数、又は、その定義域に属する元をその値域に属する何れかの元に一対一で写像する関数みなせる関数である。単射関数の例は、参考文献１に開示された「KDF(Key Derivation Function)」などのハッシュ関数である。
【００４４】
HS(S=1,...,Smax)：HSは２個の値を入力として１個の有限体Fqの元を出力する衝突困難な関数を表す。Smaxは正の整数定数である。関数HSの例は１個の巡回群GTの元と１個のバイナリ系列とを入力として１個の有限体Fqの元を出力する衝突困難な関数や、２個のバイナリ系列を入力として１個の有限体Fqの元を出力する衝突困難な関数などである。関数HSの具体例は、入力された２個の値を１つのバイナリ系列に写す単射関数と、参考文献１に開示された「cryptographic hash function」などのハッシュ関数と、「バイナリ系列を有限体の元へ写す変換関数（例えば参考文献１の「Octet string and integer/finite field conversion」参照）を含む関数である。入力された２個の値を１つのバイナリ系列に写す単射関数の具体例は、入力された１個の巡回群GTの元をバイナリ系列に写像してそのバイナリ系列と入力された１個のバイナリ系列との排他的論理和を出力する関数、又は、入力された２つのバイナリ系列の排他的論理和を出力する関数などである。安全性の観点から、関数HSは一方向性関数であることが望ましく、ランダム関数であることがより望ましい。関数HSの一部のみが一方向性関数やランダム関数であってもよいが、安全性の観点から、すべての関数HSは一方向性関数であることが望ましく、ランダム関数であることがより望ましい。安全性の観点から、関数HS(S=1,...,Smax)は互いに異なる関数であることが望ましい。
【００４５】
R：Rは１個の値を入力として１個のバイナリ系列を出力する単射関数を表す。単射関数Rの例は１個の巡回群GTの元を入力として１個のバイナリ系列を出力する関数や、１個のバイナリ系列を入力として１個のバイナリ系列を出力する関数などである。単射関数Rの具体例は、入力された１個の値を１つのバイナリ系列に写す単射関数と参考文献１に開示された「cryptographic hash function」などのハッシュ関数とを含む関数、又は、参考文献１に開示された「cryptographic hash function」などのハッシュ関数である。安全性の観点から、単射関数Rは一方向性関数であることが望ましく、ランダム関数であることがより望ましい。 
【００４６】
〔関数暗号方式〕
次に、関数暗号方式の基本的な構成について説明する。
関数暗号方式とは、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に暗号文が復号される方式である。「第１情報」と「第２情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、「"Predicate Encryption Supporting Disjunctions, Polynomial Equations, and Inner Products," with Amit Sahai and Brent Waters One of 4 papers from Eurocrypt 2008 invited to the Journal of Cryptology」（参考文献９）に開示された述語暗号方式は関数暗号方式の一種である。
【００４７】
これ以外にも様々な公知の関数暗号方式が存在するが、以下では未公開の新たな関数暗号方式を説明する。以下に説明する新たな関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第１情報と第２情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧，∨，¬の何れか又はすべてを含む。各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が「真」となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。
【００４８】
＜論理式と階層的な秘密分散との関係＞
上述した所定の論理式と階層的な秘密分散との関係を説明する。
秘密分散とは、しきい値Kt(Kt≧1)個以上のシェア情報が得られた場合にのみ秘密情報が復元されるように、秘密情報をN(N≧2)個のシェア情報に分散することである。Kt=Nを満たす秘密分散の方式（SSS: Secret Sharing Scheme）をN-out-of-N分散方式（或いは「N-out-of-Nしきい値分散方式」）といい、Kt＜Nを満たす秘密分散の方式をKt-out-of-N分散方式（或いは「Kt-out-of-Nしきい値分散方式」）という（例えば、参考文献１０「黒沢馨、尾形わかは、“現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)”、コロナ社 、２００４年３月、p.116-119」、参考文献１１「A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.」等参照）。
【００４９】
N-out-of-N分散方式では、すべてのシェア情報share(1),...,share(N)が与えられれば秘密情報SEを復元できるが、任意のN-1個のシェア情報share(φ1),...,share(φN-1)が与えられても秘密情報SEの情報はまったく得られない。以下に、N-out-of-N分散方式の一例を示す。
・SH1,...,SHN-1をランダムに選択する。
・SHN=SE-(SH1+...+SHN-1)の計算を行う。
・SH1,...,SHNを各シェア情報share(1),...,share(N)とする。
・すべてのシェア情報share(1),...,share(N)が与えられれば、以下の復元処理によって秘密情報SEの復元が可能である。
SE=share(1)+...+share(N)          …(31)
【００５０】
Kt-out-of-N分散方式では、任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)が与えられれば秘密情報SEを復元できるが、任意のKt-1個のシェア情報share(φ1),...,share(φKt-1)が与えられても秘密情報SEの情報はまったく得られない。添え字のKtはKtを表す。以下にKt-out-of-N分散方式の一例を示す。
・f(0)=SEを満たすKt-1次の多項式f(x)=ξ0+ξ1・x+ξ2・x2+...+ξKt-1・xKt-1をランダムに選ぶ。すなわち、ξ0=SEとし、ξ1,...,ξKt-1をランダムに選ぶ。シェア情報をshare(ρ)=(ρ, f(ρ))（ρ=1,...,N）とする。(ρ, f(ρ))からのρ及びf(ρ)の抽出が可能であり、(ρ, f(ρ))の例はρとf(ρ)とのビット結合値である。
・任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)（(φ1,...,φKt)⊂(1,...,N)）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報SEの復元が可能である。
SE=f(0)=LA1・f(φ1)+...+ LAKt・f(φKt)    …(32)
【数１１】
0005466763.tif 000012
は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(33)の分母は、以下のように表される。
(φρ-φ1)・...・(φρ-φρ-1)・(φρ-φρ+1)・...・(φρ-φKt)
式(33)の分子は、以下のように表される。
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φKt)
【００５１】
上述した各秘密分散は体上でも実行可能である。また、これらを拡張して秘密情報SEに応じた値をシェア情報shareに応じた値に秘密分散することもできる。秘密情報SEに応じた値とは秘密情報SEそのものや秘密情報SEの関数値であり、シェア情報shareに応じた値とはシェア情報shareそのものやシェア情報の関数値である。例えば、有限体Fqの元である秘密情報SE∈Fqに応じた巡回群GTの元gTSE∈GTを秘密情報SEの各シェア情報share(1),share(2)に応じた巡回群GTの元gTshare(1),gTshare(2)∈GTに秘密分散することもできる。上述した秘密情報SEはシェア情報shareの線形結合となる（式(31)(32)）。秘密情報SEがシェア情報shareの線形結合となる秘密分散方式を線形秘密分散方式と呼ぶ。
【００５２】
上述した所定の論理式は、秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。すなわち、ド・モルガンの法則により、上述した所定の論理式はリテラルからなる論理式、又は、論理記号∧，∨の少なくとも一部とリテラルとからなる論理式（これらを「標準形論理式」と呼ぶことにする）によって表現でき、この標準形論理式は秘密情報を階層的に秘密分散して得られる木構造データによって表現できる。
【００５３】
標準形論理式を表現する木構造データは複数のノードを含み、少なくとも一部のノードは１個以上の子ノードの親ノードとされ、親ノードの１つはルートノードとされ、子ノードの少なくとも一部は葉ノードとされる。ルートノードの親ノードや、葉ノードの子ノードは存在しない。ルートノードには秘密情報に応じた値が対応し、各親ノードの子ノードには当該親ノードに対応する値を秘密分散して得られたシェア情報に応じた値が対応する。各ノードでの秘密分散形態（秘密分散方式やしきい値）は標準形論理式に応じて定まる。また、各葉ノードには標準形論理式を構成する各リテラルが対応し、当該各リテラルの真理値は第１情報と第２情報との組み合わせによって定まる。
【００５４】
ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られないものとする。また、上述した秘密分散の性質により、親ノードに対応するシェア情報に応じた値（その親ノードがルートノードであれば秘密情報に応じた値）は、その子ノードに対応するシェア情報に応じた値が当該親ノードに対応するしきい値以上の個数だけ得られた場合にのみ復元される。そのため、どの葉ノードに対応するリテラルの真理値が真になったのかと木構造データの構成（各ノードでの秘密分散の形態を含む）とに応じ、最終的にルートノードに対応する秘密情報に応じた値が復元できるか否かが定まる。各葉ノードに対応する各リテラルの真理値が標準形論理式の真理値を真にする場合にのみ最終的にルートノードに対応する秘密情報に応じた値が復元できるように木構造データが構成されている場合、このような木構造データは標準形論理式を表現する。このような標準形論理式を表現する木構造データは容易に設定できる。以下に具体例を示す。
【００５５】
図１は、命題変数PRO(1),PRO(2)と命題変数PRO(3)の否定¬PRO(3)と論理記号∧，∨とを含む標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を表現する木構造データを例示する図である。図１に例示する木構造データは複数のノードN1,...,N5を含む。ノードN1はノードN2,N5の親ノードとされ、ノードN2はノードN3,N4の親ノードとされ、親ノードの１つノードN1がルートノードとされ、子ノードの一部であるノードN3,N4,N5が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N5には、秘密情報SEに応じた値が1-out-of-2分散方式で秘密分散された各シェア情報SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散された各シェア情報SE-SH1,SH1に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=SE-SH1に応じた値が対応し、葉ノードN4にはシェア情報share(2)=SH1に応じた値が対応し、葉ノードN5にはシェア情報share(3)=SEに応じた値が対応する。葉ノードN3,N4,N5には標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)を構成する各リテラルPRO(1),PRO(2),¬PRO(3)がそれぞれ対応し、当該各リテラルPRO(1),PRO(2),¬PRO(3)の真理値は第１情報と第２情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第１情報と第２情報との組み合わせが標準形論理式PRO(1)∧PRO(2)∨¬PRO(3)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。
【００５６】
図２は、命題変数PRO(1),PRO(2),PRO(3),PRO(6),PRO(7)と命題変数PRO(4),PRO(5)の否定¬PRO(4),¬PRO(5)と論理記号∧，∨とを含む標準形論理式(PRO(1)∧PRO(2))∨(PRO(2)∧PRO(3))∨(PRO(1)∧PRO(3))∨¬PRO(4)∨(¬PRO(5)∨PRO(6))∧PRO(7)を表現する木構造データを例示する図である。
【００５７】
図２に例示する木構造データは複数のノードN1,...,N11を含む。ノードN1はノードN2,N6,N7の親ノードとされ、ノードN2はノードN3,N4,N5の親ノードとされ、ノードN7はノードN8,N11の親ノードとされ、ノードN8はノードN9,N10の親ノードとされ、親ノードの１つであるノードN1がルートノードとされ、ノードN3,N4,N5,N6,N9,N10,N11が葉ノードとされる。ノードN1には秘密情報SEに応じた値が対応し、ノードN1の子ノードN2,N6,N7には、秘密情報SEに応じた値が1-out-of-3分散方式で秘密分散された各シェア情報SE,SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4,N5には、シェア情報SEに応じた値が2-out-of-3分散方式で秘密分散された各シェア情報(1,f(1)),(2,f(2)),(3,f(3))に応じた値がそれぞれ対応する。ノードN7の子ノードN8,N11には、シェア情報SEに応じた値が2-out-of-2分散方式で秘密分散して得られた各シェア情報SH4,SE-SH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9,N10には、シェア情報SH4に応じた値が1-out-of-2分散方式で秘密分散して得られた各シェア情報SH4,SH4に応じた値がそれぞれ対応する。すなわち、葉ノードN3にはシェア情報share(1)=(1,f(1))に応じた値が対応し、葉ノードN4にはシェア情報share(2)=(2,f(2))に応じた値が対応し、葉ノードN5にはシェア情報share(3)=(3,f(3))に応じた値が対応し、葉ノードN6にはシェア情報share(4)=SEに応じた値が対応し、葉ノードN9にはシェア情報share(5)=SH4に応じた値が対応し、葉ノードN10にはシェア情報share(6)=SH4に応じた値が対応し、葉ノードN11にはシェア情報share(7)=SE-SH4に応じた値が対応する。また、葉ノードであるノードN3,N4,N5,N6,N9,N10,N11には標準形論理式(PRO(1)∧PRO(2))∨(PRO(2)∧PRO(3))∨(PRO(1)∧PRO(3))∨¬PRO(4)∨(¬PRO(5)∨PRO(6))∧PRO(7)を構成する各リテラルPRO(1),PRO(2),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)がそれぞれ対応し、各リテラルPRO(1),PRO(2),PRO(3),¬PRO(4),¬PRO(5),PRO(6),PRO(7)の真理値は第１情報と第２情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第１情報と第２情報との組み合わせが標準形論理式(PRO(1)∧PRO(2))∨(PRO(2)∧PRO(3))∨(PRO(1)∧PRO(3))∨¬PRO(4)∨(¬PRO(5)∨PRO(6))∧PRO(7)の真理値を真にする場合にのみ秘密情報SEに応じた値が復元される。 
【００５８】
＜アクセス構造＞
上述のように秘密情報を階層的に秘密分散して得られる木構造データによって所定の論理式を表現した場合、第１情報と第２情報との組み合わせに対して得られる葉ノードでのシェア情報に応じた値から秘密情報に応じた値を復元できるか否かによって、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となるか「偽」となるかを判定できる。以下、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に第１情報と第２情報との組み合わせを受け入れ、「偽」となる場合に第１情報と第２情報との組み合わせを拒絶する仕組みをアクセス構造と呼ぶ。
【００５９】
上述のように所定の論理式を表現した木構造データの葉ノードの総数をΨとし、各葉ノードに対応する識別子をλ=1,...,Ψとする。各葉ノードに対応するn(λ)次元ベクトルv(λ)→の集合{v(λ)→}λ=1,...,Ψを第１情報とし、n(λ)次元ベクトルw(λ)→の集合{w(λ)→}λ＝1,...,Ψを第２情報とする。また、上述した木構造データをラベル付き行列LMT(MT,LAB)として実装する。
【００６０】
ラベル付き行列LMT(MT,LAB)は、以下のΨ行COL列（COL≧1）の行列MTと、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)とを含む。
【数１２】
0005466763.tif 000013
【００６１】
行列MTの各要素mtλ,col（col=1,...,COL）は次の２つの要件を満たす。第１に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトルGV→と秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトルCV→との間に以下の関係が成立する。
GV→=(gv1,...,gvCOL)∈FqCOL          …(35)
CV→=(cv1,...,cvCOL)∈FqCOL          …(36)
SE=GV→・(CV→)T          …(37)
以下にCOL次元ベクトルGV→の具体例を示す。
GV→=(1F,...,1F)∈FqCOL          …(38)
ただし、GV→=(1F,0F,...,0F)∈FqCOLなどのその他のCOL次元ベクトルがGV→であってもよい。
【００６２】
第２に、識別子λに対応する葉ノードにシェア情報share(λ)∈Fqに応じた値が対応する場合、以下の関係が成立する。
(share(1),...,share(Ψ))T=MT・(CV→)T      …(39)
上述のように所定の論理式を表現した木構造データが定まれば、これら２つの要件を満たす行列MTを選択することは容易である。秘密情報SEやシェア情報share(λ)が変数であったとしても、これら２つの要件を満たす行列MTを選択することは容易である。すなわち、行列MTを定めた後で秘密情報SEやシェア情報share(λ)の値が定められてもよい。
【００６３】
また、行列MTの各行λ=1,...,Ψに対応付けられたラベルLAB(λ)は、識別子λに対応する葉ノードに対応するリテラル（PRO(λ)又は¬PRO(λ)）に対応する。ここで、命題変数PRO(λ)の真理値が「真」であることと第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が含むv(λ)→と第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が含むw(λ)→との内積v(λ)→・w(λ)→が０となることとが等価であると扱い、命題変数PRO(λ)の真理値が「偽」であることと内積v(λ)→・w(λ)→が０とならないこととが等価であると扱う。PRO(λ)に対応するラベルLAB(λ)がv(λ)→を表し、¬PRO(λ)に対応するラベルLAB(λ)が¬v(λ)→を表すものとする。なお、¬v(λ)→はv(λ)→の否定を表す論理式であり、¬v(λ)→からv(λ)→の特定が可能である。LAB(λ)がv(λ)→を表すことを「LAB(λ)=v(λ)→」と表記し、LAB(λ)が¬v(λ)→を表すことを「LAB(λ)=¬v(λ)→」と表記する。LAB(λ)（λ=1,...,Ψ）の集合{LAB(λ)}λ=1,...,ΨをLABと表記する。
【００６４】
Ψ次元ベクトルTFV→が以下のように定義される。
TFV→=(tfv(1),...,tfv(Ψ))          …(40)
要素tfv(λ)は、内積v(λ)→・w(λ)→が０のときにtfv(λ)=１となり、０以外のときにtfv(λ)=0となる。
tfv(λ)=1  （PRO(λ)が真）    if  v(λ)→・w(λ)→=0    …(41)
tfv(λ)=0  （PRO(λ)が偽）    if  v(λ)→・w(λ)→≠0  …(42)
【００６５】
さらに、以下の論理式の真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。
{(LAB(λ)=v(λ)→)∧(tfv(λ)=1)}∨{(LAB(λ)=¬v(λ)→)∧(tfv(λ)=0)}
…(43)
すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すると、行列MTが含む行ベクトルのうちLIT(λ)=1となる行ベクトルmtλ→=(mtλ,1,...,mtλ,COL)のみからなる部分行列MTTFVは以下のように表記できる。
MTTFV=(MT)LIT(λ)=1          …(44)
【００６６】
上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できることと、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属することとは等価である。すなわち、識別子λに対応する行ベクトルmtλ→で張られるベクトル空間にCOL次元ベクトルGV→が属するか否かを判定することで、識別子λに対応するシェア情報share(λ)に応じた値から秘密情報SEに応じた値が復元できるか否かが判定できる。、行ベクトルmtλ→で張られるベクトル空間とは、行ベクトルmtλ→の線形結合で表すことができるベクトル空間を意味する。
【００６７】
ここで、上述の部分行列MTTFVの各行ベクトルmtλ→で張られるベクトル空間span<MTTFV>にCOL次元ベクトルGV→が属する場合に第１情報と第２情報との組み合わせが受け入れられ、そうでない場合に第１情報と第２情報との組み合わせが拒絶されることにする。これにより、上述のアクセス構造が具体化される。なお、上述したようにラベル付き行列LMT(MT,LAB)が第１情報に対応する場合、アクセス構造が第１情報と第２情報との組み合わせを受け入れることを「アクセス構造が第２情報を受け入れる」といい、アクセス構造が第１情報と第２情報との組み合わせを受け入れないことを「アクセス構造が第２情報を拒絶する」という。
受け入れ  if  GV→∈span<MTTFV>
拒絶      if  ¬(GV→∈span<MTTFV>)
【００６８】
GV→∈span<MTTFV>の場合、以下を満たす係数const(μ)が存在し、このような係数const(μ)は行列MTのサイズのオーダーの多項式時間で求めることができる。
SE=Σμ∈SETconst(μ)・share(μ)          …(45)
{const(μ)∈Fq|μ∈SET},SET⊆{1,...,λ|LIT(λ)=1}
【００６９】
＜アクセス構造を用いた関数暗号方式の基本方式＞
以下では、アクセス構造を用いた関数暗号方式によって鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本方式を例示する。この基本方式はSetup(1sec，(Ψ;n(1),...,n(Ψ)))，GenKey(PK,MSK,LMT(MT,LAB))，Enc(PK,M,{λ,v(λ)→|λ=1,...,Ψ})(v1(λ)=1F)，Dec(PK,SKS,C)を含む。また、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされる。
【００７０】
［Setup(1sec，(Ψ;n(1),...,n(Ψ)))：セットアップ］
−入力：1sec，(Ψ;n(1),...,n(Ψ))
−出力：マスター鍵情報MSK，公開パラメータPK
【００７１】
Setupでは各ψ=0,...,Ψについて以下の処理が実行される。
(Setup-1) 1secを入力としてセキュリティパラメータsecでの位数q、楕円曲線E、巡回群G1, G2,GT、双線形写像eψ(ψ=0,...,Ψ)が生成される（param=(q, E, G1, G2,GT, eψ)）。
(Setup-2) τ'∈Fqが選択され、X*(ψ)=τ'・(X(ψ)-1)Tを満たす行列X(ψ)，X*(ψ)が選択される。
(Setup-3) 基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(21)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B(ψ)が生成される。
(Setup-4) 基底ベクトルai*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(23)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B*(ψ)が生成される。
(Setup-5) B*(ψ)＾の集合{B*(ψ)＾}ψ=0,...,Ψをマスター鍵情報MSK={B*(ψ)＾}ψ=0,...,Ψとする。B(ψ)＾の集合{B(ψ)＾}ψ=0,...,Ψと1secとparamとを公開パラメータPKとする。ただし、B*(ψ)＾は行列B*(ψ)又はその部分行列であり、B(ψ)＾は行列B(ψ)又はその部分行列である。集合{B*(ψ)＾}ψ=0,...,Ψは、少なくとも、b1*(0),b1*(λ) …,bn(λ)*(λ)（λ=1,...,Ψ）を含む。集合{B(ψ)＾}ψ=0,...,Ψは、少なくとも、b1(0),b1(λ),…,bn(λ)(λ)（λ=1,...,Ψ）を含む。以下に一例を示す。
・n(0)+ζ(0)≧5, ζ(λ)=3・n(λ)
・B(0)＾=(b1(0) b3(0) b5(0))T
・B(λ)＾
=(b1(λ) … bn(λ)(λ) b3・n(λ)+1(λ) … b4・n(λ)(λ))T（λ=1,...,Ψ）
・B*(0)＾=(b1*(0) b3*(0) b4*(0))T
・B*(λ)＾
=(b1*(λ) … bn(λ)*(λ) b2・n(λ)+1*(λ) … b3・n(λ)*(λ))T（λ=1,...,Ψ）
【００７２】
［GenKey(PK,MSK,LMT(MT,LAB))：鍵情報生成］
−入力：公開パラメータPK，マスター鍵情報MSK，第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}に対応するラベル付き行列LMT(MT,LAB)
−出力：鍵情報SKS
【００７３】
(GenKey-1) 式(35)-(39)を満たす秘密情報SEに対して以下の処理が実行される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)          …(46)
ただし、Iは2以上n(0)+ζ(0)以下の定数である。coefι(0)∈Fqは定数又は乱数である。「乱数」とは真性乱数や擬似乱数を意味する。以下にD*(0)の一例を示す。なお、式(47)のcoef4(0)は乱数である。
D*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)          …(47)
【００７４】
(GenKey-2) 式(35)-(39)を満たすshare(λ)(λ=1,...,Ψ)に対して以下の処理が実行される。
LAB(λ)=v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(48)
LAB(λ)=¬v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(49)
ただしcoef(λ),coefι(λ)∈Fqは定数又は乱数である。以下に一例を示す。
LAB(λ)=v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(50)
LAB(λ)=¬v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(51)
なお、式(50)(51)のcoef(λ)及びcoefι(λ)は乱数である。
【００７５】
(GenKey-3) 以下の鍵情報が生成される。
SKS=(LMT(MT,LAB),D*(0),D*(1),...,D(Ψ))          …(52)
【００７６】
［Enc(PK,M,VSET2)：暗号化］
−入力：公開パラメータPK，平文M，第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}(w1(λ)=1F)
−出力：暗号文C
【００７７】
(Enc-1) 以下の処理によって共通鍵Kの暗号文C(ψ)(ψ=0,...,Ψ)が生成される。
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)          …(53)
C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)
…(54)
ただし、υ,υι(ψ)∈Fq(ψ=0,...,Ψ)は定数又は乱数であり、以下の関係が満たされる。
(coef2(0),...,coefI(0))・(υ2(0),...,υI(0))=υ'      …(55)
coefι(λ)・υι(λ)=0F (ι=n(λ)+1,...,n(λ)+ζ(λ))  …(56)
υ'の例はυ2(0),...,υI(0)の何れか１個である。例えば、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)が乱数であり、ζ(λ)=3・n(λ)、I=5であり、以下の関係が満たされる。
(υ2(0),...,υI(0))=(0F,υ3(0),0F,υ5(0))
υ'=υ3(0)
(υn(λ)+1(λ),...,υ3・n(λ)(λ))=(0F,...,0F)
【００７８】
(Enc-2) 以下の共通鍵が生成される。
K=gTτ・τ'・υ'∈GT          …(57)
例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(58)
【００７９】
(Enc-3) 共通鍵Kを用いて平文Mの暗号文C(Ψ+1)が生成される。
C(Ψ+1)=EncK(M)          …(59)
共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリア（Camellia）（登録商標）やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncK(M)を生成してもよい。ただし、式(60)の例ではM∈GTとされる。
C(Ψ+1)=gTυ'・M          …(60)
【００８０】
(Enc-4) 以下の暗号文が生成される。
C=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,C(Ψ+1))          …(61)
ただし、下付き添え字の「w(λ)→」は「w(λ)→」を表す。
【００８１】
［Dec(PK,SKS,C)：復号］
−入力：公開パラメータPK，鍵情報SKS，暗号文C
−出力：平文M'
【００８２】
(Dec-1) λ=1,...,Ψについて、鍵情報SKSが含むラベル付き行列LMT(MT,LAB)の各ラベルLAB(λ)であるn(λ)次元ベクトルv(λ)→と暗号文CのVSET2が含むn(λ)次元ベクトルw(λ)→との内積v(λ)→・w(λ)→が0となるか否かが判定され、これとLMT(MT,LAB)の各ラベルLAB(λ)とによってGV→∈span<MTTFV>であるか否かが判定される（式(40)-(45)）。GV→∈span<MTTFV>でなければ暗号文Cが拒絶され、GV→∈span<MTTFV>であれば暗号文Cが受け入れられる。
【００８３】
(Dec-2) 暗号文Cが受け入れられると、SET⊆{1,...,λ|LIT(λ)=1}と式(45)を満たす係数const(μ)(μ∈SET)とが計算される。
【００８４】
(Dec-3) 以下の共通鍵が生成される。
【数１３】
0005466763.tif 000014
【００８５】
ここで、式(6)(25)(55)より、以下の関係が満たされる。
【数１４】
0005466763.tif 000015
【００８６】
式(6)(25)(41)(48)(54)(56)及びw1(λ)=1Fより、以下の関係が満たされる。
【数１５】
0005466763.tif 000016
【００８７】
式(6)(25)(42)(49)(54)(56)より、以下の関係が満たされる。
【数１６】
0005466763.tif 000017
【００８８】
式(45)(63)-(65)より以下の関係が満たされる。
【数１７】
0005466763.tif 000018
例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(67)
【００８９】
(Dec-4) 共通鍵Kを用い、以下のように平文M'が生成される。
M'=DecK(C(Ψ+1))=DecK(C(Ψ+1))          …(68)
例えば、式(60)に例示した共通鍵暗号方式の場合、以下のように平文M'が生成される。
M'=C(Ψ+1)/K          …(69)
【００９０】
なお、gTをGTの生成元とする代わりにgTτやgTτ'やgTτ・τ'をGTの生成元と扱ってもよい。また、鍵情報SKSのλと暗号文のλとを対応関係を特定する写像を用いてC(λ)とD*(λ)との組み合わせを特定し、［Dec(PK,SKS,C)：復号］の処理が実行されてもよい。第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の1番目の要素w1(λ)が1Fとされるだけではなく、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}のn(λ)番目の要素vn(λ)(λ)が1Fとされてもよい。要素w1(λ)が1Fでない場合にはw(λ)→の代わりにw(λ)→/w1(λ)を用いてもよく、要素vn(λ)(λ)が1Fでない場合にはv(λ)→の代わりにv(λ)→/vn(λ)(λ)を用いてもよい。第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の代わりに第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が用いられ、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}の代わりに第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が用いられてもよい。この場合には第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}の1番目の要素v1(λ)が1Fとされる。
【００９１】
〔CCA安全性〕
以下の[1]-[4]が実行された場合に式(70)の関係が満たされるとき、以下の暗号オラクル及び復号オラクルに対応する暗号方式はCCA安全である。
Pr[bit=bit']<(1/2)-FNK(sec)          …(70)
ただしFNK(sec)はsecの関数であり、0<FNK(sec)≦1/2が満たされる。[2]の後に[3]が行われるのであれば「CCA2に対して安全である」といい、[3]の後に[2]が行われるのであれば「CCA1に対して安全である」という。「CCA2」は「CCA1」よりも強力な攻撃法である。
[1]攻撃者に公開パラメータPKが与えられる。
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルに2つのビット列である平文M0,M1を渡し、暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを暗号化し、その暗号文Cbitを攻撃者に渡す。
[3]攻撃者は、鍵情報SKSを持つ復号オラクルに暗号文Cbit'（Cbit'≠Cbit）を渡し、復号オラクルから暗号文Cbit'の復号結果を受け取ることができる。
[4]攻撃者は、bit'∈{0,1}を出力する。
【００９２】
〔アクセス構造を用いた関数暗号方式の基本方式のCCA安全性〕
上述したアクセス構造を用いた関数暗号方式の基本方式はCCA安全ではない。このことを簡単な例を示して説明する。この簡単な例では、平文Mがバイナリ系列である。平文Mに対する共通鍵Kを用いた共通鍵暗号方式の暗号文C(Ψ+1)=EncK(M)（式(59)）が以下の式に従って生成される。
C(Ψ+1)=MAP(K)(+)M        …(71)
共通鍵Kを用いた暗号文C(Ψ+1)の復号結果（式(68)）が以下の式に従って生成される。
M'=C(Ψ+1)(+)MAP(K)        …(72)
なお、MAP(K)はK∈GTのバイナリ系列への写像を表す。この場合、攻撃者は以下のような戦略（以下「想定戦略」と呼ぶ）をとることができる。
[1]攻撃者に公開パラメータPKが与えられる。
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルに第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}と2つの平文M0, M1を渡す。暗号オラクルは、ランダムにbit∈{0,1}を選択し、一方の平文Mbitを共通鍵K（式(57)）で暗号化して以下の暗号文Cbit(Ψ+1)
Cbit(Ψ+1)=MAP(K)(+)Mbit        …(73)
を生成する。暗号オラクルはさらに暗号文C(0), C(λ)(λ=1,...,Ψ)(式(53)(54))を生成し、以下の暗号文を攻撃者に渡す。
Cbit=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,Cbit(Ψ+1)) …(74)
[3]攻撃者は、鍵情報SKS(式(52))を持つ復号オラクルに以下の暗号文Cbit'を渡し、復号オラクルから暗号文Cbit'の復号結果を受け取る。
Cbit'=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,Cbit(Ψ+1)(+)ΔM) …(75)
ただしΔMは攻撃者に値が知られたバイナリ系列である。
ここで、bit=0だったのであれば、Cbit(Ψ+1)=MAP(K)(+)M0であり、Cbit(Ψ+1)(+)ΔMの復号結果はM0(+)ΔMとなる。一方、bit=1だったのであれば、Cbit(Ψ+1)=MAP(K)(+)M1であり、Cbit(Ψ+1)(+)ΔMの復号結果はM0(+)ΔMとなる。
[4]攻撃者は、Cbit'の復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する。
この場合Pr[bit=bit']=1となり、式(70)を満たさない。
【００９３】
〔本形態のアクセス構造を用いた関数暗号方式〕
上述のように、アクセス構造を用いた関数暗号方式の基本方式はCCA安全ではない。一方、アクセス構造を用いた関数暗号方式の基本方式にCCA安全性を持たせるためにCHK 変換方式やBK 変換方式を用いるのでは、CCA安全性を向上させるためのみに用いる2次元の暗号文空間がさらに必要となる。本形態では、CCA安全性を向上させるための追加の暗号文空間なしにCCA安全性が向上する。
【００９４】
＜関数暗号方式の改良方式＞
以下に、本形態の関数暗号方式の改良方式を概説する。
[暗号化処理]
暗号化処理を行う暗号化装置が以下の処理を実行する。
(Enc-11) 乱数生成部が、乱数ｒを生成する。
(Enc-12) 第１暗号化部が、乱数ｒに応じたバイナリ系列とバイナリ系列の平文Mとの排他的論理和値である暗号文C2を生成する。乱数ｒは秘密情報であり、乱数ｒを知らないものは暗号文C2から平文Mを復元できない。
(Enc-13) 関数演算部が、乱数ｒと暗号文C2との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、Smax（Smax≧1）個の関数値HS(ｒ,C2)(S=1,...,Smax)を生成する。
(Enc-14) 共通鍵生成部が、巡回群GTの生成元gT及び定数τ,τ'に対し、以下の関係を満たす共通鍵Kを生成する。
K=gTτ・τ'・υ'∈GT        …(76)
(Enc-15) 第２暗号化部が、共通鍵Kを用いて共通鍵暗号方式によって乱数ｒを暗号化して暗号文C(Ψ+1)を生成する。
(Enc-16) 第３暗号化部が、以下のC(0), C(λ)（λ=1,...,Ψ）, C(Ψ+1)を含む暗号文C1を生成する。
C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)      …(77)
C(λ)
=υ・Σι=1n(λ)wι(λ)・bι(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)    …(78)
C(Ψ+1)
【００９５】
式(55)(56)の関係が満たされ、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ,C2)(S=1,...,Smax)の何れかに対応する。言い換えると、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ,C2)(S=1,...,Smax)の何れかに応じて定まる。例えば、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部が関数値HS(ｒ,C2)(S=1,...,Smax)の何れか又は関数値HS(ｒ,C2)(S=1,...,Smax)の何れかの関数値である。関数値HS(ｒ,C2)(S=1,...,Smax)に対応しないυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))は定数や乱数とされる。
【００９６】
[復号処理]
復号処理を行う復号装置が以下の処理を実行する。
(DEC-11) 式(45)を満たす係数const(μ)が存在する場合、共通鍵生成部が以下の第１鍵情報D*(0)，第２鍵情報D*(λ)（λ=1,...,Ψ）及び共通鍵K’を生成する。
第１鍵情報は以下の式で表される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)        …(79)
LAB(λ)=v(λ)→を満たすλに対する第２鍵情報D*(λ)は、以下の式で表される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)      …(80)
LAB(λ)=¬v(λ)→を満たすλに対する第２鍵情報D*(λ)は、以下の式で表される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)      …(81)
共通鍵生成部は、入力された暗号文C'(0)、C'(λ)（λ=1,...,Ψ）を用いて、以下の式に従って共通鍵K’を生成する。
【数１８】
0005466763.tif 000019
(DEC-12) 第１復号部が、共通鍵K'を用い、入力された暗号文C'(Ψ+1)を復号して復号値r'を生成する。
(DEC-13) 関数演算部が、復号値r'と入力された暗号文C2'との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、Smax（Smax≧1）個の関数値HS(ｒ',C2')(S=1,...,Smax)を生成する。
(DEC-14) 暗号文C'(0),C'(λ)と暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0),C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)とが一致しない場合、判定部が復号を拒絶する。一方、暗号文C'(0),C'(λ)と暗号文C''(0),C''(λ)とが一致する場合、第２復号部が復号値r'に応じたバイナリ系列と入力されたバイナリ系列の暗号文C2'との排他的論理和である復号値M'を生成する。
【００９７】
なお、υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ',C2')(S=1,...,Smax)の何れかに対応する。言い換えると、υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値が関数値HS(ｒ',C2')(S=1,...,Smax)の何れかに応じて定まる。例えば、υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部が関数値HS(ｒ',C2')(S=1,...,Smax)の何れか又は関数値HS(ｒ',C2')(S=1,...,Smax)の何れかの関数値である。また、関数値HS(ｒ',C2')(S=1,...,Smax)に対応しないυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))は定数又は乱数とされる。
【００９８】
＜関数暗号方式の改良方式のCCA安全性＞
この改良方式に対し、上述の想定戦略が適用された場合を想定する。
[1]攻撃者に公開パラメータPKが与えられる。
[2]攻撃者は、公開パラメータPKを持つ暗号オラクルに第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}と2つの平文M0, M1を渡す。暗号オラクルは、ランダムにbit∈{0,1}を選択し、乱数ｒを生成し(Enc-11)、乱数ｒに応じたバイナリ系列とバイナリ系列の平文Mbitとの排他的論理和値である暗号文C2を生成し(Enc-12)、乱数ｒと暗号文C2との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、Smax（Smax≧1）個の関数値HS(ｒ,C2)(S=1,...,Smax)を生成し(Enc-13)、K=gTτ・τ'・υ'∈GT（式(76)）を満たす共通鍵Kを生成し(Enc-14)、共通鍵Kを用いて共通鍵暗号方式によって乱数ｒを暗号化して暗号文C(Ψ+1)を生成する。さらに、暗号オラクルは、C(0)=υ・b1(0)+Σι=2Iυι(0)・bι(0)（式(77)）、C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)（式(78)）及びC(Ψ+1)を含む暗号文C1を生成する(Enc-16)。ここで、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部が関数値HS(ｒ,C2)(S=1,...,Smax)の何れかに依存する。暗号オラクルは、生成した暗号文C1及びC2を含む暗号文Cbitを攻撃者に渡す。
[3]攻撃者は、以下の暗号文を生成できる。
C2'=C2(+)ΔM        …(83)
しかしながら、乱数ｒを知らない攻撃者は乱数ｒと暗号文C2'との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、関数値HS(ｒ,C2')(S=1,...,Smax)を生成することができない。そのため、攻撃者は、暗号文C1と暗号文C2'とを含む暗号文Cbit'を、第１鍵情報D*(0)（式(79)）及び第２鍵情報D*(λ)（式(80)(81)）を持つ復号オラクルに渡す。
暗号文Cbit'が入力された復号オラクルは、式(45)を満たす係数const(μ)が存在する場合に共通鍵K'（式(82)）を生成し(DEC-11)、共通鍵K'を用いて暗号文C1が含む暗号文C'(Ψ+1)を復号して復号値r'を生成し(DEC-12)、復号値r'と入力された暗号文C2'との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、Smax（Smax≧1）個の関数値HS(ｒ',C2')(S=1,...,Smax)を生成する(DEC-13)。関数HSの衝突困難性によって高い確率でHS(ｒ',C2')≠HS(ｒ,C2)となるため、暗号文C'(0),C'(λ)と暗号文C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0), C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)とが一致しない確率が高く、復号は拒絶される。
[4]攻撃者は、C2'=C2(+)ΔMの復号結果を取得できないため、「復号結果がM0(+)ΔMのときにbit'=0を出力し、M1(+)ΔMのときにbit'=1を出力する」ことができない。よって、この攻撃者の戦略は成功しない。
【００９９】
〔実施形態〕
次に、上記改良方式の実施形態を説明する。以下では、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が鍵情報に組み込まれ、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が暗号文に組み込まれる例を示す。しかしながら、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}が鍵情報に組み込まれ、第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}が暗号文に組み込まれる構成でもかまわない。なお、本形態の例では、第１情報VSET1を構成するn(λ)次元ベクトルv(λ)→が特定のポリシーに対応し、第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}を構成するn(λ)次元ベクトルw(λ)→が属性に対応する。n(λ)次元ベクトルw(λ)→に対応する属性がn(λ)次元ベクトルv(λ)→に対応するポリシーに合致するときに内積v(λ)→・w(λ)→=0となり、n(λ)次元ベクトルw(λ)→に対応する属性がn(λ)次元ベクトルv(λ)→に対応するポリシーに合致しないときに内積v(λ)→・w(λ)→≠0となるように設定されている。
【０１００】
[全体構成]
図３に例示するように、本形態の暗号システム１は、暗号化装置１１０と復号装置１２０と鍵生成装置１３０とを有する。暗号化装置１１０と復号装置１２０、復号装置１２０と鍵生成装置１３０は、ネットワークや可搬型記録媒体などを介した情報伝達が可能とされている。 
【０１０１】
[暗号化装置]
図４に例示するように、本形態の暗号化装置１１０は、入力部１１１、出力部１１２、記憶部１１３、制御部１１４、乱数生成部１１５、暗号化部１１６ａ，１１６ｄ，１１６ｅ、関数演算部１１６ｂ、共通鍵生成部１１６ｃ及び結合部１１７を有する。
暗号化装置１１０は、例えば、CPU（Central Processing Unit）、RAM（Random Access Memory）、ROM（Read-Only Memory）等を備える公知又は専用のコンピュータと特別なプログラムを含む特別な装置である。乱数生成部１１５、暗号化部１１６ａ，１１６ｄ，１１６ｅ、関数演算部１１６ｂ、共通鍵生成部１１６ｃ及び結合部１１７は、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、乱数生成部１１５が公知の乱数生成用IC(integrated Circuit)とするなど、処理部の少なくとも一部が特別な集積回路で構成してもよい。また、記憶部１１３は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。入力部１１１は、例えば、キーボードなどの入力インタフェースや、モデム、LAN（Local Area Network）カード等の通信装置や、ＵＳＢ端子などの入力ポートなどである。出力部１１２は、例えば、出力インタフェースや、モデム、LANカード等の通信装置、ＵＳＢ端子などの出力ポートなどである。また、暗号化装置１１０は、制御部１１４の制御のもと各処理を実行する。
【０１０２】
[復号装置]
図５に例示するように、本形態の復号装置１２０は、入力部１２１、出力部１２２、記憶部１２３、制御部１２４、共通鍵生成部１２６ａ、復号部１２６ｂ，１２６ｅ、関数演算部１２６ｃ、判定部１２６ｄ及び分離部１２７を有する。
復号装置１２０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムを含む特別な装置である。すなわち、制御部１２４、共通鍵生成部１２６ａ、復号部１２６ｂ，１２６ｅ、関数演算部１２６ｃ、判定部１２６ｄ及び分離部１２７は、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、処理部の少なくとも一部が特別な集積回路で構成されてもよい。また、記憶部１２３は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、入力部１２１は、例えば、入力インタフェースや通信装置や入力ポートなどである。出力部１２２は、例えば、出力インタフェースや通信装置や出力ポートなどである。また、復号装置１２０は、制御部１２４の制御のもと各処理を実行する。
【０１０３】
[鍵生成装置]
図６に例示するように、本形態の鍵生成装置１３０は、入力部１３１、出力部１３２、記憶部１３３、制御部１３４、選択部１３５、シェア情報生成部１３６ａ、秘密情報生成部１３６ｂ及び鍵生成部１３６ｃ，１３６ｄ，１３６ｅを有する。
鍵生成装置１３０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムを含む特別な装置である。すなわち、制御部１３４、選択部１３５、シェア情報生成部１３６ａ、秘密情報生成部１３６ｂ及び鍵生成部１３６ｃ，１３６ｄ，１３６ｅは、例えば、CPUが特別なプログラムを実行することで構成される処理部である。また、処理部の少なくとも一部が特別な集積回路で構成されてもよい。また、記憶部１３３は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。また、入力部１３１は、例えば、入力インタフェースや通信装置や入力ポートなどである。出力部１３２は、例えば、出力インタフェースや通信装置や出力ポートなどである。また、鍵生成装置１３０は、制御部１３４の制御のもと各処理を実行する。
【０１０４】
[事前設定]
次に、本形態の各処理を実行するための事前設定を説明する。
図示していない管理装置によって前述の[Setup(1sec，(Ψ;n(1),...,n(Ψ)))：セットアップ］が実行され、集合{B(ψ)＾}ψ=0,...,Ψと1secとparam=(q, E, G1, G2, GT, eψ)とからなる公開パラメータPKと、マスター鍵情報MSK={B*(ψ)＾}ψ=0,...,Ψとが設定される。公開パラメータPKは、暗号化装置１１０、復号装置１２０及び鍵生成装置１３０で利用可能なようにこれらの装置に設定される。マスター鍵情報MSKは、鍵生成装置１３０で利用可能なように鍵生成装置１３０に設定される。マスター鍵情報MSKは秘密情報であり、公開されない。装置への公開パラメータPKなどの設定は、装置を構成する特別なプログラムに公開パラメータPKなどが組み込まれることで行われてもよいし、装置の記憶装置に格納されることで行われてもよい。本形態では、特別なプログラムに公開パラメータPKなどが組み込まれている例を示す。 
【０１０５】
[鍵情報の生成処理]
鍵情報の生成処理は、特に、復号装置１２０の記憶部１２３に鍵情報SKSが格納されていない場合に実行される。復号装置１２０の記憶部１２３に鍵情報SKSが格納されているときには、この処理が省略されてもよい。鍵情報の生成処理は暗号文の生成前に行われてもよいし、暗号文の生成後に行われてもよい。
【０１０６】
図７に例示するように、鍵情報の生成処理では、まず鍵生成装置１３０（図６）の入力部１３１に、生成する鍵情報に対応するラベル付き行列LMT(MT,LAB)が入力される。前述のように、ラベル付き行列LMT(MT,LAB)は、式(34)の行列MTと第１情報VSET1を構成するn(λ)次元ベクトルv(λ)→に対応するラベルLAB(λ)（LAB(λ)=v(λ)→又はLAB(λ)=¬v(λ)→）とが対応付けられた情報である。入力されたラベル付き行列LMT(MT,LAB)は記憶部１３３に格納される（ステップＳ１１）。
【０１０７】
次に、選択部１３５が有限体Fqの元を要素とするCOL次元ベクトルCV→∈FqCOL（式(36)）を任意に選択し、COL次元ベクトルCV→を記憶部１３３に格納する（ステップＳ１２）。シェア情報生成部１３６ａに行列MTとCOL次元ベクトルCV→とが入力され、シェア情報生成部１３６ａが式(39)に従ってシェア情報share(λ)∈Fq（λ=1,...,Ψ）を計算し、生成したシェア情報share(λ)∈Fq（λ=1,...,Ψ）を記憶部１３３に格納する（ステップＳ１３）。秘密情報生成部１３６ｂにCOL次元ベクトルCV→が入力され、秘密情報生成部１３６ｂが式(37)に従って秘密情報SEを生成して記憶部１３３に格納する（ステップＳ１４）。
【０１０８】
次に、鍵生成部１３６ｃに秘密情報SEが入力され、鍵生成部１３６ｃは式(46)に従って鍵情報D*(0)を生成して記憶部１３３に格納する。例えば、鍵生成部１３６ｃは式(47)に従って鍵情報D*(0)を生成して記憶部１３３に格納する（ステップＳ１５）。鍵生成部１３６ｄにラベル情報LAB(λ)（λ=1,...,Ψ）が入力され、鍵生成部１３６ｄは式(48)(49)に従って鍵情報D*(λ)（λ=1,...,Ψ）を生成して記憶部１３３に格納する。例えば、鍵生成部１３６ｄは式(50)(51)に従って鍵情報D*(λ)（λ=1,...,Ψ）を生成して記憶部１３３に格納する（ステップＳ１６）。ラベル付き行列LMT(MT,LAB)、鍵情報D*(0)及び鍵情報D*(λ)（λ=1,...,Ψ）は鍵生成部１３６ｅに入力され、鍵生成部１３６ｅは、式(52)に従って鍵情報SKSを生成して出力部１３２に送る（ステップＳ１７）。
出力部１３２は鍵情報SKSを出力する（ステップＳ１８）。鍵情報SKSは復号装置１２０（図５）の入力部１２１に入力され、記憶部１２３に格納される。
【０１０９】
[暗号化処理]
図８に例示するように、暗号化処理では、まず暗号化装置１１０（図４）の入力部１１１に第２情報VSET2={λ,w(λ)→|λ=1,...,Ψ}とバイナリ系列の平文Mとが入力され、それらが記憶部１１３に格納される（ステップＳ２１）。
【０１１０】
次に、乱数生成部１１５が乱数ｒを生成し、乱数ｒを記憶部１１３に格納する。乱数ｒは単射関数Rの定義域をなす集合の元である。例えば、単射関数Rが１個の巡回群GTの元を入力とする関数であるなら乱数rは巡回群GTの元であり、単射関数Rが１個のバイナリ系列を入力とする関数であるなら乱数rはバイナリ系列である（ステップＳ２２）。
暗号化部１１６ａに乱数r及び平文Mが入力される。暗号化部１１６ａは、以下のように、乱数rに単射関数Rを作用させて得られたバイナリ系列である関数値R(r)と平文Mとの排他的論理和値を暗号文C2とする。
C2=M(+)R(r)        …(84)
暗号文C2は記憶部１１３に格納される（ステップＳ２３）。
【０１１１】
関数演算部１１６ｂに乱数ｒと暗号文C2とが入力される。関数演算部１１６ｂは、乱数ｒと暗号文C2との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力し、Smax（Smax≧1）個の関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)を生成する。なお、本形態のSmaxは定数である。以下にSmaxの一例を示す（ステップＳ２４）。
Smax=3+Σλ=1Ψn(λ)        …(85)
【０１１２】
次に、共通鍵生成部１１６ｃが巡回群GTの生成元gT及び定数τ,τ',υ'∈Fqに対して式(76)を満たす共通鍵K∈GTを生成する。υ'∈Fqは乱数でもよいが、本形態では、共通鍵生成部１１６ｃに入力された関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の何れかに対応する値をυ'∈Fqとする。例えば、関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の何れか又は関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の何れかの関数値がυ'∈Fqとなる。以下にυ'∈Fqの一例を示す（ステップＳ２５）。
υ'=H2(ｒ,C2)∈Fq        …(86)
【０１１３】
暗号化部１１６ｄには共通鍵Kと乱数rとが入力される。暗号化部１１６ｄは、共通鍵Kを用いて共通鍵暗号方式によって乱数ｒを暗号化し、以下の暗号文C(Ψ+1)を生成する。
C(Ψ+1)=EncK(r)        …(87)
暗号文C(Ψ+1)は記憶部１１３に格納される（ステップＳ２６）。
【０１１４】
暗号化部１１６ｅには、第２情報VSET2、関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の少なくとも一部及び暗号文C(Ψ+1)が入力される。暗号化部１１６ｅは、予め定められた基準に従い、関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の少なくとも一部に対応する値をυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値とし、式(77)(78)に従ってC(0)及びC(λ)（λ=1,...,Ψ）を生成する。例えば、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部が、関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の少なくとも一部又は関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)の少なくとも一部の関数値とされる。式(55)(56)が満たされる必要もある。例えば、Smax=3+Σλ=1Ψn(λ)の場合、ζ(λ)=3・n(λ)、I=5とし、υ2(0),υ4(0),υn(λ)+1(λ),...,υ3・n(λ)(λ)をそれぞれ零元0Fとし、υ'=υ3(0)とし、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)のそれぞれをH1(ｒ,C2),...,HSmax(ｒ,C2)の何れかとする。この際、安全性の観点から、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)とH1(ｒ,C2),...,HSmax(ｒ,C2)とが一対一で対応することが望ましい。その場合、Smaxの値は、υ,υ3(0),υ5(0),υ3・n(λ)+1(λ),...,υ4・n(λ)(λ)の個数以上である。
関数値HS(ｒ,C2)∈Fq(S=1,...,Smax)のいずれにも対応しないυ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))は、例えば、有限体Fqから選択された定数とされる。υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の何れがH1(ｒ,C2),...,HSmax(ｒ,C2)の何れに対応するのかは、例えば、予め定められている。
暗号化部１１６ｅは、第２情報VSET2、C(0)、C(λ)（λ=1,...,Ψ）及びC(Ψ+1)を含む、以下のような暗号文C1を生成する。
C1=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2'C(Ψ+1))        …(88)
暗号文C1は記憶部１１３に格納される（ステップＳ２７）。 
【０１１５】
暗号文C1及び暗号文C2は結合部１１７に入力される。結合部１１７は、暗号文C1に対応するバイナリ系列と暗号文C2とのビット結合値を暗号文Codeとして生成する。
Code=C1|C2        …(89)
復号装置１２０は、暗号文Code内の暗号文C1の位置と暗号文C2の位置とを特定できる。例えば、暗号文Code内の暗号文C1の位置と暗号文C2の位置とが固定とされる、又は、暗号文Code内の暗号文C1の位置と暗号文C2の位置とを表す付加情報が暗号文Codeに付加される（ステップＳ２８）。
暗号文Codeは出力部１１２に送られる。出力部１１２は暗号文Codeを出力する（ステップＳ２９）。これで暗号化処理が終了する。
【０１１６】
[復号処理]
図９に例示するように、復号処理では、まず復号装置１２０（図５）の入力部１２１に暗号文Code'が入力され、記憶部１２３に格納される。暗号文Code'は例えば上述の暗号文Codeである（ステップＳ４１）。
【０１１７】
暗号文Code'は分離部１２７に入力され、分離部１２７は予め定めれれた方法で暗号文Code'を暗号文C1'と暗号文C2'とに分離し、暗号文C1'と暗号文C2'とを記憶部１２３に格納する。暗号文Code'が暗号文Codeである場合、C1=C1'かつC2=C2'である（ステップＳ４２）。
【０１１８】
次に共通鍵生成部１２６ａに鍵情報SKS及び暗号文C1'が入力される。共通鍵生成部１２６ａは、鍵情報SKS及び暗号文C1'を用いて共通鍵K'∈GTを復元可能であるか否かを判定する。すなわち、共通鍵生成部１２６ａは、ラベル付き行列LMT(MT,LAB)に対応する第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}、暗号文C1'が含む第２情報VSET2'={λ,w(λ)→|λ=1,...,Ψ}、及びLMT(MT,LAB)の各ラベルLAB(λ)とを用い、鍵情報SKSが含むラベル付き行列LMT(MT,LAB)の各ラベルLAB(λ)であるn(λ)次元ベクトルv(λ)→と暗号文CのVSET2が含むn(λ)次元ベクトルw(λ)→との内積v(λ)→・w(λ)→が0となるか否かをそれぞれ判定し、それらの結果とLMT(MT,LAB)の各ラベルLAB(λ)とを用いてGV→∈span<MTTFV>であるか否かが判定する。前述のように、GV→∈span<MTTFV>であれば共通鍵K'∈GTが復元可能であり、GV→∈span<MTTFV>でなければ共通鍵K'∈GTが復元可能でない（ステップＳ４３）。ステップS４３の処理の具体例は後述する。共通鍵K'∈GTが復元可能でないと判断された場合には復号が拒絶され（ステップＳ４８）、復号処理が終了する。
【０１１９】
一方、共通鍵K'∈GTが復元可能であると判断された場合、共通鍵生成部１２６ａは、式(45)を満たす係数const(μ)を求め、式(82)に従って共通鍵K'∈GTを計算する。生成された共通鍵K'は記憶部１２３に格納される（ステップＳ４４）。
【０１２０】
暗号文C1'が含む暗号文C'(Ψ+1)及び共通鍵K'は復号部１２６ｂに入力される。C1=C1'で或る場合、C(Ψ+1)=C'(Ψ+1)が満たされる。復号部１２６ｂは、共通鍵K'を用い、入力された暗号文C'(Ψ+1)を復号し、以下の復号値r'を得る。
r'=DecK'(C'(Ψ+1))        …(90)
復号部１２６ｂは、復号値r'を記憶部１２３に格納する（ステップＳ４５）。
【０１２１】
関数演算部１２６ｃに復号値r'と暗号文C2'とが入力される。関数演算部１２６ｃは、復号値r'と暗号文C2'との組をSmax（Smax≧1）個の衝突困難な関数HS(S=1,...,Smax)のそれぞれに入力して関数値HS(ｒ',C2')(S=1,...,Smax)を生成する。各関数値HS(ｒ',C2')(S=1,...,Smax)は記憶部１２３に格納される（ステップＳ４６）。
【０１２２】
次に、判定部１２６ｄに、関数値HS(ｒ',C2')∈Fq(S=1,...,Smax)の少なくとも一部、及び、暗号文C1'が含む第２情報VSET2'並びに暗号文C'(0),{C'(λ)}(λ,w(λ)→)∈VSET2'が入力される。判定部１２６ｄは、第２情報VSET2'が含むn(λ)次元ベクトルw(λ)→及び関数値HS(ｒ',C2')の少なくとも一部を用いて、以下の暗号文C''(0), C''(λ)（λ=1,...,Ψ）を生成する。
C''(0)=υ''・b1(0)+Σι=2Iυι''(0)・bι(0)        …(91)
C''(λ)=υ''・Σι=1n(λ)wι(λ)・bι(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)υι''(λ)・bι(λ)        …(92)
暗号文C''(0)及びC''(λ)（λ=1,...,Ψ）の生成方法は、第２情報VSET2が第２情報VSET2'に置換され、関数値HS(ｒ,C2)が関数値HS(ｒ',C2')に置換され、υ,υι(0)(ι=2,...,I),υι(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))がυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))に置換される以外は、ステップＳ２７での暗号文C(0)及びC(λ)（λ=1,...,Ψ）の生成方法と同一である。すなわち、判定部１２６ｄは、上記の予め定められた基準に従い、関数値HS(ｒ',C2')∈Fq(S=1,...,Smax)の少なくとも一部に対応する値をυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部の値とし、式(91)(92)に従ってC''(0)及びC''(λ)（λ=1,...,Ψ）を生成する。例えば、υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の少なくとも一部が、関数値HS(ｒ',C2')∈Fq(S=1,...,Smax)の少なくとも一部又は関数値HS(ｒ',C2')∈Fq(S=1,...,Smax)の少なくとも一部の関数値とされる。式(55)(56)のυι(0),υι(λ)がυι''(0),υι''(λ)に置換された関係が満たされる必要もある。例えば、Smax=3+Σλ=1Ψn(λ)の場合、ζ(λ)=3・n(λ)、I=5とし、υ2''(0),υ4''(0),υn(λ)+1''(λ),...,υ3・n(λ)''(λ)をそれぞれ零元0Fとし、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ) ''(λ)のそれぞれをH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れかとする。例えば、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)とH1(ｒ',C2'),...,HSmax(ｒ',C2')とは一対一で対応する。その場合、Smaxの値は、υ'',υ3''(0),υ5''(0),υ3・n(λ)+1''(λ),...,υ4・n(λ)''(λ)の個数以上である。
関数値HS(ｒ',C2')∈Fq(S=1,...,Smax)のいずれにも対応しないυ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))は、例えば、有限体Fqから選択された定数（ステップＳ２７と同一の定数）とされる。υ'',υι''(0)(ι=2,...,I),υι''(λ)(ι=n(λ)+1,...,n(λ)+ζ(λ))の何れがH1(ｒ',C2'),...,HSmax(ｒ',C2')の何れに対応するのかは、例えば、ステップＳ２７と同一の基準に従って予め定められている。
判定部１２６ｄは、以下のすべてが満たされるか否かを判定する（ステップＳ４７）。
C'(0)=C''(0)        …(93)
C'(λ)=C''(λ)（λ=1,...,Ψ）        …(94) 
【０１２３】
ここで、式(93)(94)の少なくとも一部が満たさない場合には復号が拒絶され（ステップＳ４８）、復号処理が終了する。
一方、式(93)(94)がすべて満たされる場合、復号部１２６ｅにバイナリ系列の暗号文C2'及び復号値r'が入力される。復号部１２６ｅは、復号値r'に単射関数Rを作用させたバイナリ系列の関数値R(r')と暗号文C2'との排他的論理和値を復号値M'として生成する（ステップＳ４９）
M'=C2'(+)R(r')        …(95)
。復号値M'は出力部１２２に送られ、出力部１２２は復号値M'を出力する（ステップＳ５０）。これで復号処理が終了する。
【０１２４】
［ステップＳ４３の処理の具体例］
以下にステップＳ４３の処理の具体例を説明する。なお、以下では説明の簡略化のため、式(38)のCOL次元ベクトルGV→が用いられる場合を例示する。ただし、これは本発明を限定するものではなく、式(36)のように一般化されたCOL次元ベクトルGV→が用いられる場合に以下の処理が拡張され、適用されてもよい。
図１０に例示するように、まず共通鍵生成部１２６ａは、ラベル付き行列LMT(MT,LAB)に対応する第１情報VSET1={λ,v(λ)→|λ=1,...,Ψ}、暗号文C1'が含む第２情報VSET2'={λ,w(λ)→|λ=1,...,Ψ}、及びLMT(MT,LAB)の各ラベルLAB(λ)とを用い、式(41)-(44)に示した部分行列MTTFVを生成する。ここではMTTFVが以下のように表現される。
【数１９】
0005466763.tif 000020
ただし、式(96)のMTTFVはω行COL列の行列であり、ωは１以上の整数であり、ROW(1),...,ROW(ω)はそれぞれLIT(ROW(1))=1,..., LIT(ROW(ω))=1となる行列MT（式(34)）の行番号ROW(1),...,ROW(ω)∈SETである（ステップＳ４３１）。
【０１２５】
次に、共通鍵生成部１２６ａは、MTTFVの行ベクトルmtλ'→=(mtλ',1,...,mtλ',COL)（λ'= ROW(1),...,ROW(ω)）ごとの演算やMTTFVの行ベクトルmtλ'→間の演算を行って、対角成分を乗法単位元1FとしたΩ×Ωの上三角行列を１行１列からΩ行Ω列までの部分行列とし、Ω+１行以降の行ベクトルmtλ'→が存在する場合にはΩ+１行以降の行ベクトルmtλ'→の全要素を加法単位元0Fとした上三角化行列MTTFV'を生成する。ただし、Ωは１以上であって部分行列MTTFVの行数及び列数以下の整数である。MTTFV'は例えば以下のようになる。
【数２０】
0005466763.tif 000021
ただしΩ+１行以降の各要素が存在しない場合もあり得、また、Ω+１列以降の各要素が存在しない場合もあり得る。
【０１２６】
このような上三角化行列MTTFV'は例えば、ガウスの消去法を利用して生成できる。すなわち、例えばまず、部分行列MTTFVの１行目の行ベクトルmt1→=(mt1,1,...,mt1,COL)をmt1,1で除算したものをMTTFV'の１行目の行ベクトルとする。次に、部分行列MTTFVの２行目の行ベクトルmt2→=(mt2,1,...,mt2,COL)からMTTFV'の１行目の行ベクトルをmt2,1倍した行ベクトルを減じた行ベクトル(0F,mt2,2'',...,mt2,COL'')をmt2,2''で除算したものをMTTFV'の２行目の行ベクトルとする。同様に、既に生成したMTTFV'の各行ベクトルを用いてそれよりも大きな行番号の行ベクトルを加工していくことにより、上三角化行列MTTFV'が生成できる。なお、上三角化行列MTTFV'を生成するための演算は、行ベクトル単位の単項演算と行ベクトル間の２項演算であり、同一の行ベクトル内の異なる要素に対して異なる演算を行うことは許されない。除算するための法が加法単位元0Fとなった場合には加工対象の行ベクトルが選びなおされる。部分行列MTTFVが互いに線形独立でない複数の行ベクトル（すなわち一次従属な複数の行ベクトル）を含む場合、そのような行ベクトルを代表する１つの行ベクトルがΩ×Ωの上三角行列の要素を含む行ベクトルとなり、その他の行ベクトルは加法単位元0Fのみを要素とした行ベクトルとなる（ステップＳ４３２）。
【０１２７】
次に、共通鍵生成部１２６ａはλ'=2に設定する（ステップＳ４３３）。共通鍵生成部１２６ａは、以下の式(98)のベクトルを新たな(mt1,1' ... mt1,COL')として、上三角化行列MTTFV'の１行目の行ベクトル(mt1,1' ... mt1,COL')を更新する。
(mt1,1' ... mt1,COL')-(mt1,λ' - 1F)・(mtλ',1' ... mtλ',COL')  …(98)
(mtλ',1' ... mtλ',COL')は上三角化行列MTTFV'のλ'行目の行ベクトルを表す。
共通鍵生成部１２６ａはλ'=Ωであるか否かを判定し（ステップＳ４３５）、λ'=Ωでなければλ'+１を新たなλ'とし（ステップＳ４３６）、ステップＳ４３４の処理に戻る。一方、λ'=Ωであれば共通鍵生成部１２６ａは、以下が満たされるか否かを判定する（ステップＳ４３７）。
(mt1,1' ... mt1,COL')=(1F,...,1F)        …(99)
共通鍵生成部１２６ａは、式(99)が満たされるならばK'の復号が可能であると判定し（ステップＳ４３８）、これを満たさないならばK'の復号が不可能であると判定する（ステップＳ４３９）。
【０１２８】
ステップＳ４３２の上三角化行列MTTFV'を生成するためのすべての演算内容とステップＳ４３４でのすべての演算内容とは記憶部１２３に格納される。K'の復号が可能であると判定された場合（ステップＳ４３８）、上三角化行列MTTFV'を生成するためのすべての演算とステップＳ４３４でのすべての演算が、部分行列MTTFVの各要素を不定元として得られる行列に施される。それによって得られる行列の１行目の列ベクトルは、部分行列MTTFVの各要素を不定元として得られる行列INDTFVの列ベクトルindλ'→=(indλ',1,...,indλ',COL)（λ'=ROW(1),...,ROW(ω)∈SET）の線形和、すなわち、当該列ベクトルindλ'→と当該列ベクトルに対応する係数const(λ')との積和となる。
const(ROW(1))・indROW(1)→+...+const(ROW(ω))・indROW(ω)→
行列INDTFVのμ行目（μ∈SET）の列ベクトルindμ→に対応する係数const(μ)が式(45)を満たす係数const(μ)となる（式(37)(39)の関係参照）。
【０１２９】
〔変形例等〕
本発明は上述の各実施の形態に限定されるものではない。例えば、ステップＳ４７では、式(93)(94)がともに満たされるか否かが判定されたが、その代わりにC'(0)及びC'(λ)（λ=1,...,Ψ）を結合した情報とC''(0)及びC''(λ)（λ=1,...,Ψ）を結合した情報とが一致するか否かが判定されてもよい。或いはC'(0)及びC'(λ)（λ=1,...,Ψ）に対応する１つの関数値とC''(0)及びC''(λ)（λ=1,...,Ψ）に対応する１つの関数値とが一致するか否かが判定されてもよい。或いは式(93)(94)がともに満たされる場合に第１値が出力され、式(93)(94)の少なくとも一部が満たされない場合に第２値が出力される関数によって判定がなされてもよい。
【０１３０】
ステップＳ４８で復号が拒絶されるときに、復号装置１２０がエラー情報を出力してもよいし、復号結果と無関係な乱数を出力してもよいし、何も出力しなくてもよい。
上述の有限体Fq上で定義された各演算が位数qの有限環Zq上で定義された演算に置き換えられてもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置き換える方法の一例は、素数やそのべき乗値以外のqを許容する方法である。
式(46)(48)-(51)(53)-(56)その他の演算において加法単位元が乗じられる項は巡回群G1やG2の単位元となる。加法単位元が乗じられる項の演算は行われてもよいし、行われなくてもよい。
【０１３１】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１３２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記憶装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。
【符号の説明】
【０１３３】
１  暗号システム
１１０  暗号化装置
１２０  復号装置
【図１】
0005466763.tif 000024
【図２】
0005466763.tif 000025
【図３】
0005466763.tif 000026
【図４】
0005466763.tif 000027
【図５】
0005466763.tif 000028
【図６】
0005466763.tif 000029
【図７】
0005466763.tif 000030
【図８】
0005466763.tif 000031
【図９】
0005466763.tif 000032
【図１０】
0005466763.tif 000033