(57)【特許請求の範囲】
【請求項１】
分散装置と、Σα=1Lh(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)と、取得装置と、を有し、
前記分散装置は、
或る秘密分散方式を用い、H(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に秘密情報を秘密分散してシェア情報SH(α,h(α))を生成し、当該シェア情報SH(α,h(α))を出力するように構成された秘密分散部を含み、
前記分散管理装置PA(α,h(α))は、
前記部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報と、前記シェア情報SH(α,h(α))とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力するように構成された分散秘密値生成部を含み、
同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ用いる前記共通情報は互いに同一であり、
同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ行う前記共通演算は互いに同一であり、
前記取得装置は、
同一の前記部分集合SUB(α)に対応する複数の前記分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの前記秘密復元値SUBSK(α)を得るように構成され、前記復元処理が前記秘密分散方式に従った処理である、復元部と、
前記秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力するように構成された合成部と、を含み、
前記秘密情報は、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとした場合における、当該基底ベクトルbi*の集合(b1*,...,bn+ζ*)であり、
前記秘密分散部は、各基底ベクトルbi*の要素θ(i,β)・g∈Gをそれぞれ前記部分集合SUB(α)ごとに独立に秘密分散したシェア情報SH(i,β,α,h(α))∈Gを生成するように構成され、前記シェア情報SH(α,h(α))は、前記シェア情報SH(i,β,α,h(α))∈G (i = 1, ..., n + z, b = 1, ..., n + z)の集合であり、
前記分散秘密値生成部は、前記シェア情報SH(i,β,α,h(α)) (i = 1, ..., n + z, b = 1, ..., n + z)と前記共有値σ(α)と前記有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)とを用い、前記分散秘密値DSH(α,h(α))を生成し、前記分散秘密値DSH(α,h(α))は、n+ζ個のシェア情報SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))を要素とするn+ζ次元のシェア基底ベクトルSHbi*(α,h(α))=(SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))∈Gn+ζに対する、DSH(α,h(α))=σ(α)・{Σμ=1nwμ・SHbμ*(α,h(α))}+Σμ=n+1n+ζSHbμ*(α,h(α))∈Gn+ζであり、
前記秘密復元値SUBSK(α)は、SUBSK(α)=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζである、秘密分散システム。
【請求項２】
請求項１の秘密分散システムであって、
前記合成部は、前記生成情報SK={(σ(1)+...+σ(L))/L}・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*を算出するように構成される、秘密分散システム。
【請求項３】
秘密情報を入力とし、H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に前記秘密情報を秘密分散してシェア情報SH(α,h(α))を生成し、当該シェア情報SH(α,h(α))を出力するように構成された秘密分散部を有し、
前記秘密情報は、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとした場合における、当該基底ベクトルbi*の集合(b1*,...,bn+ζ*)であり、
前記秘密分散部は、各基底ベクトルbi*の要素θ(i,β)・g∈Gをそれぞれ前記部分集合SUB(α)ごとに独立に秘密分散したシェア情報SH(i,β,α,h(α))∈Gを生成するように構成され、前記シェア情報SH(α,h(α))は、前記シェア情報SH(i,β,α,h(α))∈G (i=1,...,n+z, b=1,...,n+z)の集合である、分散装置。
【請求項４】
H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報と、前記部分集合SUB(α)ごとに独立に秘密情報を秘密分散して得られたシェア情報SH(α,h(α))とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力するように構成された分散秘密値生成部を有し、
同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ用いる前記共通情報は互いに同一であり、
同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ行う前記共通演算は互いに同一であり、 
前記提供情報は、有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)であり、
前記分散秘密値生成部は、前記シェア情報SH(i,β,α,h(α))と前記共有値σ(α)と有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)とを用い、前記分散秘密値DSH(α,h(α))を生成し、前記分散秘密値DSH(α,h(α))は、n+ζ個（ζ≧1）のシェア情報SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))を要素とするn+ζ次元のシェア基底ベクトルSHbi*(α,h(α))=(SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))∈Gn+ζに対する、DSH(α,h(α))=σ(α)・{Σμ=1nwμ・SHbμ*(α,h(α))}+Σμ=n+1n+ζSHbμ*(α,h(α))∈Gn+ζである、分散管理装置。
【請求項５】
H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合をSUB(α)とした場合における、同一の前記部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、当該部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの前記秘密復元値SUBSK(α)を得るように構成され、前記復元処理が或る秘密分散方式に従った処理である、復元部と、
前記秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力するように構成された合成部と、有し、
前記秘密復元値SUBSK(α)は、前記部分集合SUB(α)ごとに共有される共有値をσ(α)とし、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとし、有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルをw→=(w1,...,wn)とした場合における、SUBSK(α)=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζである、取得装置。
【請求項６】
請求項５の取得装置であって、
前記合成部は、前記生成情報SK={(σ(1)+...+σ(L))/L}・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*を算出するように構成される、取得装置。
【請求項７】
(a) 分散装置において、或る秘密分散方式を用い、Σα=1L h(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)からなる集合に属するH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に秘密情報を秘密分散してシェア情報SH(α,h(α))を生成し、当該シェア情報SH(α,h(α))を出力するステップと、
(b) 前記分散管理装置PA(α,h(α))において、前記シェア情報SH(α,h(α))と、前記部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力するステップと、
(c) 取得装置において、同一の前記部分集合SUB(α)に対応する複数の前記分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの前記秘密復元値SUBSK(α)を得、前記復元処理が前記秘密分散方式に従った処理である、ステップと、
(d) 前記取得装置において、前記秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力するステップと、を有し、
前記ステップ(b)において、同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ用いる前記共通情報は互いに同一であり、同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ行う前記共通演算は互いに同一であり、
前記秘密情報は、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとした場合における、当該基底ベクトルbi*の集合(b1*,...,bn+ζ*)であり、
前記ステップ（ａ）は、各基底ベクトルbi*の要素θ(i,β)・g∈Gをそれぞれ前記部分集合SUB(α)ごとに独立に秘密分散したシェア情報SH(i,β,α,h(α))∈Gを生成するステップであり、
前記シェア情報SH(α,h(α))は、前記シェア情報SH(i,β,α,h(α))∈G (i=1,...,n+z, b=1,...,n+z)の集合であり、
前記ステップ（ｂ）は、前記シェア情報SH(i,β,α,h(α)) (i = 1, ..., n + z, b = 1, ..., n + z)と前記共有値σ(α)と前記有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)とを用い、前記分散秘密値DSH(α,h(α))を生成するステップであり、
前記分散秘密値DSH(α,h(α))は、n+ζ個のシェア情報SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))を要素とするn+ζ次元のシェア基底ベクトルSHbi*(α,h(α))=(SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))∈Gn+ζに対する、DSH(α,h(α))=σ(α)・{Σμ=1nwμ・SHbμ*(α,h(α))}+Σμ=n+1n+ζSHbμ*(α,h(α))∈Gn+ζであり、
前記秘密復元値SUBSK(α)は、SUBSK(α)=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζである、秘密分散方法。
【請求項８】
分散装置の処理方法であって、
（ａ）秘密情報が分散装置に入力されるステップと、
（ｂ）前記分散装置の第１手段において、H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に前記秘密情報を秘密分散してシェア情報SH(α,h(α))を生成するステップと、
（ｃ）前記分散装置の第２手段において、前記シェア情報SH(α,h(α))を出力するステップと、を有し、
前記秘密情報は、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとした場合における、当該基底ベクトルbi*の集合(b1*,...,bn+ζ*)であり、
前記ステップ（ｂ）は、各基底ベクトルbi*の要素θ(i,β)・g∈Gをそれぞれ前記部分集合SUB(α)ごとに独立に秘密分散したシェア情報SH(i,β,α,h(α))∈Gを生成するステップであり、
前記シェア情報SH(α,h(α))は、前記シェア情報SH(i,β,α,h(α))∈G (i = 1, ..., n + z, b = 1, ..., n + z)の集合である、処理方法。
【請求項９】
分散管理装置の処理方法であって、
（ａ）前記分散管理装置の第１手段において、H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報と、前記部分集合SUB(α)ごとに独立に秘密情報を秘密分散して得られたシェア情報SH(α,h(α))とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成するステップと、
（ｂ）前記分散管理装置の第２手段において、前記分散秘密値DSH(α,h(α))を出力するステップと、を有し、
同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ用いる前記共通情報は互いに同一であり、同一の前記部分集合SUB(α)に属する前記分散管理装置PA(α,h(α))がそれぞれ行う前記共通演算は互いに同一であり、
前記提供情報は、有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)であり、
前記ステップ（ｂ）は、前記シェア情報SH(i,β,α,h(α))と前記共有値σ(α)と有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)とを用い、前記分散秘密値DSH(α,h(α))を生成するステップであり、
前記分散秘密値DSH(α,h(α))は、n+ζ個（ζ≧1）のシェア情報SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))を要素とするn+ζ次元のシェア基底ベクトルSHbi*(α,h(α))=(SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))∈Gn+ζに対する、DSH(α,h(α))=σ(α)・{Σμ=1nwμ・SHbμ*(α,h(α))}+Σμ=n+1n+ζSHbμ*(α,h(α))∈Gn+ζである、処理方法。
【請求項１０】
取得装置の処理方法であって、
前記取得装置の第１手段において、H(α)(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合をSUB(α)とした場合における、同一の前記部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、当該部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの前記秘密復元値SUBSK(α)を得、前記復元処理が或る秘密分散方式に従った処理である、ステップと、
前記取得装置の第２手段において、前記秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力するステップと、
を有し、
前記秘密復元値SUBSK(α)は、前記部分集合SUB(α)ごとに共有される共有値をσ(α)とし、巡回群Gの生成元をgとし、θ(i,β)(i=1,...,n+ζ, β=1,...,n+ζ, n≧1, ζ≧1)を有限体Fqの元とし、前記巡回群Gのn+ζ個の元を要素とするn+ζ次元の基底ベクトルをbi*=(θ(i,1)・g,...,θ(i,n+ζ)・g)∈Gn+ζとし、有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルをw→=(w1,...,wn)とした場合における、SUBSK(α)=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζである、処理方法。
【請求項１１】
請求項３の分散装置としてコンピュータを機能させるためのプログラム。
【請求項１２】
請求項４の分散管理装置としてコンピュータを機能させるためのプログラム。
【請求項１３】
請求項５の取得装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散技術に関する。
【背景技術】
【０００２】
秘密情報を保管する場合、秘密情報の紛失や破壊のリスクと盗難のリスクとがある。紛失や破壊のリスクは秘密情報を複数保管しておくことで低減できる。しかし、この場合には盗難のリスクが増加する。これらのリスクを共に解決する方法の一つとして、秘密分散法（SSS: Secret Sharing Scheme）がある（例えば、非特許文献１，２参照）。
【０００３】
秘密分散法とは、秘密情報MSKから複数のシェア情報SH(1),...,SH(N)を生成し、これらを複数の分散管理装置PA(1),...,PA(N)に分散して管理させ、これらのシェア情報SH(1),...,SH(N)のうち所定数以上のシェア情報を得ることができた場合にのみ、秘密情報MSKが復元できる方式である。以下に、秘密分散法の代表的な方式を示す。
【０００４】
〔(N,N)しきい値秘密分散法〕
(N,N)しきい値秘密分散法は、すべてのシェア情報SH(1),...,SH(N)が与えられれば秘密情報MSKを復元できるが、任意のN-1個のシェア情報SH(φ1),...,SH(φN-1)が与えられても秘密情報MSKの情報はまったく得られない方式である。以下に、その一例を示す。
・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)
が得られる。
【０００７】
〔(K,N)しきい値秘密分散法〕
(K,N)しきい値秘密分散法は、任意の相違なるK個のシェア情報SH(φ1),...,SH(φK)が与えられれば秘密情報MSKを復元できるが、任意のK-1個のシェア情報SH(φ1),...,SH(φK-1)が与えられても秘密情報MSKの情報はまったく得られない方式である。以下にその一例を示す。
・f(0)=MSKを満たすK-1次の多項式f(x)=ξ0+ξ1・x+ξ2・x2+...+ξK-1・xK-1をランダムに選ぶ。すなわち、ξ0=MSKとし、ξ1,..., ξK-1をランダムに選ぶ。シェア情報をSHρ=(ρ, f(ρ))（ρ=1,...,N）とする。
・任意の相違なるK個のシェア情報SH(φ1),...,SH(φK)（(φ1,...,φK)⊂(1,...,N)）が得られた場合、例えば、ラグランジェ(Lagrange)の補間公式を用い、以下のような復元処理によって秘密情報MSKを復元できる。
MSK=f(0)=λ1・f(φ1)+...+λK・f(φK)            …(3)
【数１】
0005562475.tif 000002
は先頭からρ番目の被演算子〔分母の要素(φρ-φρ)、分子の要素(x-φρ)〕が存在しないことを意味する。すなわち、式(4)の分母は、
(φρ-φ1)・...・(φρ-φρ-1)・(φρ-φρ+1)・...・(φρ-φK)
であり、式(4)の分子は
(x-φ1)・...・(x-φρ-1)・(x-φρ+1)・...・(x-φK)
である。これらの関係は体上でも成立する。
【０００８】
また、式(3)の演算は線形である。そのため、各シェア情報SH(φ1),...,SH(φK)と値σとを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(φ1),...,SH'(φK)として復元された値は、秘密情報MSKと値σとを被演算子として線形演算CALCを行った結果と等しくなる。一方、各シェア情報SH(φ1),...,SH(φK)と、互いに独立な値σ(φ1),...,σ(φK)とを被演算子とし、シェア情報ごとに同一の線形演算CALCを行った結果を各シェア情報SH'(φ1),...,SH'(φK)として復元処理が実行された場合には、通常、秘密情報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と任意な値σとを被演算子に含む演算の結果と同一の生成情報SKを得ることができる。
【００１１】
しかし、このような方式を実現することは容易ではない。すなわち、各分散管理装置PA(1),...,PA(N)がそれぞれ互いに独立な値σ(1),...,σ(N)を用いて演算を実行したのでは、取得装置は各分散管理装置の演算結果をシェア情報とした復元処理によって生成情報SKを生成することができない。一方、値σは生成情報SKを推測するための情報となり得るため、すべての分散管理装置PA(1),...,PA(N)が値σそのものを共有することは、安全性の観点から好ましくない。
【００１２】
本発明はこのような点に鑑みてなされたものであり、上記条件１〜３を満たす方式を安全に実現することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では、まず、分散装置において、Σα=1Lh(α)個の分散管理装置PA(α,h(α))(α=1,...,L, L≧2, h(α)=1,...,H(α), H(α)≧2)からなる集合に属するH(α)個の分散管理装置PA(α,1),...,PA(α,H(α))からなる部分集合SUB(α)ごとに独立に秘密情報を秘密分散してシェア情報SH(α,h(α))を生成し、当該シェア情報SH(α,h(α))を出力する。次に、分散管理装置PA(α,h(α))において、部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報と、シェア情報SH(α,h(α))とを用い、共通演算を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力する。なお、同一の前記部分集合SUB(α)に属する分散管理装置PA(α,h(α))の分散秘密値生成部がそれぞれ用いる共通情報は互いに同一であり、同一の部分集合SUB(α)に属する分散管理装置PA(α,h(α))の分散秘密値生成部がそれぞれ行う共通演算は互いに同一である。
【００１４】
次に、取得装置において、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの秘密復元値SUBSK(α)を出力する。そして、取得装置において、秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力する。
【００１５】
ここで、本発明では、部分集合SUB(α)ごとに独立に秘密情報を秘密分散し、部分集合SUB(α)ごとに共有される共有値σ(α)を含む共通情報を用い、分散秘密値DSH(α,h(α))を生成する。この場合、部分集合SUB(α)ごとの復元処理によって得られる秘密復元値SUBSK(α)は、秘密情報と共有値σ(α)を含む共通情報とを被演算子に含む演算の結果と同一となる。よって、復元後の秘密復元値SUBSK(α)を用いて生成される生成情報SKは、秘密情報と任意の値σとを被演算子に含む演算の結果と同一となる。また、本発明では、すべての分散管理装置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方程式
y2+a1・x・y+a3・y=x3+a2・x2+a4・x+a6
（ただし、a1,a2,a3,a4,a6∈Fq）を満たすx,y∈Fqからなる点(x,y)の集合に無限遠点と呼ばれる特別な点Ｏを付加したもので定義される。楕円曲線Ｅ上の任意の２点に対して楕円加算と呼ばれる二項演算＋及び楕円曲線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(α))を生成し、当該シェア情報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（α）に共通の提供情報wとを含む。また、同一の部分集合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(α))を生成する。
【００４３】
図８Ｂに例示するように、まず、秘密分散部１１４−α（図５Ａ）の関数選択部１１４ａ−αが、予め定められた有限体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(α)), f(α,φ(h(α)))・g∈G)      …(5)
を生成して出力する（ステップＳ１１２ｃ／《ステップＳ１１２の詳細》の説明終わり）。
【００４６】
次に、制御部１１３は、一時記憶部１１１に格納されたαがLであるか否かを判定する（ステップＳ１１３）。ここで、α=Lでないと判定された場合、制御部１１３は、α+1を新たなαとし、その設定内容を一時記憶部１１１に格納し（ステップＳ１１４）、新たなαによってステップＳ１１２の処理を実行させる。一方、ステップＳ１１３でα=Lであると判定された場合、各秘密分散部１１４−αから出力された各シェア情報SH(α,h(α))が送信部１１５に送られる。送信部１１５は、各シェア情報SH(α,h(α))を、それぞれ、ネットワーク１５０経由で分散管理装置〔PA(α,h(α))〕１２０−α−h(α)に送信する（ステップＳ１１５）。すなわち、シェア情報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(α)に格納する（ステップＳ１２２）。
【００５０】
また、本形態では、取得装置１３０（図４）の記憶部１３２から読み出された提供情報wが送信部１３５からネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕１２０−α−h(α)に送信される。この提供情報wは、すべての分散管理装置PA(α,h(α))１２０−α−h（α）に共通である。提供情報wは、分散管理装置〔PA(α,h(α))〕１２０−α−h(α)（図３Ａ）の受信部１２６−α−h(α)で受信され、記憶部１２２−α−h(α)に格納される（ステップＳ１２３）。
【００５１】
次に、分散秘密値生成部１２４−α−h(α)が、記憶部１２２−α−h(α)からシェア情報SH(α,h(α))と共有値σ(α)と提供情報wとを読み込む。分散秘密値生成部１２４−α−h(α)は、共有値σ(α)と提供情報wとを含む共通情報と、シェア情報SH(α,h(α))とを用い、共通演算FNC1を行って分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力する（ステップＳ１２４）。
【００５２】
《ステップＳ１２４の詳細》
同一の部分集合SUB(α)に属する分散管理装置PA(α,h(α))１２０−α−h(α)の分散秘密値生成部１２４−α−h(α)がそれぞれ用いる共通情報は互いに同一であり、同一の部分集合SUB(α)に属する分散管理装置PA(α,h(α))１２０−α−h(α)の分散秘密値生成部１２４−α−h(α)がそれぞれ行う共通演算は互いに同一である。また、本形態のシェア情報は式(5)に示すものである。
【００５３】
図９Ｂに例示するように、まず、本形態の分散秘密値生成部１２４−α−h(α)の線形演算部１２４ａ−α−h（α）に、共有値σ(α)と提供情報wとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g)のf(α,φ(h(α)))・gとが入力される。線形演算部１２４ａ−α−h（α）は、
dsh(α,φ(h(α)))=σ(α)・w・f(α,φ(h(α)))・g∈G       …(6)
の演算を行い、その演算結果dsh(α,φ(h(α)))を出力する（ステップＳ１２４ａ）。
出力された演算結果dsh(α,φ(h(α)))は、分散秘密値合成部１２４ｂ−α−h（α）に入力される。分散秘密値合成部１２４ｂ−α−h（α）には、さらにシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α)))・g)のインデックスφ(h(α))が入力され、分散秘密値合成部１２４ｂ−α−h（α）は、
DSH(α,h(α))=(φ(h(α)),dsh(α,φ(h(α))))       …(7)
の演算によって分散秘密値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(α),dsh(α,φ1(α)))
・・・                              …(8)
DSH(α,φR(α)(α))=(φR(α)(α),dsh(α,φR(α)(α))
ただし、
(φ1(α),...,φR(α)(α))⊂(φ(1),...,φ(H(α)))       …(9)
(dsh1(α),...,dshＲ(α)(α))⊂(dsh(α,φ(1)),...,dsh(α,φ(H(α))))  …(10)
である。
【００５９】
まず、図１０Ｂに例示するように、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))の各インデックスφ1(α),...,φR(α)(α)が係数算出部１３４ａ−αに入力され、係数算出部１３４ａ−αは、各ρ=1,...,R(α)について、それぞれ、
【数２】
0005562475.tif 000003
の演算を行い、各係数λρ(x)(ρ=1,...,R(α))を生成して出力する（ステップＳ１３４ａ）。
【００６０】
次に、生成された各係数λρ(x)と、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))のdsh1(α),...,dshＲ(α)(α)とが、多項式演算部１３４ｂ−αに入力される。多項式演算部１３４ｂ−αは、
SUBSK(α)=λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)∈G    …(12)
の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する（ステップＳ１３４ｂ／《ステップＳ１３４の詳細》の説明終わり）。
【００６１】
次に、制御部１３３は、一時記憶部１３１に格納されたαがLであるか否かを判定する（ステップＳ１３５）。ここで、α=Lでないと判定された場合、制御部１３３は、α+1を新たなαとし、その設定内容を一時記憶部１３１に格納し（ステップＳ１３６）、新たなαによってステップＳ１３４の処理を実行させる。
【００６２】
一方、ステップＳ１３５でα=Lであると判定された場合、各復元部１３４−αから出力された各秘密復元値SUBSK(α)が合成部１３７に送られる。合成部１３７は、各部分集合SUB(α)についてそれぞれ生成された各秘密復元値SUBSK(α)を用いて生成情報
SK=FNC2(SUBSK(1),...,SUBSK(L))           …(13)
を生成し、当該生成情報SKを出力する（ステップＳ１４１）。
【００６３】
《ステップＳ１４１の詳細》
以下に式(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(α)が、共有値σ(α)と提供情報wを含む共通情報とシェア情報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（α）の構成を説明するための図である。なお、これらの図において、第１実施形態と共通する部分については、第１実施形態と同じ符号を付した。
【００７０】
第１実施形態の変形例１では、図５Ａの秘密分散部１１４−αが秘密分散部２１４−αに置換され、図５Ｂの分散秘密値生成部１２４−α−h（α）が分散秘密値生成部２２４−α−h（α）に置換される。その他の構成は、第１実施形態と同様である。
【００７１】
《第１実施形態の変形例１におけるステップＳ１１２の変形》
第１実施形態の変形例１では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、図８Ｂに示したステップＳ１１２ａ及びＳ１１２ｂが実行される。次に、ステップＳ１１２ｃの代わりに、秘密分散部２１４−αの分散処理部２１４ｃ−α（図１１Ａ）が、多項式f(α,x)∈Fqとインデックスφ(h(α))∈Fqとを用い、シェア情報
SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))       …(16)
を生成して出力する（《第１実施形態の変形例１におけるステップＳ１１２の変形》の説明終わり）。
【００７２】
《第１実施形態の変形例１におけるステップＳ１２４の変形》
第１実施形態の変形例１では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、ステップＳ１２４ａの代わりに、線形演算部２２４ａ−α−h（α）（図１１Ｂ）に、共有値σ(α)と提供情報wとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))のf(α,φ(h(α)))とが入力され、線形演算部２２４ａ−α−h（α）は、
dsh(α,φ(h(α)))=σ(α)・w・f(α,φ(h(α)))・g∈G       …(17)
の演算を行い、その演算結果dsh(α,φ(h(α)))∈Gを出力する。演算結果dsh(α,φ(h(α)))∈Gは分散秘密値DSH(α,h(α))の一部の情報となる。その後、図９Ｂに示したステップＳ１２４ｂの処理を実行する（《第１実施形態の変形例１におけるステップＳ１２４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００７３】
〔第１実施形態の変形例２〕
次に、第１実施形態の変形例２を説明する。
第１実施形態の変形例２でも有限体Fqの元θ∈Fqを秘密分散する。第１実施形態の変形例１との相違点は、演算結果dsh(α,φ(h(α)))が巡回群Gの元ではなく、有限体Fqの元である点である。
【００７４】
図１２Ａは、第１実施形態における変形例２の分散秘密値生成部３２４−α−h（α）の構成を説明するための図であり、図１２Ｂは、第１実施形態における変形例２の復元部３３４−αの構成を説明するための図である。なお、これらの図において、第１実施形態と共通する部分については、第１実施形態と同じ符号を付した。
【００７５】
第１実施形態の変形例２では、図５Ｂの分散秘密値生成部１２４−α−h（α）が分散秘密値生成部３２４−α−h（α）に置換され、図６の復元部１３４−αが復元部３３４−αに置換される。また、第１実施形態の変形例１と同様、図５Ａの分散処理部１１４ｃ−αが分散処理部２１４ｃ−αに置換される。その他の構成は、第１実施形態と同様である。
【００７６】
《第１実施形態の変形例２におけるステップＳ１１２の変形》
第１実施形態の変形例１におけるステップＳ１１２の変形と同一である。
【００７７】
《第１実施形態の変形例２におけるステップＳ１２４の変形》
第１実施形態の変形例２では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、ステップＳ１２４ａの代わりに、線形演算部３２４ａ−α−h（α）（図１２Ａ）に、共有値σ(α)と提供情報wとシェア情報SH(α,h(α))=(φ(h(α)), f(α,φ(h(α))))のf(α,φ(h(α)))とが入力され、線形演算部３２４ａ−α−h（α）が、
dsh(α,φ(h(α)))=σ(α)・w・f(α,φ(h(α)))∈Fq       …(18)
の演算を行い、その演算結果dsh(α,φ(h(α)))∈Fqを出力する。演算結果dsh(α,φ(h(α)))∈Fqは分散秘密値DSH(α,h(α))の一部の情報となる。その後、図９Ｂに示したステップＳ１２４ｂの処理を実行する。
【００７８】
《第１実施形態の変形例２におけるステップＳ１３４の変形》
まず、図１０Ｂに示したステップＳ１３４ａの処理が実行される。次に、１０Ｂに示したステップＳ１３４ｂの処理の代わりに、各係数λρ(x)と、式(8)に示すDSH(α,φ1(α)),...,DSH(α,φR(α)(α))のdsh1(α),...,dshＲ(α)(α)とが、多項式演算部３３４ｂ−α（図１２Ｂ）に入力され、多項式演算部３３４ｂ−αが、
SUBSK(α)={λ1(ω)・dsh1(α)+...+λR(α)(ω)・dshＲ(α)(α)}・g∈G   …(19)
の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する（《第１実施形態の変形例２におけるステップＳ１３４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００７９】
〔第１実施形態の変形例３〕
第１実施形態の変形例３は、(R(α)，H(α))しきい値秘密分散法の代わりに(H(α)，H(α))しきい値秘密分散法を用いて秘密情報を秘密分散する変形例である。
図１３Ａは、第１実施形態における変形例３の秘密分散部４１４−αの構成を説明するための図であり、図１３Ｂは、第１実施形態における変形例３の分散秘密値生成部４２４−α−h（α）の構成を説明するための図であり、図１３Ｃは、第１実施形態における変形例３の復元部４３４−αの構成を説明するための図である。
【００８０】
第１実施形態の変形例３では、図５Ａの秘密分散部１１４−αが秘密分散部４１４−αに置換され、図５Ｂの分散秘密値生成部１２４−α−h（α）が分散秘密値生成部４２４−α−h（α）に置換され、図６の復元部１３４−αが復元部４３４−αに置換される。その他の構成は、第１実施形態と同様である。
【００８１】
《第１実施形態の変形例３におけるステップＳ１１２の変形》
第１実施形態の変形例３では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、秘密分散部４１４−α（図１３Ａ）の乱数生成部４１４ａ−αにおいて、H(α)-1個の巡回群Gの元
SH(α,1),...,SH(α,H(α)-1)∈G       …(20)
をランダムに選択し、これらを出力する。
【００８２】
次に、逆元演算部４１４ｂ−αに、秘密情報θ・g∈Gと、H(α)-1個の巡回群Gの元SH(α,1),...,SH(α,H(α)-1)∈Gとが入力される。逆元演算部４１４ｂ−αは、
SH(α,h(α))=θ・g -{SH(α,1)+...+SH(α,H(α)-1)}∈G       …(21)
の演算によって、SH(α,h(α))を生成して出力する。
そして、秘密分散部４１４−αは、
SH(α,1),...,SH(α,H(α))∈G
を部分集合SUB(α)のシェア情報として出力する。これらのシェア情報は、
SH(α,1)+SH(α,2)+...+SH(α,H(α))=θ・g∈G       …(22)
を満たす（《第１実施形態の変形例３におけるステップＳ１１２の変形》の説明終わり）。
【００８３】
《第１実施形態の変形例３におけるステップＳ１２４の変形》
第１実施形態の変形例３では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、分散秘密値生成部４２４−α−h(α)（図１３Ｂ）に、共有値σ(α)と提供情報wとシェア情報SH(α,1),...,SH(α,H(α))とが入力される。分散秘密値生成部４２４−α−h(α)は、
DSH(α,h(α))=σ(α)・w・SH(α,h(α))∈G       …(23)
の演算によって、分散秘密値DSH(α,h(α))を生成して出力する（《第１実施形態の変形例３におけるステップＳ１２４の変形》の説明終わり）。
【００８４】
《第１実施形態の変形例３におけるステップＳ１３２の変形》
第１実施形態の変形例３では、図１０Ａに示したステップＳ１３２の処理が以下のように変形される。
この変形例３でも、制御部１３３が、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かを判定するが、変形例３での「必要数」はH(α)個である。つまり、この変形例３の場合、各α=1,...,Lについて、それぞれ、すべての分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かが判定される。
【００８５】
《第１実施形態の変形例３におけるステップＳ１３４の変形》
第１実施形態の変形例３では、図１０Ｂに示したステップＳ１３４の処理が以下のように変形される。
この変形例３の分散秘密値DSH(α,h(α))は式(23)に示すものである。また、復元部４３４−α（図１３Ｃ）には、αに対応するすべての分散秘密値DSH(α,h(α))（h(α)=1,...,H(α)）が入力される。そして、復元部４３４−αは、
SUBSK(α)=DSH(α,1)+...+DSH(α,H(α))∈G       …(24)
の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する（《第１実施形態の変形例３におけるステップＳ１３４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００８６】
〔第１実施形態の変形例４〕
第１実施形態の変形例４も、(R(α)，H(α))しきい値秘密分散法の代わりに(H(α)，H(α))しきい値秘密分散法を用いて秘密情報を秘密分散する変形例である。変形例３との相違点は、有限体Fqの元である秘密情報θ∈Fqを秘密分散する点である。
【００８７】
図１４Ａは、第１実施形態における変形例４の秘密分散部５１４−αの構成を説明するための図であり、図１４Ｂは、第１実施形態における変形例４の分散秘密値生成部５２４−α−h（α）の構成を説明するための図であり、図１４Ｃは、第１実施形態における変形例４の復元部５３４−αの構成を説明するための図である。
【００８８】
第１実施形態の変形例４では、図５Ａの秘密分散部１１４−αが秘密分散部５１４−αに置換され、図５Ｂの分散秘密値生成部１２４−α−h（α）が分散秘密値生成部５２４−α−h（α）に置換され、図６の復元部１３４−αが復元部５３４−αに置換される。その他の構成は、第１実施形態と同様である。
【００８９】
《第１実施形態の変形例４におけるステップＳ１１２の変形》
第１実施形態の変形例４では、図８Ｂに示したステップＳ１１２の処理が以下のように変形される。
まず、秘密分散部５１４−α（図１４Ａ）の乱数生成部５１４ａ−αにおいて、H(α)-1個の有限体Fqの元
SH(α,1),...,SH(α,H(α)-1)∈Fq       …(25)
をランダムに選択し、これらを出力する。
【００９０】
次に、逆元演算部５１４ｂ−αに、秘密情報θ∈Fqと、H(α)-1個の有限体Fqの元
SH(α,1),...,SH(α,H(α)-1)∈Fqとが入力される。逆元演算部５１４ｂ−αは、
SH(α,h(α))=θ -{SH(α,1)+...+SH(α,H(α)-1)}∈Fq       …(26)
の演算によって、SH(α,h(α))を生成して出力する。
【００９１】
そして、秘密分散部５１４−αは、
SH(α,1),...,SH(α,H(α))∈Fq       …(27)
を部分集合SUB(α)のシェア情報として出力する。これらのシェア情報は、
SH(α,1)+SH(α,2)+...+SH(α,H(α))=θ∈Fq       …(28)
を満たす（《第１実施形態の変形例４におけるステップＳ１１２の変形》の説明終わり）。
【００９２】
《第１実施形態の変形例４におけるステップＳ１２４の変形》
第１実施形態の変形例４では、図９Ｂに示したステップＳ１２４の処理が以下のように変形される。
まず、分散秘密値生成部５２４−α−h(α)（図１４Ｂ）に、共有値σ(α)と提供情報wとシェア情報SH(α,1),...,SH(α,H(α))とが入力される。分散秘密値生成部５２４−α−h(α)は、
DSH(α,h(α))=σ(α)・w・SH(α,h(α))∈Fq       …(29)
の演算によって、分散秘密値DSH(α,h(α))を生成して出力する（《第１実施形態の変形例４におけるステップＳ１２４の変形》の説明終わり）。
【００９３】
《第１実施形態の変形例４におけるステップＳ１３２の変形》
第１実施形態の変形例３と同じである。
【００９４】
《第１実施形態の変形例４におけるステップＳ１３４の変形》
第１実施形態の変形例４では、図１０Ｂに示したステップＳ１３４の処理が以下のように変形される。
この変形例４の分散秘密値DSH(α,h(α))は式(29)に示すものである。また、復元部５３４−α（図１４Ｃ）には、αに対応するすべての分散秘密値DSH(α,h(α))（h(α)=1,...,H(α)）が入力される。そして、復元部５３４−αは、
SUBSK(α)={DSH(α,1)+...+DSH(α,H(α))}・g∈G       …(30)
の演算によって、部分集合SUB(α)の秘密復元値SUBSK(α)を生成して出力する（《第１実施形態の変形例４におけるステップＳ１３４の変形》の説明終わり）。その他の処理は、第１実施形態と同様である。
【００９５】
〔第１実施形態のその他の変形例〕
その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、第１実施形態の変形例４の式(29)の代わりに
DSH(α,h(α))=σ(α)・w・SH(α,h(α))∈Fq       …(31)
の演算を行い、式(30)の代わりに式(24)の演算を行ってもよい。また、秘密復元値SUBSK(α)が有限体Fqの元となる構成であってもよい。
【００９６】
また、本形態では、各部分集合SUB(α)に対してそれぞれ同一の秘密分散法を用いて秘密分散を行ったが、互いに異なる各部分集合SUBに対して互いに異なる秘密分散法を用いてもよい。
【００９７】
また、本形態では、各部分集合SUB(α)ごとに共有値生成装置１４０−αを設けたが、各部分集合SUB(α)の何れかの分散管理装置が共有値生成装置の機能を持っていてもよい。この場合には、共有値生成装置１４０−αは不要となる。
【００９８】
また、本形態では、共有値σ(α)と提供情報wとを含む共通情報と、シェア情報SH(α,h(α))とを用い、共通演算FNC1を行って分散秘密値DSH(α,h(α))を生成することとした。しかし、提供情報wを用いることなく、共有値σ(α)を共通情報として分散秘密値DSH(α,h(α))を生成してもよい。また、共通情報が、共有値σ(α)と提供情報wとその他の情報とを含むこととしてもよい。
【００９９】
また、分散秘密値DSH(α,h(α))を求めるための共通演算は、部分集合SUB(α)ごとに統一する必要はあるが、必ずしも、互いに異なる部分集合SUB(α)間で同一の共通演算を行う必要はない。
【０１００】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は第１実施形態を内積述語暗号の鍵生成に応用した形態である。
〔定義〕
まず、本形態で使用する用語や記号を定義する。
行列：「行列」とは演算が定義された集合の元を矩形に並べたものを表す。環の元を要素とするものだけではなく、群の元を要素とするものも「行列」と表現する。
(・)T：(・)Tは・の転置行列を表す。
(・)-1：(・)-1は・の逆行列を表す。
∧：∧は論理積を表す。
∨：∨は論理和を表す。
Ｚ：Ｚは整数集合を表す。
ｋ：ｋはセキュリティパラメータ（k∈Z, k>0）を表す。
【０１０１】
Fq：Fqは位数qの有限体を表す。位数qは１以上の整数であり、例えば、素数や素数のべき乗値を位数qとする。すなわち、有限体Fqの例は素体やそれを基礎体とした拡大体である。
0F：0Fは有限体Fqの加法単位元を表す。
1F：1Fは有限体Fqの乗法単位元を表す。
【０１０２】
δ(i,j)：δ(i,j)はクロネッカーのデルタ関数を表す。i=jの場合にδ(i,j)=1Fを満たし、i≠jの場合にδ(i,j)=0 Fを満たす。
【０１０３】
E：Eは有限体Fq上で定義された楕円曲線を表す。
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に対するχ・Ω∈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で定義された演算を行うことを意味する。
【０１０５】
n：nは1以上の整数を表す。
ζ：ζは1以上の整数を表す。ζの一例は２又は３である。
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は以下の性質を満たす。
［双線形性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζ及びν，κ∈Fqについて以下の関係を満たす。
e(ν・Γ1,κ・Γ2)=e(Γ1,Γ2)ν・κ          …(33)
［非退化性］すべてのΓ1∈G1n+ζ，Γ2∈G2n+ζを巡回群GTの単位元に写す関数ではない。
［計算可能性］あらゆる
Γ1∈G1n+ζ，Γ2∈G2n+ζ          …(34)
についてe(Γ1,Γ2)を効率的に計算するアルゴリズムが存在する。
【０１０９】
本形態では、巡回群G1と巡回群G2との直積G1×G2を巡回群GTに写す非退化な双線形写像を計算するための関数
Pair:G1×G2→GT            …(35)
を用いて双線形関数eを構成する。本形態の双線形関数eは、巡回群G1のn+ζ個の元γβ (β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1,...,γn+ζ)と、巡回群G2のn+ζ個の元γβ*(β=1,...,n+ζ)からなるn+ζ次元ベクトル(γ1*,...,γn+ζ*)との入力に対し、巡回群GTの１個の元
e=Πβ=1n+ζPair(γβ, γβ*)          …(36)
を出力する関数である。
【０１１０】
なお、双線形関数Pairは、巡回群G1の１個の元と巡回群G2の１個の元との組を入力とし、巡回群GTの１個の元を出力する関数であり、以下の性質を満たす。
［双線形性］すべてのΩ1∈G1，Ω2∈G2及びν，κ∈Fqについて以下の関係を満たす。
Pair(ν・Ω1,κ・Ω2)=Pair(Ω1,Ω2)ν・κ          …(37)
［非退化性］すべての
Ω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個の要素を巡回群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+ζ)：巡回群G2のn+ζ個の元を要素とするn+ζ次元の基底ベクトルを表す。基底ベクトルai*の一例は、κ2・g2∈G2をi次元目の要素とし、残りのn個の要素を巡回群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τ
を満たす。一方、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：基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai(i=1,...,n+ζ)が式(39)によって表現される場合、行列Aは、
【数３】
0005562475.tif 000004
となる。
【０１１９】
A*：基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。例えば、基底ベクトルai*(i=1,...,n+ζ)が式(40)によって表現される場合、行列A*は、
【数４】
0005562475.tif 000005
となる。
【０１２０】
X：有限体Fqの元を要素とするn+ζ行n+ζ列の行列を表す。基底ベクトルaiの座標変換に用いられる。行列Ｘのi行j列(i=1,...,n+ζ,j=1,...,n+ζ)の要素をχi,j∈Fqとすると、行列Xは、
【数５】
0005562475.tif 000006
となる。なお、行列Ｘの各要素χi,jを変換係数と呼ぶ。
【０１２１】
X *：X *は行列Xの逆行列の転置行列Ｘ*=(Ｘ-1)Tを表す。基底ベクトルai*の座標変換に用いられる。行列X*のi行j列の要素をχi,j*∈Fqとすると、行列Ｘ*は、
【数６】
0005562475.tif 000007
となる。なお、行列Ｘ*の各要素χi,j*を変換係数と呼ぶ。
【０１２２】
この場合、n+ζ行n+ζ列の単位行列をIとするとＸ・(Ｘ*)T=Ｉを満たす。すなわち、単位行列
【数７】
0005562475.tif 000008
に対し、
【数８】
0005562475.tif 000009
を満たす。ここで、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+ζ次元の基底ベクトルを表す。行列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+ζ次元の基底ベクトルを表す。行列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)の関係から、
【数９】
0005562475.tif 000010
を満たす。特に、τ=κ1・κ2=1Fである場合（例えば、κ1=κ2=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は、
【数１０】
0005562475.tif 000011
となる。
【０１２８】
B*：B*は基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列を表す。B*=X*・A*を満たす。例えば、基底ベクトルbi*(i=1,...,n+ζ)が式(55)によって表現される場合、行列B*は、
【数１１】
0005562475.tif 000012
となる。
【０１２９】
w→：w→は有限体Fqの元を要素とするn次元ベクトルを表す。
w→=(w1,...,wn)∈Fqn           …(60)
wμ：wμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
v→：v→は有限体Fqの元を要素とするn次元ベクトルを表す。
v→=(v1,...,vn)∈Fqn           …(61)
vμ：vμはn次元ベクトルのμ(μ=1,...,n)番目の要素を表す。
【０１３０】
〔内積述語暗号〕
次に、内積述語暗号の基本的な構成について説明する。
＜述語暗号＞
述語暗号（「関数暗号」と呼ぶ場合もある）とは、「属性情報」と呼ばれる情報と「述語情報」と呼ばれる情報との組み合わせが所定の論理式を「真」にする場合に暗号文が復号できる方式である。「属性情報」と「述語情報」の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。従来の述語暗号の構成は、例えば、参考文献８「"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」等に開示されている。
【０１３１】
＜内積述語暗号＞
内積述語暗号は、属性情報や述語情報としてベクトルを用い、それらの内積が０となる場合に暗号文が復号される述語暗号である。内積述語暗号では、内積が０となることと論理式が「真」となることとが等価である。
【０１３２】
［論理式と多項式との関係］
内積述語暗号では、論理和や論理積からなる論理式を多項式で表現する。
まず、「xがη1である」という命題１と「xがη2である」という命題２との論理和 (x=η1)∨(x=η2)を
(x-η1)・(x-η2)          …(62)
という多項式で表現する。すると、各真理値と式(62)の関数値との関係は以下のようになる。
【表１】
0005562475.tif 000013
【０１３３】
[表1]から分かるように、論理和(x=η1)∨(x=η2)が真である場合、式(62)の関数値は0になり、論理和(x=η1)∨(x=η2)が偽である場合、式(62)の関数値は0以外の値となる。すなわち、論理和(x=η1)∨(x=η2)が真であることと、式(62)の関数値が0となることとは等価である。よって、論理和は式(62)で表現できる。
【０１３４】
また、「xがη1である」という命題１と「xがη2である」という命題２との論理積 (x=η1)∧(x=η2)を
ι1・(x-η1)+ι2・(x-η2)          …(63)
という多項式で表現する。ただし、ι1及びι2は乱数である。すると、真理値と式(63)の関数値とは以下の関係となる。
【表２】
0005562475.tif 000014
【０１３５】
[表２]から分かるように、論理積 (x=η1)∧(x=η2)が真である場合、式(63)の関数値は0になり、論理積 (x=η1)∧(x=η2)が偽である場合、式(63)の関数値は0以外の値となる。すなわち、論理積 (x=η1)∧(x=η2)が真であることと、式(63)の関数値が0となることとは等価である。よって、論理積は式(63)で表現できる。
【０１３６】
以上のように、式(62)と式(63)とを用いることで論理和や論理積からなる論理式を多項式f(x)で表現できる。例えば、論理式{(x=η1)∨(x=η2)∨(x=η3)}∧(x=η4)∧(x=η5)は、多項式
f(x)=ι1・{(x-η1)・(x-η2)・(x-η3)}+ι2・(x-η4)+ι3・(x-η5)    …(64)
で表現できる。
【０１３７】
なお、式(62）では、１つの不定元xを用いて論理和を表現したが、複数の不定元を用いて論理和を表現することも可能である。例えば、２つの不定元x0及びx1を用い、「x0がη0である」という命題１と「x1がη1である」という命題２との論理和 (x0=η0)∨(x1=η1)を
(x0-η0)・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理和を多項式で表現することも可能である。
【０１３８】
また、式(63）では、１つの不定元xを用いて論理積を表現したが、複数の不定元を用いて論理積を表現することも可能である。例えば、また、「x0がη0である」という命題１と「x1がη1である」という命題２との論理積 (x0=η0)∧(x1=η1)を
ι0・(x0-η0)+ι1・(x1-η1)
という多項式で表現することも可能であり、３つ以上の不定元を用い、論理積を多項式で表現することも可能である。
【０１３９】
論理和及び／又は論理積を含む論理式をH(H≧1)種類の不定元x0,...,xH-1を用いて表現した多項式をf(x0,...,xH-1)と表現する。また、各不定元x0,...,xH-1に対応する命題を「xhがηhである」とする。ただし、ηh（h=0,...H-1）は命題ごとに定まる定数である。この場合、当該論理式を示す多項式f(x0,...,xH-1)は、不定元xhと定数ηhとの差をとる多項式によって当該不定元xhが当該定数ηhであるという命題を表現し、命題をそれぞれ表現する多項式の積によって当該命題の論理和を表現し、命題又は命題の論理和をそれぞれ表現する多項式の線形和によって当該命題又は命題の論理和の論理積を表現し、それによって論理式を表現した多項式となる。例えば、５つの不定元x0,...,x4を用い、論理式{(x0=η0)∨(x1=η1)∨(x2=η2)}∧(x3=η3)∧(x4=η4)を多項式で表現すると、
f(x0,...,x4)=ι0・{(x0-η0)・(x1-η1)・(x2-η2)}+ι1・(x3-η3)+ι2・(x4-η4)
となる。
【０１４０】
［多項式と内積の関係］
論理式を示す多項式f(x0,...,xH-1)は、２つのn次元ベクトルの内積で表現できる。すなわち、多項式f(x0,...,xH-1)は、当該多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトル
v→=(v1,...,vn)
と、当該多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
w→=(w1,...,wn)
との内積
f(x0,...,xH-1)=w→・v→
に等しい。すなわち、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルv→と、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトルw→との内積が0であるか否かとは等価である。
f(x0,...,xH-1)=0  ←→  w→・v→=0
【０１４１】
例えば、１つの不定元xで表現された多項式f(x)=θ0・x0+θ1・x+...+θn-1・xn-1は、２つのn次元ベクトル
w→=(w1,...,wn)=(θ0,...,θn-1)          …(65)
v→=(v1,...,vn)=(x0,...,xn-1)          …(66)
の内積
f(x)= w→・v→          …(67)
で表現できる。すなわち、論理式を示す多項式f(x)が0であるか否かと、式(67)の内積が0であるか否かとは等価である。
f(x)=0  ←→  w→・v→=0          …(68)
【０１４２】
また、多項式f(x0,...,xH-1)の各項の不定元成分を各要素とするベクトルを
w→=(w1,...,wn)
とし、多項式f(x0,...,xH-1)の各項の係数成分を各要素とするベクトル
v→=(v1,...,vn)
としても、論理式を示す多項式f(x0,...,xH-1)が0であるか否かと、ベクトルw→とベクトルv→との内積が0であるか否かとは等価である。
【０１４３】
例えば、式(65)(66)の代わりに
w→=(w1,...,wn)=(x0,...,xn-1)        …(69)
v→=(v1,...,vn)=(θ1,...,θn-1)          …(70)
としても、論理式を示す多項式f(x)が0であるか否かと、式(67)の内積が0であるか否かとは等価である。
【０１４４】
内積述語暗号では、ベクトルv→=(v0,...,vn-1)及びw→=(w0,...,wn-1)の何れか一方を属性情報とし、他方を述語情報とし、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。例えば、n次元ベクトル(θ0,...,θn-1)が述語情報とされ、n次元ベクトル(x0,...,xn-1)が属性情報とされ、属性情報と述語情報の一方が暗号文に埋め込まれ、他方が鍵情報に埋め込まれる。なお、以下では、鍵情報に埋め込まれるn次元ベクトルをw→=(w1,...,wn)とし、暗号文に埋め込まれるn次元ベクトルをv→=(v1,...,vn)とする。例えば、
述語情報：w→=(w1,...,wn)=(θ0,...,θn-1)
属性情報：v→=(v1,...,vn)=(x0,...,xn-1)
であるか、
述語情報：v→=(v1,...,vn)=(θ0,...,θn-1)
属性情報：w→=(w1,...,wn)=(x0,...,xn-1)
である。
【０１４５】
［内積述語暗号の基本構成］
以下では、内積述語暗号を用いて鍵カプセル化メカニズムKEM (Key Encapsulation Mechanisms)を構成する場合の基本構成を例示する。この構成はSetup(1k)，GenKey(MSK,w→)，Enc(PA,v→)，Dec(SKw,C2)を含む。
《Setup(1k)：セットアップ》
−入力：セキュリティパラメータk
−出力：マスター鍵情報MSK，公開パラメータPK
Setup(1k)の一例では、まず、セキュリティパラメータkをnとして、n+ζ次元の基底ベクトルai(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列Aと、基底ベクトルai*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列A*と、座標変換のためのn+ζ行n+ζ列の行列X，X*とが選択される。次に、式(52)に従って座標変換されたn+ζ次元の基底ベクトルbi(i=1,...,n+ζ)が算出され、式(54)に従って座標変換されたn+ζ次元の基底ベクトルbi*(i=1,...,n+ζ)が算出される。そして、基底ベクトルbi*(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B*がマスター鍵情報MSKとして出力され、ベクトル空間V, V*、基底ベクトルbi(i=1,...,n+ζ)を要素とするn+ζ行n+ζ列の行列B、セキュリティパラメータk、有限体Fq、楕円曲線E、巡回群G1, G2, GT、生成元g1, g2, gT、双線形関数eなどが公開パラメータPKとして出力される。
【０１４６】
《GenKey(MSK,w→)：鍵情報生成》
−入力：マスター鍵情報MSK，ベクトルw→
−出力：ベクトルw→に対応する鍵情報D*
GenKey(MSK,w→)の一例では、まず、有限体Fqから元σ∈Fqが選択される。そして、マスター鍵情報MSKである行列B*を用い、ベクトルw→に対応する鍵情報
D*=σ・(Σμ=1nwμ・bμ*)+bn+1*∈G2n+1        …(71)
が生成され、出力される。なお、巡回群G2上での離散対数問題の求解が困難である場合、鍵情報D*からbμ*の成分を分離抽出することは困難である。
【０１４７】
《Enc(PA,v→)：暗号化》
−入力：公開パラメータPK，ベクトルv→
−出力：暗号文C2，共通鍵K
Enc(PA,v→)の一例では、まず、共通鍵Kと有限体Fqの元である乱数υ0とが生成される。そして、行列Bなどの公開パラメータPKと、有限体Fqの元υ1,...,υζと、ベクトルv→と、乱数υ0とを用い、暗号文
C2=υ0・(Σμ=1nvμ・bμ)+Σμ=n+1n+ζυμ-ｎ・bμ∈G1n+ζ        …(72)
が生成される。そして、暗号文C2と共通鍵Kとが出力される。共通鍵Kの一例はK=gTτ・υ1∈GTである。ここで、添え字のυ1はυ1を意味する。また、前述のようにτの一例はτ=1Fである。なお、巡回群G1上での離散対数問題の求解が困難である場合、暗号文C2からbμの成分を分離抽出することは困難である。
【０１４８】
《Dec(SKw,C2)：復号・鍵共有》
−入力：ベクトルw→に対応する鍵情報D1*，暗号文C2
−出力：共通鍵K
Dec(SKw,C2)の一例では、まず、暗号文C2と鍵情報D1*とが式(32)の双線形関数eに入力される。すると、式(33)(56)の性質から、
【数１２】
0005562475.tif 000015
を満たす。
【０１４９】
ここで、内積w→・v→=0であれば、式(73)は、
【数１３】
0005562475.tif 000016
と変形できる。この結果から共通鍵Kが生成され出力される。共通鍵Kの一例はK=gTτ・υ1∈GTである。
【０１５０】
＜全体構成＞
図１５は、第２実施形態の分散装置８１０の構成を説明するためのブロック図である。また、図１６は、第２実施形態の分散管理装置〔PA(α,h(α))〕８２０−α−ｈ（α）の構成を説明するためのブロック図である。図１７は、第２実施形態の取得装置８３０の構成を説明するためのブロック図である。図１８は、図１７の合成部８３５の構成を説明するためのブロック図である。なお、これらの図において第１実施形態と共通する部分については、第１実施形態と同じ符号を付して説明を簡略化する。
【０１５１】
本形態の秘密分散システムは、図１の分散装置１１０が分散装置８１０に置換され、分散管理装置〔PA(α,h(α))〕１２０−α−ｈ（α）が分散管理装置〔PA(α,h(α))〕８２０−α−ｈ（α）に置換され、取得装置１３０が取得装置８３０に置換されたものである。
【０１５２】
＜分散装置８１０＞
図１５に例示するように、本形態の分散装置８１０は、一時記憶部１１１と、記憶部１１２と、制御部１１３と、秘密分散部８１４−α（α=1,...,L）と、送信部１１５とを有する。なお、本形態の分散装置８１０は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１５３】
＜分散管理装置〔PA(α,h(α))〕８２０−α−h（α）＞
図１６に例示するように、本形態の分散管理装置〔PA(α,h(α))〕８２０−α−h（α）は、一時記憶部１２１−α−h（α）と、記憶部１２２−α−h（α）と、制御部１２３−α−h（α）と、分散秘密値生成部８２４−α−h（α）と、送信部１２５−α−h（α）と、受信部１２６−α−h（α）とを有する。なお、本形態の分散管理装置〔PA(α,h(α))〕８２０−α−h（α）は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１５４】
＜共有値生成装置１４０−α＞
第１実施形態と同様である。
【０１５５】
＜取得装置８３０＞
図１７に例示するように、本形態の取得装置８３０は、一時記憶部１３１と、記憶部１３２と、制御部１３３と、復元部８３４−α（α=1,...,L）と、合成部８３５と、送信部１３５と、受信部１３６とを有する。また、図１８に例示するように、合成部８３５は、第１演算部８３５ａと第２演算部８３５ｂとを有する。なお、本形態の取得装置８３０は、例えば、CPU、RAM、ROM等を備える公知のコンピュータに所定のプログラムが読み込まれて実行されることで構成される。
【０１５６】
＜秘密分散処理＞
次に、本形態の秘密分散処理を説明する。
本形態では、第１実施形態を応用し、内積述語暗号のマスター鍵情報MSKである行列B*（式(59)）を秘密分散し、式(71)に例示したような鍵情報D*を復元する。以下では、式(71)の鍵情報D*を生成情報
SK=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζ        …(75)
に一般化して説明する。式(71)はζ=1の例である。
【０１５７】
まず、式(55)に示した行列B*を構成する各要素
χi,β・κ2・g2∈G2  (i=1,...,n+ζ,β=1,...,n+ζ)       …(76)
を
θ(i,β)・g2∈G2          …(77)
θ(i,β)=χi,β・κ2∈Fq        …(78)
と表現する。すなわち、式(55)の基底ベクトルbi*を
bi*=(θ(i,1)・g2,...,θ(i,n+ζ)・g2)∈G2n+ζ        …(79)
と表現する。すると、第１実施形態又はその変形例を多次元に拡張することで、行列B*の秘密分散や生成情報SKの復元を実行できることが分かる。
【０１５８】
以下では、第１実施形態及びその変形例との相違点を中心に説明し、それらと共通する事項については説明を省略する。
[事前処理]
本形態の秘密分散処理の事前処理として、各基底ベクトルbi*の要素である秘密情報θ(i,β)・g2∈G2(i=1,...,n+ζ,β=1,...,n+ζ)を特定するための情報θ(i,β)∈Fqが分散装置８１０の記憶部１１２に格納される。
【０１５９】
[秘密分散処理の全体]
図１９は、第２実施形態の秘密分散処理の全体を説明するための図である。以下、図１９を用いて、本形態の秘密分散処理の全体を説明する。
本形態では、まず、分散装置８１０（図１５）が、部分集合SUB(α)ごとに独立に、各基底ベクトルbi*の要素である秘密情報θ(i,β)・g2∈G2を秘密分散してシェア情報SH(i,β,α,h(α))を生成し、当該シェア情報SH(i,β,α,h(α))を出力する（ステップＳ８１）。なお、秘密分散の具体的な方法は第１実施形態と同様である。また、シェア情報SH(i,β,α,h(α))∈G2(i=1,...,n+ζ,β=1,...,n+ζ)の集合をシェア情報SH(α,h(α))と呼ぶ。各シェア情報SH(α,h(α))は、それぞれ、ネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕８２０−α−h（α）に分散して送信される。
【０１６０】
各シェア情報SH(α,h(α))が送信された各分散管理装置〔PA(α,h(α))〕８２０−α−h（α）は、それぞれ、シェア情報SH(α,h(α))を構成するシェア情報SH(i,β,α,h(α))と、部分集合SUB(α)ごとに共有される共有値σ(α)と、有限体Fqの元を要素wμ(μ=1,...,n)とするn次元ベクトルw→=(w1,...,wn)とを用い、分散秘密値DSH(α,h(α))を生成する（ステップＳ８２）。本形態の分散秘密値DSH(α,h(α))は、n+ζ個のシェア情報SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))を要素とするn+ζ次元のシェア基底ベクトル
SHbi*(α,h(α))=(SH(i,1,α,h(α)),...,SH(i,n+ζ,α,h(α))∈Gn+ζ    …(80)
に対する、
DSH(α,h(α))
=σ(α)・{Σμ=1nwμ・SHbμ*(α,h(α))}+Σμ=n+1n+ζSHbμ*(α,h(α))∈Gn+ζ  …(81)
である。本形態の場合、互いに異なる部分集合SUB(α)でそれぞれ共有される共有値σ(α)は互いに独立である。
【０１６１】
各分散管理装置〔PA(α,h(α))〕８２０−α−h（α）から出力された各分散秘密値DSH(α,h(α))は、それぞれ、ネットワーク１５０経由で取得装置８３０に送信される。取得装置８３０は、同一の部分集合SUB(α)に対応する複数の分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって秘密復元値
SUBSK(α)=σ(α)・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζ        …(82)
を生成する（ステップＳ８３）。この処理は、分散秘密値DSH(α,h(α))の次元μごとに第１実施形態又はその変形例で示した復元処置を実行することで実現できる。
【０１６２】
次に、取得装置８３０は、各部分集合SUB(α)についてそれぞれ生成された秘密復元値SUBSK(α)を用いて生成情報SKを生成し、当該生成情報SKを出力する（ステップＳ８４）。  なお、本形態では、取得装置８３０が秘密復元値SUBSK(α)を線形結合して生成情報SKを生成する。生成情報の具体例は、
SK={(σ(1)+...+σ(L))/L}・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζ    …(83)
である。
【０１６３】
[分散装置の処理（テップＳ８１）]
図２０は、第２実施形態の分散装置の処理を例示するための図である。以下、この図を用いて、分散装置８１０の処理の詳細を説明する。
まず、分散装置８１０（図１５）の制御部１１３が、α=１，β=1に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ８１１）。次に、分散装置８１０の制御部１１３が、i=１に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ８１２）。
【０１６４】
次に、記憶部１１２から秘密情報θ(i,β)・g2∈G2(i=1,...,n+ζ,β=1,...,n+ζ)を特定するための情報θ(i,β)∈Fqそれぞれ読み出され、秘密分散部８１４−αに入力される。秘密分散部８１４−αは、各情報θ(i,β)∈Fqを用いて各秘密情報θ(i,β)・g2を秘密分散し、部分集合SUB(α)に対するH(α)個のシェア情報
SH(i,β,α,1),...,SH(i,β,α,H(α))          …(84)
を生成して出力する（ステップＳ８１３）。この処理は、第１実施形態のステップＳ１１２又はその変形と同様な方法で実行できる。
【０１６５】
次に、制御部１１３は、一時記憶部１１１に格納されたβがn+ζであるか否かを判定する（ステップＳ８１４）。ここで、β=n+ζでないと判定された場合、制御部１１３は、β+1を新たなβとし、その設定内容を一時記憶部１１１に格納し（ステップＳ８１５）、新たなβによってステップＳ８１３の処理を実行させる。
【０１６６】
一方、ステップＳ８１４でβ=n+ζであると判定された場合、制御部１１３は、β=1に設定し、その設定内容を一時記憶部１１１に格納する（ステップＳ８１６）。そして次に、制御部１１３は、一時記憶部１１１に格納されたiがn+ζであるか否かを判定する（ステップＳ８１７）。ここで、i=n+ζでないと判定された場合、制御部１１３は、i+1を新たなiとし、その設定内容を一時記憶部１１１に格納し（ステップＳ８１８）、新たなiによってステップＳ８１３の処理を実行させる。
【０１６７】
一方、ステップＳ８１７でi=n+ζであると判定された場合、制御部１１３は、一時記憶部１１１に格納されたαがLであるか否かを判定する（ステップＳ１１３）。ここで、α=Lでないと判定された場合、制御部１１３は、α+1を新たなαとし、その設定内容を一時記憶部１１１に格納し（ステップＳ１１４）、新たなαによってステップＳ８１２の処理を実行させる。
【０１６８】
一方、ステップＳ１１３でα=Lであると判定された場合、各秘密分散部８１４−αから出力された各シェア情報SH(α,h(α))が送信部１１５に送られる。送信部１１５は、ネットワーク１５０経由で、(n+ζ)2個ずつのシェア情報
SH(i,β,α,h(α)) (i=1,...,n+ζ,β=1,...,n+ζ)         …(85)
をそれぞれ分散管理装置〔PA(α,h(α))〕８２０−α−h(α)に送信する（ステップＳ８１９）。すなわち、(n+ζ)2個のシェア情報SH(i,β,1,1)(i=1,...,n+ζ,β=1,...,n+ζ)からなるシェア情報SH(1,1)は分散管理装置〔PA(1,1)〕８２０−1−1に、(n+ζ)2個のシェア情報SH(i,β,1,2)(i=1,...,n+ζ,β=1,...,n+ζ)からなるシェア情報SH(1,2)は分散管理装置〔PA(1,2)〕８２０−1−２に、・・・、(n+ζ)2個のシェア情報SH(i,β, L, H(L))(i=1,...,n+ζ,β=1,...,n+ζ)からなるシェア情報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(α)が、送信された(n+ζ)2個のシェア情報SH(i,β,α,h(α))(i=1,...,n+ζ,β=1,...,n+ζ)からなるシェア情報SH(α, h(α))を受信し、それを記憶部１２２−α−h(α)に格納する（ステップＳ８２１）。なお、過去にステップＳ８２１の処理が実行され、既にシェア情報SH(α,h(α))が分散管理装置〔PA(α,h(α))〕８２０−α−h(α)の記憶部１２２−α−h(α)に格納されているのであれば、ステップＳ８２１の処理を省略してもよい。
【０１７２】
また、分散管理装置〔PA(α,h(α))〕８２０−α−h(α)の受信部１２６−α−h(α)は、共有値生成装置１４０−αから送信された共有値σ(α)を受信し、それを記憶部１２２−α−h(α)に格納する（ステップＳ１２２）。
【０１７３】
また、本形態では、取得装置８３０（図１７）の記憶部１３２から読み出された提供情報であるn次元ベクトルw→=(w1,...,wn)が、送信部１３５から、ネットワーク１５０経由で各分散管理装置〔PA(α,h(α))〕８２０−α−h(α)に送信される。このn次元ベクトルw→=(w1,...,wn)は、すべての分散管理装置PA(α,h(α))８２０−α−h（α）に共通である。n次元ベクトルw→=(w1,...,wn)は、分散管理装置〔PA(α,h(α))〕８２０−α−h(α)（図１６）の受信部１２６−α−h(α)で受信され、記憶部１２２−α−h(α)に格納される（ステップＳ８２３）。
【０１７４】
次に、分散秘密値生成部８２４−α−h(α)が、記憶部１２２−α−h(α)からシェア情報SH(α,h(α))と共有値σ(α)とn次元ベクトルw→=(w1,...,wn)とを読み込む。分散秘密値生成部８２４−α−h(α)は、共有値σ(α)とw→=(w1,...,wn)とを含む共通情報と、シェア情報SH(α,h(α))とを用い、式(81)に示す分散秘密値DSH(α,h(α))を生成し、当該分散秘密値DSH(α,h(α))を出力する（ステップＳ８２４）。
【０１７５】
生成された分散秘密値DSH(α,h(α))は送信部１２５−α−h（α）に送られる。送信部１２５−α−h（α）は、分散秘密値DSH(α,h(α))をネットワーク１５０経由で取得装置８３０に送信する（ステップＳ１２５）。
【０１７６】
［取得装置の処理（ステップＳ８３，Ｓ８４）］
図２２は、第２実施形態の取得装置の処理を例示するための図である。
各分散管理装置PA(α,h(α))８２０−α−h(α)から送信された分散秘密値DSH(α,h(α))は、取得装置８３０（図１７）の受信部１３６で受信され、記憶部１３２に格納される（ステップＳ１３１）。
【０１７７】
次に、制御部１３３が、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたか否かを判定する（ステップＳ１３２）。ここで、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されていないと判定された場合には、ステップＳ１３１の処理に戻される。
【０１７８】
一方、必要数以上の分散秘密値DSH(α,h(α))が記憶部１３２に格納されたと判定された場合、制御部１３３が、α=１に設定し、その設定内容を一時記憶部１３１に格納する（ステップＳ１３３）。次に、記憶部１３２から部分集合SUB(α)に対応する必要数分の分散秘密値DSH(α,h(α))が読み出され、復元部８３４−αに入力される。復元部８３４−αは、入力された分散秘密値DSH(α,h(α))を用い、部分集合SUB(α)ごとの復元処理によって式(82)に示す秘密復元値SUBSK(α)を生成し、当該部分集合SUB(α)ごとの秘密復元値SUBSK(α)を出力する（ステップＳ８３４）。
【０１７９】
次に、制御部１３３は、一時記憶部１３１に格納されたαがLであるか否かを判定する（ステップＳ１３５）。ここで、α=Lでないと判定された場合、制御部１３３は、α+1を新たなαとし、その設定内容を一時記憶部１３１に格納し（ステップＳ１３６）、新たなαによってステップＳ８３４の処理を実行させる。
【０１８０】
一方、ステップＳ１３５でα=Lであると判定された場合、各復元部１３４−αから出力された各秘密復元値SUBSK(α)が合成部８３５に送られる。合成部８３５の第１演算部８３５ａ（図１８）は、線形和
SUBSK(1)+...+SUBSK(L)
=(σ(1)+...+σ(L))・{Σμ=1nwμ・bμ*}+L・Σμ=n+1n+ζbμ*∈Gn+ζ        …(86)
を生成して出力する（ステップＳ８４１）。
【０１８１】
線形和SUBSK(1)+...+SUBSK(L)は、第２演算部８３５ｂに入力される。第２演算部８３５ｂは、生成情報
SK={(σ(1)+...+σ(L))/L}・{Σμ=1nwμ・bμ*}+Σμ=n+1n+ζbμ*∈Gn+ζ    …(87)
を生成し、当該生成情報SKを出力する（ステップＳ８４２）。
【０１８２】
＜第２実施形態の変形例＞
本形態でも、第１実施形態の各変形例を適用できる。
【０１８３】
〔その他の変形例等〕
本発明は上述の各実施の形態に限定されるものではない。例えば、上述の有限体Fq上で定義された各演算を位数qの有限環Zq上で定義された演算に置き換えてもよい。有限体Fq上で定義された各演算を有限環Zq上で定義された演算に置き換える方法の一例は、素数やそのべき乗値以外のqを許容する方法である。
【０１８４】
また、式(71)の代わりに
D*=σ・(Σμ=1nwμ・bμ*)+Σι=n+1n+ζυι・bι*∈G2n+ζ
を用いてもよい。ただし、υιは定数や変数（乱数など）などである。
【０１８５】
また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１８６】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１８７】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１８８】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１８９】
１  秘密分散システム
１１０，８１０  分散装置
１２０，８２０  分散管理装置
１３０，８３０  取得装置
１４０  共有値生成装置
【図１】
0005562475.tif 000017
【図２】
0005562475.tif 000018
【図３】
0005562475.tif 000019
【図４】
0005562475.tif 000020
【図５】
0005562475.tif 000021
【図６】
0005562475.tif 000022
【図７】
0005562475.tif 000023
【図８】
0005562475.tif 000024
【図９】
0005562475.tif 000025
【図１０】
0005562475.tif 000026
【図１１】
0005562475.tif 000027
【図１２】
0005562475.tif 000028
【図１３】
0005562475.tif 000029
【図１４】
0005562475.tif 000030
【図１５】
0005562475.tif 000031
【図１６】
0005562475.tif 000032
【図１７】
0005562475.tif 000033
【図１８】
0005562475.tif 000034
【図１９】
0005562475.tif 000035
【図２０】
0005562475.tif 000036
【図２１】
0005562475.tif 000037
【図２２】
0005562475.tif 000038