(57)【特許請求の範囲】
【請求項１】
M, Nが2以上の整数であり、Ni (i=0,...,N-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が前記集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を前記集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす前記集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を前記値y(M-1)に移す写像であり、
M-1個の値v(m) (m=0,...,M-2)を選択する選択部と、
M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得る第１変換部と、
前記集合Gの要素である値αに対して値a(M-1)=g(α, a(0),...,a(M-2))を得る第１計算部と、
集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)がa(i, qi)であり、前記値αの分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1)) (i=0,...,N-1)を得る分散値生成部と、
を有するデータ分散装置。
【請求項２】
請求項１のデータ分散装置で得られた分散値Ti(α)を用い、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)∈Ti(α)について値a(i, ni)=P(v(i, ni))を得る第３変換部と、
前記第３変換部で得られた前記値a(i, ni)とv(i, qi)=a(M-1) (qi∈{0,...,Ni-1}, ni≠qi)であるa(i, qi)=v(i, qi)∈Ti(α)との少なくとも何れかを含むSi(α)={a(i,0),...,a(i,Ni-1)}を変換分散値として得る変換分散値生成部と、
を有する分散データ変換装置。
【請求項３】
請求項１のデータ分散装置で得られた分散値Ti(α) (i=0,...,N-1)の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得る第２変換部と、
前記第２変換部で得られた前記値a(m) (m=0,...,M-2)と前記分散値Ti(α)の何れかが含む値a(M-1)とを用いてα=f(a(0),...,a(M-1))を得る復元部と、
を有するデータ復元装置。
【請求項４】
M, N, Rが2以上の整数であり、Ni,r (i=0,...,N-1, r=0,...,R-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が前記集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を前記集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす前記集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を前記値y(M-1)に移す写像であり、
M-1個の値v(m) (m=0,...,M-2)を選択する選択部と、
rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得る第１変換部と、
前記集合Gの要素である値αrに対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を得る第１計算部と、
集合Ar={ar(0),...,ar(M-1)}の部分集合がSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)であり、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個がar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}であり、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)がar(i, qi,r)=ar(M-1)であり、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1)) (i=0,...,N-1, r=0,...,R-1)を得る分散値生成部と、
を有するデータ分散装置。
【請求項５】
請求項４のデータ分散装置で得られた分散値Ti(αr)に含まれるvｒ’(i, ni,r’) (r’∈{0,...,R-1})について値ar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1})を得る第３変換部と、
前記第３変換部で得られた前記値ar(i, ni,r) (ni,r∈{0,...,Ni,r-1})とvr(i, qi,r)=ar(M-1) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)であるar(i, qi,r)=vr(i, qi,r)∈Ti(αr)との少なくとも何れかを含むSi(αr)={ar(i,0),...,ar(i,Ni,r-1)}を変換分散値として得る変換分散値生成部と、
を有する分散データ変換装置。
【請求項６】
請求項４のデータ分散装置で得られた分散値Ti(αr) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,...,M-2)を得る第２変換部と、
前記第２変換部で得られた前記値ar(m) (m=0,...,M-2)と前記分散値Ti(αr)の何れかが含む値ar(M-1)とを用いてαr=f(ar(0),...,ar(M-1))を得る復元部と、
を有するデータ復元装置。
【請求項７】
N, Rが2以上の整数であり、Ni (i=0,...,N-1)が1以上N-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり、y=f(y(0),...,y(N-1))が前記集合Gの要素であるN個の値y(0),...,y(N-1)からなる部分集合(y(0),...,y(N-1))を前記集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(N-2))がy=f(y(0),...,y(N-1))を満たす前記集合Gの要素であるN個のy, y(0),...,y(N-2)からなる部分集合(y, y(0),...,y(N-2))を前記値y(N-1)に移す写像であり、
N-1個の値v(n) (n=0,...,N-2)を選択する選択部と、
rと値v(n)とに対応する値をz(r, v(n))とし、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を得る第１変換部と、
前記集合Gの要素である値αr (r=0,...,R-1)に対して値ar(N-1)=g(αr, ar(0),...,ar(N-2))を得る第１計算部と、
前記値v(n)を分散値Tn(β) (n=0,...,N-2、β={α0,...,αR-1})とし、前記値ar(N-1)を分散値TN-1(αr)とする分散値生成部と、
を有するデータ分散装置。
【請求項８】
請求項７のデータ分散装置で得られた分散値Tn(β)＝v(n)から値ar(n)=P(z(r, v(n))) (r=0,...,R-1)を変換分散値として得る変換分散値生成部を有する分散データ変換装置。
【請求項９】
請求項７のデータ分散装置で得られた分散値Tn(β) (n=0,...,N-2)を用いて、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を得る第２変換部と、
前記第２変換部で得られた前記値ar(n) (n=0,...,N-2)と前記分散値TN-1(αr)=ar(N-1)とを用いてαr=f(ar(0),...,ar(N-1)) (r=0,...,R-1)を得る復元部と、
を有するデータ復元装置。
【請求項１０】
M, N, Kが2以上の整数であり、K≦Nであり、Ni (i=0,...,N-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が前記集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を前記集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす前記集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を前記値y(M-1)に移す写像であり、
M-1個の値v(m) (m=0,...,M-2)を選択する選択部と、
M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得る第１変換部と、
前記集合Gの要素である値αに対して値a(M-1)=g(α, a(0),...,a(M-2))を得る第１計算部と、
(K, N)閾値秘密分散法Uに従って前記値a(M-1)を秘密分散してN個の分散値Ui(a(M-1)) (i=0,...,N-1)を得る内部分散部と、
集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)が空値であり、前記値αの分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1))) (i=0,...,N-1)を得る分散値生成部と、
を有するデータ分散装置。
【請求項１１】
請求項１０のデータ分散装置で得られた分散値Ti(α) (i=0,...,N-1)を用い、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)∈Ti(α)について値a(i, ni)=P(v(i, ni))を得る第３変換部と、
前記分散値Ti(α)(i=0,...,N-1)に含まれるK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から前記値a(M-1)を得る第２内部復元部と、
前記第３変換部で得られた前記値a(i, ni)と前記第２内部復元部で得られた前記値a(M-1)との少なくとも何れかを含むSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)を変換分散値として得る変換分散値生成部と、
を有する分散データ変換装置。
【請求項１２】
請求項１０のデータ分散装置で得られた分散値Ti(α) (i=0,...,N-1)の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得る第２変換部と、
前記分散値Ti(α)(i=0,...,N-1)に含まれるK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から前記値a(M-1)を得る第１内部復元部と、
前記第２変換部で得られた前記値a(m) (m=0,...,M-2)と前記第１内部復元部で得られた前記値a(M-1)とを用いてα=f(a(0),...,a(M-1))を得る復元部と、
を有するデータ復元装置。
【請求項１３】
M, N, K, Rが2以上の整数であり、K≦Nであり、Ni,r (i=0,...,N-1, r=0,...,R-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を前記集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が前記集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を前記集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす前記集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を前記値y(M-1)に移す写像であり、
M-1個の値v(m) (m=0,...,M-2)を選択する選択部と、
rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得る第１変換部と、
前記集合Gの要素である値αr (r=0,...,R-1)に対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を得る第１計算部と、
(K, N)閾値秘密分散法Uに従って前記値ar(M-1)を秘密分散してrのそれぞれについてN個の分散値Ui(ar(M-1)) (i=0,...,N-1)を得る内部分散部と、
集合Ar={ar(0),...,ar(M-1)}の部分集合がSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)であり、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個がar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}であり、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)が空値であり、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1), Ui(ar(M-1))) (i=0,...,N-1, r=0,...,R-1)を得る分散値生成部と、
を有するデータ分散装置。
【請求項１４】
請求項１３のデータ分散装置で得られた分散値Ti(αr) (r=0,...,R-1)に含まれるvｒ’(i, ni,r’) (r’∈{0,...,R-1})について値ar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1})を得る第３変換部と、
前記分散値Ti(αr)(i=0,...,N-1)に含まれるK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から前記値ar(M-1)を得る第２内部復元部と、
前記第３変換部で得られた前記値aｒ(i, ni,r)と前記第２内部復元部で得られた前記値ar(M-1)との少なくとも何れかを含むSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1)を変換分散値として得る変換分散値生成部と、
を有する分散データ変換装置。
【請求項１５】
請求項１３のデータ分散装置で得られた分散値Ti(α0) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得る第２変換部と、
前記分散値Ti(αr) (i=0,...,N-1)に含まれるK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から前記値ar(M-1)を得る第１内部復元部と、
前記第２変換部で得られた前記値ar(m) (m=0,...,M-2)と前記第１内部復元部で得られた前記値ar(M-1)とを用いてαr=f(ar(0),...,ar(M-1))を得る復元部と、
を有するデータ復元装置。
【請求項１６】
請求項１のデータ分散装置であって、
前記M-1個の値v(m) (m=0,...,M-2)のデータ量の合計値は、M-1個の前記集合Gの要素のデータ量の合計値よりも小さい、データ分散装置。
【請求項１７】
請求項７のデータ分散装置であって、
N-1個の前記分散値Tn(β) (n=0,...,N-2)のデータ量の合計値は、R×(N-1)個の前記集合Gの要素のデータ量の合計値よりも小さい、データ分散装置。
【請求項１８】
請求項１０のデータ分散装置であって、
a(i,j)≠a(M-1)である(i,j)に対するNi-1個のv(i,j)のデータ量とUi(a(M-1))のデータ量との合計値は、Ni個の前記集合Gの要素のデータ量の合計値よりも小さい、データ分散装置。
【請求項１９】
請求項１３のデータ分散装置であって、
ar(i,j)≠ar(M-1)である(i,j)に対するNi,r-1個のvr(i,j)のデータ量とUi(ar(M-1))のデータ量との合計値は、Ni,r個の前記集合Gの要素のデータ量の合計値よりも小さい、データ分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散技術に関する。
【背景技術】
【０００２】
秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。分散値の総数をN、復元に必要な分散値の最小数をK（≦N）としたとき、N, K の値に制限がない方式とある方式とがある。秘密分散の単純な方法として、加法的秘密分散(Additive Secret Sharing)がある。これはMを2以上の整数として、データa=a0+a1+…+aM-1について、各分散値をA={a0,a1,…,aM-1}の部分集合とする。ただしa,a0,a1,…,aM-1は加法群の要素、特にa0,a1,…,aM-2は当該加法群からランダムに選択された値である。
【０００３】
また、秘密分散を要素技術とした秘密計算（マルチパーティ計算）方式も提案されている（例えば、非特許文献１，２等参照）。このような秘密計算方式では、各主体が保有するデータの分散値を他の主体に送り、当該分散値を他の主体に明かすことなく意中の計算を実行させる。計算を行った各主体からは計算結果の分散値が得られる。このような分散値がK個以上得られれば計算結果を復元でき、得られなければ計算結果を復元できない。
【０００４】
例えば、非特許文献１の秘密計算方式では、秘密分散方式として加法的秘密分散方式が用いられ、aの分散値をSi(a)=ai（i=0,1,…,N-1）とし、M=N=Kとして秘密計算が行われる。この方式では、明らかにN個の分散値Si(a)からaを復元でき、かつN-1個の分散値からはaを一切復元できない。非特許文献２の秘密計算方式では、秘密分散方式として加法的秘密分散方式が用いられ、aの分散値をSi(a)={ai, ai+1 mod 3} （i=0,1,…,N-1）とし、M=N=3, K=2として秘密計算が行われる。この方式では、明らかに任意の2個の分散値Si(a)からaを復元でき、かつ１個の分散値からはaを一切復元できない。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】D. Bogdanov, S. Laur, and J. Willemson, “Sharemind: A framework for fast privacy-preserving computations,” Cryptology ePrint Archive: Report 2008/289, [平成２３年１１月３０日検索]、インターネット＜http://eprint.iacr.org/2008/289＞
【非特許文献２】千田浩司, 五十嵐大, 高橋克巳, “効率的な３パーティ秘匿関数計算の提案とその運用モデルの考察,” 情報処理学会研究報告 第48回 CSEC 研究会, 2010.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
非特許文献１や２に記載の加法的秘密分散では、分散値の総データ量がそれぞれ元データのN倍、6倍となっている。復元に必要な分散値の総データ量はそれぞれ元データのN倍、3倍となっている。分散値のデータ量の増加は通信時間や保存データの増大につながるため、できるだけ分散値のデータ量を抑えることが望ましい。このような課題は加法的秘密分散のみならず、その他の秘密分散方式にも共通するものである。
本発明はこのような点に鑑みてなされたものであり、秘密分散方式の分散値のデータ量を抑えることを目的とする。
【課題を解決するための手段】
【０００７】
M, Nが2以上の整数であり、Ni (i=0,...,N-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を値y(M-1)に移す写像であるとする。
【０００８】
データ分散時には、M-1個の値v(m) (m=0,...,M-2)を選択し、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、集合Gの要素である値αに対して値a(M-1)=g(α, a(0),...,a(M-2))を得、値αの分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1)) (i=0,...,N-1)を得る。ただし、集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)がa(i, qi)である。
【０００９】
データ復元時には、分散値Ti(α) (i=0,...,N-1)の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、値a(m) (m=0,...,M-2)と分散値Ti(α)の何れかが含む値a(M-1)とを用いてα=f(a(0),...,a(M-1))を得る。
【発明の効果】
【００１０】
本発明では、秘密分散方式の分散値のデータ量を抑えることができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、秘密分散システムの機能構成を例示するブロック図である。
【図２】図２Ａは、データ分散装置の機能構成を例示するブロック図であり、図２Ｂは、データ復元装置の機能構成を例示するブロック図である。
【図３】図３は、分散データ変換装置の機能構成を例示するブロック図である。
【図４】図４は、データ分散装置の処理を例示するためのフローチャートである。
【図５】図５は、分散データ変換装置の処理を例示するためのフローチャートである。
【図６】図６は、データ復元装置の処理を例示するためのフローチャートである。
【図７】図７は、データ分散装置の処理を例示するためのフローチャートである。
【図８】図８は、分散データ変換装置の処理を例示するためのフローチャートである。
【図９】図９は、データ復元装置の処理を例示するためのフローチャートである。
【図１０】図１０Ａは、データ分散装置の機能構成を例示するブロック図であり、図１０Ｂは、データ復元装置の機能構成を例示するブロック図である。
【図１１】図１１Ａ及び図１１Ｂは、分散データ変換装置の機能構成を例示するブロック図である。
【図１２】図１２は、データ分散装置の処理を例示するためのフローチャートである。
【図１３】図１３Ａ及び図１３Ｂは、データ分散装置の処理を例示するためのフローチャートである。
【図１４】図１４は、データ復元装置の処理を例示するためのフローチャートである。
【図１５】図１５は、秘密分散システムの機能構成を例示するブロック図である。
【図１６】図１６Ａは、データ分散装置の機能構成を例示するブロック図であり、図１６Ｂは、データ復元装置の機能構成を例示するブロック図である。
【図１７】図１７は、分散データ変換装置の処理を例示するためのフローチャートである。
【図１８】図１８は、データ分散装置の処理を例示するためのフローチャートである。
【図１９】図１９は、分散データ変換装置の処理を例示するためのフローチャートである。
【図２０】図２０は、データ復元装置の処理を例示するためのフローチャートである。
【図２１】図２１は、分散データ変換装置の処理を例示するためのフローチャートである。
【図２２】図２２は、分散データ変換装置の処理を例示するためのフローチャートである。
【図２３】図２３は、データ復元装置の処理を例示するためのフローチャートである。
【発明を実施するための形態】
【００１２】
以下、図面を参照して本発明の実施形態を説明する。
〔第１実施形態〕
まず、第１実施形態の概要を説明する。
第１実施形態では、M, Nが2以上の整数であり、Ni(i=0,...,N-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を値y(M-1)に移す写像である。
【００１３】
集合Gは演算が定義された集合であり、集合Gの具体例は群（例えば、加法群や乗法群など）や体である。例えば、任意の正整数μを法とした剰余類の代表元からなる加法群{0,1,...,μ-1}を集合Gとすることができる。正整数μの一例はμ=232である。写像P(x)は、入力された「xに対応する値」に対して集合Gの要素を出力するものである。同一の「xに対応する値」には同一の「P(x)」が対応する。すなわち、写像P(x)は入力が等しければ出力も等しくなる、確定的な関数である。「xに対応する値」と「P(x)」とは一対一で対応してもよいし、しなくてもよい。「xに対応する値」は、値xそのものであってもよいし、xとその他の値との組み合わせ値（例えば、rとxとに対応する値z(r, x)）であってもよい。写像P(x)の例はxをシードとして集合Gの要素を返す擬似乱数生成関数である。また例えば、xを秘密鍵として固定の平文に対して集合Gに属する暗号文を出力する共通鍵暗号関数をP(x)として用いることができる。写像y=f(y(0),...,y(M-1))及びg(y, y(0),...,y(M-2))の具体例は以下の通りである。例えば集合Gが加法群なのであれば、y=y(0)+...+y(M-1)∈G，y=-y(0)-...-y(M-1)∈G，y=y(0)-y(1)+y(2)-...+y(M-1)∈Gなどを写像y=f(y(0),...,y(M-1))とすることができる。例えば、集合Gがμを法とした剰余類の代表元からなる加法群なのであれば、例えばy=y(0)+...+y(M-1) (mod μ)などを写像y=f(y(0),...,y(M-1))とすることができる。集合Gが乗法群なのであれば、例えばy=y(0)・...・y(M-1)∈G，y={y(0)}-1・...・y{(M-1)}-1∈G，y=y(0)・{y(1)}-1・y(2)・{y(3)}-1・...・y(M-1)などを写像y=f(y(0),...,y(M-1))とすることができる。写像g(y, y(0),...,y(M-2))は写像y=f(y(0),...,y(M-1))に対して上記の関係を満たす。例えば、写像y=f(y(0),...,y(M-1))がy=y(0)+...+y(M-1) (mod μ)である場合、写像g(y, y(0),...,y(M-2))はy(M-1)=y-y(0)-y(1)...-y(M-2) (mod μ)である。「写像」は、関数であってもよいし、アルゴリズムであってもよい。また、M≦Nであってもよいし、M≧Nであってもよい。
【００１４】
第１実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、M-1個の値v(m) (m=0,...,M-2)を選択し、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、集合Gの要素である値αに対して値a(M-1)=g(α, a(0),...,a(M-2))を得、値αの分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1)) (i=0,...,N-1)を得る。ただし、集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)がa(i, qi)である。データ分散装置で得られたN個の分散値Ti(α) (i=0,...,N-1)は、例えばN個の分散データ変換装置のそれぞれに提供される。
【００１５】
本形態のデータ復元装置は、N個の分散値Ti(α) (i=0,...,N-1)の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、得られた値a(m) (m=0,...,M-2)と上記分散値Ti(α)の何れかが含む値a(M-1)とを用いてα=f(a(0),...,a(M-1))を得る。
【００１６】
本形態の分散データ変換装置のそれぞれは、自らに提供された分散値Ti(α)を用い、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)∈Ti(α)について値a(i, ni)=P(v(i, ni))を得、値a(i, ni)とv(i, qi)=a(M-1) (qi∈{0,...,Ni-1}, ni≠qi)であるa(i, qi)=v(i, qi)∈Ti(α)との少なくとも何れかを含むSi(α)={a(i,0),...,a(i,Ni-1)}を変換分散値として得ることもできる。このように得られる変換分散値Si(α)は、秘密計算の入力値として用いられる。例えば、複数の分散データ変換装置１２０−ｉで得られた変換分散値Si(α)に対してそれぞれ同一の秘密計算を行って得られる各結果は、αに演算を施して得られる演算結果の秘密分散値となる。秘密計算の具体例は、非特許文献１，２等に開示された線形演算などである。秘密計算は単項演算であってもよいし、多項演算であってもよい。
【００１７】
本形態において好ましくは、M-1個の値v(m) (m=0,...,M-2)のデータ量の合計値は、M-1個の集合Gの要素のデータ量の合計値よりも小さい。より好ましくは、値v(m)それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００１８】
＜構成＞
図１に例示するように、第１実施形態の秘密分散システム１は、データ分散装置１１０、N個の分散データ変換装置１２０−ｉ（i=0,...,N-1）、及びデータ復元装置１３０を有する。データ分散装置１１０は、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置１２０−ｉ（i=0,...,N-1）に対して情報の提供が可能である。N個の分散データ変換装置１２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置１３０に対して情報の提供が可能である。
【００１９】
図２Ａに例示するように、本形態のデータ分散装置１１０は、入力部１１１、出力部１１２、メモリ１１３、制御部１１４、選択部１１５、変換部１１６、計算部１１７、及び分散値生成部１１８を有する。本形態のデータ分散装置１１０は、例えば、CPU(central processing unit)，RAM(random-access memory)等を有する公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ分散装置１１０は、制御部１１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２０】
図２Ｂに例示するように、本形態のデータ復元装置１３０は、入力部１３１、出力部１３２、メモリ１３３、制御部１３４、変換部１３５、及び復元部１３６を有する。本形態のデータ復元装置１３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ復元装置１３０は、制御部１３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２１】
図３に例示するように、本形態の分散データ変換装置１２０−ｉ (i=0,...,N-1)は、入力部１２１−ｉ、出力部１２２−ｉ、メモリ１２３ａ−ｉ、記憶部１２３ｂ−ｉ，１２３ｃ−ｉ、制御部１２４−ｉ、変換部１２５−ｉ、変換分散値生成部１２６−ｉ、及び秘密計算部１２７−ｉを有する。本形態の分散データ変換装置１２０−ｉは、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態の分散データ変換装置１２０−ｉは、制御部１２４−ｉの制御のもとで各処理を実行する。入力部１２１−ｉに入力されたデータや各処理で得られたデータはメモリ１２３ａ−ｉや記憶部１２３ｂ−ｉに格納され、メモリ１２３ａ−ｉや記憶部１２３ｂ−ｉに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００２２】
＜データ分散処理＞
図４に例示するように、データ分散装置１１０（図２Ａ）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。値αの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。値αのデータ量、すなわち集合Gの要素のデータ量は、例えば1メガバイト以上である。
【００２３】
選択部１１５は、M-1個の値v(m) (m=0,...,M-2)を選択し、値v(m) (m=0,...,M-2)を出力する（ステップＳ１１２）。選択部１１５は、逐一、ランダムにM-1個の値v(m) (m=0,...,M-2)を選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってM-1個の値v(m) (m=0,...,M-2)を選択してもよい。例えば、選択される値v(m) (m=0,...,M-2)それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも十分小さいことが望ましい。安全性を考慮すると、値v(m)は、値v(m)から生成される値a(m)やP(x)から値v(m)を特定することが困難となる程度の値（全数探索による攻撃や現在の計算機の性能を考慮すれば、値v(m)は80ビット程度かそれ以上の乱数）とするのが望ましい。
【００２４】
値v(m) (m=0,...,M-2)は変換部１１６に入力される。変換部１１６は、入力された値v(m) (m=0,...,M-2)からM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を計算し、当該M-1個の値a(m) (m=0,...,M-2)を出力する（ステップＳ１１３）。P(x)が擬似乱数生成関数の場合、値a(m)は擬似乱数となる。
【００２５】
入力部１１１に入力された値αと変換部１１６から出力されたM-1個の値a(m) (m=0,...,M-2)とは計算部１１７に入力される。計算部１１７は、これらの値α，a(m) (m=0,...,M-2)から値a(M-1)=g(α, a(0),...,a(M-2))∈Gを計算し、当該値a(M-1)を出力する（ステップＳ１１４）。例えば、写像g(y, y(0),...,y(M-2))がy(M-1)=y-y(0)-y(1)...-y(M-2) (mod μ)である場合、計算部１１７はa(M-1)=α-a(0)-a(1)...-a(M-2) (mod μ)を計算し、それによって得られた値a(M-1)を出力する。
【００２６】
選択部１１５から出力されたM-1個の値v(m) (m=0,...,M-2)と計算部１１７から出力された値a(M-1)は、分散値生成部１１８に入力される。分散値生成部１１８は、これらの値a(M-1)，v(m) (m=0,...,M-2)を用い、値αのN個の分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1)) (i=0,...,N-1)を生成して出力する。ただし、集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)がa(i, qi)である。P-1(X)(X∈G)はP(x)の逆写像を表す（ステップＳ１１５）。
一例を挙げると、分散値生成部１１８は、M=N，Ni=N-1とし、集合Aから値a(i)を除いて得られる部分集合A＼a(i)をSi(α) (i=0,...,N-1)とし、分散値Ti(α) (i=0,...,N-1)を以下のように生成する。
T0(α)=(v(1), v(2),..., v(M-2), a(M-1)),
T1(α)=(v(0), v(2),..., v(M-2), a(M-1)),...,
TM-2(α)=(v(0), v(1),..., v(M-3), a(M-1)),
TM-1(α)=(v(0), v(1),..., v(M-3), v(M-2))       ...(1)
【００２７】
N個の分散値Ti(α) (i=0,...,N-1)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=0,...,N-1)を出力する（ステップＳ１１６）。出力された分散値Ti(α) (i=0,...,N-1)のそれぞれは、分散データ変換装置１２０−ｉ(i=0,...,N-1)のそれぞれに提供される。例えば、分散値Ti(α)は、ネットワーク等を経由して、対応する分散データ変換装置１２０−ｉ（図３）に送信される。分散データ変換装置１２０−ｉ(i=0,...,N-1)のそれぞれに提供された分散値Ti(α)は入力部１２１−ｉに入力され、記憶部１２３ｂ−ｉに格納される。
【００２８】
＜分散データ変換処理／分散値出力処理＞
分散データ変換装置１２０−ｉ(i=0,...,N-1)が実行する分散データ変換処理及び分散値出力処理を説明する。これらの処理は、すべての分散データ変換装置１２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうちK個（K≦N）の分散データ変換装置１２０−ｋ（k∈{0,...,N-1}）のみで実行されてもよい。
図５に例示するように、分散データ変換装置１２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行わずに分散値を出力する場合、制御部１２４−ｉは分散値の変換を行わずに分散値Ti(α)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ１２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは、格納している分散値Ti(α)を読み出して出力する。分散値Ti(α)は出力部１２２−ｉに送られ、出力部１２２−ｉは分散値Ti(α)を出力する（ステップＳ１２２−ｉ）。出力された分散値Ti(α)はデータ復元装置１３０に提供される。例えば、分散値Ti(α)は、ネットワーク等を経由してデータ復元装置１３０に送信される。分散データ変換装置１２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する場合には、分散データ変換処理及び分散値出力処理を実行するすべての分散データ変換装置１２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する。
【００２９】
一方、分散データ変換装置１２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行う場合、制御部１２４−ｉは、分散値の変換を行うために分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1))を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ１２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは分散値Ti(α)を読み出す。
読み出された分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1))を構成する要素のうち、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応する値v(i, ni)∈Ti(α) (ni∈{0,...,Ni-1})は変換部１２５−ｉに入力される。読み出された分散値Ti(α)がv(i, qi)=a(i, qi)=a(M-1) ∈Ti(α) (qi∈{0,...,Ni-1}, ni≠qi)である値v(i, qi)を含む場合、当該値v(i, qi)は変換分散値生成部１２６−ｉに入力される。
【００３０】
変換部１２５−ｉは、入力された値v(i, ni)から値a(i, ni)=P(v(i, ni))を計算し、当該値a(i, ni)を出力する（ステップＳ１２３−ｉ）。
【００３１】
変換分散値生成部１２６−ｉには、変換部１２５−ｉで得られた値a(i, ni) (ni∈{0,...,Ni-1})と、記憶部１２３ｂ−ｉから読み出されたv(i, qi)=a(i, qi)=a(M-1) (qi∈{0,...,Ni-1}, ni≠qi)と（存在するのであれば）が入力される。変換分散値生成部１２６−ｉは、入力された値からなる変換分散値Si(α)={a(i,0),...,a(i,Ni-1)}を生成し（ステップＳ１２４−ｉ）、当該変換分散値Si(α)を記憶部１２３ｃ−ｉに格納する（ステップＳ１２５−ｉ）。例えば、式(1)の分散値Ti(α)に対応する変換分散値Si(α)は以下のようになる。
S0(α)=(a(1), a(2),..., a(M-2), a(M-1)),
S1(α)=(a(0), a(2),..., a(M-2), a(M-1)),...,
SM-2(α)=(a(0), a(1),..., a(M-3), a(M-1)),
SM-1(α)=(a(0), a(1),..., a(M-3), a(M-2))
【００３２】
秘密計算部１２７−ｉは、所定の契機で記憶部１２３ｃ−ｉに格納された変換分散値Si(α)={a(i,0),...,a(i,Ni-1)}を読み出し、変換分散値Si(α)を入力とした秘密計算を実行し、その演算結果である分散値Ei={e(i,0),...,e(i,Ni-1)}を出力する。分散値Eiは出力部１２２−ｉから出力され、データ復元装置１３０に提供される。例えば、分散値Eiは、ネットワーク等を経由して、データ復元装置１３０に送信される。簡単な秘密計算の例は、変換分散値Si(α)={a(i,0),...,a(i,Ni-1)}の加法群Gでのスカラー倍算であり、この場合にはEi=υ・Si(α)、すなわち{e(i,0),...,e(i,Ni-1)}={υ・a(i,0),..., υ・a(i,Ni-1)}となる。ただしυは整数環の元である。
【００３３】
＜データ復元処理＞
図６に例示するように、データ復元装置１３０（図２Ｂ）の入力部１３１に、何れかK個の分散値Tk(α) (k∈{0,...,N-1})、又は、何れかK個の分散値Ek={e(k,0),...,e(k,Nk-1)} (k∈{0,...,N-1})が入力される（ステップＳ１３１）。制御部１３４は、分散値Tk(α)が入力されたか、分散値Ekが入力されたかを判定する（ステップＳ１３２）。
【００３４】
ステップＳ１３２で、分散値Tk(α)が入力されたと判定された場合、何れかK個の分散値Tk(α) (k∈{0,...,N-1})が変換部１３５に入力される。変換部１３５は、K個の分散値Tk(α) (k∈{0,...,N-1})の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を計算し、値a(m) (m=0,...,M-2)を出力する（ステップＳ１３３）。例えば、前述の式(1)の分散値T0(α), T1(α)が変換部１３５に入力された場合、変換部１３５は、分散値T0(α)が含むv(1), v(2),..., v(M-2)と分散値T1(α)が含むv(0)とを用い、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を計算する。
復元部１３６には、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)と、入力部１３１に入力された分散値Tk(α)の何れかが含む値a(M-1)とが入力される。復元部１３６は、これらを用いてα=f(a(0),...,a(M-1))を計算し、得られた値αを出力する（ステップＳ１３４）。例えば、写像y=f(y(0),...,y(M-1))がy=y(0)+y(1)...+y(M-1) (mod μ)である場合、復元部１３６はα=a(0)+a(1)+...+a(M-1) (mod μ)を計算し、それによって得られた値αを出力する。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【００３５】
一方、ステップＳ１３２で、分散値Ekが入力されたと判定された場合、K個の分散値Ek(k∈{0,...,N-1})が復元部１３６に入力される。復元部１３６は、K個の分散値Ek={e(k,0),...,e(k,Nk-1)} (k∈{0,...,N-1})の要素からなるM個の値e(0),...,e(M-1)を得、ε=f(e (0),...,e(M-1))を計算し、その結果εを出力する（ステップＳ１３６）。簡単な例として、復元部１３６に２個の分散値E0=υ・S0(α)=(υ・a(1), υ・a(2),..., υ・a(M-2), υ・a(M-1))、及びE1=υ・S1(α)=(υ・a (0), υ・a (2),..., υ・a (M-2), a(M-1))が入力された場合、復元部１３６は、これらからυ・a (0), υ・a(1), υ・a(2),..., υ・a(M-2), υ・a(M-1)を得、ε=f(υ・a (0), υ・a(1), υ・a(2),..., υ・a(M-2), υ・a(M-1))を計算する。結果εは出力部１３２に入力され、そこから出力される（ステップＳ１３７）。
【００３６】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。すなわち、本形態の分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1))を構成する要素v(i,0), v(i,1),...,v(i,Ni-1)の少なくとも一部はv(m) (m=0,...,M-2)の何れかである。したがって、集合Gの要素のみからなる従来の分散値に比べて分散値のデータ量を削減できる。分散値のデータ量をどの程度削減できるかは、v(m)のデータ量と集合Gの要素のデータ量との違いに依存する。例えば、M-1個の値v(m) (m=0,...,M-2)のデータ量の合計値がM-1個の集合Gの要素のデータ量の合計値よりも小さいのであれば、本形態の分散値の総データ量は、従来の秘密分散方式の分散値の総データ量よりも小さくなる。例えば、v(m)それぞれのデータ量が集合Gの要素のデータ量よりも小さければ、本形態の方式での分散値の総データ量は、従来の秘密分散方式の分散値の総データ量よりも小さくなる。v(m)それぞれのデータ量が集合Gの要素のデータ量に対して無視できる程度に小さいのであれば、分散値Ti(α)それぞれのデータ量は集合Gの１個の要素のデータ量と同程度となる。
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【００３７】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は第１実施形態の変形例であり、同一の値v(m)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では第１実施形態との相違点を中心に説明する。第１実施形態と共通する処理部やステップには第１実施形態と同じ参照符号を用い、説明を簡略化する。
第２実施形態では、M, N, Rが2以上の整数であり、Ni,r(i=0,...,N-1, r=0,...,R-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を値y(M-1)に移す写像である。本形態の集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例は、第１実施形態で説明した集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例と同じである。M≦Nであってもよいし、M≧Nであってもよい。M≧Rであってもよいし、M≦Rであってもよい。N≧Rであってもよいし、N≦Rであってもよい。
【００３８】
第２実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、M-1個の値v(m) (m=0,...,M-2)を選択し、rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得、集合Gの要素である値αrに対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を得、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1)) (i=0,...,N-1, r=0,...,R-1)を得る。ただし、集合Ar={ar(0),...,ar(M-1)}の部分集合がSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)であり、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個がar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}であり、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)がar(i, qi,r)=ar(M-1)である。同一の「rとv(m)との組み合わせ(r, v(m))」には同一の「z(r, v(m))」が対応する。z(r, v(m))と「rとv(m)との組み合わせ(r, v(m))」とは一対一で対応してもよいし、しなくてもよい。
【００３９】
本形態のデータ復元装置は、分散値Ti(αr) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,...,M-2)を得、値ar(m) (m=0,...,M-2)と分散値Ti(αr)の何れかが含む値ar(M-1)とを用いてαr=f(ar(0),...,ar(M-1))を得る。
【００４０】
本形態の分散データ変換装置のそれぞれは、分散値Ti(αr) (r=0,...,R-1)に含まれるvｒ’(i, ni,r’) (r’∈{0,...,R-1})について値ar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1})を得、得られた値ar(i, ni,r) (ni,r∈{0,...,Ni,r-1})とvr(i, qi,r)=ar(M-1) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)であるar(i, qi,r)=vr(i, qi,r)∈Ti(αr)との少なくとも何れかを含むSi(αr)={ar(i,0),...,ar(i,Ni,r-1)}を変換分散値として得る。このように得られた変換分散値Si(αr)は、秘密計算の入力値として用いられる。
【００４１】
本形態において好ましくは、M-1個の値v(m) (m=0,...,M-2)のデータ量の合計値は、M-1個の集合Gの要素のデータ量の合計値よりも小さい。より好ましくは、値v(m)それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【００４２】
＜構成＞
図１に例示するように、第２実施形態の秘密分散システム２は、データ分散装置２１０、N個の分散データ変換装置２２０−ｉ（i=0,...,N-1）、及びデータ復元装置２３０を有する。データ分散装置２１０は、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置２２０−ｉ（i=0,...,N-1）に対して情報の提供が可能である。N個の分散データ変換装置２２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置２３０に対して情報の提供が可能である。
【００４３】
図２Ａに例示するように、本形態のデータ分散装置２１０は、入力部１１１、出力部１１２、メモリ１１３、分割部２１１、制御部２１４、選択部１１５、変換部２１６、計算部２１７、及び分散値生成部２１８を有する。本形態のデータ分散装置２１０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ分散装置２１０は、制御部２１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００４４】
図２Ｂに例示するように、本形態のデータ復元装置２３０は、入力部１３１、出力部１３２、メモリ１３３、制御部２３４、変換部２３５、復元部２３６、及び結合部２３７を有する。本形態のデータ復元装置２３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ復元装置２３０は、制御部２３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００４５】
図３に例示するように、本形態の分散データ変換装置２２０−ｉ (i=0,...,N-1)は、入力部１２１−ｉ、出力部１２２−ｉ、メモリ１２３ａ−ｉ、記憶部１２３ｂ−ｉ，１２３ｃ−ｉ、制御部２２４−ｉ、変換部２２５−ｉ、変換分散値生成部２２６−ｉ、及び秘密計算部２２７−ｉを有する。本形態の分散データ変換装置２２０−ｉは、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態の分散データ変換装置２２０−ｉは、制御部２２４−ｉの制御のもとで各処理を実行する。入力部１２１−ｉに入力されたデータや各処理で得られたデータはメモリ１２３ａ−ｉや記憶部１２３ｂ−ｉに格納され、メモリ１２３ａ−ｉや記憶部１２３ｂ−ｉに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００４６】
＜データ分散処理＞
図７に例示するように、データ分散装置２１０（図２Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=0,...,R-1)に分割し、R個の値αr ∈G (r=0,...,R-1)を出力する（ステップＳ２１１）。例えば、集合Gが加法群{0,1,...,μ-1}であってα≧μの場合、分割部２１１は、例えばRが最小となるようにα=α0+μ・α1+...+μR-1・αR-1となる0以上μ-1以下のR個の値α0,α1,...,αR-1∈{0,1,...,μ-1}を求め、値α0,α1,...,αR-1を出力する。
【００４７】
選択部１１５は、M-1個の値v(m) (m=0,...,M-2)を選択し、値v(m) (m=0,...,M-2)を出力する（ステップＳ１１２）。例えばM=3であれば、選択部１１５は2個の値v(0), v(1)を選択し、値v(0), v(1)を出力する。
【００４８】
値v(m) (m=0,...,M-2)は変換部２１６に入力される。変換部２１６は、rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を生成し、当該(M-1)×R個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を出力する（ステップＳ２１３）。例えばM=3であれば、変換部２１６は、ar(0)=P(z(r, v(0))), ar(1)=P(z(r, v(1))) (r=0,...,R-1)を出力する。なお、P(x)が擬似乱数生成関数の場合、値ar(m)は擬似乱数となる。
【００４９】
分割部２１１から出力されたR個の値αr ∈G (r=0,...,R-1)と、変換部２１６から出力された(M-1)×R個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)とは計算部２１７に入力される。計算部２１７は、これらの値αr，ar(m) (r=0,...,R-1, m=0,...,M-2)から、各値αrに対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を生成し、当該R個のar(M-1) (r=0,...,R-1)を出力する（ステップＳ２１４）。例えば、写像g(y, y(0),...,y(M-2))がy(M-1)=y-y(0)-y(1)...-y(M-2) (mod μ)である場合、計算部２１７はar(M-1)=αr-ar(0)-ar(1)...-ar(M-2) (mod μ)を計算し、それによって得られた値ar(M-1)を出力する。この例においてM=3であれば、計算部２１７は、ar(2)=αr-ar(0)-ar(1) (mod μ)を計算し、それによって得られた値ar(2) (r=0,...,R-1)を出力する。
【００５０】
選択部１１５から出力されたM-1個の値v(m) (m=0,...,M-2)と計算部２１７から出力された値ar(M-1) (r=0,...,R-1)は、分散値生成部２１８に入力される。分散値生成部２１８は、これらの値ar(M-1)，v(m) (r=0,...,R-1, m=0,...,M-2)を用い、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1)) (i=0,...,N-1, r=0,...,R-1)を生成し、当該分散値Ti(αr)を出力する（ステップＳ２１５）。
ここで、集合Ar={ar(0),...,ar(M-1)}の部分集合をSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)とおく。分散値Ti(αr)を構成する要素のうち、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個（好ましくは、R個のv0(i, ni,0),...,vR-1(i, ni,R-1)の何れかのみ）が、ar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}である。例えば、a0(i, ni,0)≠a0(M-1)である(i, ni,0) (ni,0∈{0,...,Ni,0-1})に対応するv0(i, ni,0)が、ar(i, ni,r)=P(z(r, v0(i, ni,0)))を満たすv0(i, ni,0)∈{v(0),...,v(M-2)}とされる。ar(i, ni,r)≠ar(M-1)である(i, ni,r)に対応するv0(i, ni,0),...,vR-1(i, ni,R-1)のうちvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}以外の値は、例えば、空値であってもよいし、rやR等のパラメータであってもよい。分散値Ti(αr)を構成する要素のうち、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)がar(i, qi,r)=ar(M-1)である。
以下にM=N=3, K=2， Ni,r=2，G={0,1,...,μ-1}の場合の分散値Ti(αr) (i=0,...,2, r=0,...,R-1)を例示する。ただしφは空値を示す。
T0(α0)=(v(0), v(1)), T1(α0)=(v(1), a0(2)), T2(α0)=(a0(2) ,v(0)),
T0(α1)=φ, T1(α1)=(a1(2)), T2(α1)=(a1(2))，
T0(α2)=φ，T1(α2)=(a2(2))，T2(α2)=(a2(2)),...,
T0(αR-1)=φ，T1(αR-1)=(aR-1(2))，T2(αR-1)=(aR-1(2))      ...(2)
【００５１】
分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1)) (i=0,...,N-1, r=0,...,R-1)は出力部１１２に入力され、出力部１１２は分散値Ti(αr) (i=0,...,N-1, r=0,...,R-1)を出力する（ステップＳ２１６）。出力された分散値Ti(αr) (i=0,...,N-1, r=0,...,R-1)のそれぞれは、分散データ変換装置２２０−ｉ (i=0,...,N-1)のそれぞれに提供される。例えば、分散値Ti(αr)は、ネットワーク等を経由して、対応する分散データ変換装置２２０−ｉ（図３）に送信される。分散データ変換装置２２０−ｉ(i=0,...,N-1)のそれぞれに提供された分散値分散値Ti(αr)は入力部１２１−ｉに入力され、記憶部１２３ｂ−ｉに格納される。
【００５２】
＜分散データ変換処理／分散値出力処理＞
分散データ変換装置２２０−ｉ(i=0,...,N-1)が実行する分散データ変換処理及び分散値出力処理を説明する。これらの処理は、すべての分散データ変換装置２２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうちK個(K≦N)の分散データ変換装置２２０−ｋ（k∈{0,...,N-1}）のみで実行されてもよい。
図８に例示するように、分散データ変換装置２２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行わずに分散値を出力する場合、制御部２２４−ｉは分散値の変換を行わずに分散値Ti(αr)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ２２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは、格納している分散値Ti(αr)を読み出して出力する。分散値Ti(αr)は出力部１２２−ｉに送られ、出力部１２２−ｉは分散値Ti(αr)を出力する（ステップＳ２２２−ｉ）。出力された分散値Ti(αr)はデータ復元装置２３０に提供される。例えば、分散値Ti(αr)は、ネットワーク等を経由してデータ復元装置２３０に送信される。分散データ変換装置２２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する場合には、分散データ変換処理及び分散値出力処理を実行するすべての分散データ変換装置２２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する。
【００５３】
一方、分散データ変換装置２２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行う場合、制御部２２４−ｉは、分散値の変換を行うために分散値Ti(αr)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ２２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは分散値Ti(αr)を読み出す。
読み出された分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1))を構成する要素のうち、vｒ’(i, ni,r’)∈{v(0),...,v(M-2)} (r’∈{0,...,R-1})は変換部２２５−ｉに入力される。読み出された分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1))を構成する要素がvr(i, qi,r)=ar(M-1) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)であるar(i, qi,r)=vr(i, qi,r)∈Ti(αr)を含む場合、当該ar(i, qi,r)は変換分散値生成部２２６−ｉに入力される。
【００５４】
変換部２２５−ｉは、入力された値vｒ’(i, ni,r’) (r’∈{0,...,R-1})からar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)を計算し、当該値ar(i, ni,r)を出力する（ステップＳ２２３−ｉ）。
【００５５】
変換分散値生成部２２６−ｉには、変換部２２５−ｉで得られた値ar(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)と、記憶部１２３ｂ−ｉから読み出されたvr(i, qi,r)=ar(i, qi,r)=ar(M-1) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)と（存在するのであれば）が入力される。変換分散値生成部２２６−ｉは、入力された値からなる変換分散値Si(αr)={ar(i,0),...,ar(i,Ni,r-1)}を生成し（ステップＳ２２４−ｉ）、当該変換分散値Si(αr)を記憶部１２３ｃ−ｉに格納する（ステップＳ２２５−ｉ）。
例えば式(2)の例では、変換分散値Si(αr)(i=0,1,2, r=0,...,R-1)は以下のようになる。
Si(α0)=(a0(i mod 3), a0(i+1 mod 3)) (i=0,1,2),
S0(αθ)=φ, S1(αθ)=S2(αθ)=aθ(2) (θ=1,...,R-1)  ...(3)
【００５６】
秘密計算部２２７−ｉは、所定の契機で記憶部１２３ｃ−ｉに格納された変換分散値Si(αr)={ar(i,0),...,ar(i,Ni,r-1)}を読み出し、変換分散値Si(αr)を入力とした秘密計算を実行し、その演算結果である分散値Ei,r={er(i,0),...,er (i,Ni,r-1)}を出力する。分散値Ei,rは出力部１２２−ｉから出力され、データ復元装置２３０に提供される。例えば、分散値Ei,rは、ネットワーク等を経由して、データ復元装置２３０に送信される。
【００５７】
＜データ復元処理＞
図９に例示するように、データ復元装置２３０（図２Ｂ）の入力部１３１に、rのそれぞれについて、何れかK個の分散値Tk(αr) (k∈{0,...,N-1})、又は、何れかK個の分散値Ek,r={er(k,0),...,er(k,Nk-1)} (k∈{0,...,N-1})が入力される（ステップＳ２３１）。制御部２３４は、分散値Tk(αr)が入力されたか、分散値Ek,rが入力されたかを判定する（ステップＳ２３２）。
【００５８】
ステップＳ２３２で分散値Tk(αr)が入力されたと判定された場合、rのそれぞれについて、何れかK個の分散値Tk(αr) (k∈{0,...,N-1}, r=0,...,R-1)が変換部２３５に入力される。変換部２３５は、分散値Ti(αr) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,...,M-2)を計算し、値ar(m) (r=0,...,R-1, m=0,...,M-2)を出力する（ステップＳ２３３）。例えば、式(2)の分散値T0(αr), T1(αr) (r=0,...,R-1)が変換部２３５に入力された場合、変換部２３５は、T0(α0)=(v(0), v(1))が含むv(0), v(1)を用いて、rのそれぞれに対して2個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,1)を計算する。
復元部２３６には、rのそれぞれについてM-1個の値ar(m) (r=0,...,R-1, ｍ=0,...,M-2)と、入力部１３１に入力された分散値Tk(αr)の何れかが含む値ar(M-1) (r=0,...,R-1)とが入力される。復元部２３６は、これらを用いてαr=f(ar(0),...,ar(M-1))を計算し、得られた値αr (r=0,...,R-1)を出力する（ステップＳ２３４）。例えば、式(2)の分散値Tk(αr)の場合、復元部２３６はαr=ar(0)+ar(1)+a(2) (mod μ)を計算し、それによって得られた値αr (r=0,...,R-1)を出力する。
値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr (r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。例えば、前述の分割部２１１で、値αがα=α0+μ・α1+...+μR-1・αR-1を満たす値α0,α1,...,αR-1∈{0,1,...,μ-1}に分割されていた場合、結合部２３７は、R個の値αr(r=0,...,R-1)から値α=α0+μ・α1+...+μR-1・αR-1を計算する。値αは出力部１３２に入力され、出力部１３２は値αを出力する（ステップＳ２３６）。
【００５９】
一方、ステップＳ２３２で、分散値Ek,rが入力されたと判定された場合、rのそれぞれについてK個の分散値Ek,r(k∈{0,...,N-1})が復元部２３６に入力される。復元部２３６は、rのそれぞれについて分散値Ek,r={er(k,0),...,er(k,Nk,r-1)} (r=0,...,R-1, k∈{0,...,N-1})の要素からなるM個の値er(0),...,er(M-1)を得、εr=f(er(0),...,er(M-1))を計算し、その結果εr (r=0,...,R-1)を出力する（ステップＳ２３７）。
R個の値εr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値εr(r=0,...,R-1)を結合して値ε∈Gを生成し、当該値εを出力する（ステップＳ２３８）。例えば、前述の分割部２１１で、値αがα=α0+μ・α1+...+μR-1・αR-1を満たす値α0,α1,...,αR-1∈{0,1,...,μ-1}に分割されていた場合、結合部２３７は、R個の値εr(r=0,...,R-1)から値ε=ε0+μ・ε1+...+μR-1・εR-1を計算する。値εは出力部１３２に入力され、出力部１３２は値εを出力する（ステップＳ２３９）。
【００６０】
＜本形態の特徴＞
本形態でも従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減できる。
すなわち、本形態の分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1))を構成する要素vr(i,0), vr(i,1),...,vr(i,Ni,r-1)の少なくとも１個はv(m) (m=0,...,M-2)の何れかである。したがって、集合Gの要素のみからなる従来の分散値に比べて分散値のデータ量を削減できる。第１実施形態で説明したように、分散値のデータ量をどの程度削減できるかは、v(m)のデータ量と集合Gの要素のデータ量との違いに依存する。
【００６１】
一例を挙げると、非特許文献２に記載された加法的秘密分散では、データ分散時に、データ分散装置がSi(ar)=(ai,ai+1 mod 3)（i=0,1,2）を生成して分散データ変換装置iに送信し、分散データ変換装置iはSi(ar)を記憶する。データ復元時には、データ復元装置は何れか２つの分散データ変換装置から合わせてa0,a1,a2を受信する。この場合、各rについて、データ分散時の通信データ量および記憶データ量は6×L、データ復元時の通信データ量は3×Lとなる。
一方、本形態でM=N=3, K=2， Ni,r=2，G={0,1,...,μ-1}とし（非特許文献２と同等の環境）、値v(0), v(1)のデータ量を無視できるとすると、各rについて、データ分散時の通信データ量および記憶データ量は2×Lとなり、上記加法的秘密分散と比べてデータ量は1/3に削減されることが分かる。同様な環境での本形態のデータ復元時の通信データ量はLとなり、上記加法的秘密分散と比べてデータ量が1/3程度に削減されることが分かる。
【００６２】
さらに本形態では、各値v(m)からR個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1)を生成するため、複数の値αr(r=0,...,R-1)の秘密分散を行う場合のデータ量をさらに削減できる。また、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとのαやαrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【００６３】
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。本形態は第１実施形態の変形例であり、同一の値v(n)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では上述した実施形態との相違点を中心に説明する。上述した実施形態と共通する処理部やステップには上述した実施形態と同じ参照符号を用い、説明を簡略化する。
【００６４】
第３実施形態では、N, Rが2以上の整数であり、Ni(i=0,...,N-1)が1以上N-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(N-1))が集合Gの要素であるN個の値y(0),...,y(N-1)からなる部分集合(y(0),...,y(N-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(N-2))がy=f(y(0),...,y(N-1))を満たす集合Gの要素であるN個のy, y(0),...,y(N-2)からなる部分集合(y, y(0),...,y(N-2))を値y(N-1)に移す写像である。本形態の集合G及び写像P(x)の具体例は、第１実施形態で説明した集合G及び写像P(x)の具体例と同じである。本形態の写像y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例は以下の通りである。例えば集合Gが加法群なのであれば、y=y(0)+...+y(N-1)∈G，y=-y(0)-...-y(N-1)∈G，y=y(0)-y(1)+y(2)-...+y(N-1)∈Gなどを写像y=f(y(0),...,y(N-1))とすることができる。例えば、集合Gがμを法とした剰余類の代表元からなる加法群なのであれば、例えばy=y(0)+...+y(N-1) (mod μ)などを写像y=f(y(0),...,y(N-1))とすることができる。集合Gが乗法群なのであれば、例えばy=y(0)・...・y(N-1)∈G，y={y(0)}-1・...・y{(N-1)}-1∈G，y=y(0)・{y(1)}-1・y(2)・{y(3)}-1・...・y(N-1)などを写像y=f(y(0),...,y(N-1))とすることができる。写像g(y, y(0),...,y(N-2))は写像y=f(y(0),...,y(N-1))に対して上記の関係を満たす。例えば、写像y=f(y(0),...,y(N-1))がy=y(0)+...+y(N-1) (mod μ)である場合、写像g(y, y(0),...,y(N-2))はy(N-1)=y-y(0)-y(1)...-y(N-2) (mod μ)である。N≦Rであってもよいし、N≧Rであってもよい。
【００６５】
第３実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、N-1個の値v(n) (n=0,...,N-2)を選択し、rと値v(n)とに対応する値をz(r, v(n))とし、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を得、集合Gの要素である値αr (r=0,...,R-1)に対して値ar(N-1)=g(αr, ar(0),...,ar(N-2))を得、値v(n)を分散値Tn(β) (n=0,...,N-2)とし、値ar(N-1)を分散値TN-1(αr)とする。同一の「rとv(n)との組み合わせ(r, v(n))」には同一のz(r, v(n))が対応する。z(r, v(n))と「rとv(n)との組み合わせ(r, v(n))」とは一対一で対応してもよいし、しなくてもよい。z(r, v(n))の例は、rと値v(n)とのビット結合値である。分散値Tn(β) (n=0,...,N-2)は、例えばN-1個の分散データ変換装置のそれぞれに提供され、分散値TN-1(αr)は、例えば１個の分散データ変換装置に提供される。
【００６６】
本形態のデータ復元装置は、分散値Tn(β) (n=0,...,N-2)を用いて、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を得、値ar(n) (n=0,...,N-2)と分散値TN-1(αr)=ar(N-1)とを用いてαr=f(ar(0),...,ar(N-1)) (r=0,...,R-1)を得る。
【００６７】
分散値Tn(β) (n=0,...,N-2)の何れかが提供された本形態の分散データ変換装置は、自らに提供された分散値Tn(β)＝v(n)から値ar(n)=P(z(r, v(n))) (r=0,...,R-1)を変換分散値Sn(αr)として得る。このように得られる変換分散値Sn(αr)は、秘密計算の入力値とすることができる。一方、分散値TN-1(αr)が提供された分散データ変換装置は、分散値TN-1(αr)をそのまま変換分散値SN-1(αr)=TN-1(αr)とする。このように得られる変換分散値Si(αr) (i=0,...,N-1)は、秘密計算の入力値として用いられる。
【００６８】
＜構成＞
図１に例示するように、第３実施形態の秘密分散システム３は、データ分散装置３１０、N個の分散データ変換装置３２０−ｉ（i=0,...,N-1）、及びデータ復元装置３３０を有する。データ分散装置３１０は、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置３２０−ｉ（i=0,...,N-1）に対して情報の提供が可能である。N個の分散データ変換装置３２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置３３０に対して情報の提供が可能である。
【００６９】
図１０Ａに例示するように、本形態のデータ分散装置３１０は、入力部１１１、分割部２１１、出力部１１２、メモリ１１３、制御部３１４、選択部３１５、変換部３１６、計算部３１７、及び分散値生成部３１８を有する。本形態のデータ分散装置３１０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ分散装置３１０は、制御部３１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００７０】
図１０Ｂに例示するように、本形態のデータ復元装置３３０は、入力部１３１、出力部１３２、メモリ１３３、制御部３３４、変換部３３５、復元部３３６、及び結合部２３７を有する。本形態のデータ復元装置３３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ復元装置３３０は、制御部３３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００７１】
図１１Ａに例示するように、本形態の分散データ変換装置３２０−ｎ (n=0,...,N-2)は、入力部１２１−ｎ、出力部１２２−ｎ、メモリ１２３ａ−ｎ、記憶部３２３ｂ−ｉ，３２３ｃ−ｎ、制御部３２４−ｎ、変換分散値生成部３２６−ｎ、及び秘密計算部３２７−ｎを有する。図１１Ｂに例示するように、本形態の分散データ変換装置３２０−（Ｎ−１）は、入力部１２１−（Ｎ−１）、出力部１２２−（Ｎ−１）、メモリ１２３ａ−（Ｎ−１）、記憶部３２３ｂ−（Ｎ−１）、制御部３２４−（Ｎ−１）、及び秘密計算部３２７−（Ｎ−１）を有する。本形態の分散データ変換装置３２０−ｉ(i=0,...,N-1)は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態の分散データ変換装置３２０−ｉは、制御部３２４−ｉの制御のもとで各処理を実行する。入力部１２１−ｉに入力されたデータや各処理で得られたデータはメモリ１２３ａ−ｉや記憶部３２３ｂ−ｉに格納され、メモリ１２３ａ−ｉや記憶部３２３ｂ−ｉに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００７２】
＜データ分散処理＞
図１２に例示するように、データ分散装置３１０（図１０Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。
【００７３】
値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=0,...,R-1)に分割し、R個の値αr ∈G (r=0,...,R-1)を出力する（ステップＳ２１１）。
【００７４】
選択部３１５は、N-2個の値v(n) (n=0,...,N-2)を選択し、値v(n) (n=0,...,N-2)を出力する（ステップＳ３１２）。選択部３１５は、逐一、ランダムにN-2個の値v(n) (n=0,...,N-2)選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってN-2個の値v(n) (n=0,...,N-2)を選択してもよい。例えば、選択される値v(n) (n=0,...,N-2)それぞれのデータ量は、集合Gの要素（1個の要素）のデータ量よりも小さい。値v(n) (n=0,...,N-2)それぞれのデータ量は集合Gの要素のデータ量よりも十分小さいことが望ましい。安全性を考慮すると、値v(n)は、値v(n)から生成される値a(n)及びP(x)から値v(n)を特定することが困難となる程度の値（全数探索による攻撃や現在の計算機の性能を考慮すれば、値v(n)は80ビット程度かそれ以上の乱数）とするのが望ましい。
【００７５】
値v(n) (n=0,...,N-2)は変換部３１６に入力される。変換部３１６は、rと値v(n)とに対応する値をz(r, v(n))とし、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を計算し、それによって得られたR×(N-1)個の値ar(n) (r=0,...,R-1, n=0,...,N-2)を出力する（ステップＳ３１３）。P(x)が擬似乱数生成関数の場合、値ar(n)は擬似乱数となる。
【００７６】
分割部２１１から出力されたR個の値αr ∈G (r=0,...,R-1)と変換部３１６から出力されたR×(N-1)個の値ar(n) (r=0,...,R-1, n=0,...,N-2)とは、計算部３１７に入力される。計算部３１７は、これらの値αr, ar(n) (r=0,...,R-1, n=0,...,N-2)から、R個の値ar(N-1)=g(αr, ar(0),...,ar(N-2))∈G (r=0,...,R-1)を計算し、当該値ar(N-1) (r=0,...,R-1)を出力する（ステップＳ３１４）。例えば、写像g(y, y(0),...,y(N-2))がy(N-1)=y-y(0)-y(1)...-y(N-2) (mod μ)である場合、計算部３１７は、ar(N-1)=αr-ar(0)-ar(1)...-ar(N-2) (mod μ)を計算し、それによって得られた値ar(N-1) (r=0,...,R-1)を出力する。
【００７７】
選択部３１５から出力されたN-1個の値v(n) (n=0,...,N-2)と計算部３１７から出力された値ar(M-1) (r=0,...,R-1)とは、分散値生成部３１８に入力される。分散値生成部３１８は、これらの値ar(N-1)，v(n) (n=0,..., N-2)を用い、値v(n)を分散値Tn(β) (n=0,...,N-2)とし、値ar(N-1)を分散値TN-1(αr) (r=0,...,R-1)とする。βは集合β={α0,...,αR-1}を表し、本形態の分散値生成部３１８は、値αr (r=0,...,R-1)の集合β={α0,...,αR-1}に対してN-1個の分散値Tn(β) (n=0,...,N-2)を得る。分散値生成部３１８は、分散値Tn(β)=v(n) (n=0,..., N-2), TN-1(αr)=ar(N-1) (r=0,...,R-1)を出力する（ステップＳ３１５）。
【００７８】
分散値Tn(β) (n=0,..., N-2), TN-1(αr) (r=0,...,R-1)は出力部１１２に入力され、出力部１１２は分散値Tn(β) (n=0,..., N-2), TN-1(αr) (r=0,...,R-1)を出力する（ステップＳ３１６）。出力された分散値Tn(β) (n=0,..., N-2)のそれぞれは、分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれに提供される。出力されたTN-1(αr) (r=0,...,R-1)は分散データ変換装置３２０−（Ｎ−１）に提供される。例えば、各分散値は、ネットワーク等を経由して、対応する分散データ変換装置３２０−ｉ（図１１Ａ及び１１Ｂ）に送信される。分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれに提供された分散値Tn(β)は入力部２２１−ｎに入力され、記憶部３２３ｂ−ｎに格納される。分散データ変換装置３２０−（Ｎ−１）に提供された分散値TN-1(αr)は入力部２２１−（Ｎ−１）に入力され、記憶部３２３ｂ−（Ｎ−１）に格納される。
【００７９】
＜分散データ変換処理／分散値出力処理＞
分散データ変換装置３２０−ｎ(n=0,...,N-2)が実行する分散データ変換処理及び分散値出力処理を説明する。これらの処理は、すべての分散データ変換装置３２０−ｎ(n=0,...,N-1)で実行される。
図１３に例示するように、分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれが分散値の変換を行わずに分散値を出力する場合、制御部３２４−ｎ（図１１Ａ）は分散値の変換を行わずに分散値Tn(β)を読み出す旨を記憶部３２３ｂ−ｎに指示する（ステップＳ３２１−ｎ）。この指示を受けた記憶部３２３ｂ−ｎは、格納している分散値Tn(β)を読み出して出力する。分散値Tn(β)は出力部１２２−ｎに送られ、出力部１２２−ｎは分散値Tn(β)をデータ復元装置３３０に提供する（ステップＳ３２２−ｎ）。例えば、出力部１２２−ｎは、ネットワーク等を経由してデータ復元装置３３０に送信される。分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれが分散値の変換を行わずに分散値を出力する場合には、分散データ変換処理及び分散値出力処理を実行するすべての分散データ変換装置３２０−ｎ(n=0,...,N-2)が分散値の変換を行わずに分散値を出力する。
【００８０】
一方、分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれが分散値の変換を行う場合、制御部３２４−ｎは、分散値の変換を行うために分散値Tn(β)を読み出す旨を記憶部３２３ｂ−ｎに指示する（ステップＳ３２１−ｎ）。この指示を受けた記憶部３２３ｂ−ｎは、格納している分散値Tn(β)を読み出す。分散値Tn(β)は変換分散値生成部３２６−ｎに入力される。
【００８１】
変換分散値生成部３２６−ｎは、分散値Tn(β)＝v(n)から値ar(n)=P(z(r, v(n))) (r=0,...,R-1)を計算し、それによって得られたR個の値ar(n) (r=0,...,R-1)を変換分散値Sn(αr) (r=0,...,R-1)とする（ステップＳ３２３−ｎ）。変換分散値生成部３２６−ｎは変換分散値Sn(αr)=ar(n) (r=0,...,R-1)を記憶部３２３ｃ−ｎに格納する（ステップＳ３２５−ｎ）。
【００８２】
秘密計算部３２７−ｎは、所定の契機で記憶部３２３ｃ−ｎに格納された変換分散値Sn(αr)=ar(n) (r=0,...,R-1)を読み出し、変換分散値Sn(αr)を入力とした秘密計算を実行し、その演算結果である分散値En,rを出力する。分散値En,rは出力部１２２−ｎから出力され、ネットワーク等を経由して、データ復元装置３３０に提供される。簡単な秘密計算の例は、変換分散値Sn(αr)=ar(n)の加法群Gでのスカラー倍算であり、この場合にはEi,r=υ・Sn(αr)となる。
【００８３】
分散データ変換装置３２０−（Ｎ−１）が実行する分散データ変換処理及び分散値出力処理を説明する。
分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれが分散値の変換を行わずに分散値を出力する場合、分散データ変換装置３２０−（Ｎ−１）（図１１Ｂ）の制御部３２４−（Ｎ−１）は、記憶部３２３ｂ−（Ｎ−１）から分散値TN-1(αr) (r=0,...,R-1)を読み出し、出力部１２２−（Ｎ−１）に送る。出力部１２２−（Ｎ−１）は、分散値TN-1(αr) (r=0,...,R-1)を出力する。分散値TN-1(αr) (r=0,...,R-1)は、ネットワーク等を経由して、データ復元装置３３０に提供される。
一方、分散データ変換装置３２０−ｎ(n=0,...,N-2)のそれぞれが分散値の変換を行う場合であっても、分散データ変換装置３２０−（Ｎ−１）は分散値TN-1(αr) (r=0,...,R-1)を変更しない。秘密計算部３２７−（Ｎ−１）は、所定の契機で記憶部３２３ｂ−（Ｎ−１）に格納された分散値TN-1(αr) (r=0,...,R-1)を読み出し、分散値TN-1(αr)を入力とした秘密計算を実行し、その演算結果である分散値EN-1,rを出力する。分散値EN-1,rは出力部１２２−（Ｎ−１）から出力され、ネットワーク等を経由して、データ復元装置３３０に提供される。簡単な秘密計算の例では、分散値EN-1,r=υ・TN-1(αr) (r=0,...,R-1)とされる。
【００８４】
＜データ復元処理＞
図１４に例示するように、データ復元装置３３０（図１０Ｂ）の入力部１３１に、分散値Tn(β) (n=0,..., N-2), TN-1(αr) (r=0,...,R-1)、又は、分散値Ei,r(i=0,...,N-1, r=0,...,R-1)が入力される。（ステップＳ３３１）。制御部３３４は、分散値Tn(β), TN-1(αr)が入力されたか、分散値Ei,rが入力されたかを判定する（ステップＳ３３２）。
【００８５】
ステップＳ３３２で、分散値Tn(β), TN-1(αr)が入力されたと判定された場合、分散値Tn(β) (n=0,..., N-2)が変換部３３５に入力される。変換部３３５は、分散値Tn(β)=v(n) (n=0,...,N-2)を用いて、rのそれぞれに対してN-1個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を計算し、値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)を出力する（ステップＳ３３３）。
復元部３３６には、R×(N-1)個の値ar(n)=P(z(r, v(n))) (r=0,...,R-1, n=0,...,N-2)と、入力部１３１に入力されたR個のTN-1(αr)=ar(N-1) (r=0,...,R-1)とが入力される。復元部３３６は、値ar(n) (n=0,...,N-2)と分散値TN-1(αr)=ar(N-1)とを用いてαr=f(ar(0),...,ar(N-1)) (r=0,...,R-1)を計算し、それによって得られたR個の値αr (r=0,...,R-1)を出力する（ステップＳ３３４）。例えば、写像y=f(y(0),...,y(N-1))がy=y(0)+y(1)...+y(N-1) (mod μ)である場合、復元部３３６はαr=ar(0)+ar(1)+...+ar(N-1) (mod μ)を計算し、それによって得られた値αr (r=0,...,R-1)を出力する。R個の値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr(r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ３３５）。例えば、前述の分割部２１１で、値αがα=α0+μ・α1+...+μR-1・αR-1を満たす値α0,α1,...,αR-1∈{0,1,...,μ-1}に分割されていた場合、結合部２３７は、R個の値αr(r=0,...,R-1)から値α=α0+μ・α1+...+μR-1・αR-1を計算する。値αは出力部１３２に入力され、出力部１３２は値αを出力する（ステップＳ１３５）。
【００８６】
一方、ステップＳ３３２で、分散値Ei,rが入力されたと判定された場合、分散値Ei,r(i=0,...,N-1, r=0,...,R-1)が復元部３３６に入力される。復元部３３６は、分散値Ei,r(i=0,...,N-1, r=0,...,R-1)を用いてεr=f(E0,r,..., EN-1,r) (r=0,...,R-1)を計算し、それによって得られたR個の値εr (r=0,...,R-1)を出力する（ステップＳ３３６）。例えば、写像y=f(y(0),...,y(N-1))がy=y(0)+y(1)...+y(N-1) (mod μ)である場合、復元部３３６はεr=E0,r+E1,r+...+EN-1,r (mod μ)を計算し、それによって得られた値εr (r=0,...,R-1)を出力する。
R個の値εr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値εr(r=0,...,R-1)を結合して値ε∈Gを生成し、当該値εを出力する（ステップＳ３３７）。例えば、前述の分割部２１１で、値αがα=α0+μ・α1+...+μR-1・αR-1を満たす値α0,α1,...,αR-1∈{0,1,...,μ-1}に分割されていた場合、結合部２３７は、R個の値εr(r=0,...,R-1)から値ε=ε0+μ・ε1+...+μR-1・εR-1を計算する。値εは出力部１３２に入力され、出力部１３２は値εを出力する（ステップＳ１３７）。
【００８７】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。
比較のため以下の単純な加法的秘密分散を想定する。この単純な加法的秘密分散では、データ分散時に、R個の値ar∈G (r=0,1,…,R-1)をrのそれぞれについてN個ずつの分散値S(r,i)∈G (r=0,1,…,R-1, i=0,...,N-1)に加法的秘密分散し、R個の分散値S(0,i),...,S(R-1,i)をi番目の分散データ変換装置に送信し、各分散データ変換装置はそれらを格納する。データ復元時には、データ復元装置が全ての分散データ変換装置から分散値S(r,i)∈G (r=0,1,…,R-1, i=0,...,N-1)を受信し、R個の値ar∈G (r=0,1,…,R-1)を復元する。集合Gの要素のデータ量をLとおくと、データ分散時の通信データ量及び記憶データ量、並びにデータ復元時の通信データ量は全てN×R×Lとなる。
【００８８】
これに対し、本形態ではデータ分散時に、データ分散装置３１０が分散値Tn(β)=v(n) (n=0,...,N-2)及びTN-1(αr)=ar(N-1)を生成し、分散データ変換装置３２０−ｎに分散値Tn(β)=v(n)を送信し、分散データ変換装置３２０−（Ｎ−１）に分散値TN-1(αr)=ar(N-1)を送信する。分散データ変換装置３２０−ｎは分散値Tn(β)=v(n)を格納し、分散データ変換装置３２０−（Ｎ−１）は分散値TN-1(αr)=ar(N-1)を格納する。データ復元時には、データ復元装置３３０が、分散値Tn(β)=v(n) (n=0,...,N-2)及びTN-1(αr)=ar(N-1)を受信し、R個の値ar∈G (r=0,1,…,R-1)を復元する。値v(n)のデータ量をνとおき、集合Gの要素のデータ量をLとおくと、データ分散時の通信データ量及び記憶データ量、並びにデータ復元時の通信データ量は全て(N-1)×ν+R×Lとなる。従って(N-1)×ν+R×L＜N×R×Lであれば、すなわち、N-1個の分散値Tn(β) (n=0,...,N-2)のデータ量の合計値(N-1)×νが、R×(N-1)個の集合Gの要素のデータ量の合計値よりも小さいのであれば、本形態の通信データ量や記憶データ量は、上述の単純な加法的秘密分散の通信データ量や記憶データ量よりも小さくなる。例えば、値v(n)それぞれのデータ量は集合Gの要素のデータ量よりも小さいのであれば、本形態の通信データ量や記憶データ量は、上述の単純な加法的秘密分散の通信データ量や記憶データ量よりも小さくなる。例えば、値v(n)それぞれのデータ量が値ar∈Gのデータ量に対して無視できるほどの大きさなのであれば、形態の通信データ量や記憶データ量は、上述の単純な加法的秘密分散の通信データ量や記憶データ量の1/N程度となる。
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【００８９】
なお、本形態ではデータ分散時に、データ分散装置３１０が分散データ変換装置３２０−ｎに分散値Tn(β)=v(n)を送信し、分散データ変換装置３２０−（Ｎ−１）に分散値TN-1(αr)=ar(N-1)を送信することとした。しかしながら、データ分散時に、データ分散装置３１０が分散データ変換装置３２０−ｎにさらにRの値やr=0,...,R-1などのパラメータを送信してもよい。また、本形態ではRが２以上であるとしたが、R=1としてもよい。その場合の構成は第１実施形態でNi=0とすることで得られる。
〔第４実施形態〕
次に、本発明の第４実施形態を説明する。本形態は第１実施形態の変形例であり、第１実施形態の分散値が含んでいた集合Gの要素をさらに秘密分散し、分散値のデータ量をさらに削減するものである。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
【００９０】
本形態では、M, N, Kが2以上の整数であり、K≦Nであり、Ni (i=0,...,N-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を値y(M-1)に移す写像である。本形態の集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例は、第１実施形態で説明した集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例と同じである。M≦Nであってもよいし、M≧Nであってもよい。M≧Rであってもよいし、M≦Rであってもよい。N≧Rであってもよいし、N≦Rであってもよい。K＜Nであってもよいし、K=Nであってもよい。
【００９１】
第４実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、M-1個の値v(m) (m=0,...,M-2)を選択し、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、集合Gの要素である値αに対して値a(M-1)=g(α, a(0),...,a(M-2))を得、(K, N)閾値秘密分散法Uに従って値a(M-1)を秘密分散してN個の分散値Ui(a(M-1)) (i=0,...,N-1)を得、値αの分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1))) (i=0,...,N-1)を得る。
【００９２】
ただし、集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)が空値である。また、どのような方式が(K, N)閾値秘密分散法Uとして用いられてもよいが、１個の分散値Ui(a(M-1))のデータ量が集合Gの１個の要素のデータ量よりも小さい方式が用いられることの望ましい。例えば、参考文献１「H.Krawczyk, “Secret sharing made short,” CRYPTO’93, pp.136-146, 1993.」に記載された方式を(K, N)閾値秘密分散法Uとして用いることが望ましい（詳細は後述）。参考文献１の方式の場合、１個の分散値Ui(a(M-1))のデータ量が集合Gの１個の要素のデータ量の１／Ｋ程度となる。
【００９３】
本形態のデータ復元装置は、分散値Ti(α) (i=0,...,N-1)の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を得、分散値Ti(α) (i=0,...,N-1)に含まれるK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から値a(M-1)を得、得られた値a(m) (m=0,...,M-2)と値a(M-1)とを用いてα=f(a(0),...,a(M-1))を得る。
【００９４】
本形態の分散データ変換装置のそれぞれは、分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1))) (i=0,...,N-1)に含まれる、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)∈Ti(α)について値a(i, ni)=P(v(i, ni))を得、分散値Ti(α) (i=0,...,N-1)に含まれるK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から値a(M-1)を得、得られた値a(i, ni)と値a(M-1)との少なくとも何れかを含むSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)を変換分散値として得る。このような変換分散値Si(α)は、秘密計算の入力値として用いられる。
【００９５】
本形態において好ましくは、a(i,j)≠a(M-1)である(i,j)に対するNi-1個のv(i,j)のデータ量とUi(a(M-1))のデータ量との合計値は、Ni個の集合Gの要素のデータ量の合計値よりも小さい。より好ましくは、値v(m)それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも小さく、なおかつ、分散値Ui(a(M-1))それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも小さい。
【００９６】
＜構成＞
図１５に例示するように、第４実施形態の秘密分散システム４は、データ分散装置４１０、N個の分散データ変換装置４２０−ｉ（i=0,...,N-1）、及びデータ復元装置４３０を有する。データ分散装置４１０は、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置４２０−ｉ（i=0,...,N-1）に対して情報の提供が可能である。N個の分散データ変換装置４２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置４３０に対して情報の提供が可能である。分散データ変換装置４２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、他の分散データ変換装置４２０−ｉ’ （i’=i, i’∈{0,...,N-1}）に対して情報の提供が可能である。
【００９７】
図１６Ａに例示するように、本形態のデータ分散装置４１０は、入力部１１１、出力部１１２、メモリ１１３、制御部４１４、選択部１１５、変換部１１６、計算部１１７、内部分散部４１８、及び分散値生成部４１８を有する。本形態のデータ分散装置４１０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ分散装置４１０は、制御部４１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００９８】
図１６Ｂに例示するように、本形態のデータ復元装置４３０は、入力部１３１、出力部１３２、メモリ１３３、制御部４３４、変換部１３５、復元部１３６、及び内部復元部４３７を有する。本形態のデータ復元装置４３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ復元装置４３０は、制御部４３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【００９９】
図１７に例示するように、本形態の分散データ変換装置４２０−ｉ (i=0,...,N-1)は、入力部１２１−ｉ、出力部１２２−ｉ、メモリ１２３ａ−ｉ、記憶部１２３ｂ−ｉ，１２３ｃ−ｉ、制御部４２４−ｉ、変換部１２５−ｉ、変換分散値生成部４２６−ｉ、内部復元部４２７−ｉ、及び秘密計算部１２７−ｉを有する。本形態の分散データ変換装置４２０−ｉは、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態の分散データ変換装置４２０−ｉは、制御部４２４−ｉの制御のもとで各処理を実行する。入力部１２１−ｉに入力されたデータや各処理で得られたデータはメモリ１２３ａ−ｉや記憶部１２３ｂ−ｉ，１２３ｃ−ｉに格納され、メモリ１２３ａ−ｉや記憶部１２３ｂ−ｉ，１２３ｃ−ｉに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１００】
＜データ分散処理＞
図１８に例示するように、データ分散装置４１０（図１６Ａ）の入力部１１１に秘密分散される値α∈Gが入力される（ステップＳ１１１）。選択部１１５は、M-1個の値v(m) (m=0,...,M-2)を選択し、値v(m) (m=0,...,M-2)を出力する（ステップＳ１１２）。変換部１１６は、入力された値v(m) (m=0,...,M-2)からM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を計算し、当該M-1個の値a(m) (m=0,...,M-2)を出力する（ステップＳ１１３）。入力部１１１に入力された値αと変換部１１６から出力されたM-1個の値a(m) (m=0,...,M-2)とは計算部１１７に入力される。計算部１１７は、これらの値α，a(m) (m=0,...,M-2)から値a(M-1)=g(α, a(0),...,a(M-2))∈Gを計算し、当該値a(M-1)を出力する（ステップＳ１１４）。
【０１０１】
計算部１１７から出力された値a(M-1)は、内部分散部４１８に入力される。内部分散部４１８は、(K, N)閾値秘密分散法Uに従って値a(M-1)を秘密分散してN個の分散値Ui(a(M-1)) (i=0,...,N-1)を生成し、生成したN個の分散値Ui(a(M-1)) (i=0,...,N-1)を出力する（ステップＳ４１５）。内部分散部４１８は、例えば参考文献１に記載された方式を用いて分散値Ui(a(M-1))を生成する。内部分散部４１８が、(K, N)閾値秘密分散法Uに従って、値τ=a(M-1)∈Gを秘密分散してN個の分散値Ui(τ)を生成する方法を例示する。
【０１０２】
［(K, N)閾値秘密分散法Uの例示］
内部分散部４１８は、ζビット（例えば128ビット）のランダムな値d,d(0),...,d(N-2)∈{0,1}ζを選択し、dを共通鍵暗号方式の共通鍵とし、d(N-1)=d-d(0)-...-d(N-2) mod 2ζとする。内部分散部４１８は、共通鍵dを用いて値τを暗号化し、共通鍵暗号方式の暗号文C(d, τ)を生成する。内部分散部４１８は、暗号文C(d, τ)をC(d, τ)=C(0)|C(1)|...|C(K-1)を満たすC(0),C(1),...,C(K-1)に分割する。ただし、C(0)|C(1)|...|C(K-1)は、C(0),C(1),...,C(K-1)のビット結合を表す。内部分散部４１８は、C(k)(k=0,...,K-1)をk次の係数としたK-1次式γ(x)=Σk=0K-1 C(k)・xkを定め、K-1次式γ(x)のN個の関数値γ(i) mod q (i=0,...,N-1)を求める。ここで、qはC(0),C(1),...,C(K-1)よりも大きい素数である。内部分散部４１８は、分散値Ui(τ)=(d(i mod N),...,d(i+N-2 (mod N)), γ(i) mod q)(i=0,...,N-1)を生成する。例えば、N=3,K=2の場合、この例の分散値Ui(τ)は、U0(τ)=(d(0),d(1),γ(0) mod q), U1(τ)=(d(1),d(2),γ(1) mod q), U2(τ)=(d(2),d(0),γ(2) mod q)となる。なお、N=3,K=2の場合、U0(τ)=(d(0),d(1),C(0)), U1(τ)=(d(1),d(2), C(1)), U2(τ)=(d(2),d(0),C(0)(+)C(1))としてもよい。ただし、C(0)(+)C(1)はC(0)とC(1)との排他的論理和である（［(K, N)閾値秘密分散法Uの例示］終わり）。
【０１０３】
選択部１１５から出力されたM-1個の値v(m) (m=0,...,M-2)と、内部分散部４１８から出力されたN個の分散値Ui(a(M-1)) (i=0,...,N-1)とは、分散値生成部４１８に入力される。分散値生成部４１８は、これらの値v(m), Ui(a(M-1)) (m=0,...,M-2, i=0,...,N-1)を用い、値αのN個の分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1))) (i=0,...,N-1)を生成して出力する。ただし、集合A={a(0),...,a(M-1)}の部分集合がSi(α)={a(i,0),...,a(i,Ni-1)} (i=0,...,N-1)であり、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応するv(i, ni)がP-1(a(i, ni))であり、a(i, qi)=a(M-1)である(i, qi) (qi∈{0,...,Ni-1})に対応するv(i, qi)が空値である（ステップＳ４１６）。
一例を挙げると、分散値生成部４１８は、M=N，Ni=N-1とし、分散値Ti(α) (i=0,...,N-1)を以下のように生成する。
T0(α)=(v(1), v(2),..., v(M-2), U0(a(M-1))),
T1(α)=(v(0), v(2),..., v(M-2), U1(a(M-1))),...,
TN-2(α)=(v(0), v(1),..., v(M-3), UM-2(a(M-1))),
TM-1(α)=(v(0), v(1),..., v(M-3), v(M-2), UM-1(a(M-1)))      ...(4)
【０１０４】
N個の分散値Ti(α) (i=0,...,N-1)は出力部１１２に入力され、出力部１１２はN個の分散値Ti(α) (i=0,...,N-1)を出力する（ステップＳ４１６）。出力された分散値Ti(α) (i=0,...,N-1)のそれぞれは、分散データ変換装置４２０−ｉ(i=0,...,N-1)のそれぞれに提供される。例えば、分散値Ti(α)は、ネットワーク等を経由して、対応する分散データ変換装置４２０−ｉ（図１７）に送信される。分散データ変換装置４２０−ｉ(i=0,...,N-1)のそれぞれに提供された分散値Ti(α)は入力部４２１−ｉに入力され、記憶部１２３ｂ−ｉに格納される。
【０１０５】
＜分散データ変換処理／分散値出力処理＞
分散データ変換装置４２０−ｉ(i=0,...,N-1)が実行する分散データ変換処理及び分散値出力処理を説明する。これらの処理は、すべての分散データ変換装置４２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうちK個（K≦N）の分散データ変換装置４２０−ｋ（k∈{0,...,N-1}）のみで実行されてもよい。また、ステップＳ４２４−ｉの処理は、すべての分散データ変換装置４２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうち一部の分散データ変換装置のみで実行されてもよい。
図１９に例示するように、分散データ変換装置４２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行わずに分散値を出力する場合、制御部４２４−ｉは分散値の変換を行わずに分散値Ti(α)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ４２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは、格納している分散値Ti(α)を読み出して出力する。分散値Ti(α)は出力部１２２−ｉに送られ、出力部１２２−ｉは分散値Ti(α)を出力する（ステップＳ４２２−ｉ）。出力された分散値Ti(α)はデータ復元装置４３０に提供される。例えば、分散値Ti(α)は、ネットワーク等を経由してデータ復元装置４３０に送信される。分散データ変換装置４２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する場合には、分散データ変換処理及び分散値出力処理を実行するすべての分散データ変換装置４２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する。
【０１０６】
一方、分散データ変換装置４２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行う場合、制御部４２４−ｉは、分散値の変換を行うために分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1)))を読み出す旨を記憶部１２３ｂ−ｉに指示する。この指示を受けた記憶部１２３ｂ−ｉは分散値Ti(α)を読み出す。読み出された分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1)))を構成する要素のうち、a(i, ni)≠a(M-1)である(i, ni) (ni∈{0,...,Ni-1})に対応する値v(i, ni)∈Ti(α) (ni∈{0,...,Ni-1})は変換部１２５−ｉに入力される。読み出された分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1), Ui(a(M-1)))が含むUi(a(M-1))は内部復元部４２７−ｉに入力される。
変換部１２５−ｉは、入力された値v(i, ni)から値a(i, ni)=P(v(i, ni))を計算し、当該値a(i, ni)を出力する（ステップＳ１２３−ｉ）。
【０１０７】
内部復元部４２７−ｉには、記憶部１２３ｂ−ｉから読み出された分散値Ti(α)の他、他の分散データ変換装置４２０−ｉ’（i’≠i, i’∈{0,...,N-1}）からネットワーク(NW)等を介して送信された分散値Ti’（α)も入力される。内部復元部４２７−ｉは、このように入力されたK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から値a(M-1)を復元し、得られた値a(M-1)を出力する（ステップＳ４２４−ｉ）。例えば、分散値Uk(a(M-1))が［(K, N)閾値秘密分散法Uの例示］で説明した方法で生成されている場合、内部復元部４２７−ｉは、分散値Uk(a(M-1))=(d(k mod N),...,d(k+N-2 (mod N)), γ(k))が含むK個のγ(k) (k∈{0,...,N-1})を用いてqを法としたK-1次式γ(x)=Σk=0K-1 C(k)・xkの係数C(0),C(1),...,C(K-1)を求め、暗号文C(d, a(M-1))=C(0)|C(1)|...|C(K-1)を生成する。なお、係数C(0),C(1),...,C(K-1)は(x, γ(x))=(k, γ(k))をK-1次式γ(x)に代入して得られる方程式を解くことで得られる。また、N=3, K=2, U0(τ)=(d(0),d(1),C(0)), U1(τ)=(d(1),d(2), C(1)), U2(τ)=(d(2),d(0), C(0)(+)C(1))としていた場合には、C(0), C(1),  C(0)(+)C(1)の何れか２個からC(0), C(1)が得られる。内部復元部４２７−ｉは、K個の分散値Uk(a(M-1))=(d(k mod N),...,d(k+N-2 (mod N)), γ(k))が含むd(k mod N),...,d(k+N-2 (mod N))から共通鍵ｄ=d(0)+...+d(N-1) mod 2ζを計算し、共通鍵ｄを用いて暗号文C(d, a(M-1))を復号することで値a(M-1)を復元する。
【０１０８】
変換分散値生成部４２６−ｉには、変換部１２５−ｉで得られた値a(i, ni) (ni∈{0,...,Ni-1})と、内部復元部４２７−ｉで得られた値a(M-1)と（存在するのであれば）が入力される。変換分散値生成部４２６−ｉは、得られた値a(i, ni)と値a(M-1)との少なくとも何れかを含むSi(α)={a(i,0),...,a(i,Ni-1)}を変換分散値として生成し（ステップＳ４２４−ｉ）、当該変換分散値Si(α)を記憶部１２３ｃ−ｉに格納する（ステップＳ４２５−ｉ）。式(4)の分散値Ti(α)に対応する変換分散値Si(α)の例は以下の通りである。
S0(α)=(a(1), a(2),..., a(M-2), a(M-1)),
S1(α)=(a(0), a(2),..., a(M-2), a(M-1)),...,
SN-2(α)=(a(0), a(1),..., a(M-3), a(M-1)),
SM-1(α)=(a(0), a(1),..., a(M-3), a(M-2))
【０１０９】
秘密計算部１２７−ｉは、所定の契機で記憶部１２３ｃ−ｉに格納された変換分散値Si(α)={a(i,0),...,a(i,Ni-1)}を読み出し、変換分散値Si(α)を入力とした秘密計算（例えば線形演算）を実行し、その演算結果である分散値Ei={e(i,0),...,e(i,Ni-1)}を出力する。分散値Eiは出力部１２２−ｉから出力され、データ復元装置４３０に提供される。
【０１１０】
＜データ復元処理＞
図２０に例示するように、データ復元装置４３０（図１６Ｂ）の入力部１３１に、何れかK個の分散値Tk(α) (k∈{0,...,N-1})、又は、何れかK個の分散値Ek={e(k,0),...,e(k,Nk-1)} (k∈{0,...,N-1})が入力される（ステップＳ４３１）。制御部４３４は、分散値Tk(α)が入力されたか、分散値Ekが入力されたかを判定する（ステップＳ４３２）。
【０１１１】
ステップＳ４３２で、分散値Tk(α)が入力されたと判定された場合、何れかK個の分散値Tk(α) (k∈{0,...,N-1})が変換部１３５及び内部復元部４３７に入力され変換部１３５は、K個の分散値Tk(α) (k∈{0,...,N-1})の少なくとも一部を用いてM-1個の値a(m)=P(v(m)) (m=0,...,M-2)を計算し、値a(m) (m=0,...,M-2)を出力する（ステップＳ１３３）。内部復元部４３７は、K個の分散値Tk(α)が含むK個の異なる分散値Uk(a(M-1)) (k∈{0,...,N-1})から値a(M-1)を復元し、値a(M-1)を出力する（ステップＳ４３３）。復元部１３６には、M-1個の値a(m)=P(v(m)) (m=0,...,M-2)と値a(M-1)とが入力される。復元部１３６は、これらを用いてα=f(a(0),...,a(M-1))を計算し、得られた値αを出力する（ステップＳ１３４）。値αは出力部１３２に入力され、そこから出力される（ステップＳ１３５）。
【０１１２】
一方、ステップＳ４３２で、分散値Ekが入力されたと判定された場合、K個の分散値Ek(k∈{0,...,N-1})が復元部１３６に入力される。復元部１３６は、K個の分散値Ek={e(k,0),...,e(k,Nk-1)} (k∈{0,...,N-1})の要素からなるM個の値e(0),...,e(M-1)を得、ε=f(e (0),...,e(M-1))を計算し、その結果εを出力する（ステップＳ１３６）。結果εは出力部１３２に入力され、そこから出力される（ステップＳ１３７）。
【０１１３】
＜本形態の特徴＞
本形態では従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減することができる。すなわち、本形態の分散値Ti(α)=(v(i,0), v(i,1),...,v(i,Ni-1))を構成する要素v(i,0), v(i,1),...,v(i,Ni-1)の少なくとも１個はv(m) (m=0,...,M-2)の何れかである。したがって、集合Gの要素のみからなる従来の分散値に比べて分散値のデータ量を削減できる。さらに、本形態の分散値Ti(α)は、集合Gの要素であるa(M-1)の代わりにその秘密分散値Ui(a(M-1))を含む。そのため、秘密分散値Ui(a(M-1))のそれぞれのデータ量が集合Gの要素（１個の要素）のデータ量よりも小さいのであれば、第１実施形態よりもデータ量を削減できる。
【０１１４】
例えば、集合Gの要素のデータ量がL、N=M=3,K=2、第１実施形態での分散値がT0(α)=(v(1), a(M-1)),T1(α)=(v(0), a(M-1)),T2(α)=(v(0), v(1))である場合、値v(0), v(1)のデータ量を無視できるのであれば、データ分散時の通信データ量及び記憶データ量は2×Ｌとなり、データ復元時の通信データ量はLとなる。一方、集合Gの要素のデータ量がL、N=M=3,K=2、第４実施形態での分散値がT0(α)=(v(1), U0(a(M-1))),T1(α)=(v(0), U1(a(M-1))),T2(α)=(v(0), v(1), U2(a(M-1)))である場合、値v(0), v(1)のデータ量を無視できるのであれば、データ分散時の通信データ量及び記憶データ量は1.5×Ｌとなり、データ復元時の通信データ量はLとなる。従ってデータ分散時の通信データ量及び記憶データ量がさらに3/4に削減されることが分かる。
【０１１５】
さらに、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとの値αを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【０１１６】
〔第５実施形態〕
次に、本発明の第５実施形態を説明する。本形態は第２，４実施形態の変形例であり、第４実施形態において同一の値v(m)を複数の秘密分散に流用することで分散値のデータ量をさらに削減する。以下では上述の実施形態との相違点を中心に説明する。上述の実施形態と共通する処理部やステップには上述の実施形態と同じ参照符号を用い、説明を簡略化する。
第５実施形態では、M, N, K, Rが2以上の整数であり、K≦Nであり、Ni,r(i=0,...,N-1, r=0,...,R-1)が1以上M-1以下の整数であり、Gが或る集合であり、P(x)がxに対応する値を集合Gの要素に移す写像であり、y=f(y(0),...,y(M-1))が集合Gの要素であるM個の値y(0),...,y(M-1)からなる部分集合(y(0),...,y(M-1))を集合Gの要素である値yに移す写像であり、g(y, y(0),...,y(M-2))がy=f(y(0),...,y(M-1))を満たす集合Gの要素であるM個のy, y(0),...,y(M-2)からなる部分集合(y, y(0),...,y(M-2))を値y(M-1)に移す写像である。本形態の集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例は、第１実施形態で説明した集合G、写像P(x)、y=f(y(0),...,y(N-1))及びg(y, y(0),...,y(N-2))の具体例と同じである。M≦Nであってもよいし、M≧Nであってもよい。M≧Rであってもよいし、M≦Rであってもよい。N≧Rであってもよいし、N≦Rであってもよい。K＜Nであってもよいし、K=Nであってもよい。
【０１１７】
第５実施形態の秘密分散システムは、データ分散装置とデータ復元装置とN個の分散データ変換装置とを有する。
本形態のデータ分散装置は、M-1個の値v(m) (m=0,...,M-2)を選択し、rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得、集合Gの要素である値αr (r=0,...,R-1)に対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を得、(K, N)閾値秘密分散法Uに従って値ar(M-1)を秘密分散してrのそれぞれについてN個の分散値Ui(ar(M-1)) (i=0,...,N-1)を得、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1), Ui(ar(M-1))) (i=0,...,N-1, r=0,...,R-1)を得る。ただし、集合Ar={ar(0),...,ar(M-1)}の部分集合がSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)であり、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個（好ましくは、R個のv0(i, ni,0),...,vR-1(i, ni,R-1)の何れかのみ）がar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}であり、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)が空値である。
【０１１８】
本形態のデータ復元装置は、分散値Ti(αr) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を得、分散値Ti(αr) (i=0,...,N-1)に含まれるK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から値ar(M-1)を得、第２変換部で得られた値ar(m) (m=0,...,M-2)と第１内部復元部で得られた値ar(M-1)とを用いてαr=f(ar(0),...,ar(M-1))を得る。
【０１１９】
本形態の分散データ変換装置のそれぞれは、分散値Ti(αr) (r=0,...,R-1)に含まれるvｒ’(i, ni,r’) (r’∈{0,...,R-1})について値ar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1})を得、分散値Ti(αr)(i=0,...,N-1)に含まれるK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から値ar(M-1)を得、第３変換部で得られた値aｒ(i, ni,r)と第２内部復元部で得られた値ar(M-1)との少なくとも何れかを含むSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1)を変換分散値として得る。このように得られた変換分散値Si(αr)は、秘密計算の入力値として用いられる。
【０１２０】
本形態において好ましくは、ar(i,j)≠ar(M-1)である(i,j)に対するNi,r-1個のvr(i,j)のデータ量とUi(ar(M-1))のデータ量との合計値は、Ni,r個の集合Gの要素のデータ量の合計値よりも小さい。より好ましくは、値v(m)それぞれのデータ量は集合Gの要素（１個の要素）のデータ量よりも小さく、なおかつ、分散値Ui(ar(M-1))それぞれのデータ量は集合Gの要素のデータ量よりも小さい。さらにより好ましくは、値v(m)それぞれのデータ量は集合Gの要素のデータ量に対して無視できる程度の大きさである（例えば、（v(m)それぞれのデータ量）／（集合Gの要素のデータ量）≦80/106）。
【０１２１】
＜構成＞
図１５に例示するように、第５実施形態の秘密分散システム５は、データ分散装置５１０、N個の分散データ変換装置５２０−ｉ（i=0,...,N-1）、及びデータ復元装置５３０を有する。データ分散装置５１０は、ネットワークや可搬型記録媒体などを経由して、N個の分散データ変換装置５２０−ｉ（i=0,...,N-1）に対して情報の提供が可能である。N個の分散データ変換装置５２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、データ復元装置５３０に対して情報の提供が可能である。分散データ変換装置５２０−ｉ（i=0,...,N-1）のそれぞれは、ネットワークや可搬型記録媒体などを経由して、他の分散データ変換装置５２０−ｉ’ （i’=i, i’∈{0,...,N-1}）に対して情報の提供が可能である。
【０１２２】
図１６Ａに例示するように、本形態のデータ分散装置５１０は、入力部１１１、出力部１１２、メモリ１１３、分割部２１１、制御部５１４、選択部１１５、変換部２１６、計算部２１７、分散値生成部５１８、及び内部分散部５１８を有する。本形態のデータ分散装置５１０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ分散装置５１０は、制御部５１４の制御のもとで各処理を実行する。入力部１１１に入力されたデータや各処理で得られたデータはメモリ１１３に格納され、メモリ１１３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１２３】
図１６Ｂに例示するように、本形態のデータ復元装置５３０は、入力部１３１、出力部１３２、メモリ１３３、制御部２３４、変換部２３５、復元部２３６、結合部２３７、内部復元部５３７を有する。本形態のデータ復元装置５３０は、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態のデータ復元装置５３０は、制御部５３４の制御のもとで各処理を実行する。入力部１３１に入力されたデータや各処理で得られたデータはメモリ１３３に格納され、メモリ１３３に格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１２４】
図１７に例示するように、本形態の分散データ変換装置５２０−ｉ (i=0,...,N-1)は、入力部１２１−ｉ、出力部１２２−ｉ、メモリ１２３ａ−ｉ、記憶部１２３ｂ−ｉ，１２３ｃ−ｉ、制御部５２４−ｉ、変換部２２５−ｉ、変換分散値生成部５２６−ｉ、内部復元部５２７−ｉ、及び秘密計算部２２７−ｉを有する。本形態の分散データ変換装置５２０−ｉは、例えば、公知又は専用のコンピュータに特別なプログラムが読み込まれて構成された特別な装置である。以下では説明を省略するが、本形態の分散データ変換装置５２０−ｉは、制御部５２４−ｉの制御のもとで各処理を実行する。入力部１２１−ｉに入力されたデータや各処理で得られたデータはメモリ１２３ａ−ｉに格納され、メモリ１２３ａ−ｉに格納されたデータは必要に応じて読み出されて他の処理に利用される。
【０１２５】
＜データ分散処理＞
図２１に例示するように、データ分散装置５１０（図１６Ａ）の入力部１１１に秘密分散される値αが入力される（ステップＳ１１１）。値αは分割部２１１に入力される。分割部２１１は、値αを集合Gの要素であるR個の値αr ∈G (r=0,...,R-1)に分割し、R個の値αr ∈G (r=0,...,R-1)を出力する（ステップＳ２１１）。選択部１１５は、M-1個の値v(m) (m=0,...,M-2)を選択し、値v(m) (m=0,...,M-2)を出力する（ステップＳ１１２）。値v(m) (m=0,...,M-2)は変換部２１６に入力される。変換部２１６は、rと値v(m)とに対応する値をz(r, v(m))とし、rのそれぞれに対してM-1個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を生成し、当該(M-1)×R個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)を出力する（ステップＳ２１３）。分割部２１１から出力されたR個の値αr ∈G (r=0,...,R-1)と、変換部２１６から出力された(M-1)×R個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1, m=0,...,M-2)とは計算部２１７に入力される。計算部２１７は、これらの値αr，ar(m) (r=0,...,R-1, m=0,...,M-2)から、各値αrに対して値ar(M-1)=g(αr, ar(0),...,ar(M-2))を生成し、当該R個のar(M-1) (r=0,...,R-1)を出力する（ステップＳ２１４）。
【０１２６】
計算部２１７から出力された値ar(M-1)は、内部分散部５１８に入力される。内部分散部５１８は、(K, N)閾値秘密分散法Uに従って値ar(M-1)を秘密分散してrのそれぞれについてN個の分散値Ui(ar(M-1)) (i=0,...,N-1, r=0,...,R-1)を生成し、生成したN×R個の分散値Ui(ar(M-1)) (i=0,...,N-1, r=0,...,R-1)を出力する（ステップＳ５１５）。内部分散部５１８は、例えば、τ=ar(M-1)とおいて前述の［(K, N)閾値秘密分散法Uの例示］の処理を実行する。
【０１２７】
選択部１１５から出力されたM-1個の値v(m) (m=0,...,M-2)と、内部分散部５１８から出力されたN×R個の分散値Ui(ar(M-1)) (i=0,...,N-1, r=0,...,R-1)とは、分散値生成部５１８に入力される。分散値生成部５１８は、これらの値v(m), Ui(ar(M-1)) (m=0,...,M-2, i=0,...,N-1, r=0,...,R-1)を用い、分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1), Ui(ar(M-1))) (i=0,...,N-1, r=0,...,R-1)を生成して出力する。ただし、集合Ar={ar(0),...,ar(M-1)}の部分集合がSi(αr)={ar(i,0),...,ar(i,Ni,r-1)} (i=0,...,N-1, r=0,...,R-1)であり、ar(i, ni,r)≠ar(M-1)である(i, ni,r) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)に対応するR個のv0(i, ni,0),...,vR-1(i, ni,R-1)の少なくとも１個（好ましくは、R個のv0(i, ni,0),...,vR-1(i, ni,R-1)の何れかのみ）がar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (r’∈{0,...,R-1})を満たすvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}であり、ar(i, qi,r)=ar(M-1)である(i, qi,r) (qi,r∈{0,...,Ni,r-1}, ni,r≠qi,r)に対応するvr(i, qi,r)が空値である（ステップＳ５１６）。例えば、a0(i, ni,0)≠a0(M-1)である(i, ni,0) (ni,0∈{0,...,Ni,0-1})に対応するv0(i, ni,0)が、ar(i, ni,r)=P(z(r, v0(i, ni,0)))を満たすv0(i, ni,0)∈{v(0),...,v(M-2)}とされる。ar(i, ni,r)≠ar(M-1)である(i, ni,r)に対応するv0(i, ni,0),...,vR-1(i, ni,R-1)のうちvｒ’(i, ni,r’)∈{v(0),...,v(M-2)}以外の値は、例えば、空値であってもよいし、rやR等のパラメータであってもよい。
一例を挙げると、分散値生成部５１８は、M=N，Ni=N-1とし、分散値Ti(αr) (i=0,...,N-1)を以下のように生成する。
T0(α0)=(v(1), v(2),..., v(M-2), U0(a0(M-1))), T0(α1)=(U0(a1(M-1))),...,T0(αR-1)=(U0(aR-1(M-1))),...,TM-1(α0)=(v(0), v(1),..., v(M-3), v(M-2), UM-1(a0(M-1))),...,TM-1(αR-1)=(UM-1(aR-1(M-1))
...(5)
【０１２８】
分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1), Ui(ar(M-1))) (i=0,...,N-1, r=0,...,R-1)は出力部１１２に入力され、出力部１１２は分散値Ti(αr) (i=0,...,N-1, r=0,...,R-1)を出力する（ステップＳ５１６）。出力された分散値Ti(αr) (i=0,...,N-1, r=0,...,R-1)のそれぞれは、分散データ変換装置５２０−ｉ (i=0,...,N-1)のそれぞれに提供される。例えば、分散値Ti(αr)は、ネットワーク等を経由して、対応する分散データ変換装置５２０−ｉ（図１７）に送信される。分散データ変換装置５２０−ｉ(i=0,...,N-1)のそれぞれに提供された分散値分散値Ti(αr)は入力部１２１−ｉに入力され、記憶部１２３ｂ−ｉに格納される。
【０１２９】
＜分散データ変換処理／分散値出力処理＞
分散データ変換装置５２０−ｉ(i=0,...,N-1)が実行する分散データ変換処理及び分散値出力処理を説明する。これらの処理は、すべての分散データ変換装置５２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうちK個(K≦N)の分散データ変換装置５２０−ｋ（k∈{0,...,N-1}）のみで実行されてもよい。また、ステップＳ５２４−ｉの処理は、すべての分散データ変換装置５２０−ｉ(i=0,...,N-1)で実行されてもよいし、それらのうち一部の分散データ変換装置のみで実行されてもよい。
図２２に例示するように、分散データ変換装置５２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行わずに分散値を出力する場合、制御部５２４−ｉは分散値の変換を行わずに分散値Ti(αr)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ５２１−ｉ）。この指示を受けた記憶部５２３ｂ−ｉは、格納している分散値Ti(αr)を読み出して出力する。分散値Ti(αr)は出力部１２２−ｉに送られ、出力部１２２−ｉは分散値Ti(αr)を出力する（ステップＳ５２２−ｉ）。出力された分散値Ti(αr)はデータ復元装置５３０に提供される。例えば、分散値Ti(αr)は、ネットワーク等を経由してデータ復元装置５３０に送信される。分散データ変換装置５２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する場合には、分散データ変換処理及び分散値出力処理を実行するすべての分散データ変換装置５２０−ｉ(i=0,...,N-1)が分散値の変換を行わずに分散値を出力する。
【０１３０】
一方、分散データ変換装置５２０−ｉ(i=0,...,N-1)のそれぞれが分散値の変換を行う場合、制御部５２４−ｉは、分散値の変換を行うために分散値Ti(αr)を読み出す旨を記憶部１２３ｂ−ｉに指示する（ステップＳ５２１−ｉ）。この指示を受けた記憶部１２３ｂ−ｉは分散値Ti(αr)を読み出す。
読み出された分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni,r-1), Ui(ar(M-1)))を構成する要素のうち、vｒ’(i, ni,r’)∈{v(0),...,v(M-2)} (r’∈{0,...,R-1})は変換部２２５−ｉに入力される。読み出された分散値Ti(αr)=(vr(i,0), vr(i,1),...,vr(i,Ni-1), Ui(ar(M-1)))が含むUi(ar(M-1))は内部復元部５２７−ｉに入力される。
【０１３１】
変換部２２５−ｉは、入力された値vｒ’(i, ni,r’) (r’∈{0,...,R-1})からar(i, ni,r)=P(z(r, vｒ’(i, ni,r’))) (ni,r∈{0,...,Ni,r-1}, r=0,...,R-1)を計算し、当該値ar(i, ni,r)を出力する（ステップＳ２２３−ｉ）。
【０１３２】
内部復元部５２７−ｉには、記憶部１２３ｂ−ｉから読み出された分散値Ti(αr)の他、他の分散データ変換装置５２０−ｉ’（i’≠i, i’∈{0,...,N-1}）からネットワーク(NW)等を介して送信された分散値Ti’（αr)も入力される。内部復元部５２７−ｉは、rのそれぞれについてK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から値ar(M-1) (r=0,...,R-1)を復元し、得られた値ar(M-1) (r=0,...,R-1)を出力する（ステップＳ５２４−ｉ）
【０１３３】
変換分散値生成部５２６−ｉには、変換部１２５−ｉで得られた値ar(i, ni) (ni∈{0,...,Ni-1})と、内部復元部５２７−ｉで得られた値ar(M-1)と（存在するのであれば）が入力される。変換分散値生成部５２６−ｉは、rのそれぞれについて値ar(i, ni)と値ar(M-1)との少なくとも何れかを含むSi(αr)={ar(i,0),...,ar(i,Ni-1)}を変換分散値として生成し（ステップＳ５２４−ｉ）、当該変換分散値Si(αr)を記憶部１２３ｃ−ｉに格納する（ステップＳ５２５−ｉ）。式(5)の分散値Ti(αr)に対応する変換分散値Si(αr)の例は以下の通りである。
S0(α0)=(a0(1), a0(2),..., a0(M-2), a0(M-1)), S0(α1)=(a1(1), a1(2),..., a1(M-2), a1(M-1)),...,SM-1(αR-1)=(aR-1(0), aR-1(1),..., aR-1(M-2))
【０１３４】
秘密計算部２２７−ｉは、所定の契機で記憶部１２３ｃ−ｉに格納された変換分散値Si(αr)={ar(i,0),...,ar(i,Ni-1)}を読み出し、変換分散値Si(αr)を入力とした秘密計算を実行し、その演算結果である分散値Ei,r={er(i,0),...,er(i,Ni-1)}を出力する。分散値Ei,rは出力部１２２−ｉから出力され、データ復元装置５３０に提供される。
【０１３５】
＜データ復元処理＞
図２３に例示するように、データ復元装置５３０（図１６Ｂ）の入力部１３１に、rのそれぞれについて、何れかK個の分散値Tk(αr) (k∈{0,...,N-1})、又は、何れかK個の分散値Ek,r={er(k,0),...,er(k,Nk-1)} (k∈{0,...,N-1})が入力される（ステップＳ５３１）。制御部５３４は、分散値Tk(αr)が入力されたか、分散値Ek,rが入力されたかを判定する（ステップＳ５３２）。
【０１３６】
ステップＳ５３２で分散値Tk(αr)が入力されたと判定された場合、rのそれぞれについて、何れかK個の分散値Tk(αr) (k∈{0,...,N-1}, r=0,...,R-1)が変換部２３５に入力される。変換部２３５は、分散値Ti(αr) (i=0,...,N-1)の少なくとも一部を用いて、rのそれぞれに対してM-1個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,...,M-2)を計算し、値ar(m) (r=0,...,R-1, m=0,...,M-2)を出力する（ステップＳ２３３）。例えば、式(5)の分散値T0(αr), TM-1(αr) (r=0,...,R-1)が変換部２３５に入力された場合、変換部２３５は、分散値TM-1(α0)=(v(0), v(1),..., v(M-3), v(M-2), UM-1(a0(M-1)))が含む値v(0), v(1),..., v(M-3), v(M-2)を用い、rのそれぞれに対してM-1個の値ar(m)=P(z(r,v(m))) (r=0,...,R-1, m=0,...,M-2)を計算する。内部復元部５３７は、rのそれぞれについて、入力されたK個の異なる分散値Uk(ar(M-1)) (k∈{0,...,N-1})から値ar(M-1) (r=0,...,R-1)を復元し、当該値ar(M-1) (r=0,...,R-1)を出力する（ステップＳ５３３）。
復元部２３６には、rのそれぞれについてM-1個の値ar(m) (r=0,...,R-1, ｍ=0,...,M-2)と値ar(M-1) (r=0,...,R-1)とが入力される。復元部２３６は、これらを用いてαr=f(ar(0),...,ar(M-1))を計算し、得られた値αr (r=0,...,R-1)を出力する（ステップＳ２３４）。値αr (r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値αr(r=0,...,R-1)を結合して値α∈Gを生成し、当該値αを出力する（ステップＳ２３５）。値αは出力部１３２に入力され、出力部１３２は値αを出力する（ステップＳ２３６）。
【０１３７】
一方、ステップＳ５３２で、分散値Ek,rが入力されたと判定された場合、rのそれぞれについてK個の分散値Ek,r(k∈{0,...,N-1})が復元部２３６に入力される。復元部２３６は、rのそれぞれについて分散値Ek,r={er(k,0),...,er(k,Nk,r-1)} (r=0,...,R-1, k∈{0,...,N-1})の要素からなるM個の値er(0),...,er(M-1)を得、εr=f(er(0),...,er(M-1))を計算し、その結果εr (r=0,...,R-1)を出力する（ステップＳ２３７）。R個の値εr(r=0,...,R-1)は結合部２３７に入力される。結合部２３７は、R個の値εr (r=0,...,R-1)を結合して値ε∈Gを生成し、当該値εを出力する（ステップＳ２３８）。値εは出力部１３２に入力され、出力部１３２は値εを出力する（ステップＳ２３９）。
【０１３８】
＜本形態の特徴＞
本形態でも従来の秘密分散方式に比べ、分散値のデータ量を大幅に削減できる。本形態では、各値v(m)からR個の値ar(m)=P(z(r, v(m))) (r=0,...,R-1)を生成するため、複数の値αr(r=0,...,R-1)の秘密分散を行う場合のデータ量をさらに削減できる。さらに、本形態の分散値Ti(αr)は集合Gの要素であるar(M-1)の代わりにその秘密分散値Ui(ar(M-1))を含むため、データ量をさらに削減できる。また、分散データ変換装置での分散データ変換処理により、データ分散装置で得られた分散値からもとのαやαrを復元することなく、秘密計算の入力とすることが可能な変換分散値を生成し、秘密計算を実行することもできる。
【０１３９】
＜変形例等＞
なお、本発明は上述の実施の形態に限定されるものではない。例えば、第２，３，５実施形態では、値αを分割してR個の値αr(r=0,...,R-1)が生成されたが、値αがR個の値αrからなるデータであってもよい。例えば、値αが表データであり、αrが当該表データを構成する要素であってもよい。その他、R個の値αrが値αから分割されたものではなく、互いに独立したデータであってもよい。
【０１４０】
データ分散装置が上述の実施形態の分散値に加え、さらに別の情報（例えばrやRなどのパラメータや値v(m)など）を第２分散値として出力してもよい。例えば、第２，５実施形態において、Ti(αr)とrを含む(Ti(αr), r) (i=0,...,N-1, r=0,...,R-1)がデータ分散装置から出力されてもよい。その他、第３実施形態において、TN-1(αr)とrを含む(TN-1(αr), r) (r=0,...,R-1)がデータ分散装置から出力されてもよい。この場合、データ復元装置は、上述の実施形態の分散値に加え、さらに第２分散値を用いてデータの復元を行ってもよく、分散データ変換装置は、上述の実施形態の分散値に加え、さらに第２分散値を用いて変換分散値を生成してもよい。或いは、分散値としてrが送信されるのではなく、送信されるビットストリーム中のTi(αr)やTN-1(αr)の位置並びに順序、又は、記憶領域中に格納されたTi(αr)やTN-1(αr)のアドレスなどの情報にrを関連付け、これらの情報からTi(αr)やTN-1(αr)に対応するrが特定されてもよい。同様に、第２，３，５実施形態において、秘密計算の入力値として変換分散値に加えて当該変換分散値に対応するrが入力されてもよし、その他の方法で変換分散値に対応するrが特定されてもよい。
【０１４１】
上述の実施形態で説明した装置の少なくとも一部の処理部が同一の装置に含まれていてもよい。例えば、データ分散装置とデータ復元装置とが同一のコンピュータを用いて構成されてもよい。また、上述の実施形態で説明した装置に含まれる一部の処理部が別の装置に含まれていてもよい。例えば、分散データ変換装置の外部の秘密計算装置に秘密計算部が設けられ、秘密計算装置が分散データ変換装置から提供された変換分散値を用いて秘密計算を行ってもよい。その他、分散データ変換装置の外部の記憶装置に分散値が格納されてもよい。この場合、分散データ変換装置が存在しなくてもよい。また、装置Ａから装置Ｂへ情報を提供するとは、装置Ａから装置Ｂへ情報を送信することであってもよいし、装置Ａから出力された情報を可搬型記録媒体に格納し、装置Ｂが当該可搬型記録媒体から当該情報を読み出すことであってもよい。上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１４２】
上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体の例は、非一時的な（non-transitory）記録媒体である。このような記録媒体の例は、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等である。
【０１４３】
このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１４４】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録装置に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１４５】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１４６】
１〜５  秘密分散システム
１１０〜５１０  データ分散装置
１２０〜５２０  分散データ変換装置
１３０〜５３０  データ復元装置
【図１】
0005683503.tif 000002
【図２】
0005683503.tif 000003
【図３】
0005683503.tif 000004
【図４】
0005683503.tif 000005
【図５】
0005683503.tif 000006
【図６】
0005683503.tif 000007
【図７】
0005683503.tif 000008
【図８】
0005683503.tif 000009
【図９】
0005683503.tif 000010
【図１０】
0005683503.tif 000011
【図１１】
0005683503.tif 000012
【図１２】
0005683503.tif 000013
【図１３】
0005683503.tif 000014
【図１４】
0005683503.tif 000015
【図１５】
0005683503.tif 000016
【図１６】
0005683503.tif 000017
【図１７】
0005683503.tif 000018
【図１８】
0005683503.tif 000019
【図１９】
0005683503.tif 000020
【図２０】
0005683503.tif 000021
【図２１】
0005683503.tif 000022
【図２２】
0005683503.tif 000023
【図２３】
0005683503.tif 000024