(57)【要約】  分散装置が、基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値をそれぞれH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))を生成する。分散管理装置PA(α,h(α))が、部分集合SUB(α)ごとに共有される共通情報と、シェア情報SH(ψ,i,β,α,h(α))とに対し、部分集合SUB(α)ごとの共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成する。取得装置が、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(ψ,α)を生成し、秘密復元値SUBSK(ψ,α)を用いて生成情報D*(ψ)を生成する。
2012011565.tif 000002
【特許請求の範囲】
【請求項１】
秘密分散システムであって、
分散装置とΣα=1Lh(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)と取得装置とを有し、
前記分散装置は、
Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、n(ψ)を1以上の整数とし、ζ(ψ)を0以上の整数とし、巡回群G2の生成元をg2とし、θ(ψ,i,β)(i=1,...,n(ψ)+ζ(ψ), β=1,...,n(ψ)+ζ(ψ), n(ψ)≧1, ζ(ψ)≧1)に対する前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルをbi*(ψ)=(θ(ψ,i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)とした場合における、前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値を、それぞれH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))を生成する秘密分散部を含み、
前記分散管理装置PA(α,h(α))は、
前記部分集合SUB(α)ごとに共有される共通情報と、前記シェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))とに対し、前記部分集合SUB(α)ごとに共通の共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成する分散秘密値生成部を含み、
前記取得装置は、
同一の前記部分集合SUB(α)に対応する複数の前記分散秘密値DSH(ψ,α,h(α))を用い、前記秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって、当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)を生成する復元部と、
前記秘密復元値SUBSK(ψ,α)を用いて生成情報D*(ψ)を生成する合成部とを含む、
秘密分散システム。
【請求項２】
請求項１の秘密分散システムであって、
互いに異なる前記部分集合SUB(α)でそれぞれ共有される前記共通情報は、互いに独立である、秘密分散システム。
【請求項３】
請求項１の秘密分散システムであって、
前記共通演算は、線形性を持った演算である、秘密分散システム。
【請求項４】
請求項２の秘密分散システムであって、
前記共通演算は、線形性を持った演算である、秘密分散システム。
【請求項５】
請求項１の秘密分散システムであって、
前記合成部は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成する、秘密分散システム。
【請求項６】
請求項２の秘密分散システムであって、
前記合成部は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成する、秘密分散システム。
【請求項７】
請求項３の秘密分散システムであって、
前記合成部は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成する、秘密分散システム。
【請求項８】
請求項４の秘密分散システムであって、
前記合成部は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成する、秘密分散システム。
【請求項９】
請求項１から８の何れかの秘密分散システムであって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記分散秘密値生成部は、
SHbi*(0,α,h(α))
=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α)))
とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))・g2
をψ=0に対応する前記分散秘密値として生成し、さらに、
SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α)))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
を各λに対応する前記分散秘密値として生成する、
秘密分散システム。
【請求項１０】
請求項１から８の何れかの秘密分散システムであって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記分散秘密値生成部は、
SHbi*(0,α,h(α))
=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α)))
とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))
+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
をψ=0に対応する前記分散秘密値として生成し、さらに、
SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α)))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
を各λに対応する前記分散秘密値として生成する、秘密分散システム。
【請求項１１】
請求項９の秘密分散システムであって、
前記復元部は、
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成し、
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成する、秘密分散システム。
【請求項１２】
請求項１０の秘密分散システムであって、
前記復元部は、
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成し、
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成する、秘密分散システム。
【請求項１３】
Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、n(ψ)を1以上の整数とし、ζ(ψ)を0以上の整数とし、巡回群G2の生成元をg2とし、θ(ψ,i,β)(i=1,...,n(ψ)+ζ(ψ), β=1,...,n(ψ)+ζ(ψ), n(ψ)≧1, ζ(ψ)≧1)に対する前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルをbi*(ψ)=(θ(ψ,i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)とした場合における、前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値を、それぞれH(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))を生成する分散装置。
【請求項１４】
H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに共有される共通情報と、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、n(ψ)を1以上の整数とし、ζ(ψ)を0以上の整数とし、巡回群G2の生成元をg2とし、θ(ψ,i,β)(i=1,...,n(ψ)+ζ(ψ), β=1,...,n(ψ)+ζ(ψ), n(ψ)≧1, ζ(ψ)≧1)に対する前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルをbi*(ψ)=(θ(ψ,i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)とした場合における、前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値をそれぞれ前記部分集合SUB(α)ごとに独立に秘密分散して得られた各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))とに対し、前記部分集合SUB(α)ごとに共通の共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成する分散管理装置。
【請求項１５】
Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合をSUB(α)とした場合における、同一の前記部分集合SUB(α)に対応する複数の前記分散秘密値DSH(ψ,α,h(α))を用い、所定の秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって、当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)を生成する復元部と、
前記秘密復元値SUBSK(ψ,α)を用いて生成情報D*(ψ)を生成する合成部と、
を有する取得装置。
【請求項１６】
分散装置とΣα=1Lh(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)と取得装置とによって行われる秘密分散方法であって、
(A)  前記分散装置が、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、n(ψ)を1以上の整数とし、ζ(ψ)を0以上の整数とし、巡回群G2の生成元をg2とし、θ(ψ,i,β)(i=1,...,n(ψ)+ζ(ψ), β=1,...,n(ψ)+ζ(ψ), n(ψ)≧1, ζ(ψ)≧1)に対する前記巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルをbi*(ψ)=(θ(ψ,i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)とした場合における、前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値を、それぞれH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))を生成するステップと、
(B)  前記分散管理装置PA(α,h(α))が、前記部分集合SUB(α)ごとに共有される共通情報と、前記シェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))とに対し、前記部分集合SUB(α)ごとに共通の共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成するステップと、
(C)  前記取得装置が、同一の前記部分集合SUB(α)に対応する複数の前記分散秘密値DSH(ψ,α,h(α))を用い、前記秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって、当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)を生成するステップと、
(D)  前記取得装置が、前記秘密復元値SUBSK(ψ,α)を用いて生成情報D*(ψ)を生成するステップと、
を有する秘密分散方法。
【請求項１７】
請求項１６の秘密分散方法であって、
互いに異なる前記部分集合SUB(α)でそれぞれ共有される前記共通情報は、互いに独立である、秘密分散方法。
【請求項１８】
請求項１６の秘密分散方法であって、
前記共通演算は、線形性を持った演算である、秘密分散方法。
【請求項１９】
請求項１７の秘密分散方法であって、
前記共通演算は、線形性を持った演算である、秘密分散方法。
【請求項２０】
請求項１６の秘密分散方法であって、
前記ステップ(D)は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成するステップを含む、秘密分散方法。
【請求項２１】
請求項１７の秘密分散方法であって、
前記ステップ(D)は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成するステップを含む、秘密分散方法。
【請求項２２】
請求項１８の秘密分散方法であって、
前記ステップ(D)は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成するステップを含む、秘密分散方法。
【請求項２３】
請求項１９の秘密分散方法であって、
前記ステップ(D)は、前記秘密復元値SUBSK(ψ,α)を線形結合して前記生成情報D*(ψ)を生成するステップを含む、秘密分散方法。
【請求項２４】
請求項１６から２３の何れかの秘密分散方法であって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記ステップ(B)は、
(B-1)  SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α)))
とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))・g2
をψ=0に対応する前記分散秘密値として生成するステップと、
(B-2)  SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α)))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
を各λに対応する前記分散秘密値として生成するステップと、を含む、
秘密分散方法。
【請求項２５】
請求項１６から２３の何れかの秘密分散方法であって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記ステップ(B)は、
(B-1)  SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α)))
とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
をψ=0に対応する前記分散秘密値として生成するステップと、
(B-2)  SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α)))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
を各λに対応する前記分散秘密値として生成するステップと、を含む、
秘密分散方法。
【請求項２６】
請求項２４の秘密分散方法であって、
前記ステップ(C)は、
(C-1)  SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成するステップと、
(C-2)  SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成するステップと、を含む、
秘密分散方法。
【請求項２７】
請求項２５の秘密分散方法であって、
前記ステップ(C)は、
(C-1)  SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成するステップと、
(C-2)  SUBSK(λ,α)
=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成するステップと、を含む、
秘密分散方法。
【請求項２８】
請求項１３の分散装置としてコンピュータを機能させるためのプログラム。
【請求項２９】
請求項１４の分散管理装置としてコンピュータを機能させるためのプログラム。
【請求項３０】
請求項１５の取得装置としてコンピュータを機能させるためのプログラム。
【請求項３１】
請求項１３の分散装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項３２】
請求項１４の分散管理装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【請求項３３】
請求項１５の取得装置としてコンピュータを機能させるためのプログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散技術に関する。
【背景技術】
【０００２】
秘密情報を保管する場合、秘密情報の紛失や破壊のリスクと盗難のリスクとがある。紛失や破壊のリスクは、複数の秘密情報を保管しておくことで低減できる。しかし、この場合には盗難のリスクが増加する。これらのリスクを共に解決する方法の一つとして、秘密分散法（SSS: Secret Sharing Scheme）がある（例えば、非特許文献１，２参照）。【０００３】
秘密分散法とは、秘密情報MSKから複数のシェア情報SH(1),...,SH(N)を生成し、これらを複数の分散管理装置PA(1),...,PA(N)に分散して管理させ、これらのシェア情報SH(1),...,SH(N)のうち所定数以上のシェア情報を得ることができた場合にのみ、秘密情報MSKが復元できる方式である。以下に、秘密分散法の代表的な方式を示す。【０００４】
(N,N)しきい値秘密分散方式：
(N,N)しきい値秘密分散方式（「N-out-of-N分散方式」や「N-out-of-Nしきい値分散方式」と呼ぶ場合もある））では、すべてのシェア情報SH(1),...,SH(N)が与えられれば秘密情報MSKを復元できるが、任意のN-1個のシェア情報SH(φ1),...,SH(φN-1)が与えられても秘密情報MSKの情報はまったく得られない。以下に、(N,N)しきい値秘密分散方式の一例を示す。
・SH1,...,SHN-1をランダムに選択する。
・SHN=MSK-(SH1+...+SHN-1)の計算を行う。
・各シェア情報SH1,...,SHNを複数の分散管理装置PA(1),...,PA(N)に分散して管理させる。
・すべてのシェア情報SH1,...,SHNが与えられれば、MSK=SH1+...+SHNの復元処理によって秘密情報MSKを復元できる。【０００５】
なお、シェア情報SH1,...,SHNから秘密情報MSKするための演算MSK=SH1+...+SHNは線形である。そのため、各シェア情報SH(1),...,SH(N)と値σとを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(1),...,SH'(N)として復元処理を行った場合、秘密情報MSKと値σとを被演算子として当該線形演算CALCを行った結果が得られる。例えば、SH'(1)=σ・SH(1),..,SH'(N)=σ・SH(N)を各シェア情報SH'(1),...,SH'(N)として復元処理が実行された場合、以下の値が得られる。
σ・SH(1)+...+σ・SH(N)
=σ・(SH(1)+ ...+SH(N))
=σ・MSK                              …(1)【０００６】
一方、各シェア情報SH(1),...,SH(N)と、互いに独立な値σ(1),...,σ(N)とを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(1),...,SH'(N)として復元処理が実行された場合には、通常、秘密情報MSKを被演算子とした演算結果を得ることはできない。例えば、SH'(1)=σ(1)・SH(1),..,SH'(N)=σ(N)・SH(N)を各シェア情報SH'(1),...,SH'(N)として復元処理が実行された場合、以下の値が得られる。
σ(1)・SH(1)+...+σ(N)・SH(N)           …(2)【０００７】
(Kt,N)しきい値秘密分散方式：
(Kt,N)しきい値秘密分散方式（「Kt-out-of-N分散方式」や「Kt-out-of-Nしきい値分散方式」と呼ぶ場合もある）では、任意の相違なるKt個のシェア情報SH(φ1),...,SH(φKt)が与えられれば秘密情報MSKを復元できるが、任意のKt-1個のシェア情報SH(φ1),...,SH(φKt-1)が与えられても秘密情報MSKの情報はまったく得られない。添え字のKtはKtを表す。以下に(Kt,N)しきい値秘密分散方式の一例を示す。
・f(0)=MSKを満たすKt-1次の多項式f(x)=ξ0+ξ1・x+ξ2・x2+...+ξKt-1・xKt-1をランダムに選ぶ。すなわち、ξ0=MSKとし、ξ1,..., ξKt-1をランダムに選ぶ。シェア情報をSHρ=(ρ, f(ρ))（ρ=1,...,N）とする。
・任意の相違なるKt個のシェア情報SH(φ1),...,SH(φKt)（(φ1,...,φKt)⊂(1,...,N)）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報MSKを復元できる。
MSK=f(0)=λ1・f(φ1)+...+λKt・f(φKt)            …(3)
【数１】
2012011565.tif 000003
は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(4)の分母は以下のようになる。
(φρ-φ1)・...・(φρ-φρ-1)・(φρ-φρ+1)・...・(φρ-φKt)
式(4)の分子は以下のようになる。
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φKt)
これらの関係は体上でも成立する。【０００８】
式(3)の演算は線形である。そのため、各シェア情報SH(φ1),...,SH(φKt)と値σとを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(φ1),...,SH'(φKt)として復元された値は、秘密情報MSKと値σとを被演算子として線形演算CALCを行った結果と等しくなる。一方、各シェア情報SH(φ1),...,SH(φKt)と、互いに独立な値σ(φ1),...,σ(φKt)とを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(φ1),...,SH'(φKt)として復元処理が実行された場合には、通常、秘密情報MSKを被演算子とした演算結果を得ることはできない。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】黒沢馨、尾形わかは、“現代暗号の基礎数理 (電子情報通信レクチャーシリーズ)”、コロナ社 、２００４年３月、p.116-119
【非特許文献２】A. Shamir, "How to Share a Secret", Communications of the ACM, November 1979, Volume 22, Number 11, pp.612-613.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
以下の条件を満たす方式を想定する。
(条件１)分散装置が秘密情報MSKを秘密分散して複数のシェア情報SH(1),...,SH(N)を生成し、これらを複数の分散管理装置PA(1),...,PA(N)に分散して管理させる。
(条件２)各分散管理装置PA(1),...,PA(N)がそれぞれ何らかの演算を実行する。
(条件３)取得装置は、秘密情報MSKを得ることはできないが、所定数以上の分散管理装置で生成された演算結果が与えられた場合に、秘密情報MSKと任意な値σとを被演算子に含む演算の結果に対応する生成情報を得ることができる。【００１１】
しかし、このような方式を実現することは容易ではない。すなわち、各分散管理装置PA(1),...,PA(N)がそれぞれ互いに独立な値σ(1),...,σ(N)を用いて演算を実行したのでは、取得装置は各分散管理装置の演算結果をシェア情報とした復元処理を正しく実行することができず、所望の生成情報が得られない。一方、値σは生成情報を推測するための情報となり得るため、すべての分散管理装置PA(1),...,PA(N)が値σそのものを共有することは、安全性の観点から好ましくない。【００１２】
本発明はこのような点に鑑みてなされたものであり、上記条件１〜３を満たす方式を安全に実現することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、分散装置とΣα=1Lh(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)と取得装置とによって秘密分散処理が実行される。分散装置が、Ψを1以上の整数とし、ψを0以上Ψ以下の整数ψ=0,...,Ψとし、n(ψ)を1以上の整数とし、ζ(ψ)を0以上の整数とし、巡回群G2の生成元をg2とし、θ(ψ,i,β)(i=1,...,n(ψ)+ζ(ψ), β=1,...,n(ψ)+ζ(ψ), n(ψ)≧1, ζ(ψ)≧1)に対する巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルをbi*(ψ)=(θ(ψ,i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)とした場合における、基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値を、それぞれH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))を生成する。分散管理装置PA(α,h(α))が、部分集合SUB(α)ごとに共有される共通情報と、シェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))とに対し、部分集合SUB(α)ごとに共通の共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成する。取得装置が、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(ψ,α,h(α))を用い、前記秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)を生成し、秘密復元値SUBSK(ψ,α)を用いて生成情報D*(ψ)を生成する。【００１４】
本発明では、部分集合SUB(α)ごとに独立に秘密情報である基底ベクトルbi*(ψ)を秘密分散し、部分集合SUB(α)ごとに共有される共通情報を用い、分散秘密値DSH(ψ,α,h(α))を生成する。この場合、部分集合SUB(α)単位では、分散秘密値DSH(ψ,α,h(α))をシェア情報とした復元処理を正しく実行できる。共通情報は部分集合SUB(α)ごとに共有され、すべての分散管理装置PA(α,h(α))に共有されないため、安全性が高い。
【発明の効果】
【００１５】
以上のように、本発明では、上記条件１〜３を満たす方式を安全に実現することができる。
【図面の簡単な説明】
【００１６】
【図１】図１は、第１実施形態の秘密分散システムの全体構成を説明するためのブロック図である。
【図２】図２は、図１の分散装置の構成を説明するためのブロック図である。
【図３】図３Ａは、第１実施形態の分散管理装置の構成を説明するためのブロック図である。図３Ｂは、第１実施形態の共有値生成装置の構成を説明するためのブロック図である。
【図４】図４は、第１実施形態の取得装置の構成を説明するためのブロック図である。
【図５】図５Ａは、図２の秘密分散部の詳細を説明するためのブロック図である。図５Ｂは、図３Ａの分散秘密値生成部の詳細を説明するためのブロック図である。
【図６】図６は、図４の復元部の詳細を説明するためのブロック図である。
【図７】図７は、第１実施形態の秘密分散処理の全体を説明するための図である。
【図８】図８Ａは、第１実施形態の分散装置の処理を例示するための図である。図８Ｂは、ステップＳ１１２の処理の詳細を例示するための図である。
【図９】図９Ａは、第１実施形態の分散管理装置の処理を例示するための図である。図９Ｂは、ステップＳ１２４の処理の詳細を例示するための図である。
【図１０】図１０Ａは、第１実施形態の取得装置の処理を例示するための図である。図１０Ｂは、ステップＳ１３４の処理を例示するための図である。
【図１１】図１１Ａは、第１実施形態における変形例１の秘密分散部の構成を説明するための図である。図１１Ｂは、第１実施形態における変形例１の分散秘密値生成部の構成を説明するための図である。
【図１２】図１２Ａは、第１実施形態における変形例２の分散秘密値生成部の構成を説明するための図である。図１２Ｂは、第１実施形態における変形例２の復元部の構成を説明するための図である。
【図１３】図１３Ａは、第１実施形態における変形例３の秘密分散部の構成を説明するための図である。図１３Ｂは、第１実施形態における変形例３の分散秘密値生成部の構成を説明するための図である。図１３Ｃは、第１実施形態における変形例３の復元部の構成を説明するための図である。
【図１４】図１４Ａは、第１実施形態における変形例４の秘密分散部の構成を説明するための図である。図１４Ｂは、第１実施形態における変形例４の分散秘密値生成部の構成を説明するための図である。図１４Ｃは、第１実施形態における変形例４の復元部の構成を説明するための図である。
【図１５】図１５は、標準形論理式を表現する木構造データを例示する図である。
【図１６】図１６は、標準形論理式を表現する木構造データを例示する図である。
【図１７】図１７は、第２実施形態の秘密分散システムの全体構成を説明するためのブロック図である。
【図１８】図１８は、第２実施形態の分散装置の構成を説明するためのブロック図である。
【図１９】図１９Ａは、第２実施形態の共有値生成装置の構成を説明するためのブロック図である。図１９Ｂは、第２実施形態の共有値生成装置の構成を説明するためのブロック図である。
【図２０】図２０は、第２実施形態の分散管理装置の構成を説明するためのブロック図である。
【図２１】図２１は、第２実施形態の取得装置の構成を説明するためのブロック図である。
【図２２】図２２は、第２実施形態の秘密分散処理の全体を説明するための図である。
【図２３】図２３は、第２実施形態の秘密分散処理の全体を説明するための図である。
【図２４】図２４は、第２実施形態の分散装置の処理を例示するための図である。
【図２５】図２５は、第２実施形態の分散管理装置の処理を例示するための図である。
【図２６】図２６は、第２実施形態の取得装置の処理を例示するための図である。
【図２７】図２７は、第２実施形態における変形例１の分散管理装置の処理を例示するための図である。
【図２８】図２８は、第２実施形態における変形例１の分散管理装置の処理を例示するための図である。
【発明を実施するための形態】
【００１７】
以下、図面を参照して本発明の実施形態を説明する。
〔第１実施形態〕
まず、本発明の第１実施形態を説明する。
【００１８】
〔定義〕
本形態で使用する用語や記号を定義する。
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の乗法単位元を表す。
【００２０】
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＝Ｏを満たす点を意味する。
【００２１】
G: Gは巡回群を表す。巡回群Gの具体例は、楕円曲線Eのp等分点からなる有限集合E[p]、その部分群、剰余群などである。本形態では、巡回群G上で定義された演算を加法的に表現する。すなわち、χ∈Fq及びΩ∈Gに対するχ・Ω∈Gは、Ω∈G1に対して巡回群Gで定義された演算をχ回施すことを意味し、Ω1, Ω2∈Gに対するΩ1+Ω2∈Gは、Ω1∈GとΩ2∈Gとを被演算子として巡回群Gで定義された演算を行うことを意味する。
g：gは巡回群Gの生成元を表す。
【００２２】
＜全体構成＞
図１は、第１実施形態の秘密分散システムの全体構成を説明するためのブロック図である。
図１に例示するように、本形態の秘密分散システム１は、分散装置１１０と、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)〕１２０−α−h（α）と、取得装置１３０と、共有値生成装置１４０−１〜Ｌとを有し、それらはネットワーク１５０を通じて通信可能である。説明を簡略化するため、本形態では、分散装置１１０及び取得装置１３０が１つずつ存在する構成を例示するが、分散装置１１０及び／又は取得装置１３０が２以上存在してもよい。同様な理由により、本形態では、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))〕１２０−α−h（α）からなる集合が１つのみ存在する構成を例示するが、このような集合が複数存在していてもよい。
図１に例示するように、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))〕１２０−α−h（α）からなる集合は、H(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる複数の部分集合SUB(α)ごとに区分される。各部分集合SUB(α)には、それぞれ、各部分集合SUB(α)ごとに共有される共有値σ(α)を生成する共有値生成装置１４０−αがそれぞれ対応する。
【００２３】
＜分散装置１１０＞
図２は、図１の分散装置１１０の構成を説明するためのブロック図である。図５Ａは、図２の秘密分散部１１４−αの詳細を説明するためのブロック図である。
図２に例示するように、本形態の分散装置１１０は、一時記憶部１１１と、記憶部１１２と、制御部１１３と、秘密分散部１１４−α（α=1,...,L）と、送信部１１５とを有する。図５Ａに例示するように、本形態の秘密分散部１１４−αは、関数選択部１１４ａ−αと、インデックス生成部１１４ｂ−αと、分散処理部１１４ｃ−αとを有する。
【００２４】
本形態の分散装置１１０は、例えば、CPU（Central Processing Unit）、RAM（Random Access Memory）、ROM（Read-Only Memory）等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部１１１及び記憶部１１２は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部１１３及び秘密分散部１１４−α（α=1,...,L）は、例えば、CPUが所定のプログラムを実行することで構成される処理部である。制御部１１３及び秘密分散部１１４−α（α=1,...,L）の少なくとも一部が特別な集積回路であってもよい。送信部１１５は、例えば、モデム、LAN（Local Area Network）カード等の通信装置である。
【００２５】
分散装置１１０は、制御部１１３の制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１１１又は記憶部１１２に格納される。一時記憶部１１１又は記憶部１１２に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【００２６】
＜分散管理装置〔PA(α,h(α))〕１２０−α−h（α）＞
図３Ａは、第１実施形態の分散管理装置〔PA(α,h(α))〕１２０−α−h（α）の構成を説明するためのブロック図である。図５Ｂは、図３Ａの分散秘密値生成部１２４−α−h（α）の詳細を説明するためのブロック図である。
図３Ａに例示するように、本形態の分散管理装置〔PA(α,h(α))〕１２０−α−h（α）は、一時記憶部１２１−α−h（α）と、記憶部１２２−α−h（α）と、制御部１２３−α−h（α）と、分散秘密値生成部１２４−α−h（α）と、送信部１２５−α−h（α）と、受信部１２６−α−h（α）とを有する。図５Ｂに例示するように、分散秘密値生成部１２４−α−h（α）は、線形演算部１２４ａ−α−h（α）と、分散秘密値合成部１２４ｂ−α−h（α）とを有する。
【００２７】
分散管理装置〔PA(α,h(α))〕１２０−α−h（α）は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部１２１−α−h（α）及び記憶部１２２−α−h（α）は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部１２３−α−h（α）及び分散秘密値生成部１２４−α−h（α）は、例えば、CPUが所定のプログラムを実行することで構成される処理部である。なお、制御部１２３−α−h（α）及び分散秘密値生成部１２４−α−h（α）の少なくとも一部が特別な集積回路であってもよい。送信部１２５−α−h（α）や受信部１２６−α−h（α）は、例えば、モデム、LANカード等の通信装置である。
【００２８】
分散管理装置〔PA(α,h(α))〕１２０−α−h（α）は、制御部１２３−α−h（α）の制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１２１−α−h（α）又は記憶部１２２−α−h（α）に格納される。一時記憶部１２１−α−h（α）又は記憶部１２２−α−h（α）に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【００２９】
＜共有値生成装置１４０−α＞
図３Ｂは、第１実施形態の共有値生成装置１４０−αの構成を説明するためのブロック図である。
図３Ｂに例示するように、本形態の共有値生成装置１４０−αは、乱数生成部１４１−α及び送信部１４２−αを有する。本形態の共有値生成装置１４０−αは、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置であるが、乱数生成部１４１−αが特別な集積回路であってもよい。
【００３０】
＜取得装置１３０＞
図４は、第１実施形態の取得装置１３０の構成を説明するためのブロック図である。図６は、図４の復元部１３４−αの詳細を説明するためのブロック図である。
図４に例示するように、本形態の取得装置１３０は、一時記憶部１３１と、記憶部１３２と、制御部１３３と、復元部１３４−α（α=1,...,L）と、合成部１３７と、送信部１３５と、受信部１３６とを有する。図６に例示するように、復元部１３４−αは、係数算出部１３４ａ−αと、多項式演算部１３４ｂ−αとを有する。
【００３１】
本形態の取得装置１３０は、例えば、CPU、RAM、ROM等を備える公知又は専用のコンピュータと特別なプログラムとを含む特別な装置である。具体的には、一時記憶部１３１及び記憶部１３２は、例えば、RAM、レジスタ、キャッシュメモリ、集積回路内の素子若しくはハードディスク等の補助記憶装置、又は、これらの少なくとも一部の結合からなる記憶領域である。制御部１３３、復元部１３４−α（α=1,...,L）及び合成部１３７は、例えば、CPUが所定のプログラムを実行することで構成される処理部である。制御部１３３、復元部１３４−α（α=1,...,L）及び合成部１３７の少なくとも一部が特別な集積回路であってもよい。送信部１３５や受信部１３６は、例えば、モデム、LANカード等の通信装置である。
取得装置１３０は、制御部１３３の制御のもと各処理を実行する。以下では説明を簡略化するが、各処理部から出力されたデータは、逐一、一時記憶部１３１又は記憶部１３２に格納される。一時記憶部１３１又は記憶部１３２に格納されたデータは、必要に応じて読み出され、各処理部に入力されてその処理に利用される。
【００３２】
＜秘密分散処理＞
本形態の秘密分散処理を説明する。
[事前処理]
本形態の秘密分散処理の事前処理として、秘密情報θ・g∈Gを特定するための情報θ∈Fqが分散装置１１０の記憶部１１２に格納される。
【００３３】
[秘密分散処理の全体]
図７は、第１実施形態の秘密分散処理の全体を説明するための図である。以下、図７を用いて、本形態の秘密分散処理の全体を説明する。
本形態では、まず、分散装置１１０（図１）が、部分集合SUB(α)ごとに独立に、秘密情報θ・g∈Gを秘密分散してシェア情報SH(α,h(α))(h(α)=1,...,H(α))を生成し、当該シェア情報SH(α,h(α))を出力する（ステップＳ１１）。各シェア情報SH(α,h(α))は、それぞれ、ネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕１２０−α−h（α）に分散して送信される。
【００３４】
各シェア情報SH(α,h(α))が送信された各分散管理装置〔PA(α,h(α))〕１２０−α−h（α）は、それぞれ、そのシェア情報SH(α,h(α))と、部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報とを用い、所定の共通演算を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力する（ステップＳ１２）。
【００３５】
本形態の場合、互いに異なる部分集合SUB(α)でそれぞれ共有される共有値σ(α)は互いに独立である。同一の部分集合SUB(α)に属する分散管理装置〔PA(α,h(α))〕１２０−α−h（α）がそれぞれ用いる「共通情報」は互いに同一である。特に、本形態で例示する「共通情報」は、共有値σ(α)と、取得装置１３０から提供されたすべての分散管理装置PA(α,h(α))１２０−α−h（α）に共通の提供情報vとを含む。同一の部分集合SUB(α)に属する分散管理装置〔PA(α,h(α))〕１２０−α−h（α）がそれぞれ行う「共通演算」は互いに同一である。本形態では、すべての「共通演算」が同一であるものとする。本形態の「共通演算」は、線形性を持った演算である。
【００３６】
各分散管理装置〔PA(α,h(α))〕１２０−α−h（α）から出力された各分散秘密値DSH(α,h(α))は、それぞれ、ネットワーク１５０経由で取得装置１３０に送信される。取得装置１３０は、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成する（ステップＳ１３）。
【００３７】
次に、取得装置１３０は、各部分集合SUB(α)についてそれぞれ生成された秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力する（ステップＳ１４）。なお、本形態では、取得装置１３０が秘密復元値SUBSK(α)を線形結合して生成情報SKする。
【００３８】
[分散装置の処理（ステップＳ１１）]
図８Ａは、第１実施形態の分散装置の処理を例示するための図であり、図８Ｂは、ステップＳ１１２の処理の詳細を例示するための図である。以下、これらの図を用いて、分散装置１１０の処理の詳細を説明する。
まず、分散装置１１０（図２）の制御部１１３が、α=１に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ１１１）。次に、記憶部１１２から秘密情報θ・g∈Gを特定するための情報θ∈Fqが読み出され、秘密分散部１１４−αに入力される。秘密分散部１１４−αは、情報θ∈Fqを用いて秘密情報θ・g又は情報θを、所定の秘密分散方式に従って秘密分散し、部分集合SUB(α)に対するH(α)個のシェア情報SH(α,1),...,SH(α,H(α))を生成して出力する（ステップＳ１１２）。
【００３９】
《ステップＳ１１２の詳細》
本形態の秘密分散部１１４−αは、各部分集合SUB(α)に対し、(R(α)，H(α))しきい値秘密分散方式（但し、R(α)は、2≦R(α)＜H(α)を満たす定数）を用い、秘密情報を秘密分散して得られるシェア情報SH(α,h(α))(h(α)=1,...,H(α))を生成する。
図８Ｂに例示するように、まず、秘密分散部１１４−α（図５Ａ）の関数選択部１１４ａ−αが、予め定められた有限体Fqの元ω∈Fqに対してf(α,ω)=θを満たすR(α)-1次の多項式をf(α,x)∈Fqをランダムに選択して出力する（ステップＳ１１２ａ）。なお、xは有限体Fqの元からなる変数であり、元ω∈Fqの一例は0Fである。
次に、インデックス生成部１１４ｂ−αが、各h(α)=1,...,H(α)に対応するインデックスφ(h(α))∈Fqを生成して出力する(ステップＳ１１２b)。なお、インデックスφ(h(α))=h(α)∈Fqとする場合や、すでにインデックスφ(h(α))∈Fqが得られている場合には、ステップＳ１１２の処理は省略されてもよい。
次に、分散処理部１１４ｃ−αが、多項式f(α,x)∈Fqとインデックスφ(h(α))∈Fqとを用い、以下のシェア情報SH(α,h(α))(h(α)=1,...,H(α))を生成する。
SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g∈G)       …(5)
分散処理部１１４ｃ−αはシェア情報SH(α,h(α))を出力する（ステップＳ１１２ｃ／《ステップＳ１１２の詳細》の説明終わり）。
【００４０】
次に、制御部１１３は、一時記憶部１１１に格納されたαがLであるか否かを判定する（ステップＳ１１３）。ここで、α=Lでないと判定された場合、制御部１１３は、α+1を新たなαとし、その設定内容を一時記憶部１１１に格納し（ステップＳ１１４）、新たなαによってステップＳ１１２の処理を実行させる。一方、ステップＳ１１３でα=Lであると判定された場合、各秘密分散部１１４−αから出力された各シェア情報SH(α,h(α))(α=1,...,L)が送信部１１５に送られる。送信部１１５は、各シェア情報SH(α,h(α))(α=1,...,L)を、それぞれ、ネットワーク１５０経由で分散管理装置〔PA(α,h(α))〕１２０−α−h(α)(α=1,...,L)に送信する（ステップＳ１１５）。すなわち、シェア情報SH(1,1)は分散管理装置〔PA(1,1)〕１２０−1−1に、シェア情報SH(1,2)は分散管理装置〔PA(1,2)〕１２０−1−２に、・・・シェア情報SH(L,H(L))は分散管理装置〔PA(L,H(L))〕１２０−Ｌ−Ｈ（Ｌ）に、それぞれ送信される。
【００４１】
［共有値生成装置の処理］
各共有値生成装置１４０−α（図３Ｂ）は、自らに対応する部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕１２０−α−h(α)で共有する共有値σ(α)を生成する。本形態では、乱数生成部１４１−αが生成した乱数を共有値σ(α)とし、送信部１４２−αが共有値σ(α)を、部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕１２０−α−h(α)に送信する。
【００４２】
［分散管理装置の処理（ステップＳ１２）］
図９Ａは、第１実施形態の分散管理装置〔PA(α,h(α))〕１２０−α−h(α)の処理を例示するための図であり、図９Ｂは、ステップＳ１２４の処理の詳細を例示するための図である。以下、これらの図を用いて、本形態の分散管理装置〔PA(α,h(α))〕１２０−α−h(α)の処理を説明する。
【００４３】
まず、分散管理装置〔PA(α,h(α))〕１２０−α−h(α)（図３Ａ）の受信部１２６−α−h(α)が、送信されたシェア情報SH(α,h(α))を受信し、それを記憶部１２２−α−h(α)に格納する（ステップＳ１２１）。なお、過去にステップＳ１２１の処理が実行され、既にシェア情報SH(α,h(α))が分散管理装置〔PA(α,h(α))〕１２０−α−h(α)の記憶部１２２−α−h(α)に格納されているのであれば、ステップＳ１２１の処理を省略してもよい。
【００４４】
分散管理装置〔PA(α,h(α))〕１２０−α−h(α)の受信部１２６−α−h(α)は、共有値生成装置１４０−αから送信された共有値σ(α)を受信し、それを記憶部１２２−α−h(α)に格納する（ステップＳ１２２）。
【００４５】
本形態では、取得装置１３０（図４）の記憶部１３２から読み出された提供情報vが送信部１３５からネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕１２０−α−h(α)に送信される。この提供情報vは、すべての分散管理装置PA(α,h(α))１２０−α−h（α）に共通である。提供情報vは、分散管理装置〔PA(α,h(α))〕１２０−α−h(α)（図３Ａ）の受信部１２６−α−h(α)で受信され、記憶部１２２−α−h(α)に格納される（ステップＳ１２３）。
【００４６】
次に、分散秘密値生成部１２４−α−h(α)が、記憶部１２２−α−h(α)からシェア情報SH(α,h(α))と共有値σ(α)と提供情報vとを読み込む。分散秘密値生成部１２４−α−h(α)は、共有値σ(α)と提供情報vとを含む共通情報と、シェア情報SH(α,h(α))とを用い、共通演算FNC1を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力する（ステップＳ１２４）。
【００４７】
《ステップＳ１２４の詳細》
同一の部分集合SUB(α)に属する分散管理装置PA(α,h(α))１２０−α−h(α)の分散秘密値生成部１２４−α−h(α)がそれぞれ用いる共通情報は互いに同一であり、同一の部分集合SUB(α)に属する分散管理装置PA(α,h(α))１２０−α−h(α)の分散秘密値生成部１２４−α−h(α)がそれぞれ行う共通演算は互いに同一である。本形態のシェア情報は式(5)に示すものである。
【００４８】
図９Ｂに例示するように、まず、本形態の分散秘密値生成部１２４−α−h(α)の線形演算部１２４ａ−α−h（α）に、共有値σ(α)と提供情報vとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g)のf(α,φ(h(α)))・gとが入力される。線形演算部１２４ａ−α−h（α）は以下の演算を行い、その演算結果dsh(α,φ(h(α)))を出力する（ステップＳ１２４ａ）。
dsh(α,φ(h(α)))=σ(α)・v・f(α,φ(h(α)))・g∈G       …(6)
【００４９】
出力された演算結果dsh(α,φ(h(α)))は、分散秘密値合成部１２４ｂ−α−h（α）に入力される。分散秘密値合成部１２４ｂ−α−h（α）には、さらにシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g)のインデックスφ(h(α))が入力され、分散秘密値合成部１２４ｂ−α−h（α）は、以下の演算によって分散秘密値DSH(α,h(α))を生成する。
DSH(α,h(α))=(φ(h(α)),dsh(α,φ(h(α))))       …(7)
分散秘密値合成部１２４ｂ−α−h（α）は分散秘密値DSH(α,h(α))を出力する（ステップＳ１２４ｂ／《ステップＳ１２４の詳細》の説明終わり）。
【００５０】
生成された分散秘密値DSH(α,h(α))は送信部１２５−α−h（α）に送られる。送信部１２５−α−h（α）は、分散秘密値DSH(α,h(α))をネットワーク１５０経由で取得装置１３０に送信する（ステップＳ１２５）。
【００５１】
［取得装置の処理（ステップＳ１３，Ｓ１４）］
図１０Ａは、第１実施形態の取得装置の処理を例示するための図であり、図１０Ｂは、ステップＳ１３４の処理を例示するための図である。
各分散管理装置PA(α,h(α))１２０−α−h(α)から送信された分散秘密値DSH(α,h(α))は、取得装置１３０（図４）の受信部１３６で受信され、記憶部１３２に格納される（ステップＳ１３１）。
【００５２】
次に、制御部１３３が、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かを判定する（ステップＳ１３２）。本形態の場合、各α=1,...,Lについて、それぞれ、相違なるR(α)（2≦R(α)＜H(α)）個以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かを判定する。ここで、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されていないと判定された場合には、ステップＳ１３１の処理に戻される。
【００５３】
一方、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたと判定された場合、制御部１３３が、α=１に設定し、その設定内容を一時記憶部１３１に格納する（ステップＳ１３３）。次に、記憶部１３２から部分集合SUB(α)に対応する必要数分の分散秘密値DSH(α,h(α))が読み出され、復元部１３４−αに入力される。復元部１３４−αは、入力された分散秘密値DSH(α,h(α))を用い、前述のステップＳ１１２で用いられた秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの秘密復元値SUBSK(α)を出力する（ステップＳ１３４）。
【００５４】
《ステップＳ１３４の詳細》
本形態の分散秘密値DSH(α,h(α))は式(7)に示すものである。復元部１３４−α（図６）には、αごとにR(α)個ずつの相違なる分散秘密値DSH(α,h(α))が入力される。以下では、復元部１３４−αに入力される各αに対応する分散秘密値DSH(α,h(α))を以下のように表現する。
DSH(α,φ1(α))=(φ1(α), dsh1(α))
・・・                              …(8)
DSH(α,φR(α)(α))=(φR(α)(α), dshＲ(α)(α))
ただし、以下が満たされる。
(φ1(α),...,φR(α)(α))⊂(φ(1),...,φ(H(α)))       …(9)
(dsh1(α),...,dshＲ(α)(α))⊂(dsh(α,φ(1)),...,dsh(α,φ(H(α))))
…(10)
【００５５】
図１０Ｂに例示するように、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))の各インデックスφ1(α),...,φR(α)(α)が係数算出部１３４ａ−αに入力され、係数算出部１３４ａ−αは、各ρ=1,...,R(α)について、それぞれ以下の演算を行い、各係数λρ(x)(ρ=1,...,R(α))を生成して出力する（ステップＳ１３４ａ）。
【数２】
2012011565.tif 000004
【００５６】
生成された各係数λρ(x)と、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))のdsh1(α),...,dshＲ(α)(α)とが、多項式演算部１３４ｂ−αに入力される。多項式演算部１３４ｂ−αは、以下の演算によって部分集合SUB(α)の秘密復元値SUBSK(α)を生成する。
SUBSK(α)=λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)∈G    …(12)
多項式演算部１３４ｂ−αは、秘密復元値SUBSK(α)を出力する（ステップＳ１３４ｂ／《ステップＳ１３４の詳細》の説明終わり）。
【００５７】
制御部１３３は、一時記憶部１３１に格納されたαがLであるか否かを判定する（ステップＳ１３５）。ここで、α=Lでないと判定された場合、制御部１３３は、α+1を新たなαとし、その設定内容を一時記憶部１３１に格納し（ステップＳ１３６）、新たなαによってステップＳ１３４の処理を実行させる。
【００５８】
一方、ステップＳ１３５でα=Lであると判定された場合、各復元部１３４−αから出力された各秘密復元値SUBSK(α)が合成部１３７に送られる。合成部１３７は、各部分集合SUB(α)についてそれぞれ生成された各秘密復元値SUBSK(α)を用いて、以下の生成情報SKを生成し、当該生成情報SKを出力する（ステップＳ１４１）。
SK=FNC2(SUBSK(1),...,SUBSK(L))           …(13)
【００５９】
《ステップＳ１４１の詳細》
以下に式(13)の具体例を示す。
具体例１：SK=SUBSK(1)+...+SUBSK(L)∈G        …(14)
具体例２：SK=CE1・SUBSK(1)+...+CEL・SUBSK(L)∈G         …(15)
ただし、CEα∈Fqは係数であり、その一例はLの乗法逆元(L)-1∈Fqである。また、係数CE1,...,CELの何れか一部を0Fとしてもよい。この場合には、SUBSK(1)+...+SUBSK(L)の一部のみを用いて生成情報SKが生成される。この際、合成部１３７が、係数CE1,...,CELのうち0Fとする係数をランダムに選択してもよい。これにより、安全性が向上する。合成部１３７が、係数CE1,...,CELを自由に設定できる構成でもよい。これにより、取得装置１３０は、信頼性が低い部分集合SUB(α')に対応する秘密復元値SUBSK(α')を使用せずに生成情報SKを生成すること等が可能となる（《ステップＳ１４１の詳細》の説明終わり）。
【００６０】
＜第１実施形態の特徴＞
本形態では、分散装置１１０が部分集合SUB(α)ごとに独立に秘密情報θ・g∈Gを秘密分散してシェア情報SH(α,h(α))を生成し、各分散管理装置PA(α,h(α))１２０−α−h(α)が、共有値σ(α)と提供情報vを含む共通情報とシェア情報SH(α,h(α))とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成し、取得装置１３０が、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、秘密復元値SUBSK(α)を用いて生成情報SKを生成することとした。
【００６１】
このように部分集合SUB(α)ごとに共有される共有値σ(α)を用い、部分集合SUB(α)ごとに秘密分散、共通演算、復元処理を行うため、これらの処理の実行は可能である。さらに、すべての分散管理装置PA(α,h(α))１２０−α−h(α)が値σを共有するのではなく、部分集合SUB(α)ごとに独立に共有値σ(α)を共有するため、安全性が高い。特に、本形態では、互いに異なる部分集合SUB(α)でそれぞれ共有される共有値σ(α)は、互いに独立なものとした。これにより、高い安全性を確保できる。
【００６２】
本形態では、分散管理装置PA(α,h(α))１２０−α−h(α)(α=1,...,L)がすべて同一の共通演算FNC1を行うこととした。本形態の共通演算FNC1は、線形性を持った演算である。よって、本形態では、秘密復元値SUBSK(α)を線形結合して生成情報SKを生成することにより、各秘密復元値SUBSK(α)を用いて生成された生成情報SKを、秘密情報θ・gと或る値σとを被演算子として共通演算FNC1を行った結果と同一にすることができる。
【００６３】
本形態では、(R(α)，H(α))しきい値秘密分散方式を用い、部分集合SUB(α)ごとに秘密情報θ・g∈Gを秘密分散した。この構成は、例えば、シェア情報SH(α,h(α))が、有限体Fqの元からなる変数をxとし、予め定められた有限体Fqの元ω∈Fqに対してf(α,ω)=θを満たすR(α)-1次の多項式をf(α,x)∈Fqとし、h(α)に対応するインデックスをφ(h(α))とした場合における、巡回群Gの元f(α,φ(h(α)))・g∈Gを含む構成とすることで可能である。このように巡回群の元である秘密情報θ・g∈Gを秘密分散することで、たとえ、シェア情報SH(α,h(α))から復元された秘密情報θ・gが外部に漏洩したとしても、巡回群Gでの離散対数問題の求解が困難であるとの前提のもとでは、θが外部に漏洩することはない。これにより、高い安全性を確保できる。
【００６４】
〔第１実施形態の変形例１〕
次に、第１実施形態の変形例１を説明する。
第１実施形態では、巡回群Gの元を秘密情報θ・g∈Gとし、これを秘密分散した。しかし、有限体Fqの元θ∈Fqを秘密分散してもよい。この場合、(R(α)，H(α))しきい値秘密分散方式を用いて秘密分散されたシェア情報SH(α,h(α))は、有限体Fqの元からなる変数をxとし、予め定められた有限体Fqの元ω∈Fqに対してf(α,ω)=θを満たすR(α)-1次の多項式をf(α,x)∈Fqとし、h(α)に対応するインデックスをφ(h(α))とした場合における、有限体Fqの元f(α,φ(h(α)))∈Fqを含む。
図１１Ａは、第１実施形態における変形例１の秘密分散部２１４−αの構成を説明するための図であり、図１１Ｂは、第１実施形態における変形例１の分散秘密値生成部２２４−α−h（α）の構成を説明するための図である。なお、これらの図において、第１実施形態と共通する部分については、第１実施形態と同じ符号を付した。
【００６５】
第１実施形態の変形例１の秘密分散システム２は、分散装置１１０が分散装置２１０に置換され、分散管理装置１２０−α−ｈ（α）（α=1,...,L）が分散管理装置２２０−α−ｈ（α）（α=1,...,L）に置換される。秘密分散部１１４−α（α=1,...,L）が図１１Ａに示すような秘密分散部２１４−α（α=1,...,L）に置換され、分散秘密値生成部１２４−α−h（α）（α=1,...,L）が図１１Ｂに示すような分散秘密値生成部２２４−α−h（α）（α=1,...,L）に置換される。その他の構成は、第１実施形態と同様である。
【００６６】
《第１実施形態の変形例１におけるステップＳ１１２の変形》
第１実施形態の変形例１では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、図８Ｂに示したステップＳ１１２ａ及びＳ１１２ｂが実行される。次に、ステップＳ１１２ｃの代わりに、秘密分散部２１４−αの分散処理部２１４ｃ−α（図１１Ａ）が、多項式f(α,x)∈Fqとインデックスφ(h(α))∈Fqとを用い、以下のシェア情報SH(α,h(α))を生成して出力する。
SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))       …(16)
【００６７】
《第１実施形態の変形例１におけるステップＳ１２４の変形》
第１実施形態の変形例１では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、ステップＳ１２４ａの代わりに、線形演算部２２４ａ−α−h（α）（図１１Ｂ）に、共有値σ(α)と提供情報vとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))のf(α,φ(h(α)))とが入力され、線形演算部２２４ａ−α−h（α）は、以下の演算を行い、その演算結果dsh(α,φ(h(α)))∈Gを出力する。
dsh(α,φ(h(α)))=σ(α)・v・f(α,φ(h(α)))・g∈G       …(17)
演算結果dsh(α,φ(h(α)))∈Gは分散秘密値DSH(α,h(α))の一部の情報となる。その後、図９Ｂに示したステップＳ１２４ｂの処理を実行する（《第１実施形態の変形例１におけるステップＳ１２４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００６８】
〔第１実施形態の変形例２〕
次に、第１実施形態の変形例２を説明する。
第１実施形態の変形例２でも有限体Fqの元θ∈Fqを秘密分散する。第１実施形態の変形例１との相違点は、演算結果dsh(α,φ(h(α)))が巡回群Gの元ではなく、有限体Fqの元である点である。
【００６９】
図１２Ａは、第１実施形態における変形例２の分散秘密値生成部３２４−α−h（α）の構成を説明するための図であり、図１２Ｂは、第１実施形態における変形例２の復元部３３４−αの構成を説明するための図である。なお、これらの図において、第１実施形態と共通する部分については、第１実施形態と同じ符号を付した。
【００７０】
第１実施形態の変形例２の秘密分散システム３は、分散装置１１０が分散装置２１０に置換され、分散管理装置１２０−α−ｈ（α）（α=1,...,L）が分散管理装置３２０−α−ｈ（α）（α=1,...,L）に置換され、取得装置１３０が取得装置３３０に置換される。また、分散秘密値生成部１２４−α−h（α）（α=1,...,L）が図１２Ａに示すような分散秘密値生成部３２４−α−h（α）（α=1,...,L）に置換され、復元部１３４−α（α=1,...,L）が図１２Ｂに示すような復元部３３４−α（α=1,...,L）に置換される。その他の構成は、第１実施形態と同様である。
【００７１】
《第１実施形態の変形例２におけるステップＳ１１２の変形》
第１実施形態の変形例１におけるステップＳ１１２の変形と同一である。
【００７２】
《第１実施形態の変形例２におけるステップＳ１２４の変形》
第１実施形態の変形例２では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、ステップＳ１２４ａの代わりに、線形演算部３２４ａ−α−h（α）（図１２Ａ）に、共有値σ(α)と提供情報vとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))のf(α,φ(h(α)))とが入力され、線形演算部３２４ａ−α−h（α）が、以下の演算を行い、その演算結果dsh(α,φ(h(α)))∈Fqを出力する。
dsh(α,φ(h(α)))=σ(α)・v・f(α,φ(h(α)))∈Fq       …(18)
演算結果dsh(α,φ(h(α)))∈Fqは分散秘密値DSH(α,h(α))の一部の情報となる。その後、図９Ｂに示したステップＳ１２４ｂの処理を実行する。
【００７３】
《第１実施形態の変形例２におけるステップＳ１３４の変形》
まず、図１０Ｂに示したステップＳ１３４ａの処理が実行される。次に、１０Ｂに示したステップＳ１３４ｂの処理の代わりに、各係数λρ(x)と、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))のdsh1(α),...,dshＲ(α)(α)とが、多項式演算部３３４ｂ−α（図１２Ｂ）に入力され、多項式演算部３３４ｂ−αが、以下の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成する。
SUBSK(α)={λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)}・g∈G
…(19)
多項式演算部３３４ｂ−αは、部分集合SUB(α)の秘密復元値SUBSK(α)を出力する（《第１実施形態の変形例２におけるステップＳ１３４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００７４】
〔第１実施形態の変形例３〕
第１実施形態の変形例３は、(R(α)，H(α))しきい値秘密分散方式の代わりに(H(α)，H(α))しきい値秘密分散方式を用いて秘密情報を秘密分散する変形例である。
図１３Ａは、第１実施形態における変形例３の秘密分散部４１４−αの構成を説明するための図であり、図１３Ｂは、第１実施形態における変形例３の分散秘密値生成部４２４−α−h（α）の構成を説明するための図であり、図１３Ｃは、第１実施形態における変形例３の復元部４３４−αの構成を説明するための図である。
【００７５】
第１実施形態の変形例３の秘密分散システム４は、分散装置１１０が分散装置４１０に置換され、分散管理装置１２０−α−ｈ（α）（α=1,...,L）が分散管理装置４２０−α−ｈ（α）（α=1,...,L）に置換され、取得装置１３０が取得装置４３０に置換される。秘密分散部１１４−α（α=1,...,L）が図１３Ａに示すような秘密分散部４１４−α（α=1,...,L）に置換され、分散秘密値生成部１２４−α−h（α）（α=1,...,L）が図１３Ｂに示すような分散秘密値生成部４２４−α−h（α）（α=1,...,L）に置換され、復元部１３４−α（α=1,...,L）が図１３Ｃに示すような復元部４３４−α（α=1,...,L）に置換される。その他の構成は、第１実施形態と同様である。
【００７６】
《第１実施形態の変形例３におけるステップＳ１１２の変形》
第１実施形態の変形例３では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、秘密分散部４１４−α（図１３Ａ）の乱数生成部４１４ａ−αにおいて、以下のH(α)-1個の巡回群Gの元をランダムに選択し、これらを出力する。
SH(α,1),...,SH(α,H(α)-1)∈G       …(20)
【００７７】
次に、逆元演算部４１４ｂ−αに、秘密情報θ・g∈Gと、H(α)-1個の巡回群Gの元SH(α,1),...,SH(α,H(α)-1)∈Gとが入力される。逆元演算部４１４ｂ−αは、以下の演算によって、SH(α,h(α))を生成して出力する。
SH(α,h(α))=θ・g -{SH(α,1)+...+SH(α,H(α)-1)}∈G     …(21)
【００７８】
秘密分散部４１４−αは、以下を部分集合SUB(α)のシェア情報として出力する。
SH(α,1),...,SH(α,H(α))∈G
これらのシェア情報は、以下の関係を満たす。
SH(α,1)+SH(α,2)+...+SH(α,H(α))=θ・g∈G       …(22)
【００７９】
《第１実施形態の変形例３におけるステップＳ１２４の変形》
第１実施形態の変形例３では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、分散秘密値生成部４２４−α−h(α)（図１３Ｂ）に、共有値σ(α)と提供情報vとシェア情報SH(α,1),...,SH(α,H(α))とが入力される。分散秘密値生成部４２４−α−h(α)は、以下の演算によって、分散秘密値DSH(α,h(α))を生成して出力する
DSH(α,h(α))=σ(α)・v・SH(α,h(α))∈G       …(23)
【００８０】
《第１実施形態の変形例３におけるステップＳ１３２の変形》
第１実施形態の変形例３では、図１０Ａに示したステップＳ１３２の処理が以下のように変形される。
この変形例３でも、制御部１３３が、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かを判定するが、変形例３での「必要数」はH(α)個である。つまり、この変形例３の場合、各α=1,...,Lについて、それぞれ、すべての分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かが判定される。
【００８１】
《第１実施形態の変形例３におけるステップＳ１３４の変形》
第１実施形態の変形例３では、図１０Ｂに示したステップＳ１３４の処理が以下のように変形される。
この変形例３の分散秘密値DSH(α,h(α))は式(23)に示すものである。また、復元部４３４−α（図１３Ｃ）には、αに対応するすべての分散秘密値DSH(α,h(α))（h(α)=1,...,H(α)）が入力される。復元部４３４−αは、以下の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する。
SUBSK(α)=DSH(α,1)+...+DSH(α,H(α))∈G       …(24)
その他の処理は、第１実施形態と同様である。
【００８２】
〔第１実施形態の変形例４〕
第１実施形態の変形例４も、(R(α)，H(α))しきい値秘密分散方式の代わりに(H(α)，H(α))しきい値秘密分散方式を用いて秘密情報を秘密分散する変形例である。変形例３との相違点は、有限体Fqの元である秘密情報θ∈Fqを秘密分散する点である。
【００８３】
図１４Ａは、第１実施形態における変形例４の秘密分散部５１４−αの構成を説明するための図であり、図１４Ｂは、第１実施形態における変形例４の分散秘密値生成部５２４−α−h（α）の構成を説明するための図であり、図１４Ｃは、第１実施形態における変形例４の復元部５３４−αの構成を説明するための図である。
第１実施形態の変形例４の秘密分散システム５は、分散装置１１０が分散装置５１０に置換され、分散管理装置１２０−α−ｈ（α）（α=1,...,L）が分散管理装置５２０−α−ｈ（α）（α=1,...,L）に置換され、取得装置１３０が取得装置５３０に置換される。秘密分散部１１４−α（α=1,...,L）が図１４Ａに示すような秘密分散部５１４−α（α=1,...,L）に置換され、分散秘密値生成部１２４−α−h（α）（α=1,...,L）が図１４Ｂに示すような分散秘密値生成部５２４−α−h（α）（α=1,...,L）に置換され、復元部１３４−α（α=1,...,L）が図１４Ｃに示すような復元部５３４−α（α=1,...,L）に置換される。その他の構成は、第１実施形態と同様である。
【００８４】
《第１実施形態の変形例４におけるステップＳ１１２の変形》
第１実施形態の変形例４では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、秘密分散部５１４−α（図１４Ａ）の乱数生成部５１４ａ−αにおいて、以下のH(α)-1個の有限体Fqの元をランダムに選択し、これらを出力する。
SH(α,1),...,SH(α,H(α)-1)∈Fq       …(25)
【００８５】
次に、逆元演算部５１４ｂ−αに、秘密情報θ∈Fqと、H(α)-1個の有限体Fqの元SH(α,1),...,SH(α,H(α)-1)∈Fqとが入力される。逆元演算部５１４ｂ−αは、以下の演算によって、SH(α,h(α))を生成して出力する。
SH(α,h(α))=θ -{SH(α,1)+...+SH(α,H(α)-1)}∈Fq       …(26)
【００８６】
秘密分散部５１４−αは、以下を部分集合SUB(α)のシェア情報として出力する。
SH(α,1),...,SH(α,H(α))∈Fq       …(27)
これらのシェア情報は、以下の関係を満たす。
SH(α,1)+SH(α,2)+...+SH(α,H(α))=θ∈Fq       …(28)
【００８７】
《第１実施形態の変形例４におけるステップＳ１２４の変形》
第１実施形態の変形例４では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、分散秘密値生成部５２４−α−h(α)（図１４Ｂ）に、共有値σ(α)と提供情報vとシェア情報SH(α,1),...,SH(α,H(α))とが入力される。分散秘密値生成部５２４−α−h(α)は、以下の演算によって、分散秘密値DSH(α,h(α))を生成して出力する。
DSH(α,h(α))=σ(α)・v・SH(α,h(α))∈Fq       …(29)
【００８８】
《第１実施形態の変形例４におけるステップＳ１３２の変形》
第１実施形態の変形例３と同じである。
【００８９】
《第１実施形態の変形例４におけるステップＳ１３４の変形》
第１実施形態の変形例４では、図１０Ｂに示したステップＳ１３４の処理が以下のように変形される。
この変形例４の分散秘密値DSH(α,h(α))は式(29)に示すものである。復元部５３４−α（図１４Ｃ）には、αに対応するすべての分散秘密値DSH(α,h(α))（h(α)=1,...,H(α)）が入力される。復元部５３４−αは、以下の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する。
SUBSK(α)={DSH(α,1)+...+DSH(α,H(α))}・g∈G       …(30)
その他の処理は、第１実施形態と同様である。
【００９０】
〔第１実施形態のその他の変形例〕
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、第１実施形態の変形例４の式(29)の代わりに、以下の式(31)の演算を行い、式(30)の代わりに式(24)の演算を行ってもよい。
DSH(α,h(α))=σ(α)・v・SH(α,h(α))∈Fq       …(31)
秘密復元値SUBSK(α)が有限体Fqの元となる構成であってもよい。
【００９１】
本形態では、各部分集合SUB(α)に対してそれぞれ同一の秘密分散方式を用いて秘密分散を行ったが、互いに異なる各部分集合SUBに対して互いに異なる秘密分散方式を用いてもよい。
【００９２】
本形態では、各部分集合SUB(α)ごとに共有値生成装置１４０−αを設けたが、各部分集合SUB(α)の何れかの分散管理装置が共有値生成装置の機能を持っていてもよい。この場合には、共有値生成装置１４０−αは不要となる。
【００９３】
本形態では、共有値σ(α)と提供情報vとを含む共通情報と、シェア情報SH(α,h(α))とを用い、共通演算FNC1を行って分散秘密値DSH(α,h(α))を生成することとした。しかし、提供情報vを用いることなく、共有値σ(α)を共通情報として分散秘密値DSH(α,h(α))を生成してもよい。共通情報が、共有値σ(α)と提供情報vとその他の情報とを含んでもよい。
【００９４】
分散秘密値DSH(α,h(α))を求めるための共通演算は、部分集合SUB(α)ごとに統一する必要はあるが、必ずしも、互いに異なる部分集合SUB(α)間で同一の共通演算を行う必要はない。
【００９５】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は第１実施形態を関数暗号の鍵生成に応用した形態である。
【００９６】
＜定義＞
本形態で使用する用語や記号を定義する。
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積（ＡＮＤ）を表す論理記号である。
∨：∨は論理和（ＯＲ）を表す論理記号である。
¬：¬は否定（ＮＯＴ）を表す論理記号である。
命題変数：命題変数は命題の「真」,「偽」（"false","true"）を要素とする集合｛真，偽｝上の変数である。すなわち、命題変数の定義域は「真」,「偽」を要素とする集合である。命題変数及び命題変数の否定を総称してリテラル（literal）と呼ぶ。
論理式：論理式とは数理論理学における命題を表す式を意味する。具体的には「真」及び「偽」は論理式であり、命題変数は論理式であり、論理式の否定は論理式であり、論理式と論理式との論理積は論理式であり、論理式と論理式との論理和は論理式である。
【００９７】
Ｚ：Ｚは整数集合を表す。
sec：secはセキュリティパラメータ（sec∈Z, sec>0）を表す。
0*：0*は*個の0からなる列を表す。
1*：1*は*個の１からなる列を表す。
Fq：Fqは位数qの有限体を表す（第１実施形態と同一）。
0F： 0Fは有限体Fqの加法単位元を表す（第１実施形態と同一）。
1F：は有限体Fqの乗法単位元を表す（第１実施形態と同一）。
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
【００９８】
E： Eは有限体Fq上で定義された楕円曲線を表す（第１実施形態と同一）。
楕円曲線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は巡回群G, 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          …(32)
双線形写像eψは以下の性質を満たす。
［双線形性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)及びν，κ∈Fqについて以下の関係を満たす。
eψ(ν・Γ1,κ・Γ2)=eψ(Γ1,Γ2)ν・κ          …(33)
［非退化性］双線形写像eψは、すべてのΓ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)を巡回群GTの単位元に写す写像ではない。
［計算可能性］あらゆる
Γ1∈G1n(ψ)+ζ(ψ)，Γ2∈G2n(ψ)+ζ(ψ)          …(34)
についてeψ(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【０１０３】
本形態では、以下のような、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を用いて双線形写像eψを構成する。
Pair:G1×G2→GT          …(35)
本形態の双線形写像eψは、巡回群G1のn(ψ)+ζ(ψ)個の元γβ (β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1,...,γn(ψ)+ζ(ψ))と、巡回群G2のn(ψ)+ζ(ψ)個の元γβ*(β=1,...,n(ψ)+ζ(ψ))からなるn(ψ)+ζ(ψ)次元ベクトル(γ1*,...,γn(ψ)+ζ(ψ)*)との入力に対し、巡回群GTの１個の元を出力する。
eψ：Πβ=1n(ψ)+ζ(ψ)Pair(γβ, γβ*)          …(36)
双線形写像Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する。双線形写像Pairは、以下の性質を満たす。
［双線形性］双線形写像Pairは、すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(37)
［非退化性］双線形写像Pairは、すべての
Ω1∈G1，Ω2∈G2          …(38)
を巡回群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)          …(39)
...
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)          …(40)
...
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)           …(41)
すなわち、i=jの場合には、式(36)(37)の関係から以下の関係が満たされる。
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)との積になる。さらに、式(37)の関係から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)           …(42)
を満たす。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(ψ)+ζ(ψ))が式(39)によって表現される場合、行列A(ψ)は以下のようになる。
【数３】
2012011565.tif 000005
【０１１０】
A*(ψ)：A*(ψ)は基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。例えば、基底ベクトルai*(ψ)(i=1,...,n(ψ)+ζ(ψ))が式(40)によって表現される場合、行列A*(ψ)は以下のようになる。
【数４】
2012011565.tif 000006
【０１１１】
X(ψ)：X(ψ)は有限体Fqの元を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。行列X(ψ)は基底ベクトルai(ψ)の座標変換に用いられる。行列X(ψ)のi行j列(i=1,...,n(ψ)+ζ(ψ),j=1,...,n(ψ)+ζ(ψ))の要素をχi,j(ψ)∈Fqとすると、行列X(ψ)は以下のようになる。
【数５】
2012011565.tif 000007
なお、行列X(ψ)の各要素χi,j(ψ)を変換係数と呼ぶ。
【０１１２】
X *(ψ)：行列X*(ψ)はX*(ψ)=τ'・(X(ψ)-1)Tの関係を満たす行列である。ただし、τ'∈Fqは有限体Fqに属する任意の定数であり、例えば、τ'=1Fである。X*(ψ)は基底ベクトルai*(ψ)の座標変換に用いられる。行列X*(ψ)のi行j列の要素をχi,j*(ψ)∈Fqとすると、行列Ｘ*(ψ)は以下のようになる。
【数６】
2012011565.tif 000008
なお、行列Ｘ*(ψ)の各要素χi,j*(ψ)を変換係数と呼ぶ。
【０１１３】
この場合、n(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の単位行列をI(ψ)とするとX(ψ)・(X*(ψ))T=τ'・I(ψ)を満たす。すなわち、単位行列を以下のように定義する。
【数７】
2012011565.tif 000009
これについて以下が満たされる。
【数８】
2012011565.tif 000010
ここで、n(ψ)+ζ(ψ)次元ベクトルを以下のように定義する。
χi→(ψ)=(χi,1(ψ),...,χi,n(ψ)+ζ(ψ)(ψ))          …(49)
χj→*(ψ)=(χj,1*(ψ),...,χj,n(ψ)+ζ(ψ)*(ψ))           …(50)
すると、式(48)の関係から、n(ψ)+ζ(ψ)次元ベクトルχi→(ψ)とχj→*(ψ)との内積は、以下のようになる。
χi→(ψ)・χj→*(ψ)=τ'・δ(i,j)          …(51)
【０１１４】
bi(ψ)：bi(ψ)は巡回群G1のn(ψ)+ζ(ψ)個の元を要素とするn(ψ)+ζ(ψ)次元の基底ベクトルを表す。bi(ψ)は行列X(ψ)を用いて基底ベクトルai(ψ) (i=1,...,n(ψ)+ζ(ψ))を座標変換することで得られる。具体的には、基底ベクトルbi(ψ)は、以下の演算によって得られる。
bi(ψ)=Σj=1n(ψ)+ζ(ψ)χi,j(ψ)・aj(ψ)          …(52)
例えば、基底ベクトルaj(ψ)(j=1,...,n(ψ)+ζ(ψ))が式(39)によって表現される場合、基底ベクトルbi(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi(ψ)=(χi,1(ψ)・κ1・g1,χi,2(ψ)・κ1・g1,
...,χi,n(ψ)+ζ(ψ)(ψ)・κ1・g1)          …(53)
巡回群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*(ψ)          …(54)
例えば、基底ベクトルaj*(ψ) (j=1,...,n(ψ)+ζ(ψ))が式(40)によって表現される場合、基底ベクトルbi*(ψ)の各要素をそれぞれ列挙して表現すると、以下のようになる。
bi*(ψ)=(χi,1*(ψ)・κ2・g2 ,χi,2*(ψ)・κ2・g2,
...,χi,n(ψ)+ζ(ψ)*(ψ)・κ2・g2)        …(55)
【０１１６】
巡回群G2のn(ψ)+ζ(ψ)個の元を要素とするすべてのn(ψ)+ζ(ψ)次元ベクトルは、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)(i=1,...,n(ψ)+ζ(ψ))の線形和によって表される。すなわち、n(ψ)+ζ(ψ)次元の基底ベクトルbi*(ψ)は前述のベクトル空間V*(ψ)を張る。
【０１１７】
なお、基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、0Fを除く有限体Fqの元τ=κ1・κ2について以下の関係を満たす。
eψ(bi(ψ), bj*(ψ))=gTτ・τ'・δ(i,j)          …(56)
すなわち、式(36)(51)(53)(55)の関係から、以下の関係が満たされる。
【数９】
2012011565.tif 000011
特にτ=κ1・κ2=1F（例えば、κ1=κ2=1F）及びτ'=1Fである場合、以下の関係が満たされる。
eψ(bi(ψ), bj*(ψ))=gTδ(i,j)          …(57)
基底ベクトルbi(ψ)と基底ベクトルbi*(ψ)とは、双対ペアリングベクトル空間（ベクトル空間V(ψ)とベクトル空間V*(ψ)）の双対正規直交基底である。
式(56)の関係を満たすのであれば、式(39)(40)で例示したもの以外の基底ベクトルai(ψ)及びai*(ψ)や、式(52)(54)で例示したもの以外の基底ベクトルbi(ψ)及びbi*(ψ)を用いてもよい。
【０１１８】
B(ψ)：B(ψ)は基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列である。B(ψ)=X(ψ)・A(ψ)を満たす。例えば、基底ベクトルbi(ψ)が式(53)によって表現される場合、行列B(ψ)は、以下のようになる。
【数１０】
2012011565.tif 000012
【０１１９】
B*(ψ)：B*(ψ)は基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列を表す。B*(ψ)=X*(ψ)・A*(ψ)を満たす。例えば、基底ベクトルbi*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(55)によって表現される場合、行列B*(ψ)は、以下のようになる。
【数１１】
2012011565.tif 000013
【０１２０】
v(λ)→：v(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
v(λ)→=(v1(λ),...,vn(λ)(λ))∈Fqn(λ)          …(60)
vμ(λ)：vμ(λ)はn(λ)次元ベクトルv(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
w(λ)→：w(λ)→は有限体Fqの元を要素とするn(λ)次元ベクトルを表す。
w(λ)→=(w1(λ),...,wn(λ)(λ))∈Fqn(λ)          …(61)
wμ(λ)：wμ(λ)はn(λ)次元ベクトルw(λ)→のμ(μ=1,...,n(λ))番目の要素を表す。
【０１２１】
Enc：Encは共通鍵暗号方式の暗号化処理を示す共通鍵暗号関数を表す。
EncK(M)：EncK(M)は、共通鍵Kを用い、共通鍵暗号関数Encに従って平文Mを暗号化して得られた暗号文を表す。
Dec：Decは、共通鍵暗号方式の復号処理を示す共通鍵復号関数を表す。
DecK(C)：DecK(C)は、共通鍵Kを用い、共通鍵復号関数Decに従って暗号文Cを復号して得られた復号結果を表す。
【０１２２】
＜関数暗号方式＞
次に、関数暗号方式の基本的な構成について説明する。
関数暗号方式とは、第１情報と第２情報との組み合わせによって定まる論理式の真理値が「真」となる場合に暗号文が復号される方式である。「第１情報」と「第２情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、「"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」（参考文献９）に開示された述語暗号方式は関数暗号方式の一種である。
【０１２３】
これ以外にも様々な公知の関数暗号方式が存在するが、以下では未公開の新たな関数暗号方式を説明する。以下に説明する新たな関数暗号方式では秘密情報に応じた値が所定の論理式に応じた態様で階層的に秘密分散される。所定の論理式は、第１情報と第２情報との組み合わせによって真理値が定まる命題変数を含み、必要に応じてさらに論理記号∧，∨，¬の何れか又はすべてを含む。各命題変数の真理値が特定されることで定まる当該所定の論理式の真理値が「真」となる場合に秘密情報に応じた値が復元され、それに基づいて暗号文が復号される。
【０１２４】
＜論理式と階層的な秘密分散との関係＞
上述した所定の論理式と階層的な秘密分散との関係を説明する。
前述したように、(N,N)しきい値秘密分散方式では、すべてのシェア情報share(1),...,share(N)が与えられれば秘密情報SEを復元できるが、任意のN-1個のシェア情報share(φ1),...,share(φN-1)が与えられても秘密情報SEの情報はまったく得られない。(Kt,N)しきい値秘密分散方式では、任意の相違なるKt個のシェア情報share(φ1),...,share(φKt)が与えられれば秘密情報SEを復元できるが、任意のKt-1個のシェア情報share(φ1),...,share(φKt-1)が与えられても秘密情報SEの情報はまったく得られない。
【０１２５】
これらの秘密分散方式は体上でも実行可能である。これらを拡張して秘密情報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の線形結合となる。秘密情報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,2)しきい値秘密分散方式で秘密分散された各シェア情報SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4には、シェア情報SEに応じた値が(2,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,3)しきい値秘密分散方式で秘密分散された各シェア情報SE,SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4,N5には、シェア情報SEに応じた値が(2,3)しきい値秘密分散方式で秘密分散された各シェア情報(1,f(1)),(2,f(2)),(3,f(3))に応じた値がそれぞれ対応する。ノードN7の子ノードN8,N11には、シェア情報SEに応じた値が(2,2)しきい値秘密分散方式で秘密分散された各シェア情報SH4,SE-SH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9,N10には、シェア情報SH4に応じた値が(1,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(2),PRO(3),PRO(1),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)の真理値は第１情報と第２情報との組み合わせによって定まる。ここで、真理値が真となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られるが、真理値が偽となったリテラルに対応する葉ノードに対応するシェア情報に応じた値は得られない。この場合、第１情報と第２情報との組み合わせが標準形論理式(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(λ)とを含む。
【数１２】
2012011565.tif 000014
【０１３４】
行列MTの各要素mtλ,col（col=1,...,COL）は次の２つの要件を満たす。第１に、上述のように所定の論理式を表現した木構造データのルートノードに秘密情報SE∈Fqに応じた値が対応する場合、予め定められた有限体Fqの元を要素とするCOL次元ベクトルGV→と秘密情報SEに応じた有限体Fqの元を要素とするCOL次元ベクトルCV→との間に以下の関係が成立する。
GV→=(gv1,...,gvCOL)∈FqCOL          …(63)
CV→=(cv1,...,cvCOL)∈FqCOL          …(64)
SE=GV→・(CV→)T          …(65)
以下にCOL次元ベクトルGV→の具体例を示す。
GV→=(1F,...,1F)∈FqCOL          …(66)
ただし、GV→=(1F,0F,...,0F)∈FqCOLなどのその他のCOL次元ベクトルがGV→であってもよい。
【０１３５】
第２に、識別子λに対応する葉ノードにシェア情報share(λ)∈Fqに応じた値が対応する場合、以下の関係が成立する。
(share(1),...,share(Ψ))T=MT・(CV→)T          …(67)
上述のように所定の論理式を表現した木構造データが定まれば、これら２つの要件を満たす行列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(Ψ))          …(68)
要素tfv(λ)は、内積v(λ)→・w(λ)→が０のときにtfv(λ)=１となり、０以外のときにtfv(λ)=0となる。
tfv(λ)=1  （PRO(λ)が真）  if  v(λ)→・w(λ)→=0    …(69)
tfv(λ)=0  （PRO(λ)が偽）  if  v(λ)→・w(λ)→≠0   …(70)
さらに、以下の論理式の真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。
{(LAB(λ)=v(λ)→)∧(tfv(λ)=1)}∨{(LAB(λ)=¬v(λ)→)∧(tfv(λ)=0)}
…(71)
すなわち、識別子λに対応する葉ノードに対応するリテラルの真理値が「真」になるときLIT(λ)=1と表記し「偽」になるときLIT(λ)=0と表記する。すると、行列MTが含む行ベクトルのうちLIT(λ)=1となる行ベクトルmtλ→=(mtλ,1,...,mtλ,COL)のみからなる部分行列MTTFVは以下のように表記できる。
MTTFV=(MT)LIT(λ)=1          …(72)
【０１３８】
上述した秘密分散方式が線形秘密分散方式である場合、識別子λに対応するシェア情報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(μ)          …(73)
{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(ψ)+ζ(ψ))が式(52)に従って座標変換され、n(ψ)+ζ(ψ)次元の基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))が生成される。基底ベクトルbi(ψ) (i=1,...,n(ψ)+ζ(ψ))を要素とするn(ψ)+ζ(ψ)行n(ψ)+ζ(ψ)列の行列B(ψ)が生成される。
(Setup-4) 基底ベクトルai*(ψ) (i=1,...,n(ψ)+ζ(ψ))が式(54)に従って座標変換され、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) 式(63)-(67)を満たす秘密情報SEに対して以下の処理が実行される。
D*(0)=-SE・b1*(0)+Σι=2Icoefι(0)・bι*(0)          …(74)
ただし、Iは2以上n(0)+ζ(0)以下の定数である。coefι(0)∈Fqは定数又は乱数である。「乱数」とは真性乱数や擬似乱数を意味する。以下にD*(0)の一例を示す。なお、式(75)のcoef4(0)は乱数である。
D*(0)=-SE・b1*(0)+b3*(0)+coef4(0)・b4*(0)          …(75)
【０１４６】
(GenKey-2) 式(63)-(67)を満たすshare(λ)(λ=1,...,Ψ)に対して以下の処理が実行される。
LAB(λ)=v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(76)
LAB(λ)=¬v(λ)→となるλに対して、以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ)・bι*(λ)          …(77)
ただしcoef(λ),coefι(λ)∈Fqは定数又は乱数である。以下に一例を示す。
LAB(λ)=v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=(share(λ)+coef(λ)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ)・vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(78)
LAB(λ)=¬v(λ)→となるλに対して、例えば以下のD*(λ)が生成される。
D*(λ)=share(λ)・Σι=1n(λ)vι(λ)・bι*(λ)
+Σι=2・n(λ)+13・n(λ)coefι(λ)・bι*(λ)          …(79)
なお、式(78)(79)のcoef(λ)及びcoefι(λ)は乱数である。
【０１４７】
(GenKey-3) 以下の鍵情報が生成される。
SKS=(LMT(MT,LAB),D*(0),D*(1),...,D(Ψ))          …(80)
【０１４８】
［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)          …(81)
C(λ)=υ・Σι=1n(λ)wι(λ)・bι(λ)+Σι=n(λ)+1n(λ)+ζ(λ)υι(λ)・bι(λ)
…(82)
ただし、υ,υι(ψ)∈Fq(ψ=0,...,Ψ)は定数又は乱数であり、以下の関係が満たされる。
(coef2(0),...,coefI(0))・(υ2(0),...,υI(0))=υ'      …(83)
coefι(λ)・υι(λ)=0F (ι=n(λ)+1,...,n(λ)+ζ(λ))  …(84)
υ'の例はυ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          …(85)
が生成される。例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(86)
【０１５１】
(Enc-3) 共通鍵Kを用いて平文Mの暗号文C(Ψ+1)が生成される。
C(Ψ+1)=EncK(M)          …(87)
共通鍵暗号方式Encは、例えば共通鍵Kを用いて暗号化可能に構成されたカメリア（Camellia）（登録商標）やAESや共通鍵と平文との排他的論理和などでよいが、その他の簡単な例として以下のようにEncK(M)を生成してもよい。ただし、式(88)の例ではM∈GTとされる。
C(Ψ+1)=gTυ'・M          …(88)
【０１５２】
(Enc-4) 以下の暗号文が生成される。
C=(VSET2,C(0),{C(λ)}(λ,w(λ)→)∈VSET2,C(Ψ+1))        …(89)
ただし、下付き添え字の「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>であるか否かが判定される（式(69)-(73)）。GV→∈span<MTTFV>でなければ暗号文Cが拒絶され、GV→∈span<MTTFV>であれば暗号文Cが受け入れられる。
(Dec-2) 暗号文Cが受け入れられると、SET⊆{1,...,λ|LIT(λ)=1}と式(73)を満たす係数const(μ)(μ∈SET)とが計算される。
【０１５５】
(Dec-3) 以下の共通鍵が生成される。
【数１３】
2012011565.tif 000015
【０１５６】
式(37)(56)(83)より、以下の関係が満たされる。
【数１４】
2012011565.tif 000016
【０１５７】
式(37)(56)(69)(76)(82)(84)及びw1(λ)=1Fより、以下の関係が満たされる。
【数１５】
2012011565.tif 000017
【０１５８】
式(37)(56)(70)(77)(82)(84)より、以下の関係が満たされる。
【数１６】
2012011565.tif 000018
【０１５９】
式(73)(91)-(93)から以下の関係が満たされる。
【数１７】
2012011565.tif 000019
例えば、τ=τ'=1Fの場合、以下の関係が満たされる。
K=gTυ'∈GT          …(95)
【０１６０】
(Dec-4) 共通鍵Kを用い、以下のように平文M'が生成される。
M'=DecK(C(Ψ+1))=DecK(C(Ψ+1))          …(96)
例えば、式(88)に例示した共通鍵暗号方式の場合、以下のように平文M'が生成される。
M'=C(Ψ+1)/K          …(97)
【０１６１】
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とされる。
【０１６２】
＜全体構成＞
図１７は、第２実施形態の秘密分散システムの全体構成を説明するためのブロック図である。
図１７に例示するように、本形態の秘密分散システム６は、分散装置６１０と、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)〕６２０−α−h（α）と、取得装置６３０と、共有値生成装置６４０−１〜Ｌ，６５０とを有し、それらはネットワーク１５０を通じて通信可能である。説明を簡略化するため、本形態では、分散装置６１０及び取得装置６３０が１つずつ存在する構成を例示するが、分散装置６１０及び／又は取得装置６３０が２以上存在してもよい。同様な理由により、本形態では、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))〕６２０−α−h（α）からなる集合が１つのみ存在する構成を例示するが、このような集合が複数存在していてもよい。
【０１６３】
図１７に例示するように、Σα=1Lh(α)個の分散管理装置〔PA(α,h(α))〕６２０−α−h（α）からなる集合は、H(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる複数の部分集合SUB(α)ごとに区分される。各部分集合SUB(α)には共有値生成装置６４０−αがそれぞれ対応する。
【０１６４】
図１８は、第２実施形態の分散装置６１０の構成を説明するためのブロック図である。また、図１９Ａ及び１９Ｂは、共有値生成装置６４０−１〜Ｌ，６５０の構成を説明するためのブロック図である。図２０は、第２実施形態の分散管理装置〔PA(α,h(α))〕６２０−α−ｈ（α）の構成を説明するためのブロック図である。図２１は、第２実施形態の取得装置６３０の構成を説明するためのブロック図である。なお、これらの図において第１実施形態と共通する部分については、第１実施形態と同じ符号を付して説明を簡略化する。
【０１６５】
＜分散装置６１０＞
図１８に例示するように、本形態の分散装置６１０は、一時記憶部１１１と、記憶部１１２と、制御部１１３と、秘密分散部６１４−α（α=1,...,L）と、送信部１１５とを有する。なお、本形態の分散装置６１０は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１６６】
＜共有値生成装置６４０−α，６５０＞
図１９Ａに例示するように、本形態の共有値生成装置６４０−αは、係数設定部６４１−αと送信部６４２−αとを有する。図１９Ｂに例示するように、本形態の共有値生成部６５０は記憶部６５１と逆関数演算部６５２，６５３と送信部６５４とを有する。
【０１６７】
＜分散管理装置〔PA(α,h(α))〕６２０−α−h（α）＞
図２０に例示するように、本形態の分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、一時記憶部１２１−α−h（α）と、記憶部１２２−α−h（α）と、制御部１２３−α−h（α）と、分散秘密値生成部６２１−α−h（α），６２２−α−h（α），６２３−α−h（α）と、選択部６２４−α−h（α）と、送信部１２５−α−h（α）と、受信部１２６−α−h（α）とを有する。なお、本形態の分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１６８】
＜取得装置６３０＞
図２１に例示するように、本形態の取得装置６３０は、一時記憶部１３１と、記憶部１３２と、制御部１３３と、復元部６３４−α，６３６−α（α=1,...,L）と、合成部６３５，６３７と、受信部１３６とを有する。なお、本形態の取得装置６３０は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１６９】
＜秘密分散処理＞
次に、本形態の秘密分散処理を説明する。
本形態では、第１実施形態を応用し、アクセス構造を用いた関数暗号方式のマスター鍵情報である基底ベクトルbi*(ψ)（式(55)）を秘密分散し、それらのシェア情報に対する演算結果から鍵情報D*(ψ)を復元する。以下では式(74)(76)(77)のように一般化された鍵情報D*(ψ)を復元する例を示す。しかし、同様な処理が式(75)(78)(79)のように具体化された鍵情報D*(ψ)の場合にも適用可能なことはいうまでもない。
【０１７０】
式(55)に示した基底ベクトルbi*(ψ)を構成する式(98)に示す各要素を、式(99)のように表現する。
χi,β*(ψ)・κ2・g2∈G2(i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ)+ζ(ψ))
…(98)
θ(ψ,i,β)・g2∈G2      …(99)
ただし、以下が満たされる。
θ(ψ,i,β)=χi,β*(ψ)・κ2∈Fq    …(100)
すなわち、式(55)の基底ベクトルbi*(ψ)を以下のように表現する。
bi*=(ψ,θ(i,1)・g2,...,θ(ψ,i,n(ψ)+ζ(ψ))・g2)∈G2n(ψ)+ζ(ψ)
…(101)
この式より、第１実施形態を多次元に拡張することで基底ベクトルbi*(ψ)を秘密分散できることが分かる。秘密情報はシェア情報の線形な演算によって復元されるため、多次元の秘密分散によって得られた各次元のシェア情報に対して線形な演算を施した結果をシェア情報とみなして復元処理を行うことも可能である。そのため、第１実施形態を多次元に拡張することで鍵情報D*(ψ)の復元処理が実行できることも分かる。
【０１７１】
以下では、第１実施形態との相違点を中心に説明し、それらと共通する事項については説明を省略する。
[事前処理]
本形態の秘密分散処理の事前処理として、各基底ベクトルbi*(ψ)の要素である秘密情報θ(ψ,i,β)・g2∈G2(i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ)+ζ(ψ))を特定するための情報θ(ψ,i,β)∈Fqが分散装置６１０の記憶部１１２に格納される。共有値生成装置６５０の記憶部６５１に式(63)-(67)を満たす秘密情報SEとシェア情報share(λ)(λ=1,...,Ψ)とが格納される。式(60)のn(λ)次元ベクトルv(λ)→の集合{v(λ)→}λ=1,...,Ψである第１情報に対応するラベル付き行列LMT(MT,LAB)が、各分散管理装置６２０−α−ｈ（α）の記憶部１２２−α−ｈ（α）に、それぞれ格納される。なお、ラベル付き行列LMT(MT,LAB)は、すべての分散管理装置PA(α,h(α))６２０−α−h（α）に共通である。
【０１７２】
[秘密分散処理の全体]
図２２及び図２３は、第２実施形態の秘密分散処理の全体を説明するための図である。以下、図２２及び図２３用いて、本形態の秘密分散処理の全体を説明する。
本形態では、まず、分散装置６１０（図１７）が、基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値を、それぞれH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に、所定の秘密分散方式に従って秘密分散し、各要素θ(ψ,i,β)・g2に応じた値のシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))を生成する。本形態での基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)であり、秘密分散する対象が複数であること以外、秘密分散の具体的な方法は第１実施形態の変形例１，２，４の何れかと同じである。本形態のすべてのθ(ψ,i,β)は第１実施形態の変形例１，２，４の何れかと同じ方法で秘密分散される。つまり、本形態では、第１実施形態の変形例１，２，４の何れかの秘密分散方法のθをθ(ψ,i,β)に置換した秘密分散方法が実行される。例えば、以下のようなシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))が生成される。
SH(ψ,i,β,α,h(α))=(φ(h(α)), f(α,φ(h(α))))∈Fq
ただし、f(α,ω)=θ(ψ,i,β)を満たし、ω∈Fqは予め定められた有限体Fqの元である。
各シェア情報SH(ψ,i,β,α,h(α))は、それぞれ、ネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）(α=1,...,L)に分散して送信される（ステップＳ６１及びＳ６１’）。
【０１７３】
各シェア情報SH(ψ,i,β,α,h(α))が送信された各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）(α=1,...,L)は、それぞれ、部分集合SUB(α)ごとに共有される共通情報と、シェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))とに対し、部分集合SUB(α)ごとに共通の共通演算を行って分散秘密値DSH(ψ,α,h(α))を生成する。互いに異なる部分集合SUB(α)でそれぞれ共有される共通情報は互いに独立である。共通演算は線形性を持った演算である。本形態の共通情報は、例えば、秘密情報SEから得られたSE(α)（FNC2-1(SE)→SE(1),...,SE(α),...,SE(L)）、シェア情報share(λ)から得られたshare(λ,α)（FNC2’-1(share(λ))→share(λ,1),...,share(λ,α),...,share(λ,L)）、及び定数又は乱数であるcoefι(0,α), coef(λ,α), coefι(λ,α)∈Fqを含む。FNC2-1は線形演算関数FNC2の逆関数を表す。FNC2’-1は線形演算関数FNC2’の逆関数を表す。線形演算関数FNC2は入力されたL個の値の線形演算結果を出力する関数であり、線形演算関数FNC2の例はL個の値の線形結合値を出力する関数である。どのιに対するcoefι(0,α)やcoefι(λ,α)が共通情報とされるのか、及び、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)が定数なのか乱数なのかは、生成される鍵情報D*(ψ)の構造に依存する。本形態の各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下のようにψ=0に対応する分散秘密値DSH(0,α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)を生成する（FNC1）。
SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α)))
…(102)
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))・g2  …(103)
【０１７４】
さらに、本形態の各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下の式(104)-(106)のように各λ(λ=1,...,Ψ)に対応する分散秘密値DSH(λ,α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)を生成する（FNC1’）。
SHbi*(λ,α,h(α))
=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))) …(104)
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2  …(105)
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2  …(106)
各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）から出力された各分散秘密値DSH(ψ,α,h(α))は、それぞれ、ネットワーク１５０経由で取得装置６３０に送信される（ステップＳ６２及びＳ６２’）。
【０１７５】
取得装置６３０は、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(ψ,α,h(α))を用い、前述したステップＳ６１及びＳ６１’の秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって、当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)(ψ=0,...,Ψ, α=1,...,L)を生成する。
本形態の取得装置６３０は、例えば、以下のSUBSK(0,α)をψ=0に対応する秘密復元値とする。
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)      …(107)
本形態の取得装置６３０は、例えば、以下の式(108)又は(109)を各λ=1,...,Ψに対応する秘密復元値SUBSK(λ,α)とする。
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)      …(108)
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)                …(109)
これらの処理は、分散秘密値DSH(ψ,α,h(α))の各次元（次数）に対して第１実施形態で示した復元処置を実行することで実現できる。すなわち、各分散秘密値DSH(ψ,α,h(α))はベクトルであるが、それらの各次元（次数）に対して第１実施形態で示した復元処理（ステップＳ１３４）をそれぞれ実行することで上述の復元処理が実現できる。例えば、この復元処理に利用されるベクトルである分散秘密値DSH(ψ,α,h(α))のι次元目の要素を以下のように表現する。
(φ1(α), dsh1(α))
・・・
(φR(α)(α), dshＲ(α)(α))
この場合に式(11)の演算が行われて各係数λρ(x)(ρ=1,...,R(α))が得られ、以下の計算が行われることでψに対応する秘密復元値SUBSK(ψ,α)のι次元目が得られる。
λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)
よって、各ψ及びιに対してそれぞれ同様な処理を行うことで秘密復元値SUBSK(ψ,α)が得られる（ステップＳ６３及びＳ６３’）。
【０１７６】
取得装置６３０は、各部分集合SUB(α)についてそれぞれ生成された秘密復元値SUBSK(ψ,α)(ψ=0,...,Ψ, α=1,...,L)を用いて生成情報D*(ψ)(ψ=0,...,Ψ)を生成し、当該生成情報D*(ψ)を出力する（D*(ψ)=FNC2(SUBSK(ψ,1),...,(SUBSK(ψ,α),..., (SUBSK(ψ,L))）。
例えば、取得装置６３０は、秘密復元値SUBSK(ψ,α)を線形結合して生成情報D*(ψ)を生成する。例えば、以下の式(110-1)（110-2）を満たすように秘密分散されていたのであれば、取得装置６３０は、以下の式(111)に従ってD*(ψ)(ψ=0,...,Ψ)を生成する（ステップＳ６４及びＳ６４’）。
FNC2(SUBSK(0,1),...,(SUBSK(0,α),..., (SUBSK(0,L)))
=SUBSK(0,1)+,..., +SUBSK(0,α)+,...,+SUBSK(0,L)    …(110-1)
FNC2’(SUBSK(λ,1),...,(SUBSK(λ,α),..., (SUBSK(λ,L)))
=SUBSK(λ,1)+,..., +SUBSK(λ,α)+,...,+SUBSK(λ,L)    …(110-2)
D*(ψ)=SUBSK(ψ,1)+,..., +SUBSK(ψ,α)+,...,+SUBSK(ψ,L)    …(111)
【０１７７】
[分散装置の処理（テップＳ６１及びＳ６１’）]
図２４は、第２実施形態の分散装置の処理を例示するための図である。以下、この図を用いて、分散装置６１０の処理の詳細を説明する。
まず、分散装置６１０（図１８）の制御部１１３がψ=0に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０１）。制御部１１３がα=１，β=1に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０２）。次に、分散装置６１０の制御部１１３が、i=１に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０３）。
次に、記憶部１１２から秘密情報θ(ψ,i,β)・g2∈G2(i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ,)+ζ(ψ,))を特定するための情報θ(ψ,i,β)∈Fqがそれぞれ読み出され、秘密分散部６１４−α（α=1,...,L）に入力される。秘密分散部６１４−αは、各情報θ(ψ,i,β)∈Fqを秘密分散し、以下のように、情報θ(ψ,i,β)ごとに部分集合SUB(α)に対するH(α)個のシェア情報を生成して出力する（ステップＳ６１０４）。
SH(ψ,i,β,α,1),...,SH(ψ,i,β,α,H(α))      …(112)
例えば、情報θ(ψ,i,β)ごとに第１実施形態のステップＳ１１２の処理を実行することでステップＳ６１０４の処理が実行される。
【０１７８】
次に、制御部１１３は、一時記憶部１１１に格納されたβがn(ψ)+ζ(ψ)であるか否かを判定する（ステップＳ６１０５）。ここで、β=n(ψ)+ζ(ψ)でないと判定された場合、制御部１１３は、β+1を新たなβとし、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０５）。ステップＳ６１０５の後、ステップＳ６１０４に戻る。
【０１７９】
一方、ステップＳ６１０５でβ=n(ψ)+ζ(ψ)であると判定された場合、制御部１１３は、β=1に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０７）。次に、制御部１１３は、一時記憶部１１１に格納されたiがn(ψ)+ζ(ψ)であるか否かを判定する（ステップＳ６１０８）。ここで、i=n(ψ)+ζ(ψ)でないと判定された場合、制御部１１３は、i+1を新たなiとし、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０９）。ステップＳ６１０９の後、ステップＳ６１０４に戻る。
【０１８０】
一方、ステップＳ６１０８でi=n(ψ)+ζ(ψ)であると判定された場合、制御部１１３は、一時記憶部１１１に格納されたαがLであるか否かを判定する（ステップＳ６１１０）。ここで、α=Lでないと判定された場合、制御部１１３は、α+1を新たなαとし、その設定内容を一時記憶部１１１に格納する（ステップＳ６１１１）。ステップＳ６１１１の後、ステップＳ６１０３に戻る。
【０１８１】
一方、ステップＳ６１１０でα=Lであると判定された場合、制御部１１３は、一時記憶部１１１に格納されたψがΨであるか否かを判定する（ステップＳ６１１２）。ここで、ψ=Ψでないと判定された場合、制御部１１３は、ψ+1を新たなψとし、その設定内容を一時記憶部１１１に格納する（ステップＳ６１１３）。ステップＳ６１１３の後、ステップＳ６１０２に戻る。
【０１８２】
一方、ステップＳ６１１２でψ=Ψであると判定された場合、各秘密分散部６１４−αから出力された各SH(ψ,i,β,α,1),...,SH(ψ,i,β,α,H(α))が送信部１１５に送られる。送信部１１５は、ネットワーク１５０経由で、以下のシェア情報をそれぞれ分散管理装置〔PA(α,h(α))〕６２０−α−h(α)(α=1,...,L)に送信する（ステップＳ６１１４）。
SH(ψ,i,β,α,h(α)) (i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ)+ζ(ψ))
…(113)
すなわち、各シェア情報SH(ψ,i,β,1,h(1))は分散管理装置〔PA(1,1)〕６２０−1−1に、各シェア情報SH(ψ,i,β,2,h(2))は分散管理装置〔PA(1,2)〕６２０−1−２に、・・・、シェア情報SH(ψ,i,β,L,H(L))は分散管理装置〔PA(L,H(L))〕６２０−Ｌ−Ｈ（Ｌ）に、それぞれ送信される。
【０１８３】
［共有値生成装置の処理］
各共有値生成装置６４０−α(α=1,...,L)（図１９Ａ）は、自らに対応する部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕６２０−α−h(α)（h(α)=1,...,H(α)）で共有する共通情報coefι(0,α), coef(λ,α), coefι(λ,α)を生成する。本形態では、共通情報生成部６４１−αから出力された乱数又は定数を共通情報coefι(0,α), coef(λ,α), coefι(λ,α)とし、送信部６４２−αが共通情報coefι(0,α), coef(λ,α), coefι(λ,α)を、部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕６２０−α−h(α)（h(α)=1,...,H(α)）に送信する。
【０１８４】
共有値生成装置６５０（図１９Ｂ）は、秘密情報SEからSE(α)(α=1,...,L)を生成し、シェア情報share(λ)からshare(λ,α)(α=1,...,L)を生成する。本形態では、共通情報生成部６５２が記憶部６５１に格納された秘密情報SEを用い、以下を満たすSE(1),...,SE(α),...,SE(L)を生成する。
FNC2-1(SE)→SE(1),...,SE(α),...,SE(L)      …(114)
例えば、共通情報生成部６５２は、以下を満たすSE(1),...,SE(α),...,SE(L)を生成する。
SE=SE(1)+...+SE(α)+...+SE(L)          …(115)
本形態では、共通情報生成部６５３が記憶部６５１に格納されたシェア情報share(λ)を用い、以下のようにshare(λ,1),...,share(λ,α),...,share(λ,L)を生成する。
FNC2’-1(share(λ))→share(λ,1),...,share(λ,α),...,share(λ,L)
…(116)
例えば、共通情報生成部６５３は、以下の関係を満たすshare(λ,1),...,share(λ,α),...,share(λ,L)を生成する。
share(λ)=share(λ,1)+...+share(λ,α)+...,share(λ,L)    …(117)
SE(α)及びshare(λ,α)（α=1,...,L,λ=1,...,Ψ）は送信部６５４に送られ、送信部６５４はSE(α)及びshare(λ,α)を、部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕６２０−α−h(α)に送信する。
【０１８５】
［分散管理装置の処理（ステップＳ６２）］
図２５は、第２実施形態の分散管理装置〔PA(α,h(α))〕６２０−α−h(α)（α=1,...,L）の処理を例示するための図である。以下、この図を用いて、本形態の分散管理装置〔PA(α,h(α))〕６２０−α−h(α)の処理を説明する。
まず、分散管理装置〔PA(α,h(α))〕６２０−α−h(α)（図２０）の受信部１２６−α−h(α)が、送信されたシェア情報SH(ψ,i,β,α,h(α))を受信し、それらを記憶部１２２−α−h(α)に格納する（ステップＳ６２０１）。なお、過去にステップステップＳ６２０１の処理が実行され、既にシェア情報SH(ψ,i,β,α,h(α))が分散管理装置〔PA(α,h(α))〕６２０−α−h(α)の記憶部１２２−α−h(α)に格納されているのであれば、ステップＳ６２０１の処理を省略してもよい。
【０１８６】
分散管理装置〔PA(α,h(α))〕６２０−α−h(α)の受信部１２６−α−h(α)は、共有値生成装置６４０−α及び６５０から送信された共通情報coefι(0,α), coef(λ,α), coefι(λ,α)，SE(α)及びshare(λ,α)を受信し、それらを記憶部１２２−α−h(α)に格納する（ステップＳ６２０２）。
【０１８７】
次に、分散秘密値生成部６２１−α−h(α)が、記憶部１２２−α−h(α)からシェア情報SH(0,i,β,α,h(α))と共通情報coefι(0,α),SE(α)を読み込む。分散秘密値生成部６２１−α−h(α)は、これらを用いて式(103)を満たす分散秘密値DSH(0,α,h(α))を生成して出力する（ステップＳ６２０３）。
【０１８８】
次に制御部１２３−α−h(α）がλ=1に設定し、その設定内容を一時記憶部１２１−α−h(α）に格納する（ステップＳ６２０４）。選択部６２４−α−h(α）は、記憶部１２２−α−h(α）に格納されたラベル付き行列LMT(MT,LAB)からラベルLAB(λ)を参照してLAB(λ)=v(λ)→であるか否かを判定する（ステップＳ６２０５）。
【０１８９】
ここで、LAB(λ)=v(λ)→であれば、分散秘密値生成部６２２−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coef(λ,α), coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部６２２−α−h(α)はこれらを用いて式(105)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ６２０６）。一方、LAB(λ)=¬v(λ)→であれば、分散秘密値生成部６２３−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部６２３−α−h(α)は、これらを用いて式(106)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ６２０７）。
【０１９０】
λに対応する分散秘密値DSH(λ,α,h(α))が生成されると、制御部１２３−α−h(α)は、一時記憶部１２１−α−h(α)に格納されたλがΨであるか否かを判定（ステップＳ６２０８）し、λ＝Ψでなければλ+1を新たなλとして（ステップＳ６２０９）、ステップＳ６２０５の処理に移る。一方、λ＝Ψあれば、生成された各分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))（λ=1,...,Ψ）は送信部１２５−α−h（α）に送られる。送信部１２５−α−h（α）は、各分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))をネットワーク１５０経由で取得装置６３０に送信する（ステップＳ６２１０）。
【０１９１】
［取得装置の処理（ステップＳ６３，Ｓ６３’，Ｓ６４，Ｓ６４’）］
図２６は、第２実施形態の取得装置の処理を例示するための図である。
各分散管理装置PA(α,h(α))６３０−α−h(α)(α=1,...,L)から送信された分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))（λ=1,...,Ψ）は、取得装置６３０（図２１）の受信部１３６で受信され、記憶部１３２に格納される（ステップＳ６３０１）。
【０１９２】
次に、制御部１３３が、秘密値の復元に必要な数（以下「必要数」という）以上の分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))が記憶部１３２に格納されたか否かを判定する（ステップＳ６３０２）。ここで、必要数以上の分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))が記憶部１３２に格納されていないと判定された場合には、ステップＳ６３０１の処理に戻る。
【０１９３】
一方、必要数以上の分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))が記憶部１３２に格納されたと判定された場合、制御部１３３が、α=１に設定し、その設定内容を一時記憶部１３１に格納する（ステップＳ６３０３）。次に、記憶部１３２から部分集合SUB(α)に対応する必要数分の分散秘密値DSH(0,α,h(α))（h(α)=1,...,H(α)）が読み出され、各復元部６３４−α（α=1,...,L）に入力される。各復元部６３４−αは、入力された分散秘密値DSH(0,α,h(α))（h(α)=1,...,H(α)）を用い、部分集合SUB(α)ごとの復元処理によって式(107)を満たす秘密復元値SUBSK(0,α)を生成し、当該部分集合SUB(α)(α=1,...,L)ごとの秘密復元値SUBSK(0,α)を出力する（ステップＳ６３０４）。
【０１９４】
次に制御部１３３がλ=1に設定し、その設定内容を一時記憶部１３１に格納する（ステップＳ６３０５）。次に、記憶部１３２から部分集合SUB(α)に対応する必要数分の分散秘密値DSH(λ,α,h(α))（h(α)=1,...,H(α)）が読み出され、各復元部６３６−α（α=1,...,L）に入力される。各復元部６３６−αは、入力された分散秘密値DSH(λ,α,h(α))（h(α)=1,...,H(α)）を用い、部分集合SUB(α)ごとの復元処理によって式(108)又は(109)を満たす秘密復元値SUBSK(λ,α)を生成し、当該部分集合SUB(α)ごとの秘密復元値SUBSK(λ,α)を出力する（ステップＳ６３０６）。
次に、制御部１３３は、一時記憶部１３１に格納されたλがΨであるか否かを判定する（ステップＳ６３０７）。ここで、λ=Ψでないと判定された場合、制御部１３３は、λ+1を新たなλとし、その設定内容を一時記憶部１３１に格納する（ステップＳ６３０８）。ステップＳ６３０８の後、ステップＳ６３０６に戻る。
一方、λ=Ψであると判定された場合、制御部１３３は、一時記憶部１３１に格納されたαがLであるか否かを判定する（ステップＳ６３０９）。ここで、α=Lでないと判定された場合、制御部１３３は、α+1を新たなαとし、その設定内容を一時記憶部１３１に格納する（ステップＳ６３１０）。ステップＳ６３１０の後、ステップＳ６３０４に戻る。
【０１９５】
一方、ステップＳ６３０９でα=Lであると判定された場合、各復元部６３４−α（α=1,...,L）から出力された各秘密復元値SUBSK(0,α)（α=1,...,L）が合成部６３５に送られる。合成部６３５は、各秘密復元値SUBSK(0,α)（α=1,...,L）を用い、以下の鍵情報D*(0)を生成して出力する。
D*(0)=FNC2(SUBSK(0,1),...,(SUBSK(0,α),..., (SUBSK(0,L)）  …(118)
例えば、ψ=0とした式(111)に従って鍵情報D*(0)が生成されて出力される（ステップＳ６３１１）。
【０１９６】
さらに、各復元部６３４−α（α=1,...,L）から出力された各秘密復元値SUBSK(λ,α) （α=1,...,L）が合成部６３７に送られる。合成部６３７は、各秘密復元値SUBSK(λ,α)（α=1,...,L）を用い、以下の鍵情報D*(λ)(λ=1,...,Ψ）を生成して出力する。
D*(λ)=FNC2(SUBSK(λ,1),...,(SUBSK(λ,α),..., (SUBSK(λ,L)）…(119)
例えば、ψ=λ(λ=1,...,Ψ）とした式(111)に従って、鍵情報D*(λ)(λ=1,...,Ψ）が生成されて出力される（ステップＳ６３１２）。
【０１９７】
＜第２実施形態の変形例１＞
第２実施形態の変形例１は、第２実施形態に第１実施形態の変形例１を適用したものである。すなわち、第２実施形態の変形例１での基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下のDSH(0,α,h(α))をψ=0に対応する分散秘密値として生成する（FNC1）。
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
…(120)
さらに、本形態の各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下の式(121)又は(122)に従って、以下のDSH(λ,α,h(α))(λ=1,...,Ψ)を各λに対応する分散秘密値として生成する（FNC1’）。
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))      …(121)
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))      …(122)
その他は第２実施形態と同様である。
【０１９８】
第２実施形態の変形例１の秘密分散システム７は、分散装置６１０が分散装置７１０に置換され、分散管理装置６２０−α−ｈ（α）（α=1,...,L）が分散管理装置７２０−α−ｈ（α）（α=1,...,L）に置換される。その他の構成は、第６実施形態と同様である。
第２実施形態の変形例１では、ステップＳ６１０４の代わりに、記憶部１１２から情報θ(ψ,i,β)・g2∈G2(i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ)+ζ(ψ))がそれぞれ読み出され、秘密分散部７１４−α（α=1,...,L）（図２７）に入力される。秘密分散部７１４−αは、各情報θ(ψ,i,β)・g2∈G2を秘密分散し、情報θ(ψ,i,β)・g2∈G2ごとに、部分集合SUB(α)に対する以下のH(α)個のシェア情報を生成して出力する。
SH(ψ,i,β,α,1),...,SH(ψ,i,β,α,H(α))      …(123)
各情報θ(ψ,i,β)・g2∈G2の秘密分散方法は第１実施形態と同様である。すなわち、本形態では、第１実施形態の秘密分散方法のθ・gをθ(ψ,i,β)・g2に置換した秘密分散方法が実行される。例えば、以下のようなシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))が生成される。
SH(ψ,i,β,α,h(α))=(φ(h(α)), f(α,φ(h(α))))・g2∈G2
ただし、f(α,ω)=θ(ψ,i,β)を満たし、ω∈Fqは予め定められた有限体Fqの元である（ステップＳ７１０４）。
【０１９９】
第２実施形態の変形例１では、第２実施形態のステップＳ６２０３の代わりに、分散秘密値生成部７２１−α−h(α)が、記憶部１２２−α−h(α)からシェア情報SH(0,i,β,α,h(α))と共通情報coefι(0,α),SE(α)を読み込む。分散秘密値生成部７２１−α−h(α)は、これらを用いて式(120)を満たす分散秘密値DSH(0,α,h(α))を生成して出力する（ステップＳ７２０３）。
【０２００】
第２実施形態の変形例１では、第２実施形態のステップＳ６２０６の代わりに、分散秘密値生成部７２２−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coef(λ,α), coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部６２２−α−h(α)は、これらを用いて式(121)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ７２０６）。さらに、第２実施形態のステップＳ６２０７の代わりに、分散秘密値生成部７２３−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部６２３−α−h(α)は、これらを用いて式(122)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ７２０７）。
【０２０１】
＜第２実施形態の変形例２＞
その他、第２実施形態やその変形例１において、秘密分散方法や復元方法を例えば第１実施形態やその変形例３のように変形してもよい。
【０２０２】
〔その他の変形例等〕
本発明は上述の各実施の形態に限定されるものではない。例えば、上述の有限体Fq上で定義された各演算を位数qの有限環Zq上で定義された演算に置換してもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置換する方法の一例は、素数やそのべき乗値以外のqを許容する方法である。また、第２実施形態では生成情報として関数暗号の鍵情報を生成する処理を例示したが、それ以外の生成情報が生成されてもよい。
【０２０３】
上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０２０４】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２０５】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０２０６】
上述の各実施形態では、コンピュータ上で所定のプログラムが実行され、各装置の処理内容が実現されたが、これらの処理内容の少なくとも一部がハードウェアのみによって実現されてもよい。
【符号の説明】
【０２０７】
１〜７  秘密分散システム
１１０，２１０，４１０，５１０，６１０，７１０  分散装置
１２０〜７２０  分散管理装置
１３０，３３０，４３０，５３０，６３０  取得装置
１４０，６４０，６５０  共有値生成装置
【図１】
2012011565.tif 000020
【図２】
2012011565.tif 000021
【図３】
2012011565.tif 000022
【図４】
2012011565.tif 000023
【図５】
2012011565.tif 000024
【図６】
2012011565.tif 000025
【図７】
2012011565.tif 000026
【図８】
2012011565.tif 000027
【図９】
2012011565.tif 000028
【図１０】
2012011565.tif 000029
【図１１】
2012011565.tif 000030
【図１２】
2012011565.tif 000031
【図１３】
2012011565.tif 000032
【図１４】
2012011565.tif 000033
【図１５】
2012011565.tif 000034
【図１６】
2012011565.tif 000035
【図１７】
2012011565.tif 000036
【図１８】
2012011565.tif 000037
【図１９】
2012011565.tif 000038
【図２０】
2012011565.tif 000039
【図２１】
2012011565.tif 000040
【図２２】
2012011565.tif 000041
【図２３】
2012011565.tif 000042
【図２４】
2012011565.tif 000043
【図２５】
2012011565.tif 000044
【図２６】
2012011565.tif 000045
【図２７】
2012011565.tif 000046
【図２８】
2012011565.tif 000047
【手続補正書】
【提出日】平成24年10月26日(2012.10.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
なお、シェア情報SH1,...,SHNから秘密情報MSKを復元するための演算MSK=SH1+...+SHNは線形である。そのため、各シェア情報SH(1),...,SH(N)と値σとを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(1),...,SH'(N)として復元処理を行った場合、秘密情報MSKと値σとを被演算子として当該線形演算CALCを行った結果が得られる。例えば、SH'(1)=σ・SH(1),..,SH'(N)=σ・SH(N)を各シェア情報SH'(1),...,SH'(N)として復元処理が実行された場合、以下の値が得られる。
σ・SH(1)+...+σ・SH(N)
=σ・(SH(1)+ ...+SH(N))
=σ・MSK                              …(1) 
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００３７
【補正方法】変更
【補正の内容】
【００３７】
次に、取得装置１３０は、各部分集合SUB(α)についてそれぞれ生成された秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力する（ステップＳ１４）。なお、本形態では、取得装置１３０が秘密復元値SUBSK(α)を線形結合して生成情報SKを生成する。 
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】００３９
【補正方法】変更
【補正の内容】
【００３９】
《ステップＳ１１２の詳細》
本形態の秘密分散部１１４−αは、各部分集合SUB(α)に対し、(R(α)，H(α))しきい値秘密分散方式（但し、R(α)は、2≦R(α)＜H(α)を満たす定数）を用い、秘密情報を秘密分散して得られるシェア情報SH(α,h(α))(h(α)=1,...,H(α))を生成する。
図８Ｂに例示するように、まず、秘密分散部１１４−α（図５Ａ）の関数選択部１１４ａ−αが、予め定められた有限体Fqの元ω∈Fqに対してf(α,ω)=θを満たすR(α)-1次の多項式をf(α,x)∈Fqをランダムに選択して出力する（ステップＳ１１２ａ）。なお、xは有限体Fqの元からなる変数であり、元ω∈Fqの一例は0Fである。
次に、インデックス生成部１１４ｂ−αが、各h(α)=1,...,H(α)に対応するインデックスφ(h(α))∈Fqを生成して出力する(ステップＳ１１２b)。なお、インデックスφ(h(α))=h(α)∈Fqとする場合や、すでにインデックスφ(h(α))∈Fqが得られている場合には、ステップＳ１１２ｂの処理は省略されてもよい。
次に、分散処理部１１４ｃ−αが、多項式f(α,x)∈Fqとインデックスφ(h(α))∈Fqとを用い、以下のシェア情報SH(α,h(α))(h(α)=1,...,H(α))を生成する。
SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g∈G)       …(5)
分散処理部１１４ｃ−αはシェア情報SH(α,h(α))を出力する（ステップＳ１１２ｃ／《ステップＳ１１２の詳細》の説明終わり）。 
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００５４
【補正方法】変更
【補正の内容】
【００５４】
《ステップＳ１３４の詳細》
本形態の分散秘密値DSH(α,h(α))は式(7)に示すものである。復元部１３４−α（図６）には、αごとにR(α)個ずつの相違なる分散秘密値DSH(α,h(α))が入力される。以下では、復元部１３４−αに入力される各αに対応する分散秘密値DSH(α,h(α))を以下のように表現する。
DSH(α,φ1(α))=(φ1(α), dsh1(α))
・・・                              …(8)
DSH(α,φR(α)(α))=(φR(α)(α), dshＲ(α)(α))
ただし、以下が満たされる。
(φ1(α),...,φR(α)(α))⊂(φ(1),...,φ(H(α)))       …(9)
(dsh1(α),...,dshＲ(α)(α))⊂(dsh(α,φ(1)),...,dsh(α,φ(H(α))))   …(10)
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１０１
【補正方法】変更
【補正の内容】
【０１０１】
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(ψ)+ζ(ψ)次元のベクトル空間を表す。 
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１３０
【補正方法】変更
【補正の内容】
【０１３０】
図１６は、命題変数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,3)しきい値秘密分散方式で秘密分散された各シェア情報SE,SE,SEに応じた値がそれぞれ対応する。ノードN2の子ノードN3,N4,N5には、シェア情報SEに応じた値が(2,3)しきい値秘密分散方式で秘密分散された各シェア情報(1,f(1)),(2,f(2)),(3,f(3))に応じた値がそれぞれ対応する。ノードN7の子ノードN8,N11には、シェア情報SEに応じた値が(2,2)しきい値秘密分散方式で秘密分散された各シェア情報SH4,SE-SH4に応じた値がそれぞれ対応する。ノードN8の子ノードN9,N10には、シェア情報SH4に応じた値が(1,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に応じた値が復元される。 
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１６６
【補正方法】変更
【補正の内容】
【０１６６】
＜共有値生成装置６４０−α，６５０＞
図１９Ａに例示するように、本形態の共有値生成装置６４０−αは、係数設定部６４１−αと送信部６４２−αとを有する。図１９Ｂに例示するように、本形態の共有値生成装置６５０は記憶部６５１と共通情報生成部６５２，６５３と送信部６５４とを有する。 
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０１７４
【補正方法】変更
【補正の内容】
【０１７４】
さらに、本形態の各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下の式(104)-(106)のように各λ(λ=1,...,Ψ)に対応する分散秘密値DSH(λ,α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)を生成する（FNC1’）。
SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))
…(104)
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2      …(105)
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2      …(106)
各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）から出力された各分散秘密値DSH(ψ,α,h(α))は、それぞれ、ネットワーク１５０経由で取得装置６３０に送信される（ステップＳ６２及びＳ６２’）。 
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０１７５
【補正方法】変更
【補正の内容】
【０１７５】
取得装置６３０は、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(ψ,α,h(α))を用い、前述したステップＳ６１及びＳ６１’の秘密分散方式に従った部分集合SUB(α)ごとの復元処理によって、当該部分集合SUB(α)ごとの秘密復元値SUBSK(ψ,α)(ψ=0,...,Ψ, α=1,...,L)を生成する。
本形態の取得装置６３０は、例えば、以下のSUBSK(0,α)をψ=0に対応する秘密復元値とする。
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)      …(107)
本形態の取得装置６３０は、例えば、以下の式(108)又は(109)を各λ=1,...,Ψに対応する秘密復元値SUBSK(λ,α)とする。
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)      …(108)
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)                …(109)
これらの処理は、分散秘密値DSH(ψ,α,h(α))の各次元（次数）に対して第１実施形態で示した復元処置を実行することで実現できる。すなわち、各分散秘密値DSH(ψ,α,h(α))はベクトルであるが、それらの各次元（次数）に対して第１実施形態で示した復元処理（ステップＳ１３４）をそれぞれ実行することで上述の復元処理が実現できる。例えば、この復元処理に利用されるベクトルである分散秘密値DSH(ψ,α,h(α))のι次元目の要素を以下のように表現する。
(φ1(α), dsh1(α))
・・・
(φR(α)(α), dshＲ(α)(α))
この場合に式(11)の演算が行われて各係数λρ(x)(ρ=1,...,R(α))が得られ、以下の計算が行われることでψに対応する秘密復元値SUBSK(ψ,α)のι次元目が得られる。
λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)
よって、各ψ及びιに対してそれぞれ同様な処理を行うことで秘密復元値SUBSK(ψ,α)が得られる（ステップＳ６３及びＳ６３’）。 
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０１７６
【補正方法】変更
【補正の内容】
【０１７６】
取得装置６３０は、各部分集合SUB(α)についてそれぞれ生成された秘密復元値SUBSK(ψ,α)(ψ=0,...,Ψ, α=1,...,L)を用いて生成情報D*(ψ)(ψ=0,...,Ψ)を生成し、当該生成情報D*(ψ)を出力する（D*(ψ)=FNC2(SUBSK(ψ,1),...,(SUBSK(ψ,α),..., (SUBSK(ψ,L))）。
例えば、取得装置６３０は、秘密復元値SUBSK(ψ,α)を線形結合して生成情報D*(ψ)を生成する。例えば、以下の式(110-1)（110-2）を満たすように秘密分散されていたのであれば、取得装置６３０は、以下の式(111)に従ってD*(ψ)(ψ=0,...,Ψ)を生成する（ステップＳ６４及びＳ６４’）。
FNC2(SUBSK(0,1),...,(SUBSK(0,α),..., (SUBSK(0,L)))
=SUBSK(0,1)+...+SUBSK(0,α)+...+SUBSK(0,L)    …(110-1)
FNC2’(SUBSK(λ,1),...,(SUBSK(λ,α),..., (SUBSK(λ,L)))
=SUBSK(λ,1)+...+SUBSK(λ,α)+...+SUBSK(λ,L)    …(110-2)
D*(ψ)=SUBSK(ψ,1)+...+SUBSK(ψ,α)+...+SUBSK(ψ,L)      …(111) 
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０１７８
【補正方法】変更
【補正の内容】
【０１７８】
次に、制御部１１３は、一時記憶部１１１に格納されたβがn(ψ)+ζ(ψ)であるか否かを判定する（ステップＳ６１０５）。ここで、β=n(ψ)+ζ(ψ)でないと判定された場合、制御部１１３は、β+1を新たなβとし、その設定内容を一時記憶部１１１に格納する（ステップＳ６１０６）。ステップＳ６１０６の後、ステップＳ６１０４に戻る。 
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０１８４
【補正方法】変更
【補正の内容】
【０１８４】
共有値生成装置６５０（図１９Ｂ）は、秘密情報SEからSE(α)(α=1,...,L)を生成し、シェア情報share(λ)からshare(λ,α)(α=1,...,L)を生成する。本形態では、共通情報生成部６５２が記憶部６５１に格納された秘密情報SEを用い、以下を満たすSE(1),...,SE(α),...,SE(L)を生成する。
FNC2-1(SE)→SE(1),...,SE(α),...,SE(L)          …(114)
例えば、共通情報生成部６５２は、以下を満たすSE(1),...,SE(α),...,SE(L)を生成する。
SE=SE(1)+...+SE(α)+...+SE(L)          …(115)
本形態では、共通情報生成部６５３が記憶部６５１に格納されたシェア情報share(λ)を用い、以下のようにshare(λ,1),...,share(λ,α),...,share(λ,L)を生成する。
FNC2’-1(share(λ))→share(λ,1),...,share(λ,α),...,share(λ,L)  …(116)
例えば、共通情報生成部６５３は、以下の関係を満たすshare(λ,1),...,share(λ,α),...,share(λ,L)を生成する。
share(λ)=share(λ,1)+...+share(λ,α)+...+share(λ,L)      …(117)
SE(α)及びshare(λ,α)（α=1,...,L,λ=1,...,Ψ）は送信部６５４に送られ、送信部６５４はSE(α)及びshare(λ,α)を、部分集合SUB(α)を構成する各分散管理装置〔PA(α,h(α))〕６２０−α−h(α)に送信する。 
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０１９１
【補正方法】変更
【補正の内容】
【０１９１】
［取得装置の処理（ステップＳ６３，Ｓ６３’，Ｓ６４，Ｓ６４’）］
図２６は、第２実施形態の取得装置の処理を例示するための図である。
各分散管理装置PA(α,h(α))６２０−α−h(α)(α=1,...,L)から送信された分散秘密値DSH(0,α,h(α)),DSH(λ,α,h(α))（λ=1,...,Ψ）は、取得装置６３０（図２１）の受信部１３６で受信され、記憶部１３２に格納される（ステップＳ６３０１）。 
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０１９５
【補正方法】変更
【補正の内容】
【０１９５】
一方、ステップＳ６３０９でα=Lであると判定された場合、各復元部６３４−α（α=1,...,L）から出力された各秘密復元値SUBSK(0,α)（α=1,...,L）が合成部６３５に送られる。合成部６３５は、各秘密復元値SUBSK(0,α)（α=1,...,L）を用い、以下の鍵情報D*(0)を生成して出力する。
D*(0)=FNC2(SUBSK(0,1),...,SUBSK(0,α),...,SUBSK(0,L)）      …(118)
例えば、ψ=0とした式(111)に従って鍵情報D*(0)が生成されて出力される（ステップＳ６３１１）。 
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０１９６
【補正方法】変更
【補正の内容】
【０１９６】
さらに、各復元部６３４−α（α=1,...,L）から出力された各秘密復元値SUBSK(λ,α) （α=1,...,L）が合成部６３７に送られる。合成部６３７は、各秘密復元値SUBSK(λ,α)（α=1,...,L）を用い、以下の鍵情報D*(λ)(λ=1,...,Ψ）を生成して出力する。
D*(λ)=FNC2(SUBSK(λ,1),...,SUBSK(λ,α),...,SUBSK(λ,L)）      …(119)
例えば、ψ=λ(λ=1,...,Ψ）とした式(111)に従って、鍵情報D*(λ)(λ=1,...,Ψ）が生成されて出力される（ステップＳ６３１２）。 
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０１９７
【補正方法】変更
【補正の内容】
【０１９７】
＜第２実施形態の変形例１＞
第２実施形態の変形例１は、第２実施形態に第１実施形態の変形例１を適用したものである。すなわち、第２実施形態の変形例１での基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下のDSH(0,α,h(α))をψ=0に対応する分散秘密値として生成する（FNC1）。
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
…(120)
さらに、本形態の各分散管理装置〔PA(α,h(α))〕６２０−α−h（α）は、例えば、以下の式(121)又は(122)に従って、以下のDSH(λ,α,h(α))(λ=1,...,Ψ)を各λに対応する分散秘密値として生成する（FNC1’）。
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))      …(121)
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))      …(122)  
その他は第２実施形態と同様である。 
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０１９８
【補正方法】変更
【補正の内容】
【０１９８】
第２実施形態の変形例１の秘密分散システム７は、分散装置６１０が分散装置７１０に置換され、分散管理装置６２０−α−ｈ（α）（α=1,...,L）が分散管理装置７２０−α−ｈ（α）（α=1,...,L）に置換される。その他の構成は、第２実施形態と同様である。
第２実施形態の変形例１では、ステップＳ６１０４の代わりに、記憶部１１２から情報θ(ψ,i,β)・g2∈G2(i=1,...,n(ψ)+ζ(ψ),β=1,...,n(ψ)+ζ(ψ))がそれぞれ読み出され、秘密分散部７１４−α（α=1,...,L）（図２７）に入力される。秘密分散部７１４−αは、各情報θ(ψ,i,β)・g2∈G2を秘密分散し、情報θ(ψ,i,β)・g2∈G2ごとに、部分集合SUB(α)に対する以下のH(α)個のシェア情報を生成して出力する。
SH(ψ,i,β,α,1),...,SH(ψ,i,β,α,H(α))      …(123)
各情報θ(ψ,i,β)・g2∈G2の秘密分散方法は第１実施形態と同様である。すなわち、本形態では、第１実施形態の秘密分散方法のθ・gをθ(ψ,i,β)・g2に置換した秘密分散方法が実行される。例えば、以下のようなシェア情報SH(ψ,i,β,α,h(α))(h(α)=1,...,H(α))が生成される。
SH(ψ,i,β,α,h(α))=(φ(h(α)), f(α,φ(h(α))))・g2∈G2
ただし、f(α,ω)=θ(ψ,i,β)を満たし、ω∈Fqは予め定められた有限体Fqの元である（ステップＳ７１０４）。 
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０２００
【補正方法】変更
【補正の内容】
【０２００】
第２実施形態の変形例１では、第２実施形態のステップＳ６２０６の代わりに、分散秘密値生成部７２２−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coef(λ,α), coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部７２２−α−h(α)は、これらを用いて式(121)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ７２０６）。さらに、第２実施形態のステップＳ６２０７の代わりに、分散秘密値生成部７２３−α−h(α)が記憶部１２２−α−h(α)から、シェア情報SH(λ,i,β,α,h(α))と共通情報coefι(λ,α),share(α)とラベルLAB(λ)によって特定されるn(λ)次元ベクトルv(λ)→とを読み込む。分散秘密値生成部７２３−α−h(α)は、これらを用いて式(122)を満たす分散秘密値DSH(λ,α,h(α))を生成して出力する（ステップＳ７２０７）。 
【手続補正１９】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項９
【補正方法】変更
【補正の内容】
【請求項９】
請求項１から８の何れかの秘密分散システムであって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記分散秘密値生成部は、
SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α))
とし、Iを2以上n(0)+ζ(0)以下の定数とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))・g2
をψ=0に対応する前記分散秘密値として生成し、さらに、
SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
を各λに対応する前記分散秘密値として生成する、
秘密分散システム。 
【手続補正２０】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１０
【補正方法】変更
【補正の内容】
【請求項１０】
請求項１から８の何れかの秘密分散システムであって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記分散秘密値生成部は、
SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α))
とし、Iを2以上n(0)+ζ(0)以下の定数とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
をψ=0に対応する前記分散秘密値として生成し、さらに、
SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
を各λに対応する前記分散秘密値として生成する、秘密分散システム。
【手続補正２１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１１
【補正方法】変更
【補正の内容】
【請求項１１】
請求項９の秘密分散システムであって、
前記復元部は、
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成し、
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成する、秘密分散システム。 
【手続補正２２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１２
【補正方法】変更
【補正の内容】
【請求項１２】
請求項１０の秘密分散システムであって、
前記復元部は、
SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成し、
SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成する、秘密分散システム。 
【手続補正２３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２４
【補正方法】変更
【補正の内容】
【請求項２４】
請求項１６から２３の何れかの秘密分散方法であって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記ステップ(B)は、
(B-1)  SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α))
とし、Iを2以上n(0)+ζ(0)以下の定数とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))・g2+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))・g2
をψ=0に対応する前記分散秘密値として生成するステップと、
(B-2)  SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))・g2
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))・g2
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))・g2
を各λに対応する前記分散秘密値として生成するステップと、を含む、
秘密分散方法。
【手続補正２４】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２５
【補正方法】変更
【補正の内容】
【請求項２５】
請求項１６から２３の何れかの秘密分散方法であって、
前記基底ベクトルbi*(ψ)の各要素θ(ψ,i,β)・g2に応じた値はθ(ψ,i,β)・g2であり、
前記共通情報は、λを1以上Ψ以下の整数λ=1,...,Ψとした場合における、coefι(0,α), coef(λ,α), coefι(λ,α), SE(α), share(λ,α)を含み、
前記ステップ(B)は、
(B-1)  SHbi*(0,α,h(α))=(SH(0,i,1,α,h(α)),...,SH(0,i,I,α,h(α))
とし、Iを2以上n(0)+ζ(0)以下の定数とした場合における、
DSH(0,α,h(α))
=-SE(α)・SHb1*(0,α,h(α))+Σι=2Icoefι(0,α)・SHbι*(0,α,h(α))
をψ=0に対応する前記分散秘密値として生成するステップと、
(B-2)  SHbi*(λ,α,h(α))=(SH(λ,i,1,α,h(α)),...,SH(λ,i,n(λ)+ζ(λ),α,h(α))
とし、v(λ)→=(v1(λ),...,vn(λ)(λ))をn(λ)次元ベクトルとした場合における、
DSH(λ,α,h(α))
=(share(λ,α)+coef(λ,α)・v1(λ))・SHb1*(λ,α,h(α))
+Σι=2n(λ)coef(λ,α)・vι(λ)・SHbι*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
又は、
DSH(λ,α,h(α))
=share(λ,α)・Σι=1n(λ)vι(λ)・SHb1*(λ,α,h(α))
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・SHbι*(λ,α,h(α))
を各λに対応する前記分散秘密値として生成するステップと、を含む、
秘密分散方法。 
【手続補正２５】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２６
【補正方法】変更
【補正の内容】
【請求項２６】
請求項２４の秘密分散方法であって、
前記ステップ(C)は、
(C-1)  SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成するステップと、
(C-2)  SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成するステップと、を含む、
秘密分散方法。 
【手続補正２６】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項２７
【補正方法】変更
【補正の内容】
【請求項２７】
請求項２５の秘密分散方法であって、
前記ステップ(C)は、
(C-1)  SUBSK(0,α)=-SE(α)・b1*(0)+Σι=2Icoefι(0,α)・bι*(0)
をψ=0に対応する前記秘密復元値として生成するステップと、
(C-2)  SUBSK(λ,α)=(share(λ,α)+coef(λ,α)・v1(λ))・b1*(λ)
+Σι=2n(λ)coef(λ,α)・vι(λ)・bι*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
又は、
SUBSK(λ,α)=share(λ,α)・Σι=1n(λ)vι(λ)・b1*(λ)
+Σι=n(λ)+1n(λ)+ζ(λ)coefι(λ,α)・bι*(λ)
を各λに対応する前記秘密復元値として生成するステップと、を含む、
秘密分散方法。
【国際調査報告】
2012011565.tif 000048
2012011565.tif 000049
2012011565.tif 000050
2012011565.tif 000051