(57)【特許請求の範囲】
【請求項１】
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)を適用して得た分散値を保管する分散値保管装置と、
２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を含み、
前記分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、
w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、
前記ビット分解秘密計算装置は、
r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳにより分散値を生成し分散する加算分散部と、
前記加算分散部が生成した前記値と、前記加算分散部によって用いられなかった値との加算処理を、全加算器の秘密計算を用いて、各桁毎に実行し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部と、
を含む、ことを特徴とするビット分解秘密計算システム。
【請求項２】
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)を適用して得た分散値を保管する分散値保管装置と、
２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を含み、
前記分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、
前記ビット分解秘密計算装置は、
r12 = r1 + r2 mod 2 ^ n の秘密計算と、
r123 = r12 + r3 mod 2 ^ n の秘密計算と、
を全加算器の秘密計算によって、各桁毎に実行し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部を含む、ことを特徴とするビット分解秘密計算システム。
【請求項３】
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)を適用して得た分散値を保管する分散値保管装置と、
２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置と、
ビット結合秘密計算装置と、
を含み、
前記分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たすr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、
前記ビット結合秘密計算装置は、
r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、
r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算と、
を全加算器の秘密計算によって、各桁毎に実行し、計算結果を前記分散値保管装置に記憶する全加算器秘密計算部を含む、ことを特徴とするビット結合秘密計算システム。
【請求項４】
前記ビット分解秘密計算装置は、
前記(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、前記(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出部を含み、
前記全加算器秘密計算部は、前記加算分散部で生成され配布された前記(2,3)型ＲＳＳの前記分散情報と、前記部分分散情報抽出部で生成した前記(2,3)型ＲＳＳの前記分散情報とについて、全加算器の秘密計算を用いた加算処理を実行し、
ビット毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする請求項１に記載のビット分解秘密計算システム。
【請求項５】
前記ビット分解秘密計算装置は、
前記(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、前記(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出部を含み、
前記全加算器秘密計算部は、
r_i、r_j、r_kを含む、前記部分分散情報抽出部によって生成された前記(2,3)型ＲＳＳの３組の分散情報を用いて（i、j、kは互いに異なり、1〜3から選択される）、
下位ビットから、全加算器の秘密計算によって、r_ij = r_i + r_j mod 2 ^ n の秘密計算と、r_ij + r_k mod 2 ^ n の秘密計算とを実行し、
ビット毎の計算結果の列を前記分解分散値保管装置に記憶する、ことを特徴とする請求項２に記載のビット分解秘密計算システム。
【請求項６】
前記ビット結合秘密計算装置は、
前記(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、前記(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出部を含む、ことを特徴とする請求項３に記載のビット結合秘密計算システム。
【請求項７】
ビット分解秘密計算を提供するためのコンピュータシステムの方法であって、
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、
w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳにより分散値を生成して分散する加算分散ステップと、
前記加算分散ステップによって生成された前記値と、前記加算分散ステップにおいて用いられなかった値との加算処理を、全加算器の秘密計算を用いて、各桁毎に実行し、その結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算ステップと、
を含む、ことを特徴とする方法。
【請求項８】
ビット分解秘密計算を提供するためのコンピュータシステムの方法であって、
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、
w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、
r12 = r1 + r2 mod 2 ^ n の秘密計算と、
r123 = r12 + r3 mod 2 ^ n の秘密計算と、
を全加算器の秘密計算を用いて、各桁毎に実行し、
計算結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算ステップを含む、ことを特徴とする方法。
【請求項９】
ビット結合秘密計算を提供するためのコンピュータシステムの方法であって、
２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、
w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たすr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、
r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、
r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算と、を全加算器の秘密計算を用いて、各桁毎に実行し、
計算結果を、２のべき乗を法とする演算を用いる(2,3)型ＲＳＳを適用して得た分散値を保管する分散値保管装置に記憶する全加算器秘密計算ステップを含む、ことを特徴とする方法。
【請求項１０】
(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、前記(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出ステップを含み、
前記全加算器秘密計算ステップは、前記加算分散ステップで生成され配布された(2,3)型ＲＳＳの前記分散情報と、前記部分分散情報抽出ステップで生成した(2,3)型ＲＳＳの前記分散情報とについて、全加算器の秘密計算を用いた加算処理を実行し、ビット毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする請求項７に記載の方法。
【請求項１１】
前記(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、前記(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出ステップを含み、
前記全加算器秘密計算ステップは、r_i、r_j、r_kを含む、前記部分分散情報抽出ステップによって生成された前記(2,3)型ＲＳＳの３組の分散情報を用いて（i、j、kは互いに異なり、1〜3から選択される）、
下位ビットから、全加算器の秘密計算によって、r_ij = r_i + r_j mod 2 ^ n の秘密計算と、r_ij + r_k mod 2 ^ n の秘密計算とを実行し、
ビット毎の計算結果の列を、前記分解分散値保管装置に記憶する、ことを特徴とする請求項８に記載の方法。
【請求項１２】
(2,3)型ＲＳＳの分散情報を構成する３つの値のうち１つのインデックスを入力として、前記分散値保管装置が保管する値を読み出し、(2,3)型ＲＳＳの前記分散情報を構成する前記３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する部分分散情報抽出ステップを含む、
ことを特徴とする請求項９に記載の方法。
【請求項１３】
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、
w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳにより分散値を生成して分散する加算分散処理と、
前記加算分散処理において生成された前記値と、前記加算分散処理において用いられなかった値との加算処理を、全加算器の秘密計算を用いて、各桁毎に実行し、その結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算処理と、
を含む、
ビット分解秘密計算処理をコンピュータに実行させるプログラム。
【請求項１４】
２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすr1、r2、r3を用い、
r12 = r1 + r2 mod 2 ^ n の秘密計算と、
r123 = r12 + r3 mod 2 ^ n の秘密計算と、
を全加算器の秘密計算を用いて、各桁毎に実行し、計算結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算処理を含む、
ビット分解秘密計算処理をコンピュータに実行させるプログラム。
【請求項１５】
２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たすr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算とを全加算器の秘密計算を用いて、各桁毎に実行し、計算結果を、２のべき乗を法とする演算を用いる(2,3)型ＲＳＳを適用して得た分散値を保管する分散値保管装置に記憶する全加算器秘密計算処理を含む、
ビット結合秘密計算処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はビット分解秘密計算装置、ビット結合秘密計算装置、方法およびプログラムに関する。
【背景技術】
【０００２】
秘密計算法は、コンピュータシステムが関連する主体に対して計算過程と結果を秘匿することができる技術である。クラウドのような第３者が管理する複数のサーバに分散して保管しデータの秘密分散を行うことにより、データに対してあらゆる演算を実行することができる。第３者には、データ、計算過程、計算結果を知られることがないため、秘密計算は、特に限定されないが、例えば個人情報のような慎重に扱うべき情報に対する分析処理等をアウトソースするために用いることができる。
【０００３】
以下、(2,3)閾値のアクセス構造を有する複製秘密分散(replication type secret shared)(以下(2,3)型ＲＳＳと称する)を用いる秘密計算に関する本発明の前提として、(2,3)型ＲＳＳを用いる秘密計算について説明する。
【０００４】
(2,3)閾値型ＲＳＳは、(2,3)秘密分散の実現方法の一つである。(2,3)秘密分散においては、入力された値から３つの分散情報を生成し、２つ以上の分散情報からは元の値を復元できるが、１つ以下の分散情報からは元の値はわからない。
【０００５】
(2,3)型ＲＳＳは、0からp-1以下の値xを秘密分散する際に、
x = r1 + r2 + r3 mod p
となるような、それぞれ0からp-1以下の３つの値の組r1、r2、r3を生成し、３つの分散情報として、それぞれ(r1, r2, r3)から選んだ２つの値を有し、互いに異なる組み合わせである３組を用いることで、(2,3)秘密分散を実現する。なお、このpを法と呼ぶ。
【０００６】
秘密分散によって分散された値に関する計算を復元すること無く実行する方法は秘密計算と呼ばれている。以下に、本発明に関する(2,3)型ＲＳＳによって分散された値に対する秘密計算方法について説明する。
【０００７】
まず、値の分散方法について説明し、次に加算、減算、乗算について説明する。ここでは、複数の値のそれぞれが３台の装置に対して分散され、分散値（分散された値）に対して秘密計算を行うという手順について説明する。以下では、３台の装置を装置１、装置２、装置３と呼んで区別する。
【０００８】
＜値の分散方法＞
pを２以上の整数として、0以上p未満の値wを秘密分散する場合、
w = r1 + r2 + r3 mod p
を満たすランダムに選ばれたr1、r2、r3を生成して、以下のように保管する。
装置１は、自装置のストレージに値wの分散値として、(r1, r2)を保管する。
装置２は、自装置のストレージに値wの分散値として、(r2, r3)を保管する。
装置３は、自装置のストレージに値wの分散値として、(r3, r1)を保管する。
【０００９】
どの装置（１乃至３）も、r1、r2、r3のいずれかが足りないため、値wを得られないが、２台以上の装置が保管している分散値からならば、値wを復元可能なことが確認できる。
【００１０】
＜加算処理＞
上述した方法によって、装置１、装置２、装置３に分散して保管されている値wと値w'の分散に関して実行される加算処理について説明する。ここで、r1、r2、r3は、
w = r1 + r2 + r3 mod p 
を満たすようにランダムに選ばれ、r1'、r2'、r3'は、
w' = r1' + r2' + r3' mod p 
を満たすようにランダムに選ばれるとする。
【００１１】
装置１は、自装置のストレージに、
wの分散値として、(s1, t1) = (r1, r2)を保管し、
w'の分散値として、(s1', t1') = (r1', r2')を保管する。
装置２は、自装置のストレージに、
wの分散値として、(s2, t2) = (r2, r3)を保管し、
w'の分散値として、(s2', t2') = (r2', r3')を保管する。
装置３は、自装置のストレージに、
wの分散値として、(s3, t3) = (r3, r1)を保管し、
w'の分散値として、(s3', t3') = (r3', r1')を保管する。
【００１２】
装置１乃至３は、それぞれ以下の手順に従った処理を行う。
【００１３】
装置１は、
(s1", t1") = (r1" = s1 + s1' mod p, r2" = t1 + t1'mod p)
によって、(s1", t1")を計算し、
(s1", t1")を、w + w'の分散値として自装置のストレージに保管する。
装置２は、
(s2", t2") = (r2" = s2 + s2' mod p, r3" = t2 + t2'mod p)
によって、(s2", t2")を計算し、
(s2", t2")を、w + w'の分散値として自装置のストレージに保管する。
装置３は、
(s3", t3") = (r3" = s3 + s3' mod p, r1" = t3 + t3'mod p)
によって、(s3", t3")を計算し、
(s3", t3")を、w + w'の分散値として自装置のストレージに保管する。
【００１４】
装置１乃至３のそれぞれの計算結果は、
w + w' = r1" + r2" + r3" mod p
となるr1", r2", r3"を用いて分散したw + w'の分散値となっている。
これは、
r1" + r2" + r3" = (r1 + r2 + r3) + (r1' + r2' + r3') = w + w' mod p
から確認できる。
【００１５】
＜減算処理＞
上述した方法によって、装置１、装置２、装置３に分散して保管されている値wと値w'の分散に関して実行される減算処理について説明する。なお、
w = r1 + r2 + r3 mod p、
w' = r1' + r2' + r3' mod p
とする。
【００１６】
装置１は、自装置のストレージに、wの分散値として、(s1, t1) = (r1, r2)を保管し、w'の分散値として、(s1', t1') = (r1', r2')を保管する。
装置２は、自装置のストレージに、wの分散値として、(s2, t2) = (r2, r3)を保管し、w'の分散値として、(s2', t2') = (r2', r3')を保管する。
装置３は、自装置のストレージに、wの分散値として、(s3, t3) = (r3, r1)を保管し、w'の分散値として、(s3', t3') = (r3', r1')を保管する。
【００１７】
装置１乃至３は、それぞれ以下の手順に従った処理を行う。
【００１８】
装置１は、
(s1", t1") = (r1" = s1 - s1' mod p, r2" = t1 - t1' mod p)
によって、(s1", t1")を計算し、(s1", t1")をw - w'の分散値として自装置のストレージに保管する。
【００１９】
装置２は、
(s2", t2") = (r2" = s2 - s2' mod p, r3" = t2 - t2' mod p)
によって、(s2", t2")を計算し、(s2", t2")をw - w'の分散値として自装置のストレージに保管する。
【００２０】
装置３は、
(s3", t3") = (r3" = s3 - s3' mod p, r1" = t3 - t3' mod p)
によって、(s3", t3")を計算し、(s3", t3")をw - w'の分散値として自装置のストレージに保管する。
【００２１】
装置１乃至３のそれぞれの計算結果は、
w - w' = r1" + r2" + r3" mod p
となるr1"、r2"、r3"を用いて分散したw - w'の分散値となっている。
これは、
r1" + r2" + r3" = (r1 + r2 + r3) - (r1' + r2' + r3') = w - w' mod p
から確認できる。
【００２２】
＜乗算処理＞
上述した方法によって、装置１、装置２、装置３に保管されている値wと値w'に関して実行される乗算処理について説明する。
【００２３】
まず、各装置がどのような値を保管しているかを示す。r1、r2、r3を、 r1 + r2 + r3 = w mod p を満たすランダムに選ばれた値とし、r1'、r2'、r3'を、r1' + r2' + r3' = w' mod 2 ^ n を満たすランダムに選ばれた値とする。
【００２４】
装置１は、自装置のストレージに、wの分散値として、(s1, t1) = (r1, r2)を保管し、w'の分散値として、(s1', t1') = (r1', r2')を保管する。
装置２は、自装置のストレージに、wの分散値として、(s2, t2) = (r2, r3)を保管し、w'の分散値として、(s2', t2') = (r2', r3')を保管する。
装置３は、自装置のストレージに、wの分散値として、(s3, t3) = (r3, r1)を保管し、w'の分散値として、(s3', t3') = (r3', r1')を保管する。
【００２５】
装置１乃至３は、それぞれ以下の手順に従った処理を行う。
【００２６】
装置１、装置２、及び装置３は、
r1" + r2" + r3" = 0 mod 2 ^ n 
を満たすランダムに選ばれた値として、r1"、r2"、r3"をそれぞれ保管しているものとする。このような性質を満たすr1"、r2"、r3"は、乗算を実行するたびに使い捨てで必要となる。このような３値を、３台の装置が効率的に生成する方法については後述する。
【００２７】
装置１は、u2 = s1 s1' + s1 t1' + t1 s1' + r1" mod p 
を計算し、u2を装置２に送付する。
装置２は、u3 = s2 s2' + s2 t2' + t2 s2' + r2" mod p を計算し、u3を装置３に送付する。
装置３は、u1 = s3 s3' + s3 t3' + t3 s3' + r3" mod p を計算し、u1を装置１に送付する。
【００２８】
装置１は、自装置のストレージに(u1, u2)を、ww'の分散値として保管する。
装置２は、自装置のストレージに(u2, u3)を、ww'の分散値として保管する。
装置３は、自装置のストレージに(u3, u1)を、ww'の分散値として保管する。
【００２９】
以下が確認できる。
u1 + u2 + u3 = r1r1' + r1r2' + r2r1' + r2r2' + r2r3' + r3r2' + r3r3' + r3r1' + r1r3' + r1" + r2" + r3"
= (r1 + r2 + r3)(r1' + r2' + r3') + r1" + r2" + r3" 
= ww' mod p
【００３０】
装置１と装置２の保管する値から、ww' mod pが同じ計算方法で計算できる。他の装置の組み合わせについても同様である。このような方法によれば、両方とも(2,3)型ＲＳＳにより分散されているw及びw'に関する乗算を、各値を復元することなく実行し、(2,3)型ＲＳＳを適用してww'を分散した値を共有することができる。
【００３１】
＜乱数の生成＞
以下、３つ足すと０となる値を、装置１、装置２、装置３が通信することなく、また、各装置が所有する値を他の装置に知られることのない方法で、大量に生成する方法について説明する。ここでは、
r[i,1] + r[i,2] + r[i,3] = 0 mod 2^n 
となるr[i,1]、r[i,2]、r[i,3]を、多くのi = 1,...,Nに関して生成する方法を説明する。
【００３２】
鍵とインデックスを入力として、ｎビットの数値列を出力する擬似乱数生成器（Pseudo Random Generator；ＰＲＧ)が提供されるとする。インデックスは、カウンタなどでよい。この方法は、非特許文献３などに記載がある。
【００３３】
まず、装置のセットアップ処理として、ＰＲＧの鍵L1、L2、L3を生成する。装置１に、L1とL3を記憶させ、装置２に、L2とL1を記憶させ、装置３に、L3とL2を記憶させているものとする。
【００３４】
各装置１、２、３は、カウンタなどで同期されたインデックスidxを共有しているものとする。
【００３５】
装置１は、鍵L1とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[1]を生成する。また、装置１は、鍵L3とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[3]を生成する。そして、装置１は、
r[1] = r'[1] - r'[3] mod p
とする。
【００３６】
装置２は、鍵L2とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[2]を生成する。また、装置２は、鍵L1とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[1]を生成する。そして、装置２は、
r[2] = r'[2] - r'[1] mod p
とする。
【００３７】
装置３は、鍵L3とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[3]を生成する。また、装置３は、鍵L2とインデックスidxをＰＲＧに入力し、その出力であるｎビットの数値r'[2]を生成する。そして、装置３は、
r[3] = r'[3] - r'[2] mod p
とする。
【００３８】
以下が成り立つ。
r[1] + r[2] + r[3] = r'[1] - r'[3] + r'[2] - r'[1] + r[3] - r[2] = 0 mod p
【００３９】
Ｎ組全てが上記条件を満たす。
【００４０】
装置１が生成する値 r[1] = r'[1] - r'[3] mod p に着目すると、装置３はr'[1]が得られず、装置２はr'[3]が得られない。
【００４１】
これにより、装置２、装置３は、r[1]を計算できないことがわかる。これは、r[2]やr[3]についても同様である。
【００４２】
セットアップ処理が済んでいれば、以上の処理は、例えば計算が行われる前などにも実行可能である。
【００４３】
上述の(2,3)型ＲＳＳを用いた秘密計算において、p = 2とすると、乗算は、AND（論理積）処理とみなすことができ、加算・減算は、排他的論理和(exclusive OR;XOR)処理とみなすことができる。これによって、p = 2とした場合、上述の計算は論理演算に適した秘密計算(secure computation)となる。また、装置１乃至３の分散情報を、すべて、(1,1)、(1,1)、(1,1)とすると、これは、r1 = 1, r2 = 1, r3 = 1として、1の分散情報になっている。これは、論理積(AND)、排他的論理和(XOR)、定数1によって完全系（complete system）となり、任意の演算が実行可能となる。
【００４４】
以上の方法は、非特許文献１などに記載されている。このような方法には種々のバリエーションを考えることができる。例えば、
r1 + r2 + r3 = w mod p に関して、
(r1 - r2 mod p, r2), (r2 - r3 mod p, r3), (r3 - r1 mod p, r1) を分散情報としてもよい。３台の装置が、r1、r2、r3のうち、異なる二つの組に相当する情報を保有している方法を、(2,3)型ＲＳＳと称することにする。
【００４５】
ＲＳＳに関して、任意の演算は、p = 2とした(2,3)型ＲＳＳを用いることで、演算処理が可能である。しかし、すべての処理を、論理演算で実行することは、非効率的である。そこで、乗算と加算で構成できる演算は、pを大きく設定した(2,3)型ＲＳＳを用いた秘密計算で実行するほうがよい。
【００４６】
さらに、数値演算と論理演算の組み合わせるのが望ましい場合もある。例えば、2^4（^はべき乗演算）よりも小さい値であるa、b、cを入力として、
a * b mod 2^4 < c
を処理する場合、a * bを数値演算として処理し、比較演算を論理演算として実行するのが望ましい。a * bを数値演算として計算するのが望ましいが、a * bをcと比較する処理を数値演算として表現することは難しい。
【００４７】
このような問題を解決するため、非特許文献２に記載のビット分解（bit decomposition）と呼ばれる処理が知られている。ビット分解は、数値計算向けの分散情報を論理演算向けの分散情報に変換するための処理である。
【００４８】
例えば、p = 8を用いた(2,3)型ＲＳＳによって、値w = 5を分散し、装置１が、(1, 2)を記憶し、装置２が(2, 2)を記憶し、装置３が、(2, 1)を記憶しているものとする。
【００４９】
ビット分解を用いれば、これらの情報から、5の２進表記( = 101)である1と0と1の各ビットに対する分散情報を得ることができる。
【００５０】
具体的には、ビット分解が実行された後、装置１は、１ビット目に関して(1, 1)、２ビット目に関して(0, 1)、３ビット目に関して(1, 0)、４ビット目に関して(0, 0)を所有する。
装置２は、１ビット目に関して(1, 1)、２ビット目に関して(1, 1)、３ビット目に関して(0, 0)、４ビット目に関して(0, 0)を所有する。
装置３は、１ビット目に関して(1, 1)、２ビット目に関して(1, 0)、３ビット目に関して(0, 0)、４ビット目に関して(0, 0)を所有する。
【００５１】
ビット分解に関する関連技術として、非特許文献２に記載の方法の概要を以下に示す。この方法は以下のような手順でビット分解を実行する。
【００５２】
ビット分解を実行する値は、r = r1 + r2 + r3 mod pを満たすr1、r2、r3を用いて、共有（share）されているものとする。なお、非特許文献２では、p = 2 ^ n - 1によって表されるメルセンヌ素数を用いる。メルセンヌ素数(Mersenne prime)の性質により、手順２において、sが効率的に計算されている。
【００５３】
＜手順１＞
r12 = r1 + r2 mod p、および、r3の分散（sharing）を実行する。
【００５４】
＜手順２＞
r12 + r3 が pよりも大であるか否かを判定し、
r12 + r3 が pよりも大きい場合、s = 1とし、
それ以外の場合、s = 0
となるような秘密計算を実行する。
【００５５】
＜手順３＞
全加算器(full adder)によるr12 + r3 + s mod 2 ^ nの秘密計算を下位桁からビット毎に実行する。
【００５６】
非特許文献２の方法によれば、pがnビットの数であるとして、10n + 4ビットの総通信量によってビット分解を実行できることが記載されている。
【先行技術文献】
【非特許文献】
【００５７】
【非特許文献１】千田浩司、五十嵐大、濱田浩気、高橋克巳、「エラー検出可能な軽量 3 パーティ秘匿関数計算の提案と実装評価」、Vol. 52, No.9, 2674-2685, Sep. 2011
【非特許文献２】五十嵐大、濱田浩気、菊池亮、千田浩司、「少パーティの秘密分散ベース秘密計算のための O(l)ビット通信ビット分解およびO(|p′|)ビット通信Modulus変換法」、Computer Security Symposium 2013、21 - 23 October 2013
【非特許文献３】Toshinori Araki, Jun Furukawa, Yehuda Lindell, Ariel Nof and Kazuma Ohara, "High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority", CCS'16 Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Pages 805-817
【発明の概要】
【発明が解決しようとする課題】
【００５８】
上記非特許文献１乃至３の全開示内容は、 引用をもって本書に組み込み記載されているものとする。以下の分析は、本発明者らによってなされたものである。
【００５９】
上述の通り、非特許文献２によれば、pをnビットの数とすれば、10n + 4ビットの通信量でビット分解を行うことができる。
【００６０】
しかし、例えば非特許文献２の通信量よりも少ない通信量で、ビット分解を効率的に実行できる方法を実現することが望ましい。
【００６１】
したがって、本発明の目的は、より少ない通信量で、ビット分解及び／又はビット結合を可能とし効率的な秘密計算を実現する装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００６２】
本発明の１つの側面によれば、２のべき乗を法とする演算（arithmetic）を用いる(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)によって得た（分散した）分散値を保管する分散値保管装置と、
２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を含み、
前記分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散(sharing)に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすランダムに選ばれたr1、r2、r3を用い、前記ビット分解秘密計算装置は、
r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳによって分散値を生成し配布する加算分散部と、
前記加算分散部が生成した前記値と、前記加算分散部によって用いられなかった値との加算処理を、全加算器の秘密計算を用いて各桁毎に実行し、その結果を前記分解分散値保管装置に記憶する全加算器秘密計算部と、を含むビット分解秘密計算システムが提供される。
【００６３】
本発明の他の側面によれば、２のべき乗を法とする演算を用いる(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)を適用して得た（分散した）分散値を保管する分散値保管装置と、
２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を含み、
前記分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たすランダムに選ばれたr1、r2、r3を用い、前記ビット分解秘密計算装置は、
r12 = r1 + r2 mod 2 ^ n の秘密計算とr123 = r12 + r3 mod 2 ^ n の秘密計算とを全加算器の秘密計算によって各桁毎に実行し、その計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部を含むビット分解秘密計算システムが提供される。
【００６４】
本発明のさらなる側面によれば、２のべき乗を法とする演算を用いる(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)によって得た（分散した）分散値を保管する分散値保管装置と、
２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置と、
ビット結合秘密計算装置と、
を含み、
前記分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たすランダムに選ばれたr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、前記ビット結合秘密計算装置は、
r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算とを全加算器の秘密計算によって各桁毎に実行し、計算結果を前記分散値保管装置に記憶する全加算器秘密計算部を含むビット結合秘密計算システムが提供される。
【００６５】
本発明の１つの側面によれば、ビット分解秘密計算を提供するためのコンピュータシステムの方法であり、
２のべき乗を法とする演算を用いる(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式によって得た（分散した）分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たしランダムに選ばれたr1、r2、r3を用い、r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳによって分散値を生成し配布する加算分散ステップと、
前記加算分散ステップにおいて生成された前記値と、前記加算分散ステップにおいて用いられなかった値との加算処理を、全加算器の秘密計算を用いて各桁毎に実行し、その結果を、２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算ステップと、を含む方法が提供される。
【００６６】
本発明の他の側面によれば、ビット分解秘密計算を提供するためのコンピュータシステムの方法であり、
２のべき乗を法とする演算を用いる(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式によって得た（分散した）分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たしランダムに選ばれたr1、r2、r3を用い、r12 = r1 + r2 mod 2 ^ n の秘密計算とr123 = r12 + r3 mod 2 ^ n の秘密計算とを全加算器の秘密計算によって各桁毎に実行し、
その計算結果を、２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算ステップを含む方法が提供される。
【００６７】
本発明のさらなる側面によれば、ビット結合秘密計算を提供するためのコンピュータシステムの方法であり、
２を法とする演算を用いる(2,3)型ＲＳＳによって得た（分散した）分散値の列を保管する分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たしランダムに選ばれたr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算とを全加算器の秘密計算によって各桁毎に実行し、
その計算結果を、２のべき乗を法とする(2,3)型ＲＳＳによって得た（分散した）分散値を保管する分散値保管装置に記憶する全加算器秘密計算ステップを含む方法が提供される。
【００６８】
本発明の１つの側面によれば、２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、
w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たしランダムに選ばれたr1、r2、r3を用い、r1、r2、r3のうち２つの値について、法2 ^ n上の和をとり、前記和について、前記(2,3)型ＲＳＳにより分散値を生成して分散する加算分散処理と、
前記加算分散処理において生成された前記値と、前記加算分散処理において用いられなかった値との加算処理を、全加算器の秘密計算を用いて、各桁毎に実行し、その結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算処理と、を含む、ビット分解秘密計算処理をコンピュータに実行させるプログラムが提供される。
【００６９】
本発明の他の側面によれば、２のべき乗を法とする演算を用いた(2,3)型ＲＳＳ(Replication type Secret Sharing：複製秘密分散)方式を適用して得た分散値を保管する分散値保管装置が保管する前記(2,3)型ＲＳＳの分散情報として、値wの分散に関して、w = r1 + r2 + r3 mod 2 ^ n (^はべき乗演算、nは予め設定された正整数)を満たしランダムに選ばれた1、r2、r3を用い、
r12 = r1 + r2 mod 2 ^ n の秘密計算と、
r123 = r12 + r3 mod 2 ^ n の秘密計算と、
を全加算器の秘密計算を用いて、各桁毎に実行し、計算結果を、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置に記憶する全加算器秘密計算処理を含む、ビット分解秘密計算処理をコンピュータに実行させるプログラムが提供される。
【００７０】
本発明のさらなる側面によれば、２を法とする演算を用いた(2,3)型ＲＳＳを適用して得た分散値の列を保管する分解分散値保管装置が記憶するn個の前記(2,3)型ＲＳＳの分散情報の列として、値w_iの分散に関して、w_i = r {1, i} + r {2, i} + r_{3, i} mod 2 を満たしランダムに選ばれたr_{1, i}, r_{2, i}, r_{3, i}（i = 1,...,n)を用い、r12 = r_{1, n} || ... | r_{1, 1} + r_{2, n} || ... || r_{2, 1} mod 2 ^ n （記号||は連結演算子、^はべき乗演算、nは予め設定された正整数)の秘密計算と、r123 = r12 + r_{3, n} || ... ||r_{3, 1} mod 2 ^ n の秘密計算とを全加算器の秘密計算を用いて、各桁毎に実行し、計算結果を、２のべき乗を法とする演算を用いる(2,3)型ＲＳＳを適用して得た分散値を保管する分散値保管装置に記憶する全加算器秘密計算処理を含む、ビット結合秘密計算処理をコンピュータに実行させるプログラムが提供される。
【００７１】
本発明のさらに他の側面によれば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory）、ＵＳＢ(Universal Serial Bus)デバイス、ＳＳＤ（Solid State Device）などの半導体メモリ、又は例えばＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）又はＤＶＤ（Digital Versatile Disc）などの記憶装置などのような、上記のプログラムを記録した、非一時的なコンピュータ読み出し可能な記録媒体が提供される。
【発明の効果】
【００７２】
本発明によれば、より少ない通信量で、ビット分解及び／又はビット結合を可能とし効率的な秘密計算を実現することができる。
本発明のさらに他の特徴及び利点は、本発明を実施することが企図されている最良の形態の単なる例示により、本発明の実施形態のみを図示及び説明した添付の図面と併せて以下の詳細な説明から当業者には容易に明らかになるであろう。理解されるように、本発明は、他の異なる実施形態が可能であり、そのいくつかの詳細は、本発明から逸脱することなく、様々な明白な点において変更可能である。従って、図面及び説明は、本質的に例示的であるとみなされるべきであり、限定的ではないとみなされるべきである。
【図面の簡単な説明】
【００７３】
【図１】第１の実施形態の構成を例示する図である。
【図２】本発明の第１の実施形態の動作を説明する流れ図である。
【図３】第２の実施形態の構成を例示する図である。
【図４】本発明の第２の実施形態の動作を説明する流れ図である。
【図５】第３の実施形態の構成を例示する図である。
【図６】本発明の第３の実施形態の動作を説明する流れ図である。
【図７】本発明の第４の実施形態の構成を例示する図である。
【発明を実施するための形態】
【００７４】
図面を参照して例示的な実施形態を説明する。上記非特許文献２の方法によれば、上記手順１において、r3が共有されている。この処理を、通信無しで実行する方法について説明する。
【００７５】
r = r1 + r2 + r3 mod pを満たすr1、r2、r3を分散（shares）として用いてある値の分散（sharing）が行われることを想定する。
【００７６】
r = r1 + r2 + r3 mod pを満たすri (i = 1, 2, 3)に関連する分散（shares）を生成する場合、r = r1 + r2 + r3 mod pの分散情報（share information）のriに関する箇所以外をすべて0に設定した値が、riの分散情報となる。
【００７７】
装置１が(r2, r3)を保管し、装置２が(r3, r1)を保管し、装置３が(r1, r2)を保管しているとする。
例えば、r1に関する箇所以外を全てゼロに設定すると、装置１は(0, 0)を保有し、装置２は(0, r1)を保有し、装置３は(r1, 0)を保有する。これらは、r1の分散情報とすることができる。
【００７８】
装置２と装置３がr1自体を保管していることは秘匿性に何ら影響を与えない。これらは、元々、把握可能な値であるためである。r2、r3についても同様に、装置間において通信することなく、その分散情報を得ることができる。
【００７９】
非特許文献２の方法の上記手順３、すなわち、r12 + r3 + s mod 2 ^ nでsを加算している理由は、r12 + r3 mod p をmod 2 ^ nの秘密計算で求めるためである。
【００８０】
s = 1の場合、r12 + r3 = r' + p とすると、以下が成り立つ。
r' + p mod p = r'+ p + 1 = r' + 2 ^ n mod 2 ^ n
【００８１】
s = 0の場合、r12 + r3 = r'とすると、r' mod p = r' mod 2 ^ n となる。
【００８２】
以上のように、sの値に関わらず、上記手順３の計算結果は、r12 + r3 mod p となる。
【００８３】
しかしながら、pとして2 ^ nを用いれば、r12 + r3 が2 ^ nを越えた場合の処理は不要である。
【００８４】
＜形態＞
以上の変更を加えた本発明の一形態のビット分解法について以下に説明する。
【００８５】
＜手順１＞
r12 = r1 + r2 mod 2 ^ n の分散（sharing）を実行する。
【００８６】
＜手順２＞
各装置でr3の分散情報を生成する。
【００８７】
＜手順３＞
下位桁からビット毎に全加算器の秘密計算を実行して、
r12 + r3 + s mod 2 ^ n を計算する。
【００８８】
以上の処理の通信量を評価する。
w = r1 + r2 + r3 mod 2 ^ n を満たすr1、r2、r3をランダムに選択して、以下のように保管されているものとする。
装置１には、(r1, r2)がwの分散値（share value）として保管され、
装置２には、(r2, r3)がwの分散値として保管され、
装置３には、(r3, r1)がwの分散値として保管される。
【００８９】
＜手順１の通信量＞
r1 + r2の配布（distribution）は、装置１によって実行される。まず、装置１は、r12 = r1 + r2 mod 2 ^ n を計算し、r12A + r12B = r12 mod 2 ^ n となるr12Aとr12Bをランダムに選択する。
【００９０】
次に、装置１は、r12Aを装置２に送信し、r12Bを装置３に送信する。
【００９１】
この結果、装置１は、r12の分散値として、(r12B, r12A)を得る。
装置２は、r12の分散値として、(r12A, 0)を得る。
装置３は、r12の分散値として、(0, r12B)を得る。
この処理では、2nビットの通信を行っている。
【００９２】
＜手順２の通信量＞
上述したように、r3の分散情報は、通信を行わずに生成できる。
【００９３】
＜手順３の通信量＞
全加算器の秘密計算は、各桁のキャリーを計算するために１回のAND演算を必要とする。したがって、n桁の加算の場合、3 * (n - 1)ビットの通信が必要となる。
【００９４】
以上の結果として、5n - 3ビットの通信量でビット分解が計算できることが分かる。ここで、加算器処理によって計算結果をビット単位に分解する様子を示す例を挙げる。
【００９５】
p = 8、r = 6（２進表記で110）、r1 = 3（２進表記で011）、r2 = 2（２進表記で010）、r3 = 1（２進表記で001）のビット分解の計算過程を示す。
【００９６】
r_iの最下位桁からj桁目を ri_j、r1r2 mod 8のj桁目を r12_j、そして、r1 + r2 + r3 mod 8のj桁目を r123_j と表記する。
【００９７】
次に、
r12 + r3 mod 8 = 5 + 1 mod 8 = 6
を最下位桁から計算する手順を示す。
【００９８】
＜１桁目＞
１桁目の計算は以下の通りになる。
r123_1 = r12_1 XOR r3_1 = 0 XOR 1 XOR 1 = 0
XORはビット単位の排他的論理和である。
１桁目の計算に関する桁上がりは以下の通りになる。
c1 = r12_1 AND r3_1 = 1 AND 1 = 1
(１桁目では下位桁からの桁上がり(キャリー)がない。)
【００９９】
＜２桁目＞
２桁目の計算は以下の通りになる。
r123_2 = r12_2 XOR r3_2 XOR c1 = 0 XOR 0 XOR 1 = 1
２桁目の計算に関するキャリーは以下の通りになる。
c2 = c1 XOR (1 XOR r12_2 XOR r3_ 2) AND (r3_ 2 XOR c1) = 1 XOR (1 XOR 0 XOR 0) AND (0 XOR 1) = 0
【０１００】
＜３桁目＞
３桁目の計算は以下の通りになる。
r123_3 = r12_3 XOR r2_3 XOR c2 = 1 XOR 0 XOR 0 = 1
【０１０１】
以上のように、ＡＮＤの処理１回で、r123_1 = 0, r123_2 = 1, r123_3 = 1 のように、各桁をビット毎に分解した値を計算することが可能になる。この処理は秘密計算で実行できる。秘密計算の結果が、ビット毎に分解した値の分散値となる。
【０１０２】
上記の場合では、(2,3)閾値型ＲＳＳとして、値wが以下のように与えられるとき、
w = r1 + r2 + r3 mod p
装置１が、(r1, r2)を保管し、
装置２が、(r2, r3)を保管し、
装置３が、(r3, r1)を保管する。
【０１０３】
しかし、本発明は、r1、r2、r3の３つの値のうち異なる２つに相当する情報を保有する(2,3)閾値型ＲＳＳであれば適用可能である。例えば、 装置２は、(r2, r3)でなく、(r2 + r3, r3) を保有していてもよいし、装置２が(r2 - r3, r2 + r3) などを保有する方法であってもよい。秘密計算として加算、乗算、定数を備えていれば実施可能である。
【０１０４】
あるいは、まず、r12 = r1 + r2 mod 2 ^ nの計算を秘密計算によって実行してから、r12 + r3に関する演算を全加算器の秘密計算によって実行してもよい。この方法を用いる場合、r12を計算する通信量が3nビットとなり、装置１が分散する場合に比べて効率は悪いが、全体の通信量は、6n-3ビットである。
【０１０５】
r1 + r2の計算を全加算器の秘密計算によって実行する場合、最上位の桁から発生するキャリーに関する計算を実行する必要が無いため、3n - 3ビットの通信量で、r12に関する計算を実行できる。この場合、6n - 6ビットの通信量でビット分解を実行することができる。
【０１０６】
これらの変形例も非特許文献２の方法に比べて効率的である。
【０１０７】
また、両方の処理（r12 = r1 + r2 mod 2 ^ n、及び r12 + r3 mod 2 ^ n ）を全加算器の秘密計算を用いて実行する場合、非特許文献３に記載されているような(2,3)型ＲＳＳを用いた秘密計算法に不正耐性を付与する仕組みを用いることもできる。
【０１０８】
さらに、ビット分解された分散情報から結合された値に対する分散情報を作成することも可能である。下位の桁から上位の桁への各キャリー（carry）を、キャリー計算の秘密計算によって実行していき、すべての桁のキャリー計算を終えた段階で、各桁の秘密計算結果を結合すればよい。
【０１０９】
この方法では、r1 + r2 mod 2 ^ n相当の情報を保有している主体が存在しないため、r12 = r1 + r2 mod 2 ^ n と、r12 + r 3 mod 2 ^ n の計算の両方を、全加算器の秘密計算によって実行することになる。
【０１１０】
全加算器の計算を、下位桁から順番に実行する場合、n-1回のＡＮＤ演算が発生する。これによって、通信の回数がn-1回となる。この回数を減らすためにキャリーセーブアダー(carry save adder)を用いてもよい。この手法では、ＡＮＤ演算の回数は増えるが、回路の深さは浅くなる。
【０１１１】
＜例示的な実施形態＞
本発明の実施形態１の構成と動作について図面を参照して説明する。
【０１１２】
＜実施形態１＞
第１の実施形態では、w = r1 + r2 + r3 mod 2 ^ n を満たすランダムに選ばれたr1、r2、r3を用いた(2,3)型ＲＳＳ方式でwが分散されている場合、１つの装置がr12 = r1 + r2 mod 2 ^ n を分散し、r12 + r3 mod 2 ^ n を全加算器の秘密計算を用いて実行することによって、ビット分解された分散情報を生成する。
【０１１３】
図１は、本発明の第１の実施形態の構成を例示するブロック図である。図１を参照すると、本発明の第１の実施形態によるビット分解秘密計算システム１０は、pとして2 ^ nを用いた(2,3)型ＲＳＳを適用して得た分散値(share value)を保管する分散値保管装置１００と、ビット分解された分散情報(decomposed share value)を保管する分解分散値保管装置２００と、分散値保管装置１００が記憶する分散値を読み出し、分解分散値保管装置２００にビット分解値(bit decomposed value)を記憶させるビット分解秘密計算装置３００とを含む。
【０１１４】
第１の実施形態では、図１の装置１００、２００、３００が１組を構成し、３組の装置が設けられている。すなわち、３組のシステム１０が提供されている。装置１００、２００、３００、または装置１００、２００、３００から選択されたいずれか２つの装置は１つのユニットとして配置されていてもよいし、分散して配置されていてもよい。例えば、少なくとも装置１００と装置２００との間、及び装置２００と装置３００との間には、ＬＡＮ（Local Area Network）及び／又はＷＡＮ（Wide Area Network）などの１つ以上の通信経路が設けられてもよい。なお、図１において、装置１００と装置３００、装置３００と装置２００との間の矢印線はそれぞれ、データの流れの一例を示しているに過ぎない。装置１００と装置３００、装置３００と装置２００との間の通信は、矢印線の方向に限定されないことは勿論である。後述する他の実施形態においても同様である。
【０１１５】
分散値保管装置１００は、第１の分散値保管部１０１と、第２の分散値保管部１０２とを含む。第１の分散値保管部１０１及び第２の分散値保管部１０２は、それぞれの分散値（第１の分散値と第２の分散値）を、(2,3)型ＲＳＳ方式の分散情報を生成するために用いられた３つの値のうちどの値が用いられ、 保管される分散値を得るためにそれらの値がどのように処理されたかが分かるように保管する。
【０１１６】
分解分散値保管装置２００は、第１の分解分散値保管部２０１と第２の分解分散値保管部２０２とを含む。第１の分解分散値保管部２０１及び第２の分解分散値保管部２０２は、それぞれの分散情報（第１の分散値と第２の分散値）を、(2,3)型ＲＳＳ方式の分散情報を生成するために用いられた３つの値のうち、どの分散値が用いられ、保管される分散情報を得るためにそれらの値がどのように処理されたかが分かるように保管する。
【０１１７】
ビット分解秘密計算装置３００は、加算分散部３０１と、部分分散情報抽出部３０２と、全加算器秘密計算部３０３とを含む。ビット分解秘密計算装置３００は、分散値保管装置１００の第１の分散値保管部１０１と第２の分散値保管部１０２とが記憶する分散値を読み出し、他のビット分解秘密計算装置３００（不図示）と通信し、分解分散値保管装置２００の第１の分解分散値保管部２０１と第２の分解分散値保管部２０２とに情報（ビット分解された分散値）を記憶させる。
【０１１８】
加算分散部３０１は、(2,3)型ＲＳＳによる分散情報を構成する３つの値のうち２つのインデックスを入力として、分散値保管装置１００が記憶する分散値を読み出す。分散値保管装置１００が２つのインデックス両方の分散値を保管している場合は、加算分散部３０１は、２つのインデックスの分散値の和について、(2,3)型ＲＳＳにより分散情報を生成 し、生成した分散情報を他の２つの装置（不図示）の加算分散部３０１に送付する。
【０１１９】
部分分散情報抽出部３０２は、(2,3)型ＲＳＳ方式による分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出し、(2,3)型ＲＳＳ方式による分散情報を構成する３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する。
【０１２０】
全加算器秘密計算部３０３は、加算分散部３０１によって生成配布された(2,3)型ＲＳＳの分散情報と部分分散情報抽出部３０２によって生成された(2,3)型ＲＳＳの分散情報とについて、全加算器の秘密計算を用いた加算処理を実行し、各ビットに関して得られたビット毎の計算結果の分散情報を結合した値を、分解分散値保管装置２００に記憶させる。
【０１２１】
図２は、本発明の第１の実施形態の動作を説明する流れ図である。分散値保管装置１００には、r = r_1 + r_2 + r_3 mod 2 ^ n となるr_1、r_2、r_3を用いた(2,3)型ＲＳＳで分散された分散値が記憶されているものとする。
【０１２２】
第１の実施形態の動作では、 
r_ij = r_i + r_j mod 2 ^ n が分散（share）され、
r_ijとr_kの加算を全加算器の秘密計算で実行する。
i、j、kは互いに異なる値で1、2、3のいずれかの値の組み合わせから選択されれば、どのような組み合わせが用いられてもよい。
【０１２３】
以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット分解秘密計算装置３００が実行する。
【０１２４】
まず、各加算分散部３０１は、ビット分解秘密計算装置３００と対応付けられた分散値保管装置１００が、r_iとr_jに関する情報を記憶しているか否かを判定する。記憶している場合、各加算分散部３０１は、r_ij = r_i + r_j mod 2 ^ n を計算し、計算結果を他の２つのビット分解秘密計算装置３００の加算分散部３０１に送付する。その後、各加算分散部３０１は、r_ijの分散情報を出力する（ステップＡ１）。
【０１２５】
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値から、r_kに関する部分以外の値を０と設定した部分分散情報を出力する（ステップＡ２）。
【０１２６】
次に、全加算器秘密計算部３０３は、r_ijの分散情報と、r_kの分散情報に関して、全加算器の秘密計算を用いた加算処理を実行し、そして、加算処理結果のシーケンスを分解分散値保管装置２００に記憶する（ステップＡ３）。
【０１２７】
＜例示的な実施形態２＞
本発明の第２の例示的な実施形態の構成と動作について図面を参照して説明する。
【０１２８】
第２の例示的な実施形態では、w = r1 + r2 + r3 mod 2 ^ nを満たすr1、r2、r3を用いた(2,3)型ＲＳＳ方式でwが分散されている場合、
r12 = r1 + r2 mod 2 ^ n を全加算器の秘密計算によって実行し、
r12 + r3 mod 2 ^ n を下位ビットから全加算器の秘密計算によって計算する。
【０１２９】
図３は、本発明の第２の実施形態の構成を例示するブロック図である。図３を参照すると、本発明の第２の実施形態によるビット分解秘密計算システム１０Ａは、pとして2 ^ nを用いた(2,3)型ＲＳＳ方式を適用して得た分散値を保管する分散値保管装置１００と、ビット分解された分散情報を保管する分解分散値保管装置２００と、分散値保管装置１００が記憶する分散値を読み出し、分解分散値保管装置２００にビット分解値を記憶させるビット分解装置３００を含む。
【０１３０】
上記第１の実施形態と同様、図１の装置１００、２００、３００を１セットとした装置が３組提供される。すなわち、システム１０Ａが３セット提供される。
【０１３１】
分散値保管装置１００は、第１の分散値保管部１０１と、第２の分散値保管部１０２とを含む。第１の分散値保管部１０１及び第２の分散値保管部１０２は、分散値を、(2,3)型ＲＳＳの分散情報を生成するために用いられた３つの値のうちどの値が用いられ、 保管される分散値を得るためにそれらの値がどのように処理されたかが分かるように保管する。
【０１３２】
分解分散値保管装置２００は、第１の分解分散値保管部２０１と第２の分解分散値保管部２０２とを含む。第１の分解分散値保管部２０１及び第２の分解分散値保管部２０２は、それそれの値（ビット分解された分散値）を、(2,3)型ＲＳＳの分散情報を生成するために用いられた３つの値のうちどの分散値が用いられ、保管される分散情報を得るためにそれらの値がどのように処理されたかが分かるように保管する。
【０１３３】
ビット分解秘密計算装置３００は、部分分散情報抽出部３０２と、全加算器秘密計算部３０３とを含む。
【０１３４】
ビット分解秘密計算装置３００Ａは、分散値保管装置１００が記憶する値を読み出し、他の２つのビット分解秘密計算装置３００Ａと通信し、分解分散値保管装置２００に情報を記憶させる。
【０１３５】
部分分散情報抽出部３０２は、(2,3)型ＲＳＳ方式による分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出し、(2,3)型ＲＳＳによる分散情報を構成する３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する。
【０１３６】
全加算器秘密計算部３０３Ａは、部分分散情報抽出部３０２によって生成された(2,3)型ＲＳＳの分散情報３組を入力として、当該３つの値に関して下位ビットから全加算器の秘密計算を実行し、ビット毎の計算結果の分散情報を分解分散値保管装置２００に記憶させる。
【０１３７】
図４は、本発明の第２の実施形態の動作を説明する流れ図である。
【０１３８】
分散値保管装置１００には、r = r_1 + r_2 + r_3 mod 2 ^ n を満たすr_1、r_2、r_3を用いた(2,3)型ＲＳＳを適用して分散されるnビットの値rの分散値が記憶されているものとする。
第２の実施形態の動作では、
r_ij = r_i + r_j mod 2 ^ n を全加算器の秘密計算で実行し、
r_ij + r_k mod 2 ^ n を全加算器の秘密計算で実行する。i、j、kは互いに異なり、1、2、3のいずれか値の組み合わせから選択される値とする。
【０１３９】
以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット分解秘密計算装置３００Ａが実行する。
【０１４０】
まず、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_iに関する部分以外の値をゼロとみなした部分分散情報を出力する（ステップＢ１）。
【０１４１】
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_jに関する部分以外の値をゼロとみなした部分分散情報を出力する（ステップＢ２）。
【０１４２】
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_kに関する部分以外の値をゼロとみなした部分分散情報を出力する（ステップＢ３）。
【０１４３】
次に、全加算器秘密計算部３０３は、r_iの分散情報とr_jの分散情報に関して、最下位ビットの降順で、全加算器の秘密計算を実行し、その結果の列をr_ijの分散情報として出力する（ステップＢ４）。
【０１４４】
次に、全加算器秘密計算部３０３は、r_ijの分散情報とr_kの分散情報に関して、全加算器の秘密計算を実行し、その結果の列を分解分散値保管装置２００に記憶させる（ステップＢ５）。
【０１４５】
＜例示的な実施形態３＞
本発明の第３の例示的な実施形態の構成と動作について図面を参照して説明する。
【０１４６】
第３の例示的な実施形態では、 i = 1,..., N について、w = r_{i, 1} + r_{i, 2} + r_{i, 3} mod 2 を満たす r_{i, 1}, r_ {i, 2}, r_ {i, 3}を用いた(2,3)型ＲＳＳで、ビットwiが分散されている場合に、
r12 = r_{1, n} ||... ||r_{1, 1} + r_{2, n} ||r_{2, 1} mod 2 ^と、
r12 = r12 + r_{3, n} ||... ||r_{3, 1} mod 2 ^ n を
全加算器の秘密計算によって実行することによって、ビット結合を行う。記号||は、ビット連結(concatenation)を表す。
【０１４７】
図５は、本発明の第３の実施形態の構成を例示するブロック図である。図５を参照すると、本発明の第３の実施形態によるビット結合秘密計算システム２０は、pとして2 ^ nを用いた(2,3)型ＲＳＳを適用して得た分散値を保管する分散値保管装置１００と、分散情報を保管するビット分解分散値保管装置２００と、分解分散値保管装置２００が記憶する値を読み出し、分散値保管装置１００に値を記憶させるビット結合秘密計算装置４００とを含む。
【０１４８】
図５の装置１００、２００、及び４００が１組の装置を構成し、３組の装置が提供される。すなわち、３組のシステム２０が提供される。
【０１４９】
分散値保管装置１００は、第１の分散値保管部１０１と、第２の分散値保管部１０２とを含む。第１の分散値保管部１０１及び第２の分散値保管部１０２は、(2,3)型ＲＳＳ方式の分散情報を生成するために用いられた３つの値のうちどの値が用いられ、 保管される分散値を得るためにそれらの値がどのように処理されたかが分かるように分散値を保管する。
【０１５０】
分解分散値保管装置２００は、第１の分解分散値保管部２０１と第２の分解分散値保管部２０２とを含む。第１の分解分散値保管部２０１及び第２の分解分散値保管部２０２は、(2,3)型ＲＳＳの分散情報を生成するために用いられた３つの値のうちどの値が用いられ、保管される分散値を得るためにそれらの値がどのように処理されたかが分かるように分散値を保管する。
【０１５１】
ビット結合秘密計算装置４００は、部分分散情報抽出部３０２と全加算器秘密計算部３０３とを含む。
【０１５２】
ビット結合秘密計算装置４００は、分解分散値保管装置２００が記憶する値を読み出し、他のビット結合秘密計算装置４００と通信し、分散値保管装置１００に情報を記憶させる。
【０１５３】
部分分散情報抽出部３０２は、(2,3)型ＲＳＳによる分散情報を構成する３つの値のうち１つのインデックスを入力として、分解分散値保管装置２００が記憶する値を抽出し読み出し、(2,3)型ＲＳＳによる分散情報を構成する３つの値のうち１つを除いて値をゼロに設定した分散情報を生成する。
【０１５４】
全加算器秘密計算部３０３は、部分分散情報抽出部３０２によって生成された(2,3)型ＲＳＳの分散情報３組を入力として、３つの値に関する 下位ビットから全加算器の秘密計算を実行し、ビット毎の計算結果の分散情報を分散値保管装置１００に記憶させる。
【０１５５】
図６は、本発明の第３の実施形態の動作を説明する流れ図である。分解分散値保管装置２００には、ri = r_{i, 1} + r_{i, 2} + r_{i, 3} mod 2 となる r_{i, 1}, r_ {i, 2}, r_ {i, 3}を用いた(2,3)型ＲＳＳで分散された分散値が記憶されているものとする。
【０１５６】
第３の実施形態の動作では、
r_ij = r_ {i, n} || ... || r_ {i, 1} + r_ {j, n} || ... r_{j, 1} mod 2 ^n
を全加算器の秘密計算で実行し、
r_ij + r_ {k, n} || ... r_ {k, 1} mod 2 ^ n
を全加算器の秘密計算で実行する。インデックスi、j、kは互いに異なる値で1、2、3のいずれか値の組み合わせから選択される。
【０１５７】
以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット結合秘密計算装置４００が実行する。
【０１５８】
まず、部分分散情報抽出部３０２は、分解分散値保管装置２００の記憶する値から、r_{i, n}||...||r_{i, 1}に関する部分以外の値を０とみなした部分的に分解された分散情報を出力する（ステップＣ１）。
【０１５９】
次に、部分分散情報抽出部３０２は、分解分散値保管装置２００の記憶する値から、r_{j, n} || ... r _{j, 1}に関する部分以外の値を０とみなした部分的に分解された分散情報を抽出する（ステップＣ２）。
【０１６０】
次に、部分分散情報抽出部３０２は、分解分散値保管装置２００の記憶する値から、r_{k, n}|| ... || r_{k, 1}に関する部分以外の値を０とみなした部分的に分解された分散情報を抽出する（ステップＣ３）。
【０１６１】
次に、全加算器秘密計算部３０３は、r_{i, n} || ... || r_ {i, 1}の部分的に分解された分散情報と、r_ {j, n} || ...  ||r_ {j, 1}の部分的に分解された分散情報に関して、全加算器の秘密計算を実行し、その結果の列をr_ijの分散情報として出力する（ステップＣ４）。
【０１６２】
次に、全加算器秘密計算部３０３は、r_ijの分散情報と、r_ {k, n}||... ||r_{k, 1}の部分的に分解された分散情報に関して、全加算器の秘密計算を実行し、その結果を、分散値保管装置１００に記憶させる（ステップＣ５）。
【０１６３】
第１及び第２の実施形態でそれぞれ説明されたビット分解秘密計算システム１０および１０Ａは、例えば図７に示されるようなコンピュータシステム上で実現されてもよい。図７を参照すると、サーバシステムなどのコンピュータシステム５００は、プロセッサ(Central Processing Unit)５０２と、例えば半導体メモり（例えばＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＥＥＰＲＯＭ（Electrically Erasable Programmable Read-Only Memory））、及び／又はＨＤＤ（Hard Disk Drive）、ＣＤ（Compact Disc）、ＤＶＤ（Digital Versatile Disc）のうち少なくとも１つを含む記憶装置などのメモリ５０４と、表示装置５０６と、通信インタフェース５０８とを含む。通信インタフェース５０８（ネットワークインタフェースコントローラ（Network Interface Controller；ＮＩＣ）など）は、例えば、ＬＡＮ及び／又はＷＡＮを介して他のコンピュータシステム（主体）と通信するように構成されてもよい。図１又は図３のビット分解秘密計算装置の処理を実行するプログラムは、メモリ５０４に記憶されており、プロセッサ１１２が、メモリからプログラムを読み取り、プログラムを実行してビット分解秘密計算を実現する。メモリ５０４は、分散値保管装置１００と分解分散値保管装置２００とを含んでもよい。さらに、第３の実施形態のビット結合秘密計算システム２０も、図７に示されるようなコンピュータシステム上で実現されてもよい。
【０１６４】
第１及び第２の実施形態によれば、(2,3)型ＲＳＳによって分散された分散値を、各ビットが(2,3)型ＲＳＳで分散された値に変換することができる。
【０１６５】
第３の実施形態によれば、その逆の処理を効率的に実行することができる。
【０１６６】
上記処理によれば、値の秘密計算と、ビットの秘密計算とを組み合わせた複雑な処理を効率的に実行することが可能となる。
【０１６７】
なお、上記非特許文献１乃至３の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１６８】
１０、１０Ａ  ビット分解秘密計算システム
２０  ビット結合秘密計算システム
１００  分散値保管装置
１０１  第１の分散値保管部
１０２  第２の分散値保管部
２００  分解分散値保管装置
２０１  第１の分解分散値保管部
２０２  第２の分解分散値保管部
３００、３００Ａ  ビット分解秘密計算装置
３０１  加算分散部
３０２  部分分散情報抽出部
３０３  全加算器秘密計算部
４００  ビット結合秘密計算装置
５００  コンピュータシステム
５０２  プロセッサ
５０４  メモリ
５０６  表示装置
５０８  通信インタフェース
【図１】
0006844897.tif 000002
【図２】
0006844897.tif 000003
【図３】
0006844897.tif 000004
【図４】
0006844897.tif 000005
【図５】
0006844897.tif 000006
【図６】
0006844897.tif 000007
【図７】
0006844897.tif 000008