(57)【要約】  秘密分散システムは、計算量型秘密分散の分散値を、準同型性をもつ秘密分散の分散値に変換する。データ分散装置は、鍵選択部が、K'-1個の鍵sjを選択する。擬似乱数生成部が鍵sjから擬似乱数rjを生成する。暗号化部が、情報aから擬似乱数rjを用いて暗号文cを生成する。鍵分散部が、鍵sjを任意の秘密分散方式S1によりそれぞれN個の分散値fsj(n)に分散する。暗号文分散部が、暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する。分散データ変換装置は、復元部が、K個の分散値fsj(i)が入力されると、分散値fsj(i)を秘密分散方式S1により復元し、復元値Ujを生成し、K個の分散値fc(i)が入力されると、分散値fc(i)を分散方式S0により復元することで、復元値Uj(j=K')を生成する。再分散部が、準同型性をもつ秘密分散方式S2により復元値UjをN個の分散値fUj(n)に分散する。変換部が、K'個の分散値fUjから情報aの分散値ga(i)を生成する。
2014007310.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-1個の鍵s1,…,sK-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK-1を用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を備え、
前記分散データ変換装置は、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記秘密分散方式S0により復元することで、復元値Uj(j=K)を生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K個の分散値fU1(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換部と、
を備える秘密分散システム。
【請求項２】
データ分散装置とN台の分散データ変換装置を含む秘密分散システムであって、
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
前記データ分散装置は、
K’-1個の鍵s1,…,sK’-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK’-1を用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(n)に分散する鍵分散部と、
前記暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を備え、
前記分散データ変換装置は、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記分散方式S0により復元することで、復元値Uj(j=K’)を生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K’個の分散値fU1(i),…,fUK’(i)から前記情報aの分散値ga(i)を生成する変換部と、
を備える秘密分散システム。
【請求項３】
請求項１に記載の秘密分散システムであって、
前記暗号化部は、前記情報aから前記擬似乱数r1,…,rK-1の総和を減算して前記暗号文cを生成し、
前記変換部は、前記分散値fU1(i),…,fUK(i)の総和を前記分散値ga(i)とする
秘密分散システム。
【請求項４】
請求項２に記載の秘密分散システムであって、
前記暗号化部は、前記情報aから前記擬似乱数r1,…,rK’-1の総和を減算して前記暗号文cを生成し、
前記変換部は、前記分散値fU1(i),…,fUK’(i)の総和を前記分散値ga(i)とする
秘密分散システム。
【請求項５】
請求項１から４のいずれかに記載の秘密分散システムであって、
前記秘密分散方式S2は、Shamir秘密分散方式である
秘密分散システム。
【請求項６】
N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
K-1個の鍵s1,…,sK-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK-1を用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を備えるデータ分散装置。
【請求項７】
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
K’-1個の鍵s1,…,sK’-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK’-1を用いて暗号文cを生成する暗号化部と、
前記鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(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へ移す写像であり、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を所定の秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を所定の秘密分散方式S0により復元することで、復元値Ujを生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K個の分散値fU1(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換部を備え、
前記分散値fsj(i)は、K個の鍵s1,…,sK-1∈Sを前記秘密分散方式S1によりそれぞれN個に分散した分散値fs1(n),…,fsK-1(n)に含まれ、
前記分散値fc(i)は、前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより生成された擬似乱数r1,…,rK-1を用いて情報a∈Rから生成した暗号文cを、前記秘密分散方式S0によりN個に分散した分散値fc(n)に含まれる
分散データ変換装置。
【請求項９】
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を所定の秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を所定の分散方式S0により復元することで、復元値Uj(j=K’)を生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K’個の分散値fU1(i),…,fUK’(i)から前記情報aの分散値ga(i)を生成する変換部を備え、
前記分散値fsj(i)は、K’個の鍵s1,…,sK’-1∈Sを前記秘密分散方式S1によりそれぞれN個に分散した分散値fs1(n),…,fsK’-1(n)に含まれ、
前記分散値fc(i)は、前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより生成された擬似乱数r1,…,rK’-1を用いて情報a∈Rから生成した暗号文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へ移す写像であり、
データ分散装置が、K-1個の鍵s1,…,sK-1∈Sを選択する鍵選択ステップと、
前記データ分散装置が、前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する擬似乱数生成ステップと、
前記データ分散装置が、情報a∈Rから前記擬似乱数r1,…,rK-1を用いて暗号文cを生成する暗号化ステップと、
前記データ分散装置が、前記鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する鍵分散ステップと、
前記データ分散装置が、前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
分散データ変換装置が、K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記秘密分散方式S0により復元することで、復元値Ujを生成する復元ステップと、
前記分散データ変換装置が、前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散ステップと、
前記分散データ変換装置が、K個の分散値fU1(i),…,fUK(i)から前記情報aの分散値ga(i)を生成する変換ステップと、
を含む秘密分散方法。
【請求項１１】
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
データ分散装置が、K’-1個の鍵s1,…,sK’-1∈Sを選択する鍵選択ステップと、
前記データ分散装置が、前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する擬似乱数生成ステップと、
前記データ分散装置が、情報a∈Rから前記擬似乱数r1,…,rK’-1を用いて暗号文cを生成する暗号化ステップと、
前記データ分散装置が、前記鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(n)に分散する鍵分散ステップと、
前記データ分散装置が、前記暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
分散データ変換装置が、K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記分散方式S0により復元することで、復元値Uj(j=K’)を生成する復元ステップと、
前記分散データ変換装置が、前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散ステップと、
前記分散データ変換装置が、K’個の分散値fU1(i),…,fUK’(i)から前記情報aの分散値ga(i)を生成する変換ステップと、
を含む秘密分散方法。
【請求項１２】
請求項６または７に記載のデータ分散装置もしくは請求項８または９に記載の分散データ変換装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、計算量型秘密分散技術およびマルチパーティ計算技術に関する。
【背景技術】
【０００２】
秘密分散は、データを複数の分散値に変換し、一定個数以上の分散値を用いれば元のデータを復元でき、一定個数未満の分散値からは元のデータを一切復元できなくする技術である。分散値の総数を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以下の整数として以下の関係が成り立つため、任意の異なるK個の分散値からaを復元できる。
【数１】
2014007310.tif 000003
【０００４】
また、秘密分散の一種として、計算量的安全性に基づき一定個数未満の分散値からは元のデータを一切復元できなくする、計算量型秘密分散方式がある（例えば、非特許文献２参照）。この方式の例では、情報a=(a0,a1,…,aK-1)(a0,a1,…,aK-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の解を求めればよい。
【数２】
2014007310.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)上の乱数の線形結合で表現できる秘密分散と定義される。任意の線形秘密分散方式をマルチパーティ計算に拡張できることが知られている（非特許文献４参照）。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】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.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
Shamir秘密分散方式では、情報aおよびその各分散値のデータ量を一定とすると、分散値の総データ量がそれぞれ情報aのデータ量のおよそN倍となる。復元に必要な分散値の総データ量はそれぞれ情報aのデータ量のおよそK倍となる。分散値のデータ量の増加は通信時間や保存データの増大につながるため、できるだけ分散値のデータ量を抑えることが望ましい。【０００９】
計算量型秘密分散方式は一般にTi(a)+Ti(b)≠Ti(a+b)となる。したがって、計算量型秘密分散方式では、Shamir秘密分散方式とは異なり、各入力の加算のマルチパーティ計算を行う方法は自明でない。しかし、計算量型秘密分散方式には、分散値の総データ量や復元に必要な分散値の総データ量を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-1個の鍵s1,…,sK-1∈Sを選択する。擬似乱数生成部は、鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する。暗号化部は、情報a∈Rから擬似乱数r1,…,rK-1を用いて暗号文cを生成する。鍵分散部は、鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する。暗号文分散部は、暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する。【００１３】
この態様の分散データ変換装置は、復元部と再分散部と変換部とを備える。復元部は、K個の分散値fsj(i)が入力されると、分散値fsj(i)を所定の秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、分散値fc(i)を所定の秘密分散方式S0により復元することで、復元値Uj(j=K)を生成する。再分散部は、復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する。変換部は、K個の分散値fU1(i),…,fUK(i)から情報aの分散値ga(i)を生成する。【００１４】
この発明の他の一態様の秘密分散システムは、データ分散装置とN台の分散データ変換装置を含む。この発明では、N,K，K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であるものとする。【００１５】
この態様のデータ分散装置は、鍵選択部と擬似乱数生成部と暗号化部と鍵分散部と暗号文分散部とを備える。鍵選択部は、K’-1個の鍵s1,…,sK’-1∈Sを選択する。擬似乱数生成部は、鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する。暗号化部は、情報a∈Rから擬似乱数r1,…,rK’-1を用いて暗号文cを生成する。鍵分散部は、鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(n)に分散する。暗号文分散部は、暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する。【００１６】
この態様の分散データ変換装置は、復元部と再分散部と変換部とを備える。復元部は、K個の分散値fsj(i)が入力されると、分散値fsj(i)を所定の秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、分散値fc(i)を所定の分散方式S0により復元することで、復元値Uj(j=K’)を生成する。再分散部は、復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する。変換部は、K’個の分散値fU1(i),…,fUK’(i)から情報aの分散値ga(i)を生成する。
【発明の効果】
【００１７】
この発明の秘密分散技術によれば、計算量型秘密分散方式による分散値を、任意の準同型性をもつ秘密分散方式による分散値に変換することができる。例えば、Shamir秘密分散方式など既存の多くの線形秘密分散方式は準同型性をもつ秘密分散方式であり、Shamir秘密分散方式など既存の線形秘密分散方式による分散値を用いてマルチパーティ計算を行う方法は既知である。そのため、準同型性をもつ秘密分散方式としてShamir秘密分散方式など既存の線形秘密分散方式を選択することで、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。また、暗号文cを分散する秘密分散方式S0として符号化効率がよい計算量型秘密分散方式を適用すれば、分散値のサイズが小さくなるため、保存する分散値の総データ容量および復元に必要な分散値の総データ容量を減らすことができる。
【図面の簡単な説明】
【００１８】
【図１】図１は、第一実施形態の秘密分散システムの機能構成を例示する図である。
【図２】図２は、第一実施形態のデータ分散装置の機能構成を例示する図である。
【図３】図３は、第一実施形態の分散データ変換装置の機能構成を例示する図である。
【図４】図４は、第一実施形態のデータ分散装置の処理フローを例示する図である。
【図５】図５は、第一実施形態の分散データ変換装置の処理フローを例示する図である。
【図６】図６は、第二実施形態の秘密分散システムの機能構成を例示する図である。
【図７】図７は、第二実施形態のデータ分散装置の機能構成を例示する図である。
【図８】図８は、第二実施形態の分散データ変換装置の機能構成を例示する図である。
【図９】図９は、第二実施形態のデータ分散装置の処理フローを例示する図である。
【図１０】図１０は、第二実施形態の分散データ変換装置の処理フローを例示する図である。
【発明を実施するための形態】
【００１９】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
［第一実施形態］
この発明の第一実施形態に係る秘密分散システムは、計算量型秘密分散方式による分散値を、準同型性をもつ任意の秘密分散方式による分散値に変換する。
【００２０】
＜構成＞
図１を参照して、第一実施形態に係る秘密分散システム１の構成例を説明する。秘密分散システム１は、データ分散装置１０と少なくともN台の分散データ変換装置２０1〜２０Nとネットワーク９０を含む。データ分散装置１０と分散データ変換装置２０1〜２０Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１０と分散データ変換装置２０1〜２０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやLAN、WANなどで構成することができる。また、データ分散装置１０と分散データ変換装置２０1〜２０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１０が出力する情報をUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から分散データ変換装置２０1〜２０Nへオフラインで入力するように構成してもよい。
【００２１】
図２を参照して、秘密分散システム１に含まれるデータ分散装置１０の構成例を説明する。データ分散装置１０は、入力部１１０と鍵選択部１２０と擬似乱数生成部１３０と暗号化部１４０と鍵分散部１５０と暗号文分散部１６０と出力部１７０とを備える。
【００２２】
図３を参照して、秘密分散システム１に含まれる分散データ変換装置２０の構成例を説明する。分散データ変換装置２０は、入力部２１０と復元部２２０と再分散部２３０と変換部２４０と出力部２５０と記憶部２９０とを備える。記憶部２９０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００２３】
＜データ分散処理＞
図４を参照して、データ分散装置１０の動作例を、実際に行われる手続きの順に従って説明する。以下の説明では、N,Kは2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、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)は関数であってもよいし、アルゴリズムであってもよい。
【００２４】
ステップＳ１１０において、入力部１１０に、情報aが入力される。情報aは環Rに含まれる値である。したがって、a∈Rと表すことができる。情報aの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。情報aのデータ量は、例えば1メガバイト以上である。
【００２５】
ステップＳ１２０において、鍵選択部１２０は、K-1個の鍵s1,…,sK-1∈Sを選択する。鍵選択部１２０は、逐一ランダムにK-1個の鍵s1,…,sK-1を選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってK-1個の鍵s1,…,sK-1を選択してもよい。鍵s1,…,sK-1の鍵長は、必要な安全性と許容できる処理性能を確保できる長さに設定する。例えば、128〜256ビットとするのが一般的であるが、この限りではない。
【００２６】
鍵s1,…,sK-1は擬似乱数生成部１３０に入力される。ステップＳ１３０において、擬似乱数生成部１３０は、鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する。
【００２７】
情報aと擬似乱数r1,…,rK-1は暗号化部１４０に入力される。ステップＳ１４０において、暗号化部１４０は、情報aから擬似乱数r1,…,rK-1を用いて暗号文cを生成する。より具体的には、以下の式に示す通り、情報aから擬似乱数r1,…,rK-1の総和を減算した結果を暗号文cとする。
【数３】
2014007310.tif 000005
【００２８】
鍵s1,…,sK-1は鍵分散部１５０にも入力される。ステップＳ１５０において、鍵分散部１５０は、鍵s1,…,sK-1をそれぞれ任意の秘密分散方式S1によりN個の分散値fs1(n),…,fsK-1(n)(n=1,…,N)に分散する。秘密分散方式S1は、どのような秘密分散方式であってもよいが、情報aの復号に用いる鍵を分散するため、より安全性の高い秘密分散方式を適用することが望ましい。例えば、Shamir秘密分散方式を適用することができる。Shamir秘密分散方式は、N,Kが2以上の整数であり、N≧Kであるとして、元のデータをN個に分散した分散値のうちK個以上の分散値からは元のデータを復元することができるが、K個未満の分散値からは元のデータの情報を一切得ることができないため、安全性が高い秘密分散方式である。
【００２９】
暗号文cは暗号文分散部１６０に入力される。ステップＳ１６０において、暗号文分散部１６０は、暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)(n=1,…,N)に分散する。秘密分散方式S0はどのような秘密分散方式であってもよいが、例えば非特許文献２に記載の方法を適用することができる。ただし非特許文献２に記載の方法を適用する場合には、環R上の値cをGF(p)上のK次ベクトルに変換する必要がある。これは例えば、素数pのビット長をL+1、環Rの要素のビット長をK×L以下とすれば、環Rの要素がK×Lビットになるように上位ビットを0でパディングし、値cをLビット毎に分割し、各Lビット分割値を0以上2L未満の整数としてGF(p)の元とすればよい。
【００３０】
ステップＳ１７０において、出力部１７０は、分散値fs1(n),…,fsK-1(n),fc(n)(n=1,…,N)を出力する。出力された各分散値fs1(n),…,fsK-1(n),fc(n)(n=1,…,N)は、それぞれ分散データ変換装置２０1〜２０Nにネットワーク９０もしくはUSBメモリ等の可搬型記録媒体を経由して入力される。
【００３１】
＜分散データ変換処理＞
図５を参照して、分散データ変換装置２０iの動作例を、実際に行われる手続きの順に従って説明する。
ステップＳ２１１において、入力部２１０に、データ分散装置１０が出力したK個の分散値fsj(i)(i∈λ)もしくはK個の分散値fc(i)が入力される。分散値fsj(i)もしくはfc(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fsj(i)もしくはfc(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００３２】
K個の分散値fsj(i)もしくはK個の分散値fc(i)は復元部２２０に入力される。ステップＳ２２０において、復元部２２０は、入力された分散値fsj(i)もしくは分散値fc(i)から復元値Ujを生成する。分散値fsj(i)が入力されると、分散値fsj(i)を任意の秘密分散方式S1により復元して値ujを生成する。続いて、Uj=P(uj)を計算することで、復元値Ujとする。写像P(x)はデータ分散装置１０の備える擬似乱数生成部１３０と同じ写像である。上述の通り、データ分散装置１０の備える鍵分散部１５０により、fsj(i)(j=1,…,K-1)には鍵sjの分散値が設定されているため、同じ写像P(x)が鍵sjを写した復元値Ujは擬似乱数rjと等しくなる。秘密分散方式S1はどのような秘密分散方式であってもよいが、データ分散装置１０の備える鍵分散部１５０が用いる秘密分散方式S1と同じ方式でなければならない。
【００３３】
分散値fc(i)が入力されると、分散値fc(i)を任意の秘密分散方式S0により復元することで、復元値Uj(j=K)を生成する。上述の通り、データ分散装置１０の備える暗号文分散部１６０により、fc(i)には暗号文cの分散値が設定されているため、復元値Ujは暗号文cと等しくなる。秘密分散方式S0はどのような秘密分散方式であってもよいが、データ分散装置１０の備える暗号文分散部１６０が用いる秘密分散方式S0と同じ方式でなければならない。
【００３４】
復元値Ujは再分散部２３０に入力される。ステップＳ２３０において、再分散部２３０は、復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)(n=1,…,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のすべてが行う必要はなく、任意に選択された少なくともK台が行えばよい。
【００３６】
ステップＳ２１２において、入力部２１０に、K台の分散データ変換装置２０i(i∈λ)の備える再分散部２３０が生成したK個の分散値fU1(i),…,fUK(i)が入力される。分散値fU1(i),…,fUK(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fU1(i),…,fUK(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００３７】
分散値fU1(i),…,fUK(i)は変換部２４０に入力される。ステップＳ２４０において、変換部２４０は、K個の分散値fU1(i),…,fUK(i)から情報aの分散値ga(i)を生成する。より具体的には、以下の式に示す通り、分散値fU1(i),…,fUK(i)の総和を分散値ga(i)とすることができる。
【数４】
2014007310.tif 000006
【００３８】
上述の通り、fUK(i)は準同型性をもつ秘密分散方式S2により暗号文cを分散した分散値であり、fU1(i),…,fUK-1(i)は準同型性をもつ秘密分散方式S2により擬似乱数r1,…,rK-1をそれぞれ分散した分散値である。したがって、準同型性の性質により、fU1(i),…,fUK(i)の総和は、暗号文cと擬似乱数r1,…,rK-1の総和を加算した値を秘密分散方式S2により分散した分散値となる。暗号文cは情報aから擬似乱数r1,…,rK-1の総和を減算した値であるため、この分散値ga(i)は、情報aを秘密分散方式S2により分散した分散値と等しい。
【００３９】
ステップＳ２５０において、出力部２５０は、分散値ga(i)を出力する。分散値ga(i)を記憶部２９０へ記憶しておき、外部からの要求に応じて記憶部２９０から分散値ga(i)を読みだして出力してもよい。
なお、図５に示すステップＳ２１２からステップＳ２５０までの処理は、N台の分散データ変換装置２０1〜２０Nのすべてで行う。
【００４０】
＜機密性＞
分散データ変換装置２０1〜２０Nが得る情報aに関する情報は、準同型性をもつ秘密分散方式S2による分散値であり、各分散値の生成に用いる乱数が互いに独立であれば、この実施形態の機密性は、利用する準同型性をもつ秘密分散方式S2の機密性に帰着される。また、K台の分散データ変換装置２０iはそれぞれ情報aの分散値である復元値Ujの何れかを得るが、K個の復元値U1,…,UKすべてを得られない限り情報aを得ることはできない。そのため、この実施形態の機密性は、結局、利用する秘密分散方式S2の機密性に帰着される。
【００４１】
＜効果＞
この実施形態の秘密分散システムは、計算量型秘密分散方式による情報aの分散値fa(1),…,fa(N)を、任意の準同型性をもつ秘密分散方式S2による分散値ga(1),…,ga(N)に変換することができる。
【００４２】
準同型性をもつ秘密分散方式としては、例えば、Shamir秘密分散方式など既存の線形秘密分散方式が挙げられる。Shamir秘密分散方式など既存の線形秘密分散方式を用いてマルチパーティ計算を行う方法は既知であるため、秘密分散方式S2としてShamir秘密分散方式など既存の任意の線形秘密分散方式を選択することで、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。
【００４３】
例えば、非特許文献２に記載の計算量型秘密分散方式は分散値のサイズの下限が元のデータの1/Kとなるため、暗号文cを分散する秘密分散方式S0として非特許文献２に記載の計算量型秘密分散方式を適用すれば、分散値のサイズが元のデータと同程度となるShamir秘密分散方式と比較して、分散値を保存するために必要となる記憶容量を削減することができる。
【００４４】
［第二実施形態］
この発明の第二実施形態に係る秘密分散システムは、計算量型秘密分散方式による分散値を、準同型性をもつ任意の秘密分散方式による分散値に変換する。第一実施形態では、生成する鍵の数と秘密分散方式の復元の閾値を同数であったが、必ずしも同数でなくとも構わない。第二実施形態では、鍵の数と復元の閾値を異なる値とした場合の例を示す。
【００４５】
＜構成＞
図６を参照して、第二実施形態に係る秘密分散システム２の構成例を説明する。秘密分散システム２は、データ分散装置１２と少なくともN台の分散データ変換装置２２1〜２２Nとネットワーク９０を含む。データ分散装置１２と分散データ変換装置２２1〜２２Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１２と分散データ変換装置２２1〜２２Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやLAN、WANなどで構成することができる。また、データ分散装置１２と分散データ変換装置２２1〜２２Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１２が出力する情報をUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から分散データ変換装置２２1〜２２Nへオフラインで入力するように構成してもよい。
【００４６】
図７を参照して、秘密分散システム２に含まれるデータ分散装置１２の構成例を説明する。データ分散装置１２は、入力部１１０と鍵選択部１２２と擬似乱数生成部１３２と暗号化部１４２と鍵分散部１５２と暗号文分散部１６０と出力部１７２とを備える。
【００４７】
図８を参照して、秘密分散システム２に含まれる分散データ変換装置２２の構成例を説明する。分散データ変換装置２２は、入力部２１２と復元部２２０と再分散部２３０と変換部２４２と出力部２５０と記憶部２９０とを備える。記憶部２９０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００４８】
＜データ分散処理＞
図９を参照して、データ分散装置１２の動作例を、実際に行われる手続きの順に従って説明する。以下の説明では、N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、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)は関数であってもよいし、アルゴリズムであってもよい。
【００４９】
ステップＳ１１０において、入力部１１０に、情報aが入力される。情報aは環Rに含まれる値である。したがって、a∈Rと表すことができる。情報aの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。情報aのデータ量は、例えば1メガバイト以上である。
【００５０】
ステップＳ１２２において、鍵選択部１２２は、K’-1個の鍵s1,…,sK’-1∈Sを選択する。鍵選択部１２２は、逐一ランダムにK’-1個の鍵s1,…,sK’-1を選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってK’-1個の鍵s1,…,sK’-1を選択してもよい。鍵s1,…,sK’-1の鍵長は、必要な安全性と許容できる処理性能を確保できる長さに設定する。例えば、128〜256ビットとするのが一般的であるが、この限りではない。
【００５１】
鍵s1,…,sK’-1は擬似乱数生成部１３２に入力される。ステップＳ１３２において、擬似乱数生成部１３２は、鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する。
【００５２】
情報aと擬似乱数r1,…,rK’-1は暗号化部１４２に入力される。ステップＳ１４２において、暗号化部１４２は、情報aから擬似乱数r1,…,rK’-1を用いて暗号文cを生成する。より具体的には、以下の式に示す通り、情報aから擬似乱数r1,…,rK’-1の総和を減算した結果を暗号文cとする。
【数５】
2014007310.tif 000007
【００５３】
鍵s1,…,sK’-1は鍵分散部１５２にも入力される。ステップＳ１５２において、鍵分散部１５２は、鍵s1,…,sK’-1をそれぞれ任意の秘密分散方式S1によりN個の分散値fs1(n),…,fsK’-1(n)(n=1,…,N)に分散する。秘密分散方式S1は、どのような秘密分散方式であってもよいが、情報aの復号に用いる鍵を分散するため、より安全性の高い秘密分散方式を適用することが望ましい。例えば、Shamir秘密分散方式を適用することができる。Shamir秘密分散方式は、N,Kが2以上の整数であり、N≧Kであるとして、元のデータをN個に分散した分散値のうちK個以上の分散値からは元のデータを復元することができるが、K個未満の分散値からは元のデータの情報を一切得ることができないため、安全性が高い秘密分散方式である。
【００５４】
暗号文cは暗号文分散部１６０に入力される。ステップＳ１６０において、暗号文分散部１６０は、暗号文cを任意の分散方式S0によりN個の分散値fc(n)(n=1,…,N)に分散する。分散方式S0はどのような分散方式であってもよく、情報伝播アルゴリズム（Information Dispersal Algorithm、IDA）と呼ばれる、秘匿性を考慮しない分散方式であっても構わない。分散方式S0は、例えば非特許文献２に記載の方法を適用することができる。ただし非特許文献２に記載の方法を適用する場合には、環R上の値cをGF(p)上のK次ベクトルに変換する必要がある。これは例えば、素数pのビット長をL+1、環Rの要素のビット長をK×L以下とすれば、環Rの要素がK×Lビットになるように上位ビットを0でパディングし、値cをLビット毎に分割し、各Lビット分割値を0以上2L未満の整数としてGF(p)の元とすればよい。
【００５５】
ステップＳ１７２において、出力部１７２は、分散値fs1(n),…,fsK’-1(n),fc(n)(n=1,…,N)を出力する。出力された各分散値fs1(n),…,fsK’-1(n),fc(n)(n=1,…,N)は、それぞれ分散データ変換装置２２1〜２２Nにネットワーク９０もしくはUSBメモリ等の可搬型記録媒体を経由して入力される。
【００５６】
＜分散データ変換処理＞
図１０を参照して、分散データ変換装置２２iの動作例を、実際に行われる手続きの順に従って説明する。
ステップＳ２１１において、入力部２１２に、データ分散装置１２が出力したK個の分散値fsj(i)(i∈λ)もしくはK個の分散値fc(i)が入力される。分散値fsj(i)もしくはfc(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fsj(i)もしくはfc(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００５７】
K個の分散値fsj(i)もしくはK個の分散値fc(i)は復元部２２０に入力される。ステップＳ２２０において、復元部２２０は、入力された分散値fsj(i)もしくは分散値fc(i)から復元値Ujを生成する。分散値fsj(i)が入力されると、分散値fsj(i)を任意の秘密分散方式S1により復元して値ujを生成する。続いて、Uj=P(uj)を計算することで、復元値Ujとする。写像P(x)はデータ分散装置１２の備える擬似乱数生成部１３０と同じ写像である。上述の通り、データ分散装置１２の備える鍵分散部１５０により、fsj(i)(j=1,…,K’-1)には鍵sjの分散値が設定されているため、同じ写像P(x)が鍵sjを写した復元値Ujは擬似乱数rjと等しくなる。秘密分散方式S1はどのような秘密分散方式であってもよいが、データ分散装置１２の備える鍵分散部１５０が用いる秘密分散方式S1と同じ方式でなければならない。
【００５８】
分散値fc(i)が入力されると、分散値fc(i)を任意の分散方式S0により復元することで、復元値Uj(j=K’)を生成する。上述の通り、データ分散装置１２の備える暗号文分散部１６０により、fc(i)には暗号文cの分散値が設定されているため、復元値Uj(j=K’)は暗号文cと等しくなる。分散方式S0はどのような分散方式であってもよいが、データ分散装置１２の備える暗号文分散部１６０が用いる分散方式S0と同じ方式でなければならない。
【００５９】
復元値Ujは再分散部２３０に入力される。ステップＳ２３０において、再分散部２３０は、復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)(n=1,…,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のすべてが行う必要はなく、任意に選択された少なくともK台が行えばよい。
【００６１】
ステップＳ２１３において、入力部２１２に、K’台の分散データ変換装置２２i(i∈λ)の備える再分散部２３０が生成したK’個の分散値fU1(i),…,fUK’(i)が入力される。分散値fU1(i),…,fUK’(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fU1(i),…,fUK’(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００６２】
分散値fU1(i),…,fUK’(i)は変換部２４２に入力される。ステップＳ２４２において、変換部２４２は、K’個の分散値fU1(i),…,fUK’(i)から情報aの分散値ga(i)を生成する。より具体的には、以下の式に示す通り、分散値fU1(i),…,fUK’(i)の総和を分散値ga(i)とすることができる。
【数６】
2014007310.tif 000008
【００６３】
上述の通り、fUK’(i)は準同型性をもつ秘密分散方式S2により暗号文cを分散した分散値であり、fU1(i),…,fUK’-1(i)は準同型性をもつ秘密分散方式S2により擬似乱数r1,…,rK’-1をそれぞれ分散した分散値である。したがって、準同型性の性質により、fU1(i),…,fUK’(i)の総和は、暗号文cと擬似乱数r1,…,rK’-1の総和を加算した値を秘密分散方式S2により分散した分散値となる。暗号文cは情報aから擬似乱数r1,…,rK’-1の総和を減算した値であるため、この分散値ga(i)は、情報aを秘密分散方式S2により分散した分散値と等しい。
【００６４】
ステップＳ２５０において、出力部２５０は、分散値ga(i)を出力する。分散値ga(i)を記憶部２９０へ記憶しておき、外部からの要求に応じて記憶部２９０から分散値ga(i)を読みだして出力してもよい。
なお、図１０に示すステップＳ２１３からステップＳ２５０までの処理は、N台の分散データ変換装置２２1〜２２Nのすべてで行う。
【００６５】
＜機密性＞
分散データ変換装置２２1〜２２Nが得る情報aに関する情報は、準同型性をもつ秘密分散方式S2による分散値であり、各分散値の生成に用いる乱数が互いに独立であれば、この実施形態の機密性は、利用する準同型性をもつ秘密分散方式S2の機密性に帰着される。また、K’台の分散データ変換装置２２iはそれぞれ情報aの分散値である復元値Ujの何れかを得るが、K’個の復元値U1,…,UK’すべてを得られない限り情報aを得ることはできない。ただしUK’については、任意の分散方式で分散していたため、秘匿性は保証できない。そのため、この実施形態の機密性は、結局、K’>Kとすれば、利用する秘密分散方式S2の機密性に帰着される。
【００６６】
＜効果＞
この実施形態の秘密分散システムは、計算量型秘密分散方式による情報aの分散値fa(1),…,fa(N)を、任意の準同型性をもつ秘密分散方式S2による分散値ga(1),…,ga(N)に変換することができる。
準同型性をもつ秘密分散方式としては、例えば、Shamir秘密分散方式など既存の線形秘密分散方式が挙げられる。Shamir秘密分散方式など既存の線形秘密分散方式を用いてマルチパーティ計算を行う方法は既知であるため、秘密分散方式S2としてShamir秘密分散方式など既存の任意の線形秘密分散方式を選択することで、計算量型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。
【００６７】
例えば、非特許文献２に記載の計算量型秘密分散方式は分散値のサイズの下限が元のデータの1/Kとなるため、暗号文cを分散する分散方式S0として非特許文献２に記載の計算量型秘密分散方式を適用すれば、分散値のサイズが元のデータと同程度となるShamir秘密分散方式と比較して、分散値を保存するために必要となる記憶容量を削減することができる。
【００６８】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６９】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００７０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００７１】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００７２】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００７３】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2014007310.tif 000009
【図２】
2014007310.tif 000010
【図３】
2014007310.tif 000011
【図４】
2014007310.tif 000012
【図５】
2014007310.tif 000013
【図６】
2014007310.tif 000014
【図７】
2014007310.tif 000015
【図８】
2014007310.tif 000016
【図９】
2014007310.tif 000017
【図１０】
2014007310.tif 000018
【手続補正書】
【提出日】平成27年11月13日(2015.11.13)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ分散装置と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-1個の鍵s1,…,sK-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK-1の総和を減算して暗号文cを生成する暗号化部と、
前記鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する鍵分散部と、
前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を備え、
前記分散データ変換装置は、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記秘密分散方式S0により復元することで、復元値Uj(j=K)を生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K個の分散値fU1(i),…,fUK(i)を総和して前記情報aの分散値ga(i)を生成する変換部と、
を備える秘密分散システム。
【請求項２】
データ分散装置とN台の分散データ変換装置を含む秘密分散システムであって、
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
前記データ分散装置は、
K’-1個の鍵s1,…,sK’-1∈Sを選択する鍵選択部と、
前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する擬似乱数生成部と、
情報a∈Rから前記擬似乱数r1,…,rK’-1の総和を減算して暗号文cを生成する暗号化部と、
前記鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(n)に分散する鍵分散部と、
前記暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する暗号文分散部と、
を備え、
前記分散データ変換装置は、
K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記分散方式S0により復元することで、復元値Uj(j=K’)を生成する復元部と、
前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散部と、
K’個の分散値fU1(i),…,fUK’(i)を総和して前記情報aの分散値ga(i)を生成する変換部と、
を備える秘密分散システム。
【請求項３】
請求項１または２に記載の秘密分散システムであって、
前記秘密分散方式S2は、Shamir秘密分散方式である
秘密分散システム。
【請求項４】
請求項１から３のいずれかに記載の秘密分散システムにおいて用いられる前記データ分散装置。
【請求項５】
請求項１から３のいずれかに記載の秘密分散システムにおいて用いられる前記分散データ変換装置。
【請求項６】
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-1個の鍵s1,…,sK-1∈Sを選択する鍵選択ステップと、
前記データ分散装置が、前記鍵s1,…,sK-1からrj=P(sj)(j=1,…,K-1)を計算することにより擬似乱数r1,…,rK-1を生成する擬似乱数生成ステップと、
前記データ分散装置が、情報a∈Rから前記擬似乱数r1,…,rK-1の総和を減算して暗号文cを生成する暗号化ステップと、
前記データ分散装置が、前記鍵s1,…,sK-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK-1(n)に分散する鍵分散ステップと、
前記データ分散装置が、前記暗号文cを任意の秘密分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
分散データ変換装置が、K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記秘密分散方式S0により復元することで、復元値Ujを生成する復元ステップと、
前記分散データ変換装置が、前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散ステップと、
前記分散データ変換装置が、K個の分散値fU1(i),…,fUK(i)を総和して前記情報aの分散値ga(i)を生成する変換ステップと、
を含む秘密分散方法。
【請求項７】
N,K,K’は2以上の整数であり、N≧Kであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、Sは鍵空間であり、P(x)はx∈Sを環Rへ移す写像であり、
データ分散装置が、K’-1個の鍵s1,…,sK’-1∈Sを選択する鍵選択ステップと、
前記データ分散装置が、前記鍵s1,…,sK’-1からrj=P(sj)(j=1,…,K’-1)を計算することにより擬似乱数r1,…,rK’-1を生成する擬似乱数生成ステップと、
前記データ分散装置が、情報a∈Rから前記擬似乱数r1,…,rK’-1の総和を減算して暗号文cを生成する暗号化ステップと、
前記データ分散装置が、前記鍵s1,…,sK’-1を任意の秘密分散方式S1によりそれぞれN個の分散値fs1(n),…,fsK’-1(n)に分散する鍵分散ステップと、
前記データ分散装置が、前記暗号文cを任意の分散方式S0によりN個の分散値fc(n)に分散する暗号文分散ステップと、
分散データ変換装置が、K個の分散値fsj(i)が入力されると、前記分散値fsj(i)を前記秘密分散方式S1により復元した値ujからUj=P(uj)を計算し、K個の分散値fc(i)が入力されると、前記分散値fc(i)を前記分散方式S0により復元することで、復元値Uj(j=K’)を生成する復元ステップと、
前記分散データ変換装置が、前記復元値Ujを任意の準同型性をもつ秘密分散方式S2によりN個の分散値fUj(n)に分散する再分散ステップと、
前記分散データ変換装置が、K’個の分散値fU1(i),…,fUK’(i)を総和して前記情報aの分散値ga(i)を生成する変換ステップと、
を含む秘密分散方法。
【請求項８】
請求項４に記載のデータ分散装置もしくは請求項５に記載の分散データ変換装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2014007310.tif 000019
2014007310.tif 000020
2014007310.tif 000021
2014007310.tif 000022