(57)【要約】【課題】計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行い、復旧および再分散と改ざん検知を可能とする。【解決手段】データ分散装置１０は鍵s1,…,sKから擬似乱数r1,…,rKを生成し、情報aから擬似乱数r1,…,rKを用いて暗号文cを生成し、鍵s1,…,sKを分散値fs1(n),…,fsK(n)に分散し、暗号文cを分散値fc(n)に分散する。分散データ保有装置２０は、分散値fsi(λ)から復元値Uiを生成し、分散値fc(λ)から復元値U0を生成し、復元値U0,Uiを準同型性をもつ秘密分散方式S2により分散値fU0(n),fUi(n)に分散し、分散値fU0(i),…,fUK(i)から分散値ga(i)を生成する。分散データ保有装置２０は分散値ga(i)を用いて生成した変換用検証値c’αと分散値ga(i)を用いて生成した変換用チェックサムcαとを比較することで分散値のいずれかが改ざんされたか否かを検証する。【選択図】図１
2014138349.tif 000002
【特許請求の範囲】
【請求項１】
データ分散装置とN台の分散データ保有装置を含む秘密分散システムであって、
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
前記データ分散装置は、
K個の鍵s1,…,sK∈Sを選択する鍵選択部と、
前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を有し、
前記分散データ保有装置は、
K個の分散値fsi(λ)から前記秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から前記秘密分散方式S0により復元値U0を復元する復元部と、
前記復元値U0,Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散部と、
K+1個の分散値fU0(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換部と、
前記分散値fsi(λ)が入力されると前記復元部と前記分散部と前記変換部により前記分散値ga(i)を生成し、前記分散値ga(i)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する変換用生成部と、
前記分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を前記秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証部と、
を有する秘密分散システム。
【請求項２】
データ分散装置とN台の分散データ保有装置を含む秘密分散システムであって、
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
前記データ分散装置は、
K個の鍵s1,…,sK∈Sを選択する鍵選択部と、
前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
前記情報aを任意の準同型性をもつ秘密分散方式S2によりN個に分散した分散値ga(n)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する変換用生成部と、
を有し、
前記分散データ保有装置は、
K個の分散値fsi(λ)から前記秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から前記秘密分散方式S0により復元値U0を復元する復元部と、
前記復元値U0,Uiを前記秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散部と、
K+1個の分散値fU0(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換部と、
前記分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を前記秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証部と、
を有する秘密分散システム。
【請求項３】
請求項１または２に記載の秘密分散システムであって、
前記データ分散装置は、
前記情報aを用いて復元用チェックサムcβを生成し、前記秘密分散方式S3によりそれぞれN個の分散値fcβ(n)に分散する復元用生成部と、
前記秘密分散方式S1により前記分散値fsi(λ)から鍵s1,…,sKを復元する鍵復元部と、
前記秘密分散方式S0により前記分散値fc(λ)から暗号文cを復元する暗号文復元部と、
前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより生成した擬似乱数r1,…,rKを用いて前記暗号文cから前記情報aを復号する復号部と、
前記情報aを用いて生成した復元用検証値c’βとK個の分散値fcβ(λ)を前記秘密分散方式S3により復元した復元用チェックサムcβとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する復元用検証部と、
を有する秘密分散システム。
【請求項４】
請求項１または２に記載の秘密分散システムであって、
前記データ分散装置は、
前記秘密分散方式S1により前記分散値fsi(λ)から鍵s1,…,sKを復元する鍵復元部と、
前記秘密分散方式S0により前記分散値fc(λ)から暗号文cを復元する暗号文復元部と、
前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより生成した擬似乱数r1,…,rKを用いて前記暗号文cから前記情報aを復号する復号部と、
前記情報aを用いて生成した復元用検証値c’βとK個の分散値fcβ(λ)を前記秘密分散方式S3により復元した復元用チェックサムcβとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する復元用検証部と、
を有し、
前記分散データ保有装置は、
前記分散値fsi(λ)が入力されると前記復元部と前記分散部と前記変換部により前記分散値ga(i)を生成し、前記分散値ga(i)を用いて復元用チェックサムcβを前記秘密分散方式S3により分散した分散値fcβ(i)を生成する復元用生成部と、
を有する秘密分散システム。
【請求項５】
請求項１から４のいずれかに記載の秘密分散システムであって、
jはj∈λの整数であり、i≠jであり、
前記分散データ保有装置は、
前記分散値fs1(j),…,fsK(j),fc(j)を用いて復旧用チェックサムcγを生成し、前記秘密分散方式S3によりN個の分散値fcγ(n)に分散する復旧用生成部と、
前記分散値fs1(i),…,fsK(i),fc(i)を前記秘密分散方式S1により分散した分散値[fs1(i)],…,[fsK(i)],[fc(i)]を補間して分散値[fs1(j)],…,[fsK(j)],[fc(j)]を生成し、前記分散値[fs1(j)],…,[fsK(j)],[fc(j)]を前記秘密分散方式S1により復元して分散値fs1(j),…,fsK(j),fc(j)を生成する復旧部と、
前記分散値fs1(j),…,fsK(j),fc(j)を用いて生成した復旧用検証値c’γとK個の分散値fcγ(λ)を前記秘密分散方式S3により復元した復旧用チェックサムcγとを比較することで、前記分散値fs1(j),…,fsK(j),fc(j)のいずれかが改ざんされたか否かを検証する復旧用検証部と、
を有する秘密分散システム。
【請求項６】
請求項１から４のいずれかに記載の秘密分散システムであって、
jはj∈λの整数であり、i≠jであり、
前記データ分散装置は、
前記分散値fs1(n),…,fsK(n),fc(n)を用いて復旧用チェックサムcγを生成し、前記秘密分散方式S3によりN個の分散値fcγ(n)に分散する復旧用生成部と、
を有し、
前記分散データ保有装置は、
前記分散値fs1(i),…,fsK(i),fc(i)を前記秘密分散方式S1により分散した分散値[fs1(i)],…,[fsK(i)],[fc(i)]を補間して分散値[fs1(j)],…,[fsK(j)],[fc(j)]を生成し、前記分散値[fs1(j)],…,[fsK(j)],[fc(j)]を前記秘密分散方式S1により復元して分散値fs1(j),…,fsK(j),fc(j)を生成する復旧部と、
前記分散値fs1(j),…,fsK(j),fc(j)を用いて生成した復旧用検証値c’γとK個の分散値fcγ(λ)を前記秘密分散方式S3により復元した復旧用チェックサムcγとを比較することで、前記分散値fs1(j),…,fsK(j),fc(j)のいずれかが改ざんされたか否かを検証する復旧用検証部と、
を有する秘密分散システム。
【請求項７】
請求項１から６のいずれかに記載の秘密分散システムであって、
ζは互いに異なる1以上N以下の2K-1個の整数であり、rα1,…,rαKは前記鍵分散部が前記秘密分散方式S1で用いた乱数であり、rβ1,…,rβKはそれぞれrα1,…,rαKのいずれとも異なる乱数であり、
前記分散データ保有装置は、
前記分散値fs1(i),…,fsK(i)を前記乱数rβ1,…,rβKを用いて前記秘密分散方式S1により再分散値[fs1(i)],…,[fsK(i)]に分散する再分散部と、
再分散値[fs1(ζ)],…,[fsK(ζ)]を補間して生成した分散値[fs1(i)]’,…,[fsK(i)]’と前記分散値[fs1(i)],…,[fsK(i)]とを比較することで、分散値fs1(ζ),…,fsK(ζ)のいずれかが改ざんされたか否かを検証する一貫性検証部と、
前記再分散値[fs1(i)],…,[fsK(i)]を前記乱数rα1,…,rαKを用いて前記秘密分散方式S1により復元し、分散値f’s1(i),…,f’sK(i)を生成する再復元部と、
を有する秘密分散システム。
【請求項８】
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
K個の鍵s1,…,sK∈Sを選択する鍵選択部と、
前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を有するデータ分散装置。
【請求項９】
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
鍵siを任意の秘密分散方式S1により分散したK個の分散値fsi(λ)から前記秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、情報aを鍵s1,…,sKを用いて暗号化した暗号文cを任意の秘密分散方式S0により分散したK個の分散値fc(λ)から前記秘密分散方式S0により復元値U0を復元する復元部と、
前記復元値U0,Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散部と、
K+1個の分散値fU0(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換部と、
前記分散値ga(i)を用いて生成した変換用検証値c’αと前記分散値ga(i)を用いて生成した変換用チェックサムcαとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証部と、
を有する分散データ保有装置。
【請求項１０】
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
鍵選択部が、K個の鍵s1,…,sK∈Sを選択する鍵選択ステップと、
擬似乱数生成部が、前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成ステップと、
暗号化部が、情報a∈Rから前記擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化ステップと、
鍵分散部が、前記鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散ステップと、
暗号文分散部が、前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
復元部が、K個の分散値fsi(λ)から前記秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から前記秘密分散方式S0により復元値U0を復元する復元ステップと、
分散部が、前記復元値U0,Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散ステップと、
変換用生成部が、前記分散値fsi(λ)が入力されると前記復元ステップと前記分散ステップと前記変換ステップにより前記分散値ga(i)を生成し、前記分散値ga(i)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する変換用生成ステップと、
変換部が、K+1個の分散値fU0(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換ステップと、
変換用検証部が、前記分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を前記秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証ステップと、
を含む秘密分散方法。
【請求項１１】
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
鍵選択部が、K個の鍵s1,…,sK∈Sを選択する鍵選択ステップと、
擬似乱数生成部が、前記鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成ステップと、
暗号化部が、情報a∈Rから前記擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化ステップと、
鍵分散部が、前記鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散ステップと、
暗号文分散部が、前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
変換用生成部が、前記情報aを任意の準同型性をもつ秘密分散方式S2によりN個に分散した分散値ga(n)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりそれぞれN個の分散値fcα(n)に分散する変換用生成ステップと、
復元部が、K個の分散値fsi(λ)から前記秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から前記秘密分散方式S0により復元値U0を復元する復元ステップと、
分散部が、前記復元値U0,Uiを前記秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散ステップと、
変換部が、K+1個の分散値fU0(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換ステップと、
変換用検証部が、前記分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を前記秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、前記分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証ステップと、
を含む秘密分散方法。
【請求項１２】
請求項８に記載のデータ分散装置もしくは請求項９に記載の分散データ保有装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、計算量型秘密分散技術およびマルチパーティ計算技術に関する。
【背景技術】
【０００２】
秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。分散値の総数をN、復元に必要な分散値の最小数をK（≦N）としたとき、N,Kの値に制限がない方式と制限がある方式とがある。
【０００３】
秘密分散の代表的な方式として、Shamir秘密分散方式がある（例えば、非特許文献１参照）。この方式の例では、pを素数、GF(p)を位数pの有限体として、値a∈GF(p)に対してf(0)=aとなるような、xを変数とするK-1次式f(x)から、aの分散値Si(a)=f(i)（i=1,…,N）を得る。n1,…,nKを互いに異なる1以上N以下の整数として以下の式(1)(2)の関係が成り立つため、任意の異なるK個の分散値からaを復元できる。
【０００４】
【数１】
2014138349.tif 000003
【０００５】
また、秘密分散の一種として、計算量的安全性に基づき一定個数未満の分散値からは元のデータを一切復元できなくする、計算量型秘密分散方式がある（例えば、非特許文献２参照）。この方式の例では、値a=(a0,a1,…,aL-1)(a0,a1,…,aL-1∈GF(p))を共通鍵暗号を用いて暗号化し、当該暗号文c=(c0,c1,…,cK-1)（ただしc0,c1,…,cK-1∈GF(p)）から決まる、xを変数とするK-1次式f(x)=c0+c1x+…+cK-1xK-1から、cの分散値Ti(c)=f(i)(i=1,…,N)を得る。また共通鍵は別途Shamir秘密分散方式などにより分散する。するとn1,…,nKを互いに異なる1以上N以下の整数として、f(x)のK個の点(ni,f(ni))(i=1,…,K)からf(x)の係数c0,c1,…,cK-1を一意に求めることができる。これはc0,c1,…,cK-1を変数とする以下の行列についてc0,c1,…,cK-1の解を求めればよい。
【０００６】
【数２】
2014138349.tif 000004
【０００７】
そして共通鍵を復元して、cを復号すれば、aを得ることができる。
【０００８】
一方、秘密分散を要素技術としたマルチパーティ計算方式が提案されている。マルチパーティ計算は、各計算主体i(i=1,…,N)がそれぞれ値aiを入力として、他の計算主体に値aiを明かすことなく、特定の関数値Fi(a1,…,aN)を得る技術である。上述のShamir秘密分散方式では、値a,b∈GF(p)の分散値Si(a),Si(b)から、各計算主体の入力を明かさず、a+bの分散値Si(a+b)およびabの分散値Si(ab)を得る方法が知られている（非特許文献３参照）。すなわち、Shamir秘密分散方式であれば、加算および乗算のマルチパーティ計算ができる。なお、Si(a)+Si(b)=Si(a+b)の関係を満たす秘密分散を（加法）準同型性をもつ秘密分散と呼ぶ。
【０００９】
また、秘密分散の一種として、線形秘密分散方式がある。線形秘密分散方式は、元のデータa∈GF(p)についてすべての分散値がa∈GF(p)およびGF(p)上の乱数の線形結合で表現できる秘密分散と定義され、任意の線形秘密分散方式をマルチパーティ計算に拡張できることが知られている（非特許文献４参照）。
【００１０】
また、秘密分散の安全性を向上する機能として、復旧、再分散が可能であることが求められている。復旧とは、サーバが利用不能になるなどにより一部の分散値が失われた際に、少なくともK台のサーバが利用可能であれば、利用不能となったN-K個の分散値を利用可能なK個の分散値から秘匿性を失わずに再構築する方法である。
【００１１】
再分散とは、一旦秘密分散した分散値が一部漏洩した場合に、秘匿性を失わないように再度秘密分散する方法である。例えば、K-1個の分散値が漏洩した場合、あと1個の分散値が漏洩すると攻撃者はK個の分散値からaを復元可能となり秘匿性が破られてしまう。このような場合に再度秘密分散すれば、攻撃者が再分散する前のK-1個の分散値と再分散後の1個の分散値を保有したとしても、aの秘匿性は破られない。
【００１２】
さらに、秘密分散の安全性を向上する機能として、改ざん検知が可能であることが求められている。秘密分散の分散値のいずれかが改ざんされていると、その分散値を用いた秘匿計算の計算結果が不正な結果となる。秘匿計算を行う前に分散値の改ざんを検知することができれば計算結果の正当性を保証することができる。準同型性をもつ秘密分散による分散値は他の計算主体と通信することなく加算と乗算が可能であるため、改ざん検知に用いるチェックサムは加算と乗算のみから計算できる方式であると効率がよい。このようなチェックサムには非特許文献５に記載の技術がある。
【００１３】
非特許文献５に記載のチェックサムは、Fを体として、値a0,…,aN-1∈Fのチェックサムcを、乱数r∈Fを用いて、以下の式(3)により生成する。
【００１４】
【数３】
2014138349.tif 000005
【００１５】
非特許文献５では、以下の式(4)によりチェックサムcを検証する。
【００１６】
【数４】
2014138349.tif 000006
【００１７】
式(2)が0であれば、値a0,…,aN-1はいずれも改ざんされていないと判断する。式(2)が0以外であれば、値a0,…,aN-1は少なくとも1個が改ざんされていると判断する。
【先行技術文献】
【非特許文献】
【００１８】
【非特許文献１】A.Shamir, “How to share a secret.”, Commun. ACM 22(11), pp. 612-613, 1979.
【非特許文献２】H.Krawczyk, “Secret sharing made short.”, CRYPTO 1993, pp. 136-146, 1993.
【非特許文献３】M. Ben-Or, S. Goldwasser, and A. Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract),” STOC 1988, pp. 1-10, 1988.
【非特許文献４】R. Cramer, I. Damgard, and U. Maurer, “General Secure Multi-Party Computation from any Linear Secret-Sharing Scheme”, Eurocrypto 2000, pp. 316-334, 2000.
【非特許文献５】S. Obana and T. Araki, “Almost optimum secret sharing schemes secure against cheating for arbitrary secret distribution”, ASIACRYPT, Vol. 4284 of Lecture Notes in Computer Science, pp. 364-379, 2006.
【発明の概要】
【発明が解決しようとする課題】
【００１９】
Shamir秘密分散方式では、aおよびその各分散値のデータ量を一定とすると、分散値の総データ量がそれぞれaのデータ量のおよそN倍となる。復元に必要な分散値の総データ量はそれぞれaのデータ量のおよそK倍となる。分散値のデータ量の増加は通信時間や保存データの増大につながるため、できるだけ分散値のデータ量を抑えることが望ましい。
【００２０】
計算量型秘密分散方式は一般にTi(a)+Ti(b)≠Ti(a+b)となり、Shamir秘密分散方式のように各入力の加算のマルチパーティ計算を行う方法は自明でない。
【００２１】
この発明の目的は、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行い、復旧および再分散と改ざん検知が可能な秘密分散技術を提供することである。
【課題を解決するための手段】
【００２２】
上記の課題を解決するために、この発明の一態様による秘密分散システムは、データ分散装置とN台の分散データ保有装置を含む。この発明では、N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像である。
【００２３】
一態様によるデータ分散装置は、K個の鍵s1,…,sK∈Sを選択する鍵選択部と、鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成部と、情報a∈Rから擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化部と、鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散部と、暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部とを有する。
【００２４】
一態様による分散データ保有装置は、K個の分散値fsi(λ)から任意の秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から任意の秘密分散方式S0により復元値U0を復元する復元部と、復元値U0,Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散部と、K+1個の分散値fU0(i),…,fUK(i)から情報aの分散値ga(i)を生成する変換部と、分散値fsi(λ)が入力されると復元部と分散部と変換部により分散値ga(i)を生成し、分散値ga(i)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する変換用生成部と、分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を任意の秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証部とを有する。
【００２５】
この発明の他の態様による秘密分散システムは、データ分散装置とN台の分散データ保有装置を含む。
【００２６】
他の態様によるデータ分散装置は、K個の鍵s1,…,sK∈Sを選択する鍵選択部と、鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することにより擬似乱数r1,…,rKを生成する擬似乱数生成部と、情報a∈Rから擬似乱数r1,…,rKを用いて暗号文cを生成する暗号化部と、鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する鍵分散部と、暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、前記情報aを任意の準同型性をもつ秘密分散方式S2によりN個に分散した分散値ga(n)を用いて変換用チェックサムcαを生成し、任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する変換用生成部と、を有する。
【００２７】
他の態様による分散データ保有装置は、K個の分散値fsi(λ)から任意の秘密分散方式S1により復元した値uiから復元値Ui=P(ui)を計算し、K個の分散値fc(λ)から任意の秘密分散方式S0により復元値U0を復元する復元部と、復元値U0,Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する分散部と、K+1個の分散値fU0(i),…,fUK(i)から情報aの分散値ga(i)を生成する変換部と、分散値ga(i)を用いて生成した変換用検証値c’αとK個の分散値fcα(λ)を任意の秘密分散方式S3により復元した変換用チェックサムcαとを比較することで、分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する変換用検証部とを有する。
【発明の効果】
【００２８】
この発明の秘密分散技術によれば、計算量型秘密分散方式による分散値を任意の準同型性をもつ秘密分散方式による分散値に変換することができる。例えば、Shamir秘密分散方式など既存の多くの線形秘密分散方式は準同型性をもつ秘密分散方式であり、Shamir秘密分散方式など既存の線形秘密分散方式による分散値を用いてマルチパーティ計算を行う方法は既知である。そのため、準同型性をもつ秘密分散方式としてShamir秘密分散方式など既存の線形秘密分散方式を選択することで、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。また、暗号文cを分散する秘密分散方式S0として符号化効率がよい計算量型秘密分散方式を適用すれば分散値のサイズが小さくなるため、保存する分散値の総データ量および復元に必要な分散値の総データ量を減らすことができる。
【００２９】
また、この発明の秘密分散技術は復旧、再分散が可能となっており、一部の分散値が漏洩もしくは失われた場合でも対処することが可能である。そして、各操作においてチェックサムを検証することで分散値の改ざんを検知することができる。
【図面の簡単な説明】
【００３０】
【図１】秘密分散システムの機能構成を例示する図。
【図２】データ分散装置の機能構成を例示する図。
【図３】分散データ保有装置の機能構成を例示する図。
【図４】データ分散の処理フローを例示する図。
【図５】チェックサム生成の処理フローを例示する図。
【図６】分散データ変換の処理フローを例示する図。
【図７】データ復元の処理フローを例示する図。
【図８】分散データ復旧の処理フローを例示する図。
【図９】データ再分散の処理フローを例示する図。
【発明を実施するための形態】
【００３１】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００３２】
［実施形態］
この発明の実施形態に係る秘密分散システムは、計算量型秘密分散方式による分散値を、準同型性をもつ任意の秘密分散方式による分散値に変換する。この秘密分散システムでは復旧および再分散が可能である。また、予め元データや分散値のチェックサムを生成しておき、変換、復元、復旧の各操作においてチェックサムを検証する。
【００３３】
以下の説明では、N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、jはj∈λの整数であり、i≠jであり、ζは互いに異なる1以上N以下の2K-1個の整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であるものとする。写像P(x)は、入力されたx∈Sに対して環Rの要素を出力するものである。同一の入力xには同一のP(x)が対応する。すなわち、写像P(x)は入力が等しければ出力も等しくなる、確定的な写像である。入力xとP(x)とは一対一で対応してもよいし、しなくてもよい。例えば、写像P(x)はxをシードとして環Rの要素を返す擬似乱数生成関数である。また例えば、写像P(x)はxを暗号化鍵として固定の平文に対して環Rに属する暗号文を出力する共通鍵暗号関数である。写像P(x)は関数であってもよいし、アルゴリズムであってもよい。
【００３４】
＜構成＞
図１を参照して、実施形態に係る秘密分散システム１の構成例を説明する。秘密分散システム１は、データ分散装置１０とN（≧2）台の分散データ保有装置２０1〜２０Nとネットワーク９を含む。データ分散装置１０と分散データ保有装置２０1〜２０Nは、ネットワーク９に接続される。ネットワーク９は、データ分散装置１０と分散データ保有装置２０1〜２０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやＬＡＮ、ＷＡＮなどで構成することができる。また、データ分散装置１０と分散データ保有装置２０1〜２０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１０が出力する情報をＵＳＢメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から分散データ保有装置２０1〜２０Nへオフラインで入力するように構成してもよい。
【００３５】
図２を参照して、秘密分散システム１に含まれるデータ分散装置１０の構成例を説明する。データ分散装置１０は、入力部１１０と鍵選択部１２０と擬似乱数生成部１３０と暗号化部１４０と鍵分散部１５０と暗号文分散部１６０と復元用生成部１７０と出力部１８０と鍵復元部３１０と暗号文復元部３２０と復号部３３０と復元用検証部３４０とを有する。
【００３６】
図３を参照して、秘密分散システム１に含まれる分散データ保有装置２０nの構成例を説明する。分散データ保有装置２０nは、入力部２１０と復元部２２０と分散部２３０と変換部２４０と変換用検証部２５０と出力部２６０と補間部４１０と復旧部４２０と復旧用検証部４３０と再分散部５１０と一貫性検証部５２０と再復元部５３０と変換用生成部５４０と復旧用生成部５５０と記憶部２９０とを有する。記憶部２９０は、例えば、ＲＡＭ（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００３７】
＜データ分散処理＞
図４を参照して、データ分散装置１０の実行するデータ分散処理の動作例を、実際に行われる手続きの順に従って説明する。
【００３８】
入力部１１０には、情報aが入力される（ステップＳ１１０）。情報aは環Rに含まれる値である。したがって、a∈Rと表すことができる。情報aの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。情報aのデータ量は、例えば1メガバイト以上である。
【００３９】
鍵選択部１２０は、K個の鍵s1,…,sKを選択する（ステップＳ１２０）。鍵s1,…,sKは鍵空間Sに含まれる値である。したがって、s1,…,sK∈Sと表すことができる。鍵選択部１２０は、逐一ランダムにK個の鍵s1,…,sKを選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってK個の鍵s1,…,sKを選択してもよい。鍵s1,…,sKの鍵長は、必要な安全性と許容できる処理性能を確保できる長さに設定する。例えば、128〜256ビットとするのが一般的であるが、この限りではない。
【００４０】
K個の鍵s1,…,sKは擬似乱数生成部１３０に入力される。擬似乱数生成部１３０は、鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することによりK個の擬似乱数r1,…,rKを生成する（ステップＳ１３０）。
【００４１】
情報aおよびK個の擬似乱数r1,…,rKは暗号化部１４０に入力される。暗号化部１４０は、擬似乱数r1,…,rKを用いて情報aから暗号文cを生成する（ステップＳ１４０）。具体的には、以下の式(5)に示す通り、情報aから擬似乱数r1,…,rKの総和を減算した結果を暗号文cとする。
【００４２】
【数５】
2014138349.tif 000007
【００４３】
K個の鍵s1,…,sKは鍵分散部１５０に入力される。鍵分散部１５０は、鍵s1,…,sKを任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK(n)に分散する（ステップＳ１５０）。秘密分散方式S1はどのような秘密分散方式であってもよいが、情報aの復号に用いる鍵を分散するため、より安全性の高い秘密分散方式を適用することが望ましい。例えば、Shamir秘密分散方式を適用することができる。Shamir秘密分散方式は、N,Kが2以上の整数であり、N≧Kであるとして、元のデータaをN個に分散した分散値のうちK個以上の分散値からは元のデータaを復元することができるが、K個未満の分散値からは元のデータaの情報を一切得ることができない。したがって、安全性が高い秘密分散方式である。
【００４４】
暗号文cは暗号文分散部１６０に入力される。暗号文分散部１６０は、暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する（ステップＳ１６０）。秘密分散方式S0はどのような秘密分散方式であってもよいが、例えば非特許文献２に記載の方法を適用することができる。ただし非特許文献２に記載の方法を適用する場合には、環R上の値cをGF(p)上のK次ベクトルに変換する必要がある。これは例えば、素数pのビット長をL+1、環Rの要素のビット長をK×L以下とすれば、環Rの要素がK×Lビットになるように上位ビットを0でパディングし、値cをLビット毎に分割し、各Lビット分割値を0以上2L未満の整数としてGF(p)の元とすればよい。
【００４５】
情報aは復元用生成部１７０に入力される。復元用生成部１７０は、情報aを用いて復元用チェックサムcβを生成する（ステップＳ１７０）。生成するチェックサムはどのようなチェックサムであってもよいが、加算と乗算のみから計算できることが望ましい。例えば非特許文献５に記載のチェックサムとすることができる。具体的には、rを環R上の乱数（r∈R）とし、情報aを環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(6)により復元用チェックサムcβを生成する。
【００４６】
【数６】
2014138349.tif 000008
【００４７】
次に、復元用生成部１７０は、復元用チェックサムcβを任意の秘密分散方式S3によりN個の分散値fcβ(n)に分散する。秘密分散方式S3はどのような秘密分散方式であってもよく、この実施形態で用いる他の秘密分散方式と同じものであってもよい。例えば、Shamir秘密分散方式を適用することができる。
【００４８】
出力部１８０は、分散値fs1(n),…,fsK(n),fc(n),fcβ(n)を出力する（ステップＳ１８０）。出力された各分散値fs1(n),…,fsK(n),fc(n),fcβ(n)は、それぞれ分散データ保有装置２０1〜２０Nにネットワーク９もしくはＵＳＢメモリ等の可搬型記録媒体を経由して入力される。
【００４９】
＜チェックサム生成処理＞
図５を参照して、分散データ保有装置２０1,…,２０Nの実行するチェックサム生成処理の動作例を、実際に行われる手続きの順に従って説明する。この実施形態では分散データ保有装置２０iへ分散値fs1(i),…,fsK(i),fc(i),fcβ(i)が入力された場合を説明する。チェックサム生成処理は少なくとも分散値fs1(i),…,fsK(i),fc(i),fcβ(i)が入力された際には実行しなければならないが、以降は任意のタイミングで実行しても構わない。
【００５０】
入力部２１０には、データ分散装置１０が出力した分散値fs1(i),…,fsK(i),fc(i),fcβ(i)が入力される（ステップＳ２１０）。
【００５１】
分散値fs1(i),…,fsK(i),fc(i)は変換用生成部５４０へ入力される。変換用生成部５４０は、後述するデータ変換処理により、情報aの分散値ga(i)を生成する。続いて、生成した分散値ga(i)を用いて変換用チェックサムcαを生成する（ステップＳ５４０）。生成するチェックサムはどのようなチェックサムであってもよいが、加算と乗算のみから計算できることが望ましい。例えば、非特許文献５に記載のチェックサムとすることができる。具体的には、rを環R上の乱数（r∈R）とし、分散値ga(i)を環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(7)により変換用チェックサムcαを生成することができる。
【００５２】
【数７】
2014138349.tif 000009
【００５３】
次に、変換用生成部５４０は、変換用チェックサムcαを任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する。秘密分散方式S3は、復元用生成部１７０と同様に、どのような秘密分散方式であってもよく、この実施形態で用いる他の秘密分散方式と同じものであってもよい。例えば、Shamir秘密分散方式を適用することができる。
【００５４】
分散値fs1(i),…,fsK(i),fc(i),fcβ(i)は復旧用生成部５５０へ入力される。復旧用生成部５５０は、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を用いて復旧用チェックサムcγを生成する（ステップＳ５５０）。生成するチェックサムはどのようなチェックサムであってもよいが、加算と乗算のみから計算できることが望ましい。例えば、非特許文献５に記載のチェックサムとすることができる。具体的には、rを環R上の乱数（r∈R）とし、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(8)により復旧用チェックサムcγを生成することができる。
【００５５】
【数８】
2014138349.tif 000010
【００５６】
次に、復旧用生成部５５０は、復旧用チェックサムcγを任意の秘密分散方式S3によりN個の分散値fcγ(n)に分散する。秘密分散方式S3は、復元用生成部１７０と同様に、どのような秘密分散方式であってもよく、この実施形態で用いる他の秘密分散方式と同じものであってもよい。例えば、Shamir秘密分散方式を適用することができる。
【００５７】
出力部２６０は、分散値fcα(n),fcγ(n)を出力する（ステップＳ２６０）。出力された各分散値fcα(n),fcγ(n)は、それぞれ分散データ保有装置２０1〜２０Nにネットワーク９もしくはＵＳＢメモリ等の可搬型記録媒体を経由して入力される。また、分散値fs1(i),…,fsK(i),fc(i),fcα(i),fcβ(i),fcγ(i)を記憶部２９０へ記憶する。
【００５８】
＜分散データ変換処理＞
図６を参照して、分散データ保有装置２０1,…,２０Nの実行する分散データ変換処理の動作例を、実際に行われる手続きの順に従って説明する。
【００５９】
以下に示すステップＳ２１１からＳ２３０までの処理は、N台の分散データ保有装置２０1〜２０Nのすべてが行う必要はなく、任意に選択された少なくともK台の分散データ保有装置２０λ（λ∈{1,…,N}）が行えばよい。以下では分散データ保有装置２０i（i∈λ）が行う処理を説明する。
【００６０】
入力部２１０には、K台の分散データ保有装置２０λが記憶するそれぞれK個の分散値fsi(λ),fc(λ),fcα(λ)が入力される（ステップＳ２１１）。
【００６１】
K個の分散値fsi(λ)およびK個の分散値fc(λ)は復元部２２０に入力される。復元部２２０は、入力された分散値fsi(λ)から復元値Uiを生成し、分散値fc(λ)から復元値U0を生成する（ステップＳ２２０）。復元部２２０は、分散値fsi(λ)を任意の秘密分散方式S1により復元して値uiを生成する。続いて、Ui=P(ui)を計算することで復元値Uiを生成する。写像P(x)はデータ分散装置１０の有する擬似乱数生成部１３０と同じ写像である。上述の通り、データ分散装置１０の有する鍵分散部１５０により、分散値fsi(λ)には鍵siの分散値が設定されているため、同じ写像P(x)が鍵siを写した復元値Uiは擬似乱数riと等しくなる。秘密分散方式S1はどのような秘密分散方式であってもよいが、データ分散装置１０の有する鍵分散部１５０が用いる秘密分散方式S1と同じ方式でなければならない。
【００６２】
また、復元部２２０は、分散値fc(λ)を任意の秘密分散方式S0により復元することで復元値U0を生成する。上述の通り、データ分散装置１０の有する暗号文分散部１６０により、分散値fc(λ)には暗号文cの分散値が設定されているため、復元値U0は暗号文cと等しくなる。秘密分散方式S0はどのような秘密分散方式であってもよいが、データ分散装置１０の有する暗号文分散部１６０が用いる秘密分散方式S0と同じ方式でなければならない。
【００６３】
復元値U0および復元値Uiは分散部２３０に入力される。分散部２３０は、復元値U0および復元値Uiを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値fU0(n),fUi(n)に分散する（ステップＳ２３０）。準同型性とは2つの値a,bの分散値fa(i),fb(i)およびa+bの分散値fa+b(i)について、fa(i)+fb(i)=fa+b(i)が成り立つことをいう。秘密分散方式S2は準同型性をもつ秘密分散方式であればどのような秘密分散方式でもよい。例えば、Shamir秘密分散方式など既存の線形秘密分散方式を適用することができる。
【００６４】
以下に示すステップＳ２１２からＳ２６１までの処理は、N台の分散データ保有装置２０1〜２０Nのすべてで行う。以下では分散データ保有装置２０i（i∈{1,…,N}）が行う処理を説明する。。
【００６５】
入力部２１０には、K台の分散データ保有装置２０λの有する分散部２３０が生成したK個の分散値fU1(i),…,fUK(i)が入力される（ステップＳ２１２）。
【００６６】
復元部２２０の生成した分散値fU0(i)と入力部２１０から入力されたfU1(i),…,fUK(i)は変換部２４０に入力される。変換部２４０は、K+1個の分散値fU0(i),…,fUK(i)から情報aの分散値ga(i)を生成する（ステップＳ２４０）。具体的には、以下の式(9)に示す通り、分散値fU0(i),…,fUK(i)の総和を分散値ga(i)とする。
【００６７】
【数９】
2014138349.tif 000011
【００６８】
上述の通り、fU0(i)は準同型性をもつ秘密分散方式S2により暗号文cを分散した分散値であり、fU1(i),…,fUK(i)は準同型性をもつ秘密分散方式S2により擬似乱数r1,…,rKをそれぞれ分散した分散値である。したがって、準同型性の性質により、fU0(i),…,fUK(i)の総和は、暗号文cと擬似乱数r1,…,rKの総和を加算した値を秘密分散方式S2により分散した分散値となる。暗号文cは情報aから擬似乱数r1,…,rKの総和を減算した値であるため、この分散値ga(i)は、情報aを秘密分散方式S2により分散した分散値と等しい。
【００６９】
分散値ga(i)およびK個の分散値fcα(λ)は変換用検証部２５０に入力される。変換用検証部２５０は、分散値ga(i)を用いて変換用検証値c’αを生成する。生成する検証値は変換用生成部５４０で生成したチェックサムに対応した検証値である。例えば、変換用生成部５４０で非特許文献５に記載のチェックサムを生成した場合であれば、rを環R上の乱数（r∈R）とし、分散値ga(i)を環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(10)により変換用検証値c’αを生成することができる。
【００７０】
【数１０】
2014138349.tif 000012
【００７１】
また、変換用検証部２５０は、秘密分散方式S3によりK個の分散値fcα(λ)から変換用チェックサムcαを復元する。秘密分散方式S3はどのような秘密分散方式であってもよいが、変換用生成部５４０が用いる秘密分散方式S3と同じ方式でなければならない。
【００７２】
そして、変換用検証部２５０は、変換用検証値c’αと変換用チェックサムcαとを比較して、分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する（ステップＳ２５０）。変換用検証部２５０は、c’α=cαであれば分散値fs1(λ),…,fsK(λ),fc(λ)はいずれも改ざんされていないと判断する。c’α≠cαであれば分散値fs1(λ),…,fsK(λ),fc(λ)の少なくとも1個が改ざんされたと判断する。
【００７３】
出力部２６０は、改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。改ざんがないと判断した場合は分散値ga(i)を出力する（ステップＳ２６１）。分散値ga(i)を記憶部２９０へ記憶しておき、要求に応じて記憶部２９０から分散値ga(i)を読み出して出力してもよい。
【００７４】
＜データ復元処理＞
図７を参照して、データ分散装置１０の実行するデータ復元処理の動作例を、実際に行われる手続きの順に従って説明する。
【００７５】
入力部１１０には、K台の分散データ保有装置２０λが記憶するそれぞれK個の分散値fs1(λ),…,fsK(λ),fc(λ),fcβ(λ)が入力される（ステップＳ１１１）。
【００７６】
それぞれK個の分散値fs1(λ),…,fsK(λ)は鍵復元部３１０に入力される。鍵復元部３１０は、秘密分散方式S1により分散値fs1(λ),…,fsK(λ)からK個の鍵s1,…,sKを復元する（ステップＳ３１０）。秘密分散方式S1はどのような秘密分散方式であってもよいが、鍵分散部１５０が用いる秘密分散方式S1と同じ方式でなければならない。
【００７７】
K個の鍵s1,…,sKは擬似乱数生成部１３０に入力される。擬似乱数生成部１３０は、鍵s1,…,sKからr1=P(s1),…,rK=P(sK)を計算することによりK個の擬似乱数r1,…,rKを生成する（ステップＳ１３１）。
【００７８】
K個の分散値fc(λ)は暗号文復元部３２０に入力される。暗号文復元部３２０は、秘密分散方式S0により分散値fc(λ)から暗号文cを復元する（ステップＳ３２０）。秘密分散方式S0はどのような秘密分散方式であってもよいが、暗号文分散部１６０が用いる秘密分散方式S0と同じ方式でなければならない。
【００７９】
暗号文cおよびK個の擬似乱数r1,…,rKは復号部３３０に入力される。復号部３３０は、擬似乱数r1,…,rKを用いて暗号文cから情報aを復号する（ステップＳ３３０）。具体的には、以下の式(11)に示す通り、暗号文cに擬似乱数r1,…,rKの総和を加算した結果を情報aとする。
【００８０】
【数１１】
2014138349.tif 000013
【００８１】
情報aおよびK個の分散値fcβ(λ)は復元用検証部３４０に入力される。復元用検証部３４０は、情報aを用いて復元用検証値c’βを生成する。生成する検証値は復元用生成部１７０で生成したチェックサムに対応した検証値である。例えば、復元用生成部１７０で非特許文献５に記載のチェックサムを生成した場合であれば、rを環R上の乱数（r∈R）とし、情報aを環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(12)により復元用検証値c’βを生成することができる。
【００８２】
【数１２】
2014138349.tif 000014
【００８３】
また、復元用検証部３４０は、秘密分散方式S3によりK個の分散値fcβ(λ)から復元用チェックサムcβを復元する。秘密分散方式S3はどのような秘密分散方式であってもよいが、復元用生成部１７０が用いる秘密分散方式S3と同じ方式でなければならない。
【００８４】
そして、復元用検証部３４０は、復元用検証値c’βと復元用チェックサムcβとを比較して、分散値fs1(λ),…,fsK(λ),fc(λ)のいずれかが改ざんされたか否かを検証する（ステップＳ３４０）。復元用検証部３４０は、c’β=cβであれば分散値fs1(λ),…,fsK(λ),fc(λ)はいずれも改ざんされていないと判断する。c’β≠cβであれば分散値fs1(λ),…,fsK(λ),fc(λ)の少なくとも1個が改ざんされたと判断する。
【００８５】
出力部１８０は、改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。改ざんがないと判断した場合は復元した情報aを出力する（ステップＳ１８１）。
【００８６】
＜分散データ復旧処理＞
図８を参照して、秘密分散システム１の実行する分散データ復旧処理の動作例を、実際に行われる手続きの順に従って説明する。この実施形態では分散データ保有装置２０iが故障等により利用不可となり、保有する分散値fs1(i),…,fsK(i),fc(i),fcβ(i)が失われた場合を前提とする。
【００８７】
以下に示すステップＳ４１０からＳ４１１までの処理は、任意に選択された少なくともK台の分散データ保有装置２０λ（λ∈{1,…,N}）が行えばよい。以下では分散データ保有装置２０j(j∈λ;i≠j)が行う処理を説明する。。
【００８８】
記憶部２９０に記憶されている分散値fs1(j),…,fsK(j),fc(j),fcβ(j)が補間部４１０に入力される。補間部４１０は、分散値fs1(j),…,fsK(j),fc(j),fcβ(j)を秘密分散方式S4により分散し、再分散値[fs1(j)],…,[fsK(j)],[fc(j)],[fcβ(j)]を生成する（ステップＳ４１０）。秘密分散方式S4はどのような秘密分散方式であってもよく、例えば、Shamir秘密分散方式を用いることができる。
【００８９】
次に、補間部４１０は、再分散値[fs1(j)],…,[fsK(j)],[fc(j)],[fcβ(j)]を補間して再分散値[fs1(i)],…,[fsK(i)],[fc(i)],[fcβ(i)]を計算する（ステップＳ４１１）。補間の方法はどのような補間方法であってもよく、例えば、ラグランジュ補間により行うことができる。具体的には以下のように補間を行う。まず、ラグランジュ補間のための係数αijを求める。係数αijは、分散値fs1(j),…,fsK(j),fc(j),fcβ(j)それぞれについて、ajをいずれかの分散値として、以下の式(13)により求める。
【００９０】
【数１３】
2014138349.tif 000015
【００９１】
次に、再分散値[fs1(i)],…,[fsK(i)],[fc(i)],[fcβ(i)]は、再分散値[fs1(j)],…,[fsK(j)],[fc(j)],[fcβ(j)]それぞれについて、[ai]を補間する再分散値、[aj]を[ai]に対応する再分散値として、以下の式(14)により求める。
【００９２】
【数１４】
2014138349.tif 000016
【００９３】
以下に示すステップＳ４２０からＳ４３０までの処理は、分散データ保有装置２０i(i∈λ;i≠j)のみが行う。
【００９４】
K台の分散データ保有装置２０λが出力したそれぞれK個の再分散値[fs1(i)],…,[fsK(i)],[fc(i)],[fcβ(i)]とK個の分散値fcγ(λ)とは入力部２１０を介して復旧部４２０へ入力される。復旧部４２０は、秘密分散方式S4により再分散値[fs1(i)],…,[fsK(i)],[fc(i)],[fcβ(i)]から分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を復元する（ステップＳ４２０）。秘密分散方式S4はどのような秘密分散方式であってもよいが、補間部４１０が用いる秘密分散方式S4と同じ方式でなければならない。
【００９５】
分散値fs1(i),…,fsK(i),fc(i),fcβ(i)とK個の分散値fcγ(λ)は復旧用検証部４３０に入力される。復旧用検証部４３０は、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を用いて復旧用検証値c’γを生成する。生成する検証値は復旧用生成部５５０で生成したチェックサムに対応した検証値である。例えば、復旧用生成部５５０で非特許文献５に記載のチェックサムを生成した場合であれば、rを環R上の乱数（r∈R）とし、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を環R上のM個の値（a0,a1,…,aM-1∈R）として、以下の式(15)により復旧用検証値c’γを生成することができる。
【００９６】
【数１５】
2014138349.tif 000017
【００９７】
また、復旧用検証部４３０は、秘密分散方式S3によりK個の分散値fcγ(λ)から復旧用チェックサムcγを復元する。秘密分散方式S3はどのような秘密分散方式であってもよいが、復旧用生成部５５０が用いる秘密分散方式S3と同じ方式でなければならない。
【００９８】
そして、復旧用検証部４３０は、復旧用検証値c’γと復旧用チェックサムcγとを比較して、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)のいずれかが改ざんされたか否かを検証する（ステップＳ４３０）。復旧用検証部４３０は、c’γ=cγであれば分散値fs1(i),…,fsK(i),fc(i),fcβ(i)はいずれも改ざんされていないと判断する。c’γ≠cγであれば分散値fs1(i),…,fsK(i),fc(i),fcβ(i)の少なくとも1個が改ざんされたと判断する。
【００９９】
出力部２６０は、改ざんがあったと判断した場合はその旨を示す情報（例えば、「⊥」など）を出力する。改ざんがないと判断した場合は分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を記憶部２９０へ記憶する。
【０１００】
＜データ再分散処理＞
図９を参照して、秘密分散システム１の実行するデータ再分散処理の動作例を、実際に行われる手続きの順に従って説明する。データ再分散処理は少なくとも2K-1台の分散データ保有装置２０nが利用可能となっている必要がある。故障等により利用可能な分散データ保有装置２０nが2K-1台未満となっている場合には、データ再分散処理に先立って、上述の分散データ復旧処理により2K-1台以上の分散データ保有装置２０nを利用可能としておく。以降の説明では、2K-1台の分散データ保有装置２０ζ(ζ∈{1,…,N})が利用可能となっているものとする。データ再分散処理は、2K-1台の分散データ保有装置２０ζが行う。以下では、分散データ保有装置２０i（i∈ζ）が行う処理を説明する。
【０１０１】
記憶部２９０に記憶されている分散値fs1(i),…,fsK(i),fcβ(i)が再分散部５１０に入力される。再分散部５１０は、分散値fs1(i),…,fsK(i),fcβ(i)を秘密分散方式S1により分散して再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]を生成する（ステップＳ５１０）。秘密分散方式S1はどのような秘密分散方式であってもよいが、データ分散装置１０の有する鍵分散部１５０の用いる秘密分散方式S1と同じ方式でなければならない。
【０１０２】
再分散部５１０が秘密分散する際に用いる乱数は、鍵分散部１５０が秘密分散する際に用いた乱数と異なるものとする。例えば、rα1,…,rαKを環R上のK個の乱数（rα1,…,rαK∈R）とし、rβ1,…,rβKを環R上のK個の乱数（rβ1,…,rβK∈R）とし、乱数rα1,…,rαK,rβ1,…,rβKが相異なる乱数であるとして、鍵分散部１５０が乱数rα1,…,rαK∈Rを用いてShamir秘密分散により鍵s1,…,sKをそれぞれN個の分散値fs1(n),…,fsK(n)へ分散したとする。この場合、再分散部５１０は、乱数rβ1,…,rβK∈Rを用いてShamir秘密分散により分散値fs1(i),…,fsK(i)をそれぞれ2K-1個の再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]へ分散すればよい。
【０１０３】
再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]は出力部２６０を介して出力され、それぞれ2K-1台の分散データ保有装置２０ζにネットワーク９もしくはＵＳＢメモリ等の可搬型記録媒体を経由して入力される。
【０１０４】
2K-1台の分散データ保有装置２０ζの有する再分散部５１０が出力する再分散値[fs1(ζ)],…,[fsK(ζ)],[fcβ(ζ)]は入力部２１０を介して一貫性検証部５２０へ入力される。一貫性検証部５２０は、再分散値[fs1(ζ)],…,[fsK(ζ)],[fcβ(ζ)]を補間して再分散値[fs1(i)]’,…,[fsK(i)]’,[fcβ(i)]’を生成する（ステップＳ５２０）。補間の方法はどのような補間方法であってもよく、例えば、ラグランジュ補間により行うことができる。補間して生成した再分散値[fs1(i)]’,…,[fsK(i)]’,[fcβ(i)]’と再分散部５１０が生成した再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]とをそれぞれ比較し、分散値fs1(ζ),…,fsK(ζ),fcβ(ζ)の改ざん有無を検証する。k=1,…,Kのすべてについて[fsk(i)]’=[fsk(i)]かつ[fcβ(i)]’=[fcβ(i)]であれば、分散値fs1(ζ),…,fsK(ζ),fcβ(ζ)はいずれも改ざんされていないと判断する。いずれかのkについて[fsk(i)]’≠[fsk(i)]もしくは[fcβ(i)]’≠[fcβ(i)]であれば、少なくとも1個の分散値fs1(ζ),…,fsK(ζ),fcβ(ζ)が改ざんされたと判断する。
【０１０５】
2K-1台の分散データ保有装置２０ζがすべて改ざんなしと判断した場合、一貫性検証が成功したものとする。いずれかの分散データ保有装置２０z(z∈ζ)が改ざんありと判断した場合、一貫性検証が失敗したものとする。
【０１０６】
一貫性検証が成功した場合には、再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]が再復元部５３０に入力される。再復元部５３０は、秘密分散方式S1により乱数rα1,…,rαK∈Rを用いて再分散値[fs1(i)],…,[fsK(i)],[fcβ(i)]を復元することで、新たな分散値f’s1(i),…,f’sK(i),f’cβ(i)を生成する（ステップＳ５３０）。これにより、新たな分散値f’s1(i),…,f’sK(i),f’cβ(i)は鍵s1,…,sKを乱数rβ1,…,rβK∈Rを用いて秘密分散方式S1により分散した分散値と等しくなる。秘密分散方式S1はどのような秘密分散方式であってもよいが、データ分散装置１０の有する鍵分散部１５０の用いる秘密分散方式S1と同じ方式でなければならない。
【０１０７】
新たな分散値f’s1(i),…,f’sK(i),f’cβ(i)は復旧用生成部５５０へ入力される。復旧用生成部５５０は、分散値f’s1(i),…,f’sK(i),fc(i),f’cβ(i)を用いて新たな復旧用チェックサムc’γを生成する（ステップＳ５５０）。次に、復旧用生成部５５０は、新たな復旧用チェックサムc’γを秘密分散方式S3によりN個の分散値f’cγ(n)に分散する。
【０１０８】
出力部２６０は、分散値f’cγ(n)を出力する（ステップＳ２６２）。出力された分散値f’cγ(n)は、それぞれ分散データ保有装置２０1〜２０Nにネットワーク９もしくはＵＳＢメモリ等の可搬型記録媒体を経由して入力される。また、分散データ保有装置２０1〜２０Nは分散値f’cγ(i)を記憶部２９０へ記憶する。
【０１０９】
＜機密性＞
分散データ保有装置２０1〜２０Nが得る情報aに関する情報は、準同型性をもつ秘密分散方式S2による分散値であり、各分散値の生成に用いる乱数が互いに独立であれば、この実施形態の機密性は、利用する準同型性をもつ秘密分散方式S2の機密性に帰着される。また、K-1台の分散データ保有装置２０iは情報aの分散値である復元値Uiを得るが、K個の復元値U1,…,UKすべてを得られない限り情報aを得ることはできない。そのため、この実施形態の機密性は、結局、利用する秘密分散方式S2の機密性に帰着される。
【０１１０】
＜効果＞
この実施形態の秘密分散システムは、計算量型秘密分散方式による情報aの分散値fa(1),…,fa(N)を、任意の準同型性をもつ秘密分散方式S2による分散値ga(1),…,ga(N)に変換することができる。
【０１１１】
準同型性をもつ秘密分散方式としては、例えば、Shamir秘密分散方式など既存の線形秘密分散方式が挙げられる。Shamir秘密分散方式など既存の線形秘密分散方式を用いてマルチパーティ計算を行う方法は既知であるため、秘密分散方式S2としてShamir秘密分散方式など既存の任意の線形秘密分散方式を選択することで、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。
【０１１２】
例えば、非特許文献２に記載の計算量型秘密分散方式は分散値のサイズの下限が元のデータの1/Kとなるため、暗号文cを分散する秘密分散方式S0として非特許文献２に記載の計算量型秘密分散方式を適用すれば、分散値のサイズが元のデータと同程度となるShamir秘密分散方式と比較して、分散値を保存するために必要となる記憶容量を削減することができる。
【０１１３】
また、この発明の秘密分散技術は復旧、再分散が可能となっており、一部の分散値が漏洩もしくは失われた場合でも対処することが可能であり、安全性が向上している。
【０１１４】
そして、変換、復元、復旧の各操作においてチェックサムを検証することで分散値の改ざんを検知することができるため、各操作の正当性が保証される。
【０１１５】
［変形例１］
復元用チェックサムcβは分散データ保有装置２０1,…,２０Nそれぞれが生成してもよい。変換用チェックサムcαはデータ分散装置１０が生成してもよい。復旧用チェックサムcγはデータ分散装置１０が生成してもよい。これらの組み合わせは任意であり、例えば、すべてのチェックサムcα,cβ,cγをデータ分散装置１０が生成してもよいし、すべてのチェックサムcα,cβ,cγを分散データ保有装置２０1,…,２０Nそれぞれが生成してもよい。また、データ分散装置１０が復元用チェックサムcβと変換用チェックサムcαを生成し、分散データ保有装置２０1,…,２０Nそれぞれが復旧用チェックサムcγを生成してもよい。
【０１１６】
復元用チェックサムcβを分散データ保有装置２０1,…,２０Nが生成する場合には、分散データ保有装置２０1,…,２０Nは復元用生成部１７１を含み、データ分散装置１０は復元用生成部１７０を含まない。分散データ保有装置２０1,…,２０Nはチェックサム生成処理において以下のように復元用チェックサムcβを生成すればよい。
【０１１７】
入力部２１０から入力された分散値fs1(i),…,fsK(i),fc(i)は復元用生成部１７１に入力される。復元用生成部１７１は、上述したデータ変換処理により、情報aの分散値ga(i)を生成する。続いて、任意のマルチパーティ計算方法により、分散値ga(i)を用いて復元用チェックサムcβの分散値fcβ(i)を生成する。チェックサムの生成方法は復元用生成部１７０と同様である。マルチパーティ計算方法は例えば、非特許文献３や非特許文献４に記載の方法を用いることができる。分散値ga(i)は準同型性をもつ秘密分散方式S2による分散値であるので、加算と乗算からなるチェックサムを他の計算主体と通信することなく秘匿計算を行うことができる。したがって、分散値ga(i)を用いて計算したチェックサムは、情報aを用いて計算した復元用チェックサムcβの分散値となる。
【０１１８】
変換用チェックサムcαをデータ分散装置１０が生成する場合には、データ分散装置１０は変換用生成部５４１を含み、分散データ保有装置２０1,…,２０Nは変換用生成部５４０を含まない。データ分散装置１０はデータ分散処理において以下のように変換用チェックサムcαを生成すればよい。
【０１１９】
入力部１１０から入力された情報aは変換用生成部５４１に入力される。変換用生成部５４１は、情報aを任意の準同型性をもつ秘密分散方式S2によりN個の分散値ga(n)に分散する。続いて、i=1,…,Nごとに、分散値ga(i)を用いて変換用チェックサムcαを生成する。変換用チェックサムcαの生成方法は変換用生成部５４０と同様である。変換用生成部５４１は、変換用チェックサムcαを任意の秘密分散方式S3によりN個の分散値fcα(n)に分散する。秘密分散方式S3は変換用生成部５４０と同様である。
【０１２０】
復旧用チェックサムcγをデータ分散装置１０が生成する場合には、データ分散装置１０は復旧用生成部５５１を含み、分散データ保有装置２０1,…,２０Nは復旧用生成部５５０を含まない。データ分散装置１０はデータ分散処理において以下のように復旧用チェックサムcγを生成すればよい。
【０１２１】
鍵分散部１５０の出力する分散値fs1(n),…,fsK(n)と暗号文分散部１６０の出力する分散値fc(n)と復元用生成部１７０もしくは復元用生成部１７１の出力する分散値fcβ(n)は復旧用生成部５５１へ入力される。復旧用生成部５５１は、i=1,…,Nごとに、分散値fs1(i),…,fsK(i),fc(i),fcβ(i)を用いて復旧用チェックサムcγを生成する。復旧用チェックサムcγの生成方法は復旧用生成部５５０と同様である。復旧用生成部５５１は、復旧用チェックサムcγを任意の秘密分散方式S3によりN個の分散値fcγ(n)に分散する。秘密分散方式S3は復旧用生成部５５０と同様である。
【０１２２】
［変形例２］
変換用検証部２５０は、復元用チェックサムcβを用いて改ざん検知を行ってもよい。この場合には、分散データ保有装置２０1,…,２０Kは変換用生成部５４０を備えず、変換用検証部２５０は、以下のように改ざん検知を行えばよい。
【０１２３】
変換用検証部２５０は、上述したデータ変換処理により、情報aの分散値ga(i)を生成する。次に、変換用検証部２５０は、任意のマルチパーティ計算方法により、分散値ga(i)を用いて情報aの復元用検証値c’βを生成する。マルチパーティ計算方法は例えば、非特許文献３や非特許文献４に記載の方法を用いることができる。分散値ga(i)は準同型性をもつ秘密分散方式S2による分散値であるので、加算と乗算からなる検証値を他の計算主体と通信することなく秘匿計算を行うことができる。したがって、分散値ga(i)を用いて計算した検証値は、情報aを用いて計算した復元用検証値c’βの分散値となる。
【０１２４】
このように構成することで、秘密分散システム１は復元用チェックサムcβと変換用チェックサムcαとの両方を保持する必要がなく、必要とされるリソースを削減することができる。
【０１２５】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１２６】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【符号の説明】
【０１３１】
１  秘密分散システム
９  ネットワーク
１０  データ分散装置
２０  分散データ保有装置
１１０  入力部
１２０  鍵選択部
１３０  擬似乱数生成部
１４０  暗号化部
１５０  鍵分散部
１６０  暗号文分散部
１７０  復元用生成部
１８０  出力部
２１０  入力部
２２０  復元部
２３０  分散部
２４０  変換部
２５０  変換用検証部
２６０  出力部
３１０  鍵復元部
３２０  暗号文復元部
３３０  復号部
３４０  復元用検証部
４１０  補間部
４２０  復旧部
４３０  復旧用検証部
５１０  再分散部
５２０  一貫性検証部
５３０  再復元部
５４０  変換用生成部
５５０  復旧用生成部
【図１】
2014138349.tif 000018
【図２】
2014138349.tif 000019
【図３】
2014138349.tif 000020
【図４】
2014138349.tif 000021
【図５】
2014138349.tif 000022
【図６】
2014138349.tif 000023
【図７】
2014138349.tif 000024
【図８】
2014138349.tif 000025
【図９】
2014138349.tif 000026