(57)【要約】  秘密分散システムは、ランプ型秘密分散の分散値を、準同型性をもつ秘密分散の分散値に変換する。データ分散装置は、分散部が、情報aを任意のランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する。分散データ変換装置は、乱数選択部が、L個の乱数ri,lを要素とする乱数ベクトルriを生成する。第１乱数分散部が、乱数ベクトルriをランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する。第２乱数分散部が、L個の乱数ri,lを任意の秘密分散方式S2によりそれぞれN個の分散値gri,l(n)に分散する。撹乱部が、分散値fa(i)と分散値frλ(i)とを用いて分散値Uiを生成する。復元部が、分散値Uλからランプ型秘密分散方式S1によりL個の撹乱情報clを復元する。再分散部が、撹乱情報clを秘密分散方式S2によりそれぞれN個に分散して分散値gcl(n)を生成する。変換部が、分散値gcl(i)と分散値grλ,l(i)を用いて情報aの分散値gal(i)を生成する。
2014007311.tif 000002
【特許請求の範囲】
【請求項１】
データ分散装置とN台の分散データ変換装置を含む秘密分散システムであって、
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
前記データ分散装置は、
情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する分散部
を備え、
前記分散データ変換装置は、
L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択部と、
前記乱数ベクトルriを前記ランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散部と、
前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散部と、
前記分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱部と、
K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元部と、
前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散部と、
前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(i)を生成する変換部と、
を備える秘密分散システム。
【請求項２】
請求項１に記載の秘密分散システムであって、
前記撹乱部は、前記分散値fa(i)に前記分散値frλ(i)の総和を加算して前記分散値Uiを生成し、
前記変換部は、j=1,…,Lについて、前記分散値gcj(i)から前記分散値grλ,j(i)の総和を減算して、前記分散値gaj(i)を生成する
秘密分散システム。
【請求項３】
請求項１または２に記載の秘密分散システムであって、
前記秘密分散方式S2は、Shamir秘密分散方式である
秘密分散システム。
【請求項４】
Nは2以上の整数であり、n=1,…,Nであり、fx(n)はxのN個の分散値であり、Rは環であり、
情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する分散部
を備えるデータ分散装置。
【請求項５】
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択部と、
前記乱数ベクトルriを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散部と、
前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散部と、
情報a=(a1,…,aL)∈RLを前記ランプ型秘密分散方式S1によりN個に分散した分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱部と、
K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元部と、
前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散部と、
前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(i)を生成する変換部と、
を備える分散データ変換装置。
【請求項６】
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
データ分散装置が、情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する分散ステップと、
分散データ変換装置が、L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択ステップと、
前記分散データ変換装置が、前記乱数ベクトルriを前記ランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散ステップと、
前記分散データ変換装置が、前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散ステップと、
前記分散データ変換装置が、前記分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱ステップと、
前記分散データ変換装置が、K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元ステップと、
前記分散データ変換装置が、前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散ステップと、
前記分散データ変換装置が、前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(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を復元できる。
【数１】
2014007311.tif 000003
【０００４】
また、秘密分散の一種として、K未満の整数Lについて、K-L個以下の分散値からは元のデータを一切復元できなくする、ランプ型秘密分散方式がある（例えば、非特許文献２参照）。この方式の例では、情報a=(a0,a1,…,aL-1)(a0,a1,…,aL-1∈GF(p))および乱数rL,…,rK-1∈GF(p)から決まる、xを変数とするK-1次式f(x)=a0+a1x+…+aL-1xL-1+rLxL+…+rK-1xK-1から、aの分散値Ti(a)=f(i)（i=1,…,N）を得る。すると、n1,…,nKを互いに異なる1以上N以下の整数として、式f(x)のK個の点(ni,f(ni))(i=1,…,K)から式f(x)の係数a0,a1,…,aL-1を一意に求めることができる。これはa0,a1,…,aL-1,rL,…,rK-1を変数とする以下の行列についてa0,a1,…,aL-1の解を求めればよい。
【数２】
2014007311.tif 000004
【０００５】
一方、秘密分散を要素技術としたマルチパーティ計算方式が提案されている。マルチパーティ計算は、各計算主体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.
【非特許文献２】山本博資, “秘密分散法とそのバリエーション”, 数理解析研究所講究録 1361巻, 19-31, 2004年.
【非特許文献３】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倍となる。分散値のデータ量の増加は通信時間や保存データの増大につながるため、できるだけ分散値のデータ量を抑えることが望ましい。【０００９】
ランプ型秘密分散方式では、a+b:=(a0+b0,a1+b1,…,aL-1+bL-1)とすれば、Ti(a)+Ti(b)=Ti(a+b)となり、加算のマルチパーティ計算が可能である。しかし、ランプ型秘密分散方式では、Ti(a)Ti(b)は一般にはab:=(a0b0,a1b1,…,aL-1bL-1)の分散値にならず、乗算のマルチパーティ計算の方法は自明でないと考えられる。【００１０】
この発明はこのような点に鑑みてなされたものであり、ランプ型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができる秘密分散技術を提供することを目的とする。
【課題を解決するための手段】
【００１１】
上記の課題を解決するために、この発明の秘密分散システムは、データ分散装置とN台の分散データ変換装置を含む。この発明では、N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であるとする。【００１２】
データ分散装置は、分散部を備える。分散部は、情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する。【００１３】
分散データ変換装置は、乱数選択部と第１乱数分散部と第２乱数分散部と撹乱部と復元部と再分散部と変換部とを備える。乱数選択部は、L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する。第１乱数分散部は、乱数ベクトルriを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する。第２乱数分散部は、乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する。撹乱部は、分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する。復元部は、K個の分散値Uλから任意の準同型性をもつランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する。再分散部は、撹乱情報c1,…,cLを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する。変換部は、分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて情報aの分散値ga1(i),…,gaL(i)を生成する。
【発明の効果】
【００１４】
この発明の秘密分散技術によれば、任意の準同型性をもつランプ型秘密分散方式による分散値を、任意の準同型性をもつ秘密分散方式による分散値に変換することができる。例えば、Shamir秘密分散方式など既存の多くの線形秘密分散方式は準同型性をもつ秘密分散方式であり、Shamir秘密分散方式など既存の線形秘密分散方式による分散値を用いてマルチパーティ計算を行う方法は既知である。そのため、準同型性をもつ秘密分散方式としてShamir秘密分散方式など既存の線形秘密分散方式を選択することで、ランプ型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。また、ランプ型秘密分散方式は符号化効率がよく、分散値のサイズが小さくなるため、保存する分散値の総データ容量および復元に必要な分散値の総データ容量を減らすことができる。
【図面の簡単な説明】
【００１５】
【図１】図１は、秘密分散システムの機能構成を例示する図である。
【図２】図２は、データ分散装置の機能構成を例示する図である。
【図３】図３は、分散データ変換装置の機能構成を例示する図である。
【図４】図４は、データ分散装置の処理フローを例示する図である。
【図５】図５は、分散データ変換装置の処理フローを例示する図である。
【発明を実施するための形態】
【００１６】
以下、この発明の実施の形態について詳細に説明する。なお、図面中において同じ機能を有する構成部には同じ番号を付し、重複説明を省略する。
【００１７】
［実施形態］
この発明の実施形態に係る秘密分散システムは、任意の準同型性をもつランプ型秘密分散方式による分散値を、任意の準同型性をもつ秘密分散方式による分散値に変換する。
【００１８】
＜構成＞
図１を参照して、実施形態に係る秘密分散システム１の構成例を説明する。秘密分散システム１は、データ分散装置１０と少なくともN台の分散データ変換装置２０1〜２０Nとネットワーク９０を含む。データ分散装置１０と分散データ変換装置２０1〜２０Nは、ネットワーク９０に接続される。ネットワーク９０は、データ分散装置１０と分散データ変換装置２０1〜２０Nそれぞれとが相互に通信可能なように構成されていればよく、例えばインターネットやLAN、WANなどで構成することができる。また、データ分散装置１０と分散データ変換装置２０1〜２０Nそれぞれとは必ずしもネットワークを介してオンラインで通信可能である必要はない。例えば、データ分散装置１０が出力する情報をUSBメモリなどの可搬型記録媒体に記憶し、その可搬型記録媒体から分散データ変換装置２０1〜２０Nへオフラインで入力するように構成してもよい。
【００１９】
図２を参照して、秘密分散システム１に含まれるデータ分散装置１０の構成例を説明する。データ分散装置１０は、入力部１１０と分散部１２０と出力部１３０とを備える。
【００２０】
図３を参照して、秘密分散システム１に含まれる分散データ変換装置２０の構成例を説明する。分散データ変換装置２０は、入力部２１０と乱数選択部２２０と第１乱数分散部２３０と第２乱数分散部２３５と撹乱部２４０と復元部２５０と再分散部２６０と変換部２７０と出力部２８０と記憶部２９０とを備える。記憶部２９０は、例えば、RAM（Random Access Memory）などの主記憶装置、ハードディスクや光ディスクもしくはフラッシュメモリ（Flash Memory）などの半導体メモリ素子により構成される補助記憶装置、またはリレーショナルデータベースやキーバリューストアなどのミドルウェアにより構成することができる。
【００２１】
＜データ分散処理＞
図４を参照して、データ分散装置１０の動作例を、実際に行われる手続きの順に従って説明する。以下の説明では、N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であるものとする。
【００２２】
ステップＳ１１０において、入力部１１０に、情報aが入力される。情報aは環R上のL個の値a1,…,aLを要素とするL次元ベクトルである。したがって、a=(a1,…,aL)∈RLと表すことができる。情報aの例は、動画ファイル、音声ファイル、テキストファイル、表ファイルなどである。情報aのデータ量は、例えば1メガバイト以上である。
【００２３】
情報aは分散部１２０に入力される。ステップＳ１２０において、分散部１２０は、情報aを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(1),…,fa(N)に分散する。準同型性とは2つの情報a,bの分散値fa(i),fb(i)およびa+bの分散値fa+b(i)について、fa(i)+fb(i)=fa+b(i)が成り立つことをいう。ランプ型秘密分散方式は、K個以上の分散値から元のデータが復元でき、K未満の整数Lについて、K-L個以下の分散値からは元のデータを一切復元できなくするが、K-L+1個以上K-1個以下の分散値からは元のデータの一部が得られる秘密分散の一種である。ランプ型秘密分散方式による分散値のサイズは、元のデータのサイズの1/Lとなり、元のデータと分散値のサイズが同程度になるShamir秘密分散方式などと比較して符号化効率がよい。ランプ型秘密分散方式は様々な方式が提案されているが、この発明で用いるランプ型秘密分散方式S1は準同型性をもつランプ型秘密分散方式でなければならない。準同型性をもつランプ型秘密分散方式も数多く提案されており、例えば、「西新幹彦, 滝澤克則, “多項式補間法による強いランプ型しきい値秘密分散法”, 電子情報通信学会技術研究報告. IT, 情報理論 109(143), 127-129, 2009-07-16.」などに記載されているランプ型秘密分散方式を適用することができる。
【００２４】
ステップＳ１３０において、出力部１３０は、分散値fa(1),…,fa(N)を出力する。出力された各分散値fa(1),…,fa(N)は、それぞれ分散データ変換装置２０1〜２０Nにネットワーク９０もしくはUSBメモリ等の可搬型記録媒体を経由して入力される。
【００２５】
＜分散データ変換処理＞
図５を参照して、分散データ変換装置２０iの動作例を、実際に行われる手続きの順に従って説明する。
【００２６】
ステップＳ２１０において、入力部２１０に、データ分散装置１０が出力した分散値fa(i)が入力される。分散値fa(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fa(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００２７】
ステップＳ２２０において、乱数選択部２２０は、環RからL個の乱数ri,1,…,ri,Lを選択し、乱数ベクトルriを生成する。乱数ベクトルriは乱数ri,1,…,ri,Lを要素とするL次元ベクトルである。したがって、ri=(ri,1,…,ri,L)∈RLと表すことができる。乱数選択部２２０は、逐一ランダムにL個の乱数ri,1,…,ri,Lを選択してもよいし、事前に生成されメモリに格納されている複数個の値から所定の規則に従ってL個の乱数ri,1,…,ri,Lを選択してもよい。
【００２８】
乱数ベクトルriは第１乱数分散部２３０に入力される。ステップＳ２３０において、第１乱数分散部２３０は、乱数ベクトルriを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fri(1),…,fri(N)に分散する。ランプ型秘密分散方式S1は、準同型性をもつランプ型秘密分散方式であればどのような秘密分散方式であってもよいが、データ分散装置１０の備える分散部１２０が用いるランプ型秘密分散方式S1と同じ方式でなければならない。
【００２９】
乱数ri,1,…,ri,Lは第２乱数分散部２３５に入力される。ステップＳ２３５において、第２乱数分散部２３５は、乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)(n=1,…,N)に分散する。秘密分散方式S2は準同型性をもつ秘密分散方式であればどのような秘密分散方式でもよい。例えば、Shamir秘密分散方式など既存の線形秘密分散方式を適用することができる。より具体的には、ri,j=fi,j(0)(j=1,…,L)となる、xを変数とするK-1次多項式fi,j(x)を用いて、gri,j(n)=fi,j(n)を計算することにより、分散値gri,1(n),…,gri,L(n)を生成することができる。
【００３０】
ステップＳ２１２において、入力部２１０に、K台の分散データ変換装置２０λ(λ∈{1,…,N})の備える第１乱数分散部２３０が生成したK個の分散値frλ(i)が入力される。分散値frλ(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値frλ(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００３１】
分散値fa(i)とK個の分散値frλ(i)は撹乱部２４０に入力される。ステップＳ２４０において、撹乱部２４０は、分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する。より具体的には、以下の式のように、分散値fa(i)にK個の分散値frλ(i)の総和を加算して分散値Uiを生成する。
【数３】
2014007311.tif 000005
【００３２】
分散値fa(i)は準同型性をもつ秘密分散方式S2により情報aを分散した分散値であり、分散値frλ(i)は準同型性をもつ秘密分散方式S2によりK個の乱数ベクトルrλ(λ∈{1,…,N})をそれぞれ分散した分散値である。準同型性の性質により分散値Uiは、情報aとK個の乱数ベクトルrλの和を秘密分散方式S2により分散した分散値となる。以降の説明では、情報aとK個の乱数ベクトルrλの和を暗号文cとする。したがって、暗号文cは以下の式で表すことができる。
【数４】
2014007311.tif 000006
【００３３】
なお、図５に示すステップＳ２１１からステップＳ２４０までの処理は、N台の分散データ変換装置２０1〜２０Nのすべてが行う必要はなく、任意に選択された少なくともK台が行えばよい。
【００３４】
ステップＳ２１３において、入力部２１０に、K台の分散データ変換装置２０λ(λ∈{1,…,N})の備える撹乱部２４０が生成したK個の分散値Uλが入力される。分散値Uλは記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するようにしてもよい。記憶部２９０には記憶せず、分散値Uλが入力されると引き続き後続の処理を実行するようにしてもよい。
【００３５】
K個の分散値Uλは復元部２５０に入力される。ステップＳ２５０において、復元部２５０は、K個の分散値Uλから所定の準同型性をもつランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する。ランプ型秘密分散方式S1は、準同型性をもつランプ型秘密分散方式であればどのような秘密分散方式であってもよいが、データ分散装置１０の備える分散部１２０や分散データ変換装置２０の備える第１乱数分散部２３０が用いるランプ型秘密分散方式S1と同じ方式でなければならない。
【００３６】
L個の撹乱情報c1,…,cLは再分散部２６０に入力される。ステップＳ２６０において、再分散部２６０は、撹乱情報c1,…,cLを所定の準同型性をもつ秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)(n=1,…,N)を生成する。秘密分散方式S2は、準同型性をもつ秘密分散方式であればどのような秘密分散方式であってもよいが、第２乱数分散部２３５が用いる秘密分散方式S2と同じ方式でなければならない。
【００３７】
なお、図５に示すステップＳ２１３からステップＳ２６０までの処理は、N台の分散データ変換装置２０1〜２０Nのすべてが行う必要はなく、任意に選択された少なくとも1台が行えばよい。
【００３８】
ステップＳ２１４において、入力部２１０に、K台の分散データ変換装置２０λ(λ∈{1,…,N})の備える第２乱数分散部２３５が生成した分散値grλ,1(i),…,grλ,L(i)が入力される。分散値grλ,1(i),…,grλ,L(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値grλ,1(i),…,grλ,L(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【００３９】
分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)は変換部２７０に入力される。ステップＳ２７０において、変換部２７０は、L個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて情報aの分散値ga1(i),…,gaL(i)を生成する。より具体的には、以下の式のように、j=1,…,Lについて、分散値gcj(i)から分散値grλ,j(i)の総和を減算して分散値gaj(i)を生成する。
【数５】
2014007311.tif 000007
【００４０】
分散値gcj(i)は準同型性をもつ秘密分散方式S2により暗号文cを分散した分散値であり、分散値grλ,j(i)は準同型性をもつ秘密分散方式S2によりK個の乱数rλ,j(λ∈{1,…,N})を分散した分散値である。暗号文cは情報aとK個の乱数ベクトルrλ=(rλ,1,…,rλ,L)の和であるから、準同型性の性質により、分散値gaj(i)は、情報aを秘密分散方式S2により分散した分散値となる。
【００４１】
ステップＳ２８０において、出力部２８０は、分散値ga1(i),…,gaL(i)を出力する。分散値ga1(i),…,gaL(i)を記憶部２９０へ記憶しておき、外部からの要求に応じて記憶部２９０から分散値ga1(i),…,gaL(i)を読みだして出力してもよい。
【００４２】
なお、図５に示すステップＳ２１４からステップＳ２８０までの処理は、N台の分散データ変換装置２０1〜２０Nのすべてで行う。
【００４３】
＜機密性＞
分散データ変換装置２０1〜２０Nが得る情報aに関する情報は、準同型性をもつランプ型秘密分散方式S1による分散値および準同型性をもつ秘密分散方式S2による分散値であり、各分散値の生成に用いる乱数が互いに独立であれば、この実施形態の機密性は、利用する準同型性をもつランプ型秘密分散方式S1および準同型性をもつ秘密分散方式S2の機密性に帰着される。また、少なくとも1台の分散データ変換装置２０は暗号文cを得るが、暗号文cは情報aに他の分散データ変換装置２０が生成した乱数の和が加算されているため、すべての乱数が得られない限り情報aを得ることはできない。そのため、この実施形態の機密性は、結局、利用する秘密分散方式S2の機密性に帰着される。
【００４４】
＜効果＞
この実施形態の秘密分散システムは、任意の準同型性をもつランプ型秘密分散方式S1による情報a=(a1,…,aL)の分散値fa(1),…,fa(N)を、任意の準同型性をもつ秘密分散方式S2による分散値ga(1),…,ga(N)に変換することができる。
【００４５】
準同型性をもつ秘密分散方式としては、例えば、Shamir秘密分散方式など既存の線形秘密分散方式が挙げられる。Shamir秘密分散方式など既存の線形秘密分散方式を用いてマルチパーティ計算を行う方法は既知であるため、秘密分散方式S2としてShamir秘密分散方式など既存の線形秘密分散方式を選択することで、ランプ型秘密分散方式による分散値を用いてマルチパーティ計算を行うことができるようになる。
【００４６】
ランプ型秘密分散方式は分散値のサイズの下限が元のデータの1/Lとなるため、分散値のサイズが元のデータと同程度となるShamir秘密分散方式と比較して、分散値を保存するために必要となる記憶容量を削減することができる。
【００４７】
［プログラム、記録媒体］
この発明は上述の実施形態に限定されるものではなく、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。上記実施例において説明した各種の処理は、記載の順に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００４８】
また、上記実施形態で説明した各装置における各種の処理機能をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記各装置における各種の処理機能がコンピュータ上で実現される。
【００４９】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【００５０】
また、このプログラムの流通は、例えば、そのプログラムを記録したDVD、CD-ROM等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【００５１】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるASP（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００５２】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【図１】
2014007311.tif 000008
【図２】
2014007311.tif 000009
【図３】
2014007311.tif 000010
【図４】
2014007311.tif 000011
【図５】
2014007311.tif 000012
【手続補正書】
【提出日】平成26年12月16日(2014.12.16)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】００２６
【補正方法】変更
【補正の内容】
【００２６】
ステップＳ２１１において、入力部２１０に、データ分散装置１０が出力した分散値fa(i)が入力される。分散値fa(i)は記憶部２９０に記憶しておき、任意のタイミングで後続の処理を実行するように構成してもよい。記憶部２９０には記憶せず、分散値fa(i)が入力されると引き続き後続の処理を実行するように構成してもよい。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ分散装置とN台の分散データ変換装置を含む秘密分散システムであって、
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
前記データ分散装置は、
情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する分散部
を備え、
前記分散データ変換装置は、
L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択部と、
前記乱数ベクトルriを前記ランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散部と、
前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散部と、
前記分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱部と、
K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元部と、
前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散部と、
前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(i)を生成する変換部と、
を備える秘密分散システム。
【請求項２】
請求項１に記載の秘密分散システムであって、
前記撹乱部は、前記分散値fa(i)に前記分散値frλ(i)の総和を加算して前記分散値Uiを生成し、
前記変換部は、j=1,…,Lについて、前記分散値gcj(i)から前記分散値grλ,j(i)の総和を減算して、前記分散値gaj(i)を生成する
秘密分散システム。
【請求項３】
請求項１または２に記載の秘密分散システムであって、
前記秘密分散方式S2は、Shamir秘密分散方式である
秘密分散システム。
【請求項４】
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択部と、
前記乱数ベクトルriを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散部と、
前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散部と、
情報a=(a1,…,aL)∈RLを前記ランプ型秘密分散方式S1によりN個に分散した分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱部と、
K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元部と、
前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散部と、
前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(i)を生成する変換部と、
を備える分散データ変換装置。
【請求項５】
N,K,Lは2以上の整数であり、N≧K＞Lであり、n=1,…,Nであり、λは互いに異なる1以上N以下のK個の整数であり、iはi∈λの整数であり、fx(n)はxのN個の分散値であり、Rは環であり、
データ分散装置が、情報a=(a1,…,aL)∈RLを任意の準同型性をもつランプ型秘密分散方式S1によりN個の分散値fa(n)に分散する分散ステップと、
分散データ変換装置が、L個の乱数ri,1,…,ri,L∈Rを要素とする乱数ベクトルri=(ri,1,…,ri,L)を生成する乱数選択ステップと、
前記分散データ変換装置が、前記乱数ベクトルriを前記ランプ型秘密分散方式S1によりN個の分散値fri(n)に分散する第１乱数分散ステップと、
前記分散データ変換装置が、前記乱数ri,1,…,ri,Lを任意の準同型性をもつ秘密分散方式S2によりそれぞれN個の分散値gri,1(n),…,gri,L(n)に分散する第２乱数分散ステップと、
前記分散データ変換装置が、前記分散値fa(n)に含まれる分散値fa(i)とK個の分散値frλ(i)とを用いて分散値Uiを生成する撹乱ステップと、
前記分散データ変換装置が、K個の分散値Uλから前記ランプ型秘密分散方式S1によりL個の撹乱情報c1,…,cLを復元する復元ステップと、
前記分散データ変換装置が、前記撹乱情報c1,…,cLを前記秘密分散方式S2によりそれぞれN個に分散して分散値gc1(n),…,gcL(n)を生成する再分散ステップと、
前記分散データ変換装置が、前記分散値gc1(n),…,gcL(n)に含まれるL個の分散値gc1(i),…,gcL(i)とL×K個の分散値grλ,1(i),…,grλ,L(i)を用いて前記情報aの分散値ga1(i),…,gaL(i)を生成する変換ステップと、
を含む秘密分散方法。
【請求項６】
請求項４に記載の分散データ変換装置としてコンピュータを機能させるためのプログラム。
【国際調査報告】
2014007311.tif 000013
2014007311.tif 000014
2014007311.tif 000015
2014007311.tif 000016