(57)【要約】  秘密分散ベースの秘密計算において、より少ない通信量でビット分解とビット結合の少なくとも一方を可能とする。2のnべき乗を法とした(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、2を法とした(2,3)型RSSで分散された値の列を保管する分解分散値保管装置と、ビット分解秘密計算装置と、を１組の装置とし、３組の装置で秘密計算システムを構成し、前記ビット分解秘密計算装置は、前記分散値保管装置が保管する(2,3)閾値型RSSの分散情報として、値wに関して、w= r1+r2+r3 mod 2^n を満たすr1、r2、r3を用い、前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)型RSSによって分散する加算分散部と、前記加算分散部による前記２つの値の和を分散した値と、前記加算分散部が用いた２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて各桁毎に計算する全加算器秘密計算部と、を備える。
2019087317.tif 000002
【特許請求の範囲】
【請求項１】
２のnべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w = r1 +r 2 + r3 mod 2^n （mod は剰余演算、nは２以上の整数、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散する加算分散部と、
前記加算分散部による前記２つの値の和を分散した値と、前記加算分散部が用いた前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部と、
を備える、ことを特徴とする秘密計算装置。
【請求項２】
前記ビット分解秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値のうち、前記１つを除いて０として、前記１つの値の分散情報を生成する部分分散情報抽出部を備え、
前記全加算器秘密計算部は、
前記加算分散部で生成され配布された前記２つの値の和の分散情報と、
前記部分分散情報抽出部で生成した前記１つの値の分散情報について、全加算器の秘密計算を用いた加算処理を実行し、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする請求項１に記載の秘密計算装置。
【請求項３】
２のnべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n  （mod は剰余演算、nは２以上の整数、＾はべき乗演算）
を満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^n  と、
r123 = r12 + r3 mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部を備える、ことを特徴とする秘密計算装置。
【請求項４】
前記ビット分解秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値の各々について、各１つ以外を０とする分散情報をそれぞれ生成する部分分散情報抽出部を備え、
前記全加算器秘密計算部は、
前記部分分散情報抽出部で生成した３つの分散情報の２つの値に関して、下位桁から順に全加算器の秘密計算を実行し、結果の列を前記２つの値の分散情報とし、
前記２つの値の和の分散情報と、前記１つの値の分散情報について、全加算器の秘密計算を用いた、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする請求項３に記載の秘密計算装置。
【請求項５】
2を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値の列を保管する分解分散値保管装置と、
２のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
ビット結合秘密計算装置と、
を備え、
前記ビット結合秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット：nは２以上の整数）のうち、下位桁からの桁数である第xビット（x=1,...,n)の値w_xに関して、
w_x= r_{1,x}+r_{2,x}+r_{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
r12 = r_{1,n}||…||r_{1,1} + r_{2,n}||…||r_{2,1} mod 2^n  
（mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,x}、r_{2,x}、r{3,x}は、r1、r2、r3のxビット目を表す）と 
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n  
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分散値保管装置に記憶する全加算器秘密計算部を備える、ことを特徴とする秘密計算装置。
【請求項６】
前記ビット結合秘密計算装置は、
前記分解分散値保管装置の記憶する前記値w_xから、
前記r_{1,n}||…||r_{1,1}に関する部分以外を０とみなした分散情報、
前記r_{2,n}||…||r_{2,1}に関する部分以外を０とみなした分散情報、及び、
前記r_{3,n}||…||r_{3,1}に関する部分以外を０とみなした分散情報、
を、それぞれ、
前記r_{1,n}||…||r_{1,1}、
前記r_{2,n}||…||r_{2,1}、及び、
前記r_{3,n}||…||r_{3,1}の分散情報として出力する部分分散情報抽出部を備える、ことを特徴とする請求項５に記載の秘密計算装置。
【請求項７】
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w = r_1 + r_2 + r_3 mod 2^n （mod は剰余演算、nは２以上の整数、＾はべき乗演算）
を満たすr1、r2、r3を用い、
i=1,2,3について、r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてｘ桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する桁上がり秘密計算部と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する繰り込み秘密計算部と、
を備える、ことを特徴とする秘密計算装置。
【請求項８】
前記桁上がり秘密計算部は、
c_{x+1}を [(r_{1,x} XOR r_{2,x} XOR 1) AND (r_{1,x} XOR r_{3,x})] XOR r_{3,x} 
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR z_{x})] XOR z_{x}
の秘密計算によって計算する、ことを特徴とする請求項７に記載の秘密計算装置。
【請求項９】
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
２のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
ビット結合秘密計算装置と、
を備え、
前記ビット結合秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として、前記分散値保管装置に記憶する桁上がり秘密計算部を備えることを特徴とする秘密計算装置。
【請求項１０】
前記桁上がり秘密計算部は、
c_{x+1}を [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{3,x} 
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}
の秘密計算によって計算する、ことを特徴とする請求項９に記載の秘密計算装置。
【請求項１１】
前記ビット結合秘密計算装置は、
前記分解分散値保管装置から読み出された(2,3)閾値型RSSのrの分散情報のx桁目r_xと、前記桁上がり秘密計算部から入力された前記x桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、これら３値の排他的論理和を計算する秘密計算を実行し、計算結果r_x'をx桁目の分散情報として前記分散値保管装置に記憶する繰り込み秘密計算部と、
前記r_x'の分散情報から、i=1,2,3についてr_{i,x}'に関する部分以外を0とみなした分散情報を出力する部分分散情報抽出部と、
を備え、
前記桁上がり秘密計算部は、前記部分分散情報抽出部によって生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、5組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、前記繰り込み秘密計算部へ供給する、ことを特徴とする請求項９又は１０に記載の秘密計算装置。
【請求項１２】
請求項１乃至１１のいずれか１項に記載の秘密計算装置を３組備えた秘密計算システム。
【請求項１３】
２のべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えた秘密計算装置が３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散し、
前記２つの値の前記和を分散した値と、前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し計算結果を、ビット分解分散値として、前記分解分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【請求項１４】
２のべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えた秘密計算装置が３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w= r_1+r_2+r_3 mod 2^nを満たすr1、r2、r3を用い、
i=1,2,3について、r_{i,x}をr_xのjビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてx桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算し、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【請求項１５】
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、を備えた秘密計算装置が３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（ｎビット）として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として前記分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【請求項１６】
２のべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
を備えたコンピュータ装置に、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散する処理と、
前記２つの値の前記和を分散した値と、前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し計算結果を、ビット分解分散値として、前記分解分散値保管装置に記憶する処理を実行させるプログラム。
【請求項１７】
２のべき乗を法とする(2,3)閾値型RSS(Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えたコンピュータ装置に、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w= r_1+r_2+r_3 mod 2^n
を満たすr1、r2、r3を用い、
i=1,2,3について、r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてｘ桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する処理と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する処理と、
を実行させるプログラム。
【請求項１８】
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
２のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、を備えたコンピュータ装置に、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（ｎビット）として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、
v_{x}の分散情報をx桁目の分散情報として、前記分散値保管装置に記憶する処理を、実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密計算装置、システム、方法、プログラムに関し、特に、ビット分解、ビット結合に好適な秘密計算装置、方法、プログラムに関する。
【背景技術】
【０００２】
秘密計算法は、関連する主体に対して計算過程と結果を秘匿することができる技術である。データをクラウドのような第３者が管理する複数サーバに分散して保管することで、データに対してあらゆる演算を実行することができる。第３者には、データ、計算過程、計算結果を知られることがないため、個人情報のような機微な情報に対する分析処理をアウトソースするために用いることができる。【０００３】
(2,3)閾値のアクセス構造を有する複製秘密分散（Replicated Secret Sharing）((2,3)閾値型RSSという)を用いた秘密計算について説明する。(2,3)閾値型RSS（(2,3)型RSSとも略記される）は、(2,3)秘密分散の実現方法の一つである。(2,3)秘密分散とは、入力された値（秘密情報）から３つの分散情報を生成し、分散情報を閾値（＝２）以上の個数を集めることによって元の値（秘密情報）を復元する。２つ以上の分散情報からは元の値を復元できるが、１つ以下の分散情報からは元の値はわからない。【０００４】
(2,3)閾値型RSSは、0からp-1以下の値wを分散する際に、
w = r1 + r2 + r3 mod p         ・・・(1)
となるような0からp-1以下の３つの値の組(r1, r2, r3)を生成し、３つの分散情報として、(r1, r2, r3)から異なる２つの値を互いに異なる組み合わせとなるように選んだ３組を用いることで、(2,3)秘密分散を実現する。なお、このpを法と呼ぶ。【０００５】
秘密分散によって分散された値に関する計算を復元すること無く実行する方法は秘密計算と呼ばれている。(2, 3)複製秘密分散によって分散された値に対する秘密計算法について説明する。【０００６】
まず、値の分散方法について説明し、次に加算、減算、乗算について説明する。ここでは、ある値の分散値が３台の装置に対して分散され保管され、その後、分散値に対して秘密計算を行うという手順について説明する。以下では、３台の装置を装置１、装置２、装置３と呼んで区別する。【０００７】
＜値の分散方法＞
pを2以上の整数として、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’に関して実行される加算処理について説明する。なお、【００１１】
w = r1 + r2 + r3 mod p
w’ = r1’ + r2’ + r3’ mod p
・・・(2)
とする。【００１２】
装置１は、
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)        ・・・(3)
によって、(s1’’, t1’’)を計算し、これを加算値w + w’の分散値として保管する。【００１７】
装置２は、
(s2’’, t2’’) = (r2’’ = s2 + s2’ mod p, r3’’ = t2 + t2’ mod p)      ・・・(4)
によって、(s2’’, t2’’)を計算し、これを加算値w + w’の分散値として保管する。【００１８】
装置３は、
(s3’’, t3’’) = (r3’’ = s3 + s3’ mod p, r1’’ = t3 + t3’ mod p)      ・・・(5)
によって、(s3’’, t3’’)を計算し、これを加算値w + w’の分散値として保管する。【００１９】
それぞれの計算結果は、w + w’を、
w + w’ = r1’’ + r2’’ + r3’’mod p        ・・・(6)
となるr1’’,r2’’,r3’’を用いて分散した値となっている。これは、
r1’’ + r2’’ + r3’’
= (r1 + r2 + r3) + (r1’ + r2’ + r3’) = w + w’ mod p  ・・・(7)
から確認できる。【００２０】
＜減算処理＞
先に示した方法によって、装置１、装置２、装置３に分散して保管されている値wと値w’に関して実行される加算処理について説明する。なお、
w = r1 + r2 + r3 mod p
w’ = r1’ + r2’ + r3’ mod p
・・・(8)
とする。【００２１】
装置１は、
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)       ・・・(9)
によって、(s1’’, t1’’)を計算し、これをw-w’の分散値として保管する。【００２６】
装置２は、
(s2’’, t2’’) = (r2’’ = s2-s2’ mod p, r3’’ = t2-t2’ mod p)   ・・・(10)
によって、(s2’’, t2’’)を計算し、これをw-w’の分散値として保管する。【００２７】
装置３は、
(s3’’, t3’’) = (r3’’ = s3-s3’ mod p, r1’’ = t3-t3’ mod p)      ・・・(11)
によって、(s3’’, t3’’)を計算し、これをw-w’の分散値として保管する。【００２８】
それぞれの計算結果は、
w-w’を
w-w’ = r1’’ + r2’’ + r3’’mod p          ・・・(12)
となるr1’’、r2’’、r3’’を用いて分散した値となっている。【００２９】
これは、
r1’’ + r2’’ + r3’’
= (r1 + r2 + r3) -(r1’ + r2’ + r3’) = w-w’ mod  p   ・・・(13)
から確認することができる。【００３０】
＜乗算処理＞
先に示した方法によって、装置１、装置２、装置３に分散されて保管されているwと値w’に関して実行される乗算処理について説明する。【００３１】
まず、各装置がどのような値を保管しているかを示す。【００３２】
r1、r2、r3を、
r1 + r2 + r3 = w mod p       ・・・(14)
を満たすランダムに選ばれた値とし、
r1’、r2’、r3’を、
r1’ + r2’ + r3’ = w’ mod 2^n        ・・・(15)
を満たすランダムに選ばれた値とする。【００３３】
装置１は、
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       ・・・(16)
を満たすランダムに選ばれた値として、
装置１は、r1’’を保管し、
装置２は、r2’’を保管し、
装置３は、r3’’を保管しているものとする。このような性質を満たすr1’’、r2’’、r3’’は、乗算を実行するたびに使い捨てで必要となる。このような３値を、３装置が効率的に生成する方法については後述する。【００３８】
装置１は、
u2 = s1 * s1’ + s1 * t1’ + t1 * s1’ + r1’’ mod p     ・・・(17)
を計算し、u2を装置２に送付する。【００３９】
装置２は、
u3 = s2 * s2’ + s2 * t2’ + t2 * s2’ + r2’’ mod p     ・・・(18)
を計算し、u3を装置３に送付する。【００４０】
装置３は、
u1 = s3 * s3’ + s3 * t3’ + t3 * s3’ + r3’’ mod p     ・・・(19)
を計算し、u1を装置１に送付する。【００４１】
装置１は、(u1, u2)を、w * w’の分散値として保管する。【００４２】
装置２は、(u2, u3)を、w * w’の分散値として保管する。【００４３】
装置３は、(u3, u1)を、w * w’の分散値として保管する。【００４４】
まず、
u1 + u2 + u3
= r1 * r1’ + r1 * r2’ + r2 * r1’ + r2 * r2’ + r2 * r3’ + r3 * r2’ + r3 * r3’ + r3 * r1’ + r1 * r3’ + r1’’ + r2’’ + r3’’
= (r1 + r2 + r3) * (r1’ + r2’ + r3’) + r1’’ + r2’’ + r3’’
= w * w’ mod  p        ・・・(20)
となっていることが確認できる.【００４５】
装置１と装置２の保管する値から、w * w’ mod pが同じ計算方法で計算できる。【００４６】
他の装置の組み合わせについても同様である。このような方法によれば、(2,3)閾値型RSSで分散されているw、w’に関する乗算を、各値を復元することなく実行し、w * w’を(2,3)閾値型RSSで分散した値を共有することができる。【００４７】
＜乱数の生成＞
次に、
r1 + r2 + r3 = 0 mod 2^n       ・・・(21)
のように、３つ足すと0となる値を、装置１、装置２、装置３が通信することなく、また、各装置が所有する値を他の装置に知られることのない方法で、大量に生成する方法について説明する。【００４８】
ここでは、
ｒ[i,1] + ｒ[i,2] + ｒ[i,3] = 0 mod 2^n
なるr[i,1]、r[i,2]、r[i,3]を、多くのi = 1,…,Nに関して生成する方法を説明する。【００４９】
PRG（pseudo random generator）を、鍵とインデックスを入力として、nビットの数値列を出力する擬似乱数生成器とする。【００５０】
インデックスは、カウンタなどでよい。この方法は、非特許文献３などに記載がある。【００５１】
まず、装置のセットアップ処理として、PRGの鍵L1、L2、L3を生成する。【００５２】
装置１に、L1とL3を記憶させ、
装置２に、L2とL1を記憶させ、
装置３に、L3とL2を記憶させているものとする。【００５３】
各装置１、２、３は、カウンタなどで同期されたインデックスidxを共有しているものとする。【００５４】
装置１は、鍵L1とインデックスidxをPRGに入力し、その出力であるnビットの数値をr’[1]を生成する。【００５５】
また、装置１は、鍵L3とインデックスidxをPRGに入力し、その出力であるnビットの数値r’[3]を生成する。【００５６】
そして、装置１は、
r[1] = r’[1] - r’[3] mod p       ・・・(22)
とする。【００５７】
装置２は、鍵L2とインデックスidxをPRGに入力し、その出力であるnビットの数値r’[2]を生成する。【００５８】
また、装置２は、鍵L1とインデックスidxをPRGに入力し、その出力であるnビットの数値r’[1]を生成する。【００５９】
そして、装置２は、
r[2] = r’[2] - r’[1] mod p       ・・・(23)
とする。【００６０】
装置３は、鍵L3とインデックスidxをPRGに入力し、その出力であるnビットの数値r’[3]を生成する。【００６１】
また、装置３は、鍵L2とインデックスidxをPRGに入力し、その出力であるnビットの数値r’[2]を生成する。【００６２】
そして、装置３は、
r[3] = r ’[3] - r’[2] mod p       ・・・(24)
とする。【００６３】
r[1] + r[2] + r[3]= r’[1] - r’[3] + r’[2] - r’[1] + r[3] - r[2] = 0 mod p        ・・・(25)
が成り立ち、N組全てが条件を満たす。【００６４】
装置１が生成する値(式(22))
r[1] = r’[1] - r’[3] mod p
に着目すると、装置３はr’[1]を得られず、装置２はr’[3]を得られない。これより、装置１、装置２は、r[1]を計算できないことがわかる。これは、r[2]やr[3]についても同様である。【００６５】
セットアップ処理が済んでいれば、以上の処理は、計算が行われる前などにも実行可能である。【００６６】
このような(2,3)閾値型RSSを用いた秘密計算において、p＝2とすると、乗算は、AND処理とみなすことができ、加算・減算は、排他的論理和(exclusive OR：XOR)処理とみなすことができる。これによって、p = 2とした場合、論理演算に適した秘密計算法となる。【００６７】
また、装置１、装置２、装置３の分散情報を、すべて、(1,1)、(1,1)、(1,1)とすると、これは、r1 = 1, r2 = 1, r3 = 1として、1の分散情報になっている。これは、論理積（AND）、排他的論理和（XOR）、定数１によって完全系となり、任意の演算が実行可能となる。以上の方法は、非特許文献１などが参照される。このような方法には種々のバリエーションを考えることができる。【００６８】
例えば、
r1 + r2 + r3 = w mod p       ・・・(26)
に関して、
(r1 - r2 mod p, r2),
(r2 - r3 mod p, r3),
(r3 - r1 mod p, r1)
・・・(27)
を３つの装置のそれぞれの分散情報としてもよい。【００６９】
３つの装置が、r1、r2、r3のうち、異なる二つの組に相当する情報を保有していれば、(2,3)閾値型RSSと呼ぶことにする。つまり、任意の演算は、法（modulo） p = 2とした(2,3)閾値型RSSを用いることで、演算処理が可能である。【００７０】
しかし、すべての処理を、論理演算で実行することは、非効率的である。【００７１】
そこで、乗算と加減算で構成できるものは、pを大きく設定した(2,3)閾値型RSSを用いた秘密計算で実行するほうがよい。【００７２】
さらに、数値演算と論理演算の組み合わせたい場合もある。【００７３】
例として、それぞれが2^4より小さい値であるa、b、cを入力として、
a  * b mod 2^4 < c        ・・・(28)
を処理する場合を考える。乗算a*bを数値演算として処理し、比較演算（<）を論理演算として実行したい。【００７４】
まず、数値演算として、a*bを計算したいが、これをcと比較する処理を数値演算として表現することは難しい。【００７５】
このような問題を解決するため、非特許文献２に記載のビット分解と呼ばれる処理が知られている。ビット分解は、数値計算向けの分散情報を論理演算向けの分散情報に変換するための処理である。ビット分解は、数値を格納した１つ分散値（share）（ｌビット数値）を、ビットを格納したｌ個の分散値に変換する。【００７６】
例えば、法としてp = 8を用いた(2,3)閾値型RSSによって、値w = 5を用いて、分散し、
w = r1 + r2 + r 3 mod p        ・・・(29)
から,
r1 = 1, r2 = 2, r3 = 2として、
装置１が、(r1, r2) = (1, 2)を分散値として記憶し、
装置２が、(r2, r3) = (2, 2)を分散値として記憶し、
装置３が、(r3, r1) = (2, 1)を分散値として記憶しているものとする。【００７７】
ビット分解を用いれば、これらの情報から、w=5の２進表記（ = b0101、bは２進表記であることを示す）である1と0と1の各ビットに対する分散情報を得ることができる。【００７８】
具体的には、ビット分解が実行された後、
装置１は、
１ビット目に関して、(1, 1)、
２ビット目に関して、(0, 1)、
３ビット目に関して、(1, 0)、
４ビット目に関して、(0, 0)
を所有する。１ビット目はLSB（Least Significant Bit）である。【００７９】
装置２は、
１ビット目に関して、(1, 1)、
２ビット目に関して、(1, 1)、
３ビット目に関して、(0, 0)、
４ビット目に関して、(0, 0)
を所有する。【００８０】
装置３は、
１ビット目に関して、(1, 1)、
２ビット目に関して、(1, 0)、
３ビット目に関して、(0, 0)、
４ビット目に関して、(0, 0)
を所有する。【００８１】
ビット分解に関して非特許文献２に記載の方法の概要を以下に示す。この方法は以下のような手順でビット分解を実行する。【００８２】
ビット分解を実行したい数rは、
r = r1 + r2 + r3 mod p        ・・・(30)
を満たすr1、r2、r3を用いて、装置１、装置２、装置３に分散されているものとする。なお、非特許文献２では、p=2^n-1によって表されるメルセンヌ素数を用いる。メルセンヌ素数の性質は、手順２において、sを効率的に計算することに作用している。【００８３】
＜手順１＞
r12 = r1 + r2 mod p、および、
r3 
・・・(31)
を分散する。【００８４】
＜手順２＞
r12 + r3 が pよりも大であるか否かを判定し、
r12 + r3 が pよりも大きい場合（r12 + r3 > p）には、
s = 1                      ・・・(32)
とし、
それ以外の場合は（r12 + r3 ≦ p）、
s = 0                    ・・・(33)
となるような秘密計算を実行する。【００８５】
＜手順３＞
r12 + r3 + s mod 2^n          ・・・(34)
の計算を下位桁からビット毎に全加算器の秘密計算を実行する。【００８６】
非特許文献２の方法は、(2,3)複製秘密分散で、pがnビットの数であるとして、10n + 4ビットの総通信量によってビット分解を実行できると記載されている。
【先行技術文献】
【非特許文献】
【００８７】
【非特許文献１】軽量検証可能3パーティ秘匿関数計算の効率化及びこれを用いたセキュアなデータベース処理、五十嵐大、千田浩司、濱田浩気、高橋克己、SCIS2011
【非特許文献２】少パーティの秘密分散ベース秘密計算のためのO(l)ビット通信ビット分解およびO(|p|’)ビット通信Modulus変換法、五十嵐大、濱田浩気、菊池亮、千田浩司、CSS２０１３
【非特許文献３】High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority, Toshinori Araki, Jun Furukawa , Yehuda Lindell, Ariel Nof, Kazuma Ohara
【発明の開示】
【発明が解決しようとする課題】
【００８８】
上記非特許文献１乃至３の開示内容は、本明細書の一部を構成するものとする。 以下の分析は、本発明者らによってなされたものである。【００８９】
上記非特許文献２によれば、例えばpをnビットの数として、10n + 4ビットの通信量でビット分解を行うことができる。【００９０】
しかし、ビット分解が、例えば上記非特許文献２の通信量よりも少ない通信量で効率的に実行されることが望ましい。【００９１】
したがって、本発明の目的は、秘密分散ベースの秘密計算において、より少ない通信量でビット分解、ビット結合の少なくとも一方を可能にする装置、方法、プログラムを提供することにある。
【課題を解決するための手段】
【００９２】
本発明の一態様（第１態様）によれば、２のべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、ビット分解秘密計算装置と、を備えた秘密計算装置（ビット分解秘密計算装置）が提供される。前記ビット分解秘密計算装置は、前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散する加算分散部と、
前記加算分散部による前記２つの値の前記和を分散した値と、前記加算分散部が用いた前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部と、を備える。【００９３】
本発明の別の態様（第２態様）によれば、前記ビット分解秘密計算装置は、前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関してw= r1+r2+r3 mod 2^nを満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^n  （mod は剰余演算、＾はべき乗演算）と、
r123 = r12 + r3 mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部を備えた構成としてもよい。【００９４】
本発明の別の態様（第３態様）によれば、前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w = r_1+r_2+r_3 mod 2^n （mod は剰余演算、nは２以上の整数、＾はべき乗演算）
を満たすr1、r2、r3を用い、
i=1,2,3について、r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてx桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する桁上がり秘密計算部と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する繰り込み秘密計算部を備える。【００９５】
本発明の別の態様（第４態様）によれば、秘密計算装置は、2を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値の列を保管する分解分散値保管装置と、2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、ビット結合秘密計算装置と、を備える。前記ビット結合秘密計算装置は、前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット：nは２以上の整数）のうち、下位桁からの桁数である第xビット（x=1,...,n)の値w_xに関して、w_x= r_{1,x}+r_{2,x}+r_{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
r12 =r_{1,n}||…||r_{1,1}+ r_{2,n}||…||r_{2,1} mod 2^n  （mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,x}、r_{2,x}、r{3,x}は、r1、r2、r3のxビットを表す）と
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n  （mod は剰余演算、＾はべき乗演算）の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分散値保管装置に記憶する全加算器秘密計算部を備える。【００９６】
本発明の別の態様（第５態様）によれば、前記ビット結合秘密計算装置は、前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として前記分散値保管装置に記憶する桁上がり秘密計算部と、を備える。【００９７】
本発明のさらに別の態様（第６−１０態様）によれば、上記第１乃至第５の態様の装置による処理ステップが提供される。【００９８】
本発明のさらに別の態様（第１１−１５態様）によれば、上記第１乃至第５の態様の装置を３組備えた秘密計算システムが提供される。【００９９】
本発明のさらに別の態様（第１６−２０態様）によれば、上記第１乃至第５の態様の装置の処理をコンピュータ装置に実行させるプログラムが提供される。【０１００】
本発明のさらに別の態様（第２１−２５態様）によれば、上記第１乃至第５の態様の装置の処理をコンピュータ装置に実行させるプログラムを記録したコンピュータ読み出し可能な非一時的記録媒体（non-transitory computer-readable recordimg medium）（例えば、半導体メモリ、プログラム消去可能な読み出し専用メモリ、ハードディスクドライブ、ソリッドステートドライブ、コンパクトディスク、DVD(Digital Versatile Disc)等）が提供される。
【発明の効果】
【０１０１】
本発明によれば、秘密分散ベースの秘密計算において、より少ない通信量でビット分解とビット結合の少なくとも一方を可能としている。
【図面の簡単な説明】
【０１０２】
【図１】本発明の例示的な実施形態１の構成を例示する図である。
【図２】本発明の例示的な実施形態１の動作を例示する流れ図である。
【図３】本発明の例示的な実施形態２の構成を例示する図である。
【図４】本発明の例示的な実施形態２の動作を例示する流れ図である。
【図５】本発明の例示的な実施形態３の構成を例示する図である。
【図６】本発明の例示的な実施形態３の動作を例示する流れ図である。
【図７】本発明の例示的な実施形態４の構成を例示する図である。
【図８】本発明の例示的な実施形態４の動作を例示する流れ図である。
【図９】本発明の例示的な実施形態５の構成を例示する図である。
【図１０】本発明の例示的な実施形態５の動作を例示する流れ図である。
【図１１】本発明の例示的な実施形態６を模式的に示す図である。
【発明を実施するための形態】
【０１０３】
本発明の一形態によれば、２のべき乗を法とした(2,3)閾値型複製秘密分散(Replicated Secret Sharing：RSS)で分散された値を保管する分散値保管装置（図１の１００）と、2を法とした(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置（図１の２００）と、ビット分解秘密計算装置（図１の３００）とを備えた装置を３セット有する。
【０１０４】
各装置におけるビット分解秘密計算装置（図１の３００）は、分散値保管装置（図１の100）が保管する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n
を満たすr1、r2、r3を用い、これら３つの分散情報のうち２つの値について、法2^n（＾はべき乗演算）上の和をとり、前記和を(2,3)閾値型RSSによって分散し、前記２つの値の和（r_i +r_j mod 2^n）の分散値と、加算分散部（図１の３０３）が用いた２つの値以外の残りの１つの値（r_k、k≠i, j）との和を全加算器の秘密計算を用いて、各桁毎に計算する構成としてもよい。
【０１０５】
各装置におけるビット分解秘密計算装置（図３の３００Ａ）は、前記分散値保管装置（図３の１００）が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n
を満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^nと、
r123 = r12 + r3 mod 2^nの秘密計算を全加算器の秘密計算によって各桁毎に計算し、
計算結果を前記分解分散値保管装置に記憶させる全加算器秘密計算部（図３の３０３）を備えた構成としてもよい。前記ビット分解秘密計算装置は、(2,3)閾値型RSSの前記分散情報を構成する３つの値の各々について、各１つ以外を０とする分散情報をそれぞれ生成する部分分散情報抽出部（図３の３０２）を備えた構成としてもよい。全加算器秘密計算部（図３の３０３）は、前記部分分散情報抽出部（図３の３０２）で生成した３つの分散情報の２つの値に関して、下位桁から順に全加算器の秘密計算を実行し、結果の列を前記２つの値の分散情報とし、前記２つの値の和の分散情報と、前記１つの値の分散情報について、全加算器の秘密計算を用いた、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置（図３の２００）に記憶する構成としてもよい。
【０１０６】
本発明の別の形態によれば、前記ビット分解秘密計算装置（図７の３００Ｂ）は、前記分散値保管装置（図７の１００）が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w = r_1+r_2+r_3 mod 2^n （mod は剰余演算、nは２以上の整数、＾はべき乗演算）
を満たすr1、r2、r3を用い、
i=1,2,3について、r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてx桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する桁上がり秘密計算部（図７の３０４）と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、分解分散値保管装置（図７の２００）に記憶する繰り込み秘密計算部（図７の３０５）を備えた構成としてもよい。
【０１０７】
本発明のさらに別の形態によれば、前記分解分散値保管装置（図５の２００）が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット）のうち、第xビット（x=1,...,n)の値w_iに関して、
w_x= r_{1,x} + r_{2,x} + r_{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}
を用い、
r12 =r_{1,n}||…||r_{1,1}+ r_{2,n}||…||r_{2,1} mod 2^n
（mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,i}、r_{2,i}、r{3,i}は、r1、r2、r3のiビットを表す）と、
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を、前記分散値保管装置（図５の１００）に記憶させる全加算器秘密計算部（図５の４０３）を備えたビット結合秘密計算装置（図５の４００）を備えた構成としてもよい。
【０１０８】
本発明の別の形態によれば、ビット結合秘密計算装置(図９の４００Ａ）は、前記分解分散値保管装置（図９の２００）が記憶するn個の(2,3)閾値型RSSの分散情報の列として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として、前記分散値保管装置（図９の１００）に記憶する桁上がり秘密計算部(図９の４０４)と、を備えた構成としてもよい。
前記桁上がり秘密計算部(図９の４０４)は、c_{x+1}を [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}の秘密計算によって計算する構成としてもよい。
【０１０９】
前記ビット結合秘密計算装置(図９の４００Ａ）は、前記分解分散値保管装置（図９の２００）から読み出された(2,3)閾値型RSSのrの分散情報のx桁目r_xと、前記桁上がり秘密計算部から入力された前記x桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、これら３値の排他的論理和を計算する秘密計算を実行し、計算結果r_x'をx桁目の分散情報として前記分散値保管装置（図９の１００）に記憶する繰り込み秘密計算部（図９の４０５）と、前記r_x'の分散情報から、i=1,2,3についてr_{i,x}'に関する部分以外を0とみなした分散情報を出力する部分分散情報抽出部（図９の４０２）と、を備え、前記桁上がり秘密計算部(図９の４０４)は、前記部分分散情報抽出部（図９の４０２）によって生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、前記繰り込み秘密計算部（図９の４０５）へ供給する構成としてもよい。
【０１１０】
以下には、本発明の原理を説明しておく。
【０１１１】
非特許文献２の方法では、上記手順１において、r3を分散している。この処理を、通信無しで実行する方法について説明する。ここで、(2,3)閾値型複製秘密分散により、値rが
r = r1 + r2 + r3 mod p         ・・・(35)
を満たすr1、ｒ2、r3で装置１、装置２、装置３に分散されていることを想定する。
【０１１２】
このとき、ri (i = 1,2.3)に関連する分散情報（share）を生成したい場合、
ｒ = r1 + r2 + r3 mod pの分散情報（装置１-３に分散されている分散情報）のr1に関する箇所以外をすべて０にした値が、r1の分散情報となる。
【０１１３】
値rの分散情報として、
装置１が、(r2, r3)を保管し、
装置２が、(r3, r1)を保管し、
装置３が、(r1, r2)を保管しているとする。
【０１１４】
これらの分散情報のうち、例えばr1に関する箇所以外をゼロとすると、
装置１は、(0, 0)を保有し、
装置２は、(0, r1)を保有し、
装置３は、(r1, 0)を保有する。これらは、r1に関する分散情報とすることができる。
【０１１５】
装置２と装置３がr1自体を保管していることは秘匿性に何ら影響を与えない。これらは、元々、把握可能な値であるためである。r2、r3についても同様に、装置１、装置２、装置３は通信することなく、その分散情報を得ることができる。
【０１１６】
非特許文献２の方法の上記手順３では、
r12 + r3 + s mod 2^n         ・・・(36)
を計算している。
【０１１７】
sを加算している理由は、
r12 + r3 mod p            ・・・(37)
をmod 2^nにおける計算で求めるためである。
【０１１８】
s = 1の場合、r12 + r3 = r’ + p
とすると、
r12 + r3 + s mod 2^n
= r’ + p + 1 mod 2^n
= r’ + 2^n mod 2^n
= r' mod 2^n          ・・・(38)
となる。（∵p＝2^n-1, 2^n mod 2^n=0）
【０１１９】
s = 0の場合、r12 + r3 = r’とすると、
r12 + r3 mod 2^n
= r’ mod 2^n          ・・・(39)
となる。
【０１２０】
以上のように、sの値によらず、手順３の計算結果は、
r12 + r3 mod 2^n         ・・・(40)
となる。
【０１２１】
pとして、2^nを用いれば、r12 + r3がp=2^nを越えた場合の処理（上記手順２）が不要である。
【０１２２】
以上の変更を加えた本発明の一形態のビット分解法について以下に説明する。
【０１２３】
＜手順１＞
r12 = r1 + r2 mod 2^n          ・・・(41)
を(2,3)閾値型RSSで分散する。
【０１２４】
＜手順２＞
r3の分散情報（シェア）を装置１、２、３で生成する（通信無し）。
【０１２５】
＜手順３＞
r12 + r3 mod 2^n              ・・・(42)
の計算を下位桁からビット毎に全加算器の秘密計算を実行する。
【０１２６】
以上の処理の通信量を評価する。
【０１２７】
w = r1 + r2 + r3 mod 2^n           ・・・(43)
を満たすランダムに選ばれr1、r2、r3を生成して、以下のように保管されているものとする。
【０１２８】
装置１に、wの分散値として、(r1, r2)を保管し、
装置２に、wの分散値として (r2, r3)を保管し、
装置３に、wの分散値として（r3, r1)を保管する。
【０１２９】
＜手順１の通信量＞：
r1 + r2            ・・・(44)
の秘密分散は、装置１によって実行される。
【０１３０】
まず、装置１は、
r12 = r1 + r2 mod 2^n            ・・・(45)
を計算し、
r12A + r12B = r12 mod 2^n       ・・・(46)
となるr12Aとr12Bをランダムに選択する。
【０１３１】
次に、装置１は、
r12Aを装置２に送信し（nビット）、
r12Bを装置３に送信する（nビット）。
【０１３２】
この結果、
装置１は、値r12の分散値として、(r12B, r12A)を得る。
【０１３３】
装置２は、値r12の分散値として、(r12A, 0)を得る。
【０１３４】
装置３は、値r12の分散値として、(0, r12B)を得る。
【０１３５】
この処理では、2nビットの通信を行っている。
【０１３６】
＜手順２の通信量＞：
先に示したように、r3の分散情報は、各装置１、２、３で通信を行わずに生成できる。
【０１３７】
＜手順３の通信量＞
各装置における全加算器の秘密計算は、各桁のキャリーを計算するために１回のAND(論理積)演算が必要となる。したがって、n桁の加算の場合、(n-1)ビットのキャリーの秘密計算のために、装置１、２、３間において、3*(n-1)ビットの通信が必要となる。
【０１３８】
以上の結果として、総通信量
2n + 3 * (n-1) = 5n - 3 (ビット)           ・・・(47)
でビット分解が計算できることが分かる。
【０１３９】
ここで、加算器処理によって計算結果をビット単位に分解する様子を示す例を挙げる。
【０１４０】
p = 8、ｗ = 6 (b110) (bは２進表記)、r1 = 3(b011)、r2 = 2(b010)、 r3 = 1(b001) のビット分解の計算過程を示す（w(=6) = r1 + r2 + r3 mod p (=2^3=8) = 3 + 2 + 1 mod 8）。
【０１４１】
なお、以下では、
riの下位（LSB(Least Significant Bit)）からj桁目をri_j、
r12 = r1 + r2 mod  8           ・・・(48)
の下位からj桁目を、
r12_j
と表記する。また、
r123 = r1 + r2 + r3 mod 8          ・・・(49)
の下位からj桁目を、
r123_j
と表記する。
【０１４２】
次に、
r12 + r3 mod 8 = (3 + 2) + 1 mod 8 =  (5 + 1) mod 8 = 6      ・・・(50)
を下位桁から順に計算する手順を示す。
【０１４３】
＜1桁目(LSB)の計算＞：
r123_1 = r12_1 XOR r3_1 = 1 XOR 0 XOR 1 = 0     ・・・(51)
(r12_1は、r1_1=1とr2_1=0のXOR(排他的論理和)で与えられ、r3_1は０）。
【０１４４】
１桁目の計算に関する桁上がりc1は、
c1 = r12_1 AND  r3_1 = 1 AND 1 = 1      ・・・(52)
(１桁目では下位桁からの桁上がり（キャリー）がない)
【０１４５】
＜2桁目の計算＞：
r123_2 = r12_2 XOR r3_2 XOR c1 = 0 XOR 0 XOR 1 = 1     ・・・(53)
【０１４６】
2桁目の計算に関するキャリー c2は以下で与えられる。
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     ・・・(54)
【０１４７】
＜3桁目の計算＞：
r123_3 = r12_3 XOR r2_3 XOR c2 = 1 XOR 0 XOR 0 = 1      ・・・(55)
【０１４８】
以上のように、各桁は、ANDの処理1回で、
r123_1 = 0,
r123_2 = 1,
r123_3 = 1    
・・・(56)
のように、1桁から３桁までの各桁をビット毎に分解した値が計算できている。
【０１４９】
この処理を(2, 3))閾値型RSSに基づく秘密計算で実行すればよい。秘密計算の結果が、ビット毎に分解した値の分散値となる。
【０１５０】
上記形態では、(2,3)閾値型RSSとして、値rを
r = r1 + r2 + r3 mod p      ・・・(57)
としたとき、分散情報として、例えば、
装置１が、(r1, r2)を保管し、
装置２が、(r2, r3)を保管し、
装置３が、(r3, r1)を保管する場合の例を説明している。
【０１５１】
しかし、本実施形態は、r1、r2、r3の３つの値のうち異なる２つに相当する情報を保有する(2,3)閾値型RSSであれば適用可能である。例えば、
装置１は、分散情報として、(r2, r3)でなく、
(r2 + r3, r3)
を保有していてもよいし、
(r2 - r3, r2 + r3)
などを保有する方法であってよい。秘密計算として加算、乗算、定数を備えていれば実施可能である。
【０１５２】
本実施形態においては、
r12 = r1 + r2 mod 2^n     ・・・(58)
の計算を秘密計算によって実行してから、
r12 + r3 mod 2^n                      ・・・(59)
に関する演算を全加算器の秘密計算によって計算してもよい。
【０１５３】
この方法を用いる場合、r12を計算する通信量が3nビットとなり、装置１が分散する場合に比べて効率は悪いが、全体の通信量は、6n-3ビットである。
【０１５４】
r1 + r2の計算を全加算器の秘密計算によって計算する場合、最上位の桁から発生するキャリーに関する計算を実行する必要が無いため、3n-3ビットの通信量で、r12に関する計算を実行できる。この場合、6n-6ビットの通信量でビット分解を実行することができる。これらの変形例も非特許文献２の方式に比べて効率的である。
【０１５５】
また、両方の処理を全加算器の秘密計算を用いて実行することで、非特許文献３に記載されているような(2,3)閾値型RSSを用いた秘密計算法に不正耐性を付与する仕組みを用いることもできる。
【０１５６】
さらに、ビット分解された分散情報から結合された値に対する分散情報を作るようにしてもよい。この場合、下位の桁から上位の桁への桁上がりを、桁上がり計算の秘密計算によって実行していき、すべての桁の計算を終えた段階で、各桁の秘密計算結果を結合すればよい。この手法では、r1 + r2 mod 2^n相当の情報を保有している主体が存在しない。このため、r12 = r1 + r2 mod 2^n と、r12 + r 3 mod 2^n  の計算の両方を、全加算器の秘密計算によって実行することになる。
【０１５７】
全加算器の計算を、下位桁から順番に実行する場合、n-1回のAND演算が発生する。これによって、装置間の通信の回数がn-1回となる。この回数を減らす合、キャリーセーブアダーなどを用いた加算手法を用いてもよい。この手法は、ANDの回数は増えるが。回路の深さは浅い。
【０１５８】
＜実施形態１＞
本発明の例示的な実施形態１の構成と動作について図面を参照して説明する。第１の実施形態は、値wを
w = r1 + r2 + r3 mod 2^n        ・・・(60)
を満たすr1、ｒ2、r3を用いた(2,3)閾値型RSSで分散されている場合に、
r12 = r1 + r2 mod2^n            ・・・(61)
を１つの装置が他の装置に複製秘密分散し、
r12 + r3 mod 2^n                ・・・(62)
を全加算器の秘密計算を用いて実行することによって、ビット分解された分散情報を生成する。
【０１５９】
図１は、実施形態１の構成を例示する図である。図１を参照すると、実施形態１において、ビット分解を行う秘密計算装置１０は、分散値保管装置１００、分解分散値保管装置２００、ビット分解秘密計算装置３００を備えている。
【０１６０】
分散値保管装置１００は、
w = r1 + r2 + r3 mod p         ・・・(63)
のpとして2^nを用いた(2,3)閾値型RSSで分散された値を保管する。
【０１６１】
分解分散値保管装置２００は、ビット分解された分散情報を保管する。
【０１６２】
ビット分解秘密計算装置３００は、分散値保管装置１００の記憶する値を読み出し、分解分散値保管装置２００に値を記憶させる。
【０１６３】
実施形態１のシステムは、図１の装置１００、２００、３００の１セットが１つの装置１０を構成し、３組の装置１０が設けられている（３組の装置１０は、(2,3)閾値型RSSに関して前述した装置１、２、３に対応する）。装置１００、２００、３００、または装置１００、２００、３００から選択されたいずれか２つの装置は１つのユニットに配置されていてもよいし、分散して配置されていてもよい。例えば、少なくとも装置１００と装置２００との間、装置２００と装置３００との間には、LAN(Local Area Network）および／またはWAN(Wide Area Network)どの１つ以上の通信経路が設けられてもよい。
【０１６４】
なお、図１において、装置１００と装置３００と装置３００と装置２００との間の矢印はデータの流れの一例を模式的に示しているに過ぎない。装置１００と装置３００と装置３００と装置２００との間の通信は、矢印の方向に限定されないことは勿論である。後述する他の実施形態においても同様である。
【０１６５】
分散値保管装置１００は、(2,3)閾値型RSSで分散された第１分散値、第２分散値に関して、第１分散値を保管する第１分散値保管部１０１、第２分散値を保管する第２分散値保管部１０２を備える。第１分散値保管部１０１と第２分散値保管部１０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値を、どのように加工した値かが分かるように保管されているものとする。
【０１６６】
分解分散値保管装置２００は、第１分散値をビット分解した列（2を法とした(2,3)閾値型RSSで分散された値の列）を保管する第１分解分散値保管部２０１と第２分解分散値保管部２０２を備える。第２分散値をビット分解した列（2を法とした(2,3)閾値型RSSで分散された値の列）を保管する第１分解分散値保管部２０１と第２分解分散値保管部２０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のうちどの値をどのように加工した値かが分かるように保管されているものとする。
【０１６７】
ビット分解秘密計算装置３００は、加算分散部３０１と、部分分散情報抽出部３０２と、全加算器秘密計算部３０３とを備える。
【０１６８】
ビット分解秘密計算装置３００は、分散値保管装置１００が記憶する値を読み出し、不図示の他のビット分解秘密計算装置３００と通信し、分解分散値保管装置２００に情報を記憶させる。
【０１６９】
加算分散部３０１は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち２つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出す。分散値保管装置１００が２つのインデックスの両方を保管している場合は、その和について(2,3)閾値型RSSの分散情報を生成し、他の２装置に送付する。
【０１７０】
部分分散情報抽出部３０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした分散情報を出力する。
【０１７１】
全加算器秘密計算部３０３は、加算分散部３０１によって生成配布された(2,3)閾値型RSSの分散情報と部分分散情報抽出部３０２によって生成された(2,3)閾値型RSSの分散情報について、全加算器の秘密計算を用いた加算処理を実行し、各ビット（各桁）に関して得られたビット毎（桁毎）の計算結果の分散情報を結合した値を、分解分散値保管装置２００に記憶させる。
【０１７２】
図２は、本発明の第１の実施形態の動作を説明する流れ図である。
【０１７３】
分散値保管装置１００には、nビットの値rを
r = r_1 + r_2 + r_3 mod 2^n        ・・・(64)
となるr_1、r_2、r_3を用いた(2,3)閾値型RSSで分散された値が記憶されているものとする。
【０１７４】
本実施形態では、
r_ij = r_i + r_j mod 2^n             ・・・(65)
を分散して、r_ijとr_kの加算を全加算器の秘密計算で実行する。i、j、kは互いに異なる値で1、2、3のいずれかの値の組み合わせであれば（重複なし）、どのような組み合わせでaあってもよい。
【０１７５】
以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット分解秘密計算装置３００が実行する。
【０１７６】
＜ステップA1＞
各加算分散部３０１は、ビット分解秘密計算装置３００と対応付けられた分散値保管装置１００がr_iとr_jに関する情報を記憶しているかを判定する。記憶している場合、
r_ij = r_i + r_j mod 2^n            ・・・(66)
を計算し、分散情報を他のビット分解秘密計算装置３００の加算分散部３０１に送付する。その後、各装置は、r_ijの分散情報を出力する。
【０１７７】
＜ステップA2＞
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値から、r_kに関する部分以外を０とみなした部分分散情報を出力する。
【０１７８】
＜ステップA3＞
次に、全加算器秘密計算部３０３は、r_ijの分散情報と、r_kの分散情報に関して、全加算器の秘密計算を用いた加算処理
r_ij + r_k mod 2^n           ・・・(67)
を実行する。そして、全加算器秘密計算部３０３は、加算処理結果の列（各ビット（各桁）に関して得られたビット毎（桁毎）の計算結果の分散情報を結合した値）を分解分散値保管装置２００に記憶させる。
【０１７９】
＜実施形態２＞
本発明の例示的な実施形態２の構成と動作について図面を参照して説明する。実施形態２は、値wを
w = r1 + r2 + r3 mod 2^n            ・・・(68)
を満たすr1、r2、r3を用いた(2,3)閾値型RSSで分散されている場合に、
r12 = r1 + r2 mod 2^n             ・・・ (69)
を全加算器の秘密計算によって実行し、
r12 + r3 mod 2^n                   ・・・ (70)
を下位ビットから全加算器の秘密計算によって計算する。なお、式(68)-(70)自体は、式(60)-(62)と同じである。
【０１８０】
図３は、実施形態２の構成を例示する図である。図３を参照すると、実施形態２の秘密計算装置１０Ａは、pとして2^nを用いた(2,3)閾値型RSSで分散された値を保管する分散値保管装置１００と、ビット分解された分散情報を保管する分解分散値保管装置２００と、分散値保管装置１００の記憶する値を読み出し、分解分散値保管装置２００に値を記憶させるビット分解秘密計算装置３００Ａを含む。また、実施形態２のシステムは、前記実施形態１と同様、それぞれの装置１００、２００、３００Ａを１セットとした装置１０Ａを３組備えることで構成される。
【０１８１】
分散値保管装置１００は、(2,3)閾値型RSSで分散された第１分散値、第２分散値に関して、第１分散値を保管する第１分散値保管部１０１と、第２分散値を保管する第２分散値保管部１０２を備える。第１分散値保管部１０１と第２分散値保管部１０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０１８２】
分解分散値保管装置２００は、第１分散値をビット分解した列（2を法とした(2,3)閾値型RSSで分散された値の列）を保管する第１分解分散値保管部２０１と、第２分散値をビット分解した列を保管する第２分解分散値保管部２０２を備える。第１分解分散値保管部２０１と第２分解分散値保管部２０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０１８３】
ビット分解秘密計算装置３００Ａは、部分分散情報抽出部３０２と、全加算器秘密計算部３０３とを備える。
【０１８４】
ビット分解秘密計算装置３００Ａは、分散値保管装置１００が記憶する値を読み出し、他のビット分解秘密計算装置３００と通信し、分解分散値保管装置２００に情報を記憶させる。
【０１８５】
部分分散情報抽出部３０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出す。部分分散情報抽出部３０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした分散情報を出力する。
【０１８６】
全加算器秘密計算部３０３は、部分分散情報抽出部３０２によって生成された(2,3)閾値型RSSの分散情報３組を入力として、３つの値に関する下位ビットから全加算器の秘密計算を実行し、各ビットに関して得られたビット毎の計算結果の分散情報を分解分散値保管装置２００に記憶させる。
【０１８７】
図４は、実施形態２の動作を説明する流れ図である。
【０１８８】
分散値保管装置１００には、nビットの値rに関して、
r = r_1 + r_2 + r_3 mod 2^n          ・・・ (71)
となるr_1、r_2、r_3を用いた(2,3)閾値型RSSで分散された値が記憶されているものとする。
【０１８９】
本実施形態の動作では、
r_ij = r_i + r_j mod 2^n           ・・・ (72)
を全加算器の秘密計算で実行し、
r_ij + r_k mod 2^n                ・・・ (73)
を全加算器の秘密計算で実行する。i、j、kは互いに異なる値で1、2、3のいずれか値の組み合わせとする。以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット分解秘密計算装置３００が実行する。
【０１９０】
＜ステップB1＞
まず、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_iに関する部分以外を０とみなした分散情報（「部分分散情報」という）を出力する。
【０１９１】
＜ステップB2＞
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_jに関する部分以外を０とみなした分散情報（「部分分散情報」という）を出力する。
【０１９２】
＜ステップB3＞
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_kに関する部分以外を０とみなした分散情報（「部分分散情報」という）を出力する。
【０１９３】
＜ステップB4＞
次に、全加算器秘密計算部３０３は、r_iの分散情報とr_jの分散情報に関して、下位ビットから順に、
r_ij = r_i + r_j mod 2^n          ・・・ (74)
を全加算器の秘密計算で実行し、その結果の列をr_ijの分散情報として出力する。
【０１９４】
＜ステップB5＞
次に、全加算器秘密計算部３０３は、r_ijの分散情報とr_kの分散情報に関して、
r_ij + r_k mod 2^n            ・・・ (75)
全加算器の秘密計算で実行し、その結果の列を分解分散値保管装置２００に記憶させる。
【０１９５】
＜実施形態３＞
本発明の例示的な実施形態３の構成と動作について説明する。
【０１９６】
実施形態３では、x = 1,…,nについて、x桁目のビットw_x(1ビット)が
w_x = r_{1,x} + r_{2,x} + r_{3,x} mod 2           ・・・ (76)
を満たす分散情報（ビット分解した分散情報）r_{1,x}、r_{2,x}、r_{3,x}を用いた(2,3)閾値型RSSで分散されている場合に、
r12 = r_{1,n}||…||r_{1,1} + r_{2,n}||…||r_{2,1} mod 2^n       ・・・ (77)
と、
r12 = r12 + r_{3,n}||…||r_{3,1} mod2^n                    ・・・ (78)
を全加算器の秘密計算によって実行することによって、ビット結合を実行する場合の実施形態である。"||"は、ビット連結(concatenation)を表す。
【０１９７】
図５は、実施形態３の構成を例示する図である。図５を参照すると、実施形態３の秘密計算装置（ビット結合を行う秘密計算装置）２０は、pとして、2^nを用いた(2,3)閾値型RSSで分散された値を保管する分散値保管装置１００と、ビット分解された分散情報を保管する分解分散値保管装置２００と、分解分散値保管装置２００の記憶する値を読み出し、分散値保管装置１００に値を記憶させるビット結合秘密計算装置４００を含む。実施形態３のシステムは、それぞれの装置１００、２００、４００を１セットとする装置２０を３組備えて構成される。
【０１９８】
分散値保管装置１００は、第１分散値保管部１０１と第２分散値保管部１０２を備える。第１分散値保管部１０１と第２分散値保管部１０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０１９９】
分解分散値保管装置２００は、第１分解分散値保管部２０１と第２分解分散値保管部２０２を備える。第１分解分散値保管部２０１と第２分解分散値保管部２０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０２００】
ビット結合秘密計算装置４００は、部分分散情報抽出部４０２と、全加算器秘密計算部４０３とを備え、分解分散値保管装置２００が記憶する値を読み出し、他の２組のビット結合秘密計算装置４００と通信し、分散値保管装置１００に情報を記憶させる。部分分散情報抽出部４０２と、全加算器秘密計算部４０３は、図３の部分分散情報抽出部３０２と、全加算器秘密計算部３０３で構成し、入力と出力、処理の向きを逆とするようにしてもよい。
【０２０１】
部分分散情報抽出部４０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つのインデックスを入力として、分解分散値保管装置２００が記憶する値r_{i,n}||…||r_{i,1}を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした分散情報(「部分分解分散情報」という)を出力する。部分分散情報抽出部４０２は、分解分散値保管装置２００が記憶する値r_{j,n}||…||r_{j,1}を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした部分分散情報を出力し、さらに、分解分散値保管装置２００が記憶する値r_{k,n}||…||r_{k,1}を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした部分分散情報を出力する。
【０２０２】
全加算器秘密計算部４０３は、部分分散情報抽出部４０２によって生成された(2,3)閾値型RSSの分散情報３組を入力として、３つの値に関する下位ビットから全加算器の秘密計算を実行し、各ビットに関して得られたビット毎の計算結果の分散情報を分解分散値保管装置２００に記憶させる。
【０２０３】
図６は、実施形態３の動作を説明する流れ図である。分解分散値保管装置２００には、nビットの値rの各桁(ビット)r_xについて、
r_x = r_{1,x} + r_{2,x} + r_{3,x} mod 2          ・・・ (79)
となるr_{1,x}、r_{2,x}、r_{3,x}を用いた(2,3)閾値型RSSで分散された値が記憶されているものとする。r_{1,x}、r_{2,x}、r_{3,x}はr_1、r_2、r_3のx桁目(i=1,..,n)とする。
【０２０４】
本実施形態の動作では、
r_ij = r_{i,n}||…||r_{i,1} + r_{j,n}||…||r_{j,1} mod 2^n        ・・・ (80)
を全加算器の秘密計算で実行し、
r_ij + r_{k,n}||…||r_{k,1} mod 2^n                        ・・・ (81)
を全加算器の秘密計算で実行する。i、j、kは互いに異なる値で1、2、3のいずれか値の組み合わせとする。以下の処理は、３組の分散値保管装置１００、分解分散値保管装置２００、ビット結合秘密計算装置４００が実行する。
【０２０５】
＜ステップC1＞
まず、部分分散情報抽出部４０２は、分解分散値保管装置２００の記憶する値から、
r_{i,n}||…||r_{i,1}                  ・・・ (82)
に関する部分以外を０とみなした分散情報（r_{i,n}||…||r_{i,1}の分散情報、部分分解情報ともいう）を出力する。
【０２０６】
＜ステップC2＞
次に、部分分散情報抽出部４０２は、分解分散値保管装置２００の記憶する値から、
r_{j,n}||…||r_{j,1}               ・・・ (83)
に関する部分以外を０とみなした分散情報(r_{j,n}||…||r_{j,1}の分散情報、部分分解情報ともいう)を出力する。
【０２０７】
＜ステップC3＞
次に、部分分散情報抽出部４０２は、分解分散値保管装置２００の記憶する値から、
r_{k,n}||…||r_{k,1}               ・・・ (84)
に関する部分以外を０とみなした分散情報（r_{k,n}||…||r_{k,1}の分散情報、部分分解情報ともいう）を出力する(例えば(i,j,k)=(1,2,3))。
【０２０８】
＜ステップC4＞
次に、全加算器秘密計算部４０３は、
r_{i,n}||…||r_{i,1}                ・・・ (85)
の部分分解分散情報と、
r_{j,n}||…||r_{j,1}              ・・・ (86)
の部分分解分散情報に関して、全加算器の秘密計算を用いて、
r_ij = r_{i,n}||…||r_{i,1} + r_{j,n}||…||r_{j,1} mod 2^n         ・・・ (87)
を計算し、その結果の列をr_ijの分散情報として出力する。
【０２０９】
＜ステップC5＞
次に、全加算器秘密計算部４０３は、
r_ijの分散情報と、
r_{k,n}||…||r_{k,1}          ・・・ (88)
の部分分解分散情報に関して、
全加算器の秘密計算を用いて、
r_ij + r_{k,n}||…||r_{k,1} mod 2^n          ・・・ (89)
を計算し、その結果を、分散値保管装置１００に記憶させる。
【０２１０】
＜実施形態４＞
前述した実施形態２のビット分解処理では、r_i、r_j、r_kについて、まず２つの値を加算し、もう１つの値を加えているが、この処理は並列に実行することもできる。本発明の例示的な実施形態４は、各桁の処理を並列に実行しながらビット分解処理を行うものである。
【０２１１】
具体的には、以下の処理(z、c、d、vの計算)を、x= 1からnまで順に実行する。XORは排他的論理和を表す。
c_{1} = d_{1} = 0         ・・・ (90)
とする。なお、c_{n + 1}とd_{n + 1}は計算しなくてもよい。
r_{i,x}は、r_iのx桁目とする。z_{x}、v_{x}、c_{x}、d_{x}は、z、c、d、vのx桁目を表す。
【０２１２】
z_{x} = r_{1,x} XOR r_{2,x} XOR r_{3,x}           ・・・ (91)
【０２１３】
c_{x + 1} = [(r_{1,x} XOR r_{2,x} XOR 1) AND (r_{1,x} XOR r_{3,x})] XOR r_{3,x}         ・・・ (92)
【０２１４】
d_{x + 1} = [(c_{x} XOR d_{x} XOR 1) AND [(c_{x} XOR z_{x})] XOR z_{x}          ・・・ (93)
【０２１５】
v_{x} = z_{x} XOR c_{x} XOR d_{x}         ・・・ (94)
【０２１６】
c_{x + 1}とd_{x + 1}は、r_{1, x}, r_{2, x}、r_{3, x}、c_{x}、d_{x} を加算する際に発生する２ビットの桁上がりを表す。２ビットであるのは、５入力あるためである。
【０２１７】
c_{x}、d_{x}をz_{x}に繰り込んだ値（z_{x} XOR c_{x} XOR d_{x}）が、rのx桁目に等しく、この値を、秘密計算を用いて計算することで、v_{x}の分散情報として、rのx桁目を分散した値（分散情報）を得ることができる。
【０２１８】
ここで、11（10進表記）の分散値をビット分解する例を示す。
【０２１９】
w = 11、r_i = 3、r_j = 10、r_k = 14について、それぞれのx桁目を、
w_x、r_{i,x}、r_{j,x}、r_{k,x}と表記する。なお、以下の計算ではi=1,j=2,k=3とする。
【０２２０】
w = 11 = b1011、
r_1 =  3 = b0011、
r_2 = 10 = b1010、
r_3 = 14 = b1110
【０２２１】
＜1桁目の計算結果＞
z_{1} = 1、
c_{2} = 0、
d_{2} = 0、
v_{1} = 1
・・・ (95)
【０２２２】
＜２桁目の計算結果＞
z_{2} = 1、
c_{3} = 1、
d_{3} = 0、
v_{2} = 1
・・・ (96)
【０２２３】
＜３桁目の計算結果＞
z_{3} = 1、
c_{4} = 0、
d_{4} = 1、
v_{3} = 0
・・・ (97)
【０２２４】
＜４桁目の計算結果＞
z_{4} = 0、
v_{4} = 1、
v_{4} = 1、
v_{3} = 0、
v_{2} = 1、
v_{1} = 1
・・・ (98)
【０２２５】
以上、値w=b1011をビット毎に分解した値となる。この計算を秘密計算によって実行する。
【０２２６】
図７は、実施形態４の構成を例示する図である。図７を参照すると、実施形態４の秘密計算装置（ビット分解を行う秘密計算装置）１０Ｂは、pとして2^nを用いた(2,3)閾値型RSSで分散された値を保管する分散値保管装置１００と、ビット分解された分散情報を保管する分解分散値保管装置２００と、分散値保管装置１００の記憶する値を読み出し、分解分散値保管装置２００に値を記憶させるビット分解秘密計算装置３００Ｂを含む。また、実施形態４のシステムは、それぞれの装置１００、２００、３００を１セットとする装置１０Ｂを３組備えて構成される。
【０２２７】
分散値保管装置１００は、第１分散値保管部１０１と第２分散値保管部１０２を備える。第１分散値保管部１０１と第２分散値保管部１０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０２２８】
分解分散値保管装置２００は、第１分解分散値保管部２０１と第２分解分散値保管部２０２を備える。第１分解分散値保管部２０１と第２分解分散値保管部２０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０２２９】
ビット分解秘密計算装置３００Ｂは、部分分散情報抽出部３０２と、桁上がり秘密計算部３０４と、繰り込み秘密計算部３０５を備える。
【０２３０】
ビット分解秘密計算装置３００Ｂは、分散値保管装置１００が記憶する値を読み出し、他のビット分解秘密計算装置３００と通信し、分解分散値保管装置２００に情報を記憶させる。
【０２３１】
部分分散情報抽出部３０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした分散情報を出力する。
【０２３２】
桁上がり秘密計算部３０４は、部分分散情報抽出部３０２によって生成された(2,3)閾値型RSSの分散情報の３組のi桁目と、i-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、繰り込み秘密計算部３０５に入力する。
【０２３３】
繰り込み秘密計算部３０５は、分解分散値保管装置２００から読み出された(2,3)閾値型RSSのrの分散情報のx桁目(r_x)と、桁上がり秘密計算部３０４から入力されたx桁目の分散情報に関する２ビットの桁上がりの分散情報を入力として、これら３値の排他的論理和を計算する秘密計算を実行し、その結果をx桁目のビット分解された分散情報として、分解分散値保管装置２００に記憶させる。
【０２３４】
図８は、実施形態４の動作を説明する流れ図である。分散値保管装置１００には、nビットの値rを
r = r_1 + r_2 + r_3 mod 2^n        ・・・ (99)
となるr_1、r_2、r_3を用いた(2,3)閾値型RSSで分散された値が記憶されているものとする。以下の処理は、３組の分散値保管装置１００,分解分散値保管装置２００、ビット分解秘密計算装置３００Ｂが実行する。
c_{1}、d_{1}を0とする。
【０２３５】
＜ステップD1＞
まず、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_1に関する部分以外を０とみなした部分分散情報を出力する。なお、r_1のiビット目をr_{1,i}とする。
【０２３６】
＜ステップD2＞
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_2に関する部分以外を０とみなした部分分散情報を出力する。なお、r_2のiビット目をr_{2,i}とする。
【０２３７】
＜ステップD3＞
次に、部分分散情報抽出部３０２は、分散値保管装置１００の記憶する値からr_3に関する部分以外を０とみなした部分分散情報を出力する。なお、r_3のiビット目をr_{3,i}とする。
【０２３８】
以下の処理をx = 1,...,n（1ビットからnビット）について実行する。
【０２３９】
＜ステップD4＞
桁上がり秘密計算部３０４は、部分分散情報抽出部３０２によって生成された
r_{1,x}、
r_{2,x}、
r_{3,x}の分散情報と、
x-1桁目から生じる２ビットの桁上がりc_{x}、d_{x}に関する分散情報を入力として、
５組の入力から発生する２ビットの桁上がりc_{x + 1}とd_{x + 1}の分散情報を計算する秘密計算を実行し、繰り込み秘密計算部３０５に入力する。
【０２４０】
＜ステップD5＞
繰り込み秘密計算部３０５は、
分散値保管装置１００から読み出されたrの分散情報のx桁目と、
桁上がり秘密計算部３０４から入力されたx-1桁目の分散情報に関する２ビットの桁上がりc_{x}、d_{x}の分散情報を入力として、これら３入力の値の排他的論理和（XOR）を計算する秘密計算を実行し、その結果をx桁目のビット分解された分散情報として、分解分散値保管装置２００に記憶させる。
【０２４１】
＜実施形態５＞
前述した実施形態３のビット結合処理では、r_i、r_j、r_k (i,j,k = (1,2,3))について、まず２つの値を加算し、もう１つの値を加えている。全加算器の秘密計算によって下位桁から順に計算しているが、
r_ij = r_i + r_j            ・・・ (100)
の計算のx桁目に関する計算が終わった段階で、
r_ij + r_k                ・・・ (101)
のx桁目に関する処理を開始することができる。
【０２４２】
(s1)  r_ij = r_i + r_jの計算のx桁目に関する計算が終わった段階で、
(s2)  r_{ijk} = r_ij + r_kのx桁目に関する処理を開始することができる。
【０２４３】
これを活用すると、(s1)に関するx + 1桁目の計算と、(s2)に関するx桁目の計算を並列に実行することができる。実施形態５は、この特徴を活用しながら、ビット結合処理を行うように構成したものである。実施形態５は、ビット結合を逐次的に実行する場合に比べて、処理時間を削減できる。
【０２４４】
nビットの値
w = ｂ w_n||...||w_1          ・・・ (102)
（ｂは２進表記）
において、x = 1,...,nについて、
w_xのそれぞれが１ビットの値として分散されてとき、以下の処理を、x = 1からnまで順に計算することで、ビット結合を実行する。c_{1} = d_{1} = 0とする。なお、c_{n + 1}とd_{n + 1}は計算しなくてもよい。
【０２４５】
以下のv_{x}の分散情報がx桁目の分散情報となる。
【０２４６】
v_{x} = w_x XOR c_{x} XOR d_{x}         ・・・ (103)
【０２４７】
v_{x}の分散情報を構成する３つの値をそれぞれ、
v_{1,x}、v_{2,x}、v_{3,x}                  ・・・ (104)
として、
c_{x + 1}、ｄ{x + 1}を以下のように計算する。
【０２４８】
c_{x + 1} = [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{v,3}             ・・・ (105)
【０２４９】
d_{x + 1} = [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}         ・・・ (106)
【０２５０】
c_{x+1}とd_{x+1}は、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}から発生する２ビットの桁上がりである。
【０２５１】
v_{1,x}、v_{2,x}、v_{3,x}は、x桁目の分散情報v_{x}を３つの値に分解したものであるが、分解する前に、c_{x}とd_{x}が排他的に加えられている（XORによる加算）点が異なる。これは、x-1桁目から発生する桁上がりをx桁目に繰り込んだ結果として、x桁目の値が変化しないようにするためである。
【０２５２】
w = 11(10進) = b1011、 w_4 = 1、 w_3 = 0、w_2 = 1、w_1 = 1について、式(99)−(102)を用いて計算する。
【０２５３】
＜1桁目の計算結果＞
v_{1} = 1
ここでv_{1}の分散情報を構成する３つの値を、
v_{1,1} = 1、
v_{2,1} = 1、
v_{3,1} = 1  
・・・ (107)
とすると、
c_{2} = 1、
d_{2} = 0
・・・ (108)
となる。
【０２５４】
＜２桁目の計算結果＞
v_{2} = 0
ここで、v_{2}の分散情報を構成する３つの値を、
v_{1,2} = 1、
v_{2,2} = 1、
v_{3,2} = 0 
・・・ (109)
とすると、
c_{3} = 1、
d_{3} = 0  
・・・ (110)
となる。
【０２５５】
＜３桁目の計算結果＞
v_{3} = 1
ここで、v_{3}の分散情報を構成する３つの値を、
v_{1,3} = 1、
v_{2,3} = 1、
v_{3,3} = 1
・・・ (111)
とすると、
c_{4} = 1、
d_{4} = 1  
・・・ (112)
となる。
【０２５６】
＜４桁目の計算結果＞
v_{4} = 0
ここで、v_{4}の分散情報を構成する３つの値を、
v_{1,4} = 0、
v_{2,4} = 0、
v_{3,4} = 0
・・・ (113)
とする。
【０２５７】
このとき、v_{x} (x=1,..,4)を構成する分散情報を結合した３つの値
b0111、
b0111、
b0101           ・・・ (114)
がビット結合した分散情報となっている。
【０２５８】
実施形態５の構成と動作について説明する。実施形態５は、x = 1,…,nについて、ビットw_xが
w_x = r_{x,1} + r_{x,2} + r_{x,3}  mod 2    ・・・ (115)
を満たすr_{i,1}、r_{i,2}、r_{i,3}を用いた(2,3)閾値型RSSで分散されているとする。
【０２５９】
図９は、本発明の例示的な実施形態５の構成を例示する図である。図９を参照すると、実施形態５の秘密計算装置（ビット結合を行う秘密計算装置）２０Ａは、pとして2^nを用いた(2,3)閾値型RSSで分散された値を保管する分散値保管装置１００と、ビット分解された分散情報を保管する分解分散値保管装置２００と、分解分散値保管装置２００の記憶する値を読み出し、分散値保管装置１００に値を記憶させるビット結合秘密計算装置４００Ａを含む。実施形態５のシステムは、それぞれの装置１００、２００、４００Ａを１セットとする装置２０Ａを３組備えて構成される。
【０２６０】
分散値保管装置１００は、第１分散値保管部１０１と第２分散値保管部１０２を備える。第１分散値保管部１０１と第２分散値保管部１０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０２６１】
分解分散値保管装置２００は、第１分解分散値保管部２０１と第２分解分散値保管部２０２を備える。第１分解分散値保管部２０１と第２分解分散値保管部２０２は、それぞれの分散値が(2,3)閾値型RSSの分散情報を生成するために用いられた３つの値のどの値をどのように加工した値かが分かるように保管されているものとする。
【０２６２】
ビット結合秘密計算装置４００Ａは、部分分散情報抽出部４０２と、桁上がり秘密計算部４０４と、繰り込み秘密計算部４０５を備え、分解分散値保管装置２００が記憶する値を読み出し、他のビット結合秘密計算装置４００Ａと通信し、分散値保管装置１００に情報を記憶させる。部分分散情報抽出部４０２と、桁上がり秘密計算部４０４と、繰り込み秘密計算部４０５は、前記実施形態４の部分分散情報抽出部３０２と、桁上がり秘密計算部３０４と、繰り込み秘密計算部３０５において入力と出力、および処理の向きを逆としてもよい。
【０２６３】
部分分散情報抽出部４０２は、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つのインデックスを入力として、分散値保管装置１００が記憶する値を読み出し、(2,3)閾値型RSSの分散情報を構成する３つの値のうち１つを除いて０とした分散情報を出力する。
【０２６４】
桁上がり秘密計算部４０４は、部分分散情報抽出部４０２によって生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、繰り込み秘密計算部４０５に入力する。
【０２６５】
繰り込み秘密計算部４０５は、分解分散値保管装置２００から読み出された(2,3)閾値型RSSのrの分散情報のx桁目(r_x)と、桁上がり秘密計算部４０４から入力されたx桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、それら３値の排他的論理和を計算する秘密計算を実行し、その結果をx桁目の分散情報として分散値保管装置１００に記憶させる。
【０２６６】
図１０は、実施形態５の動作を説明する流れ図である。分解分散値保管装置２００には、nビットの値rの各桁r_x（x=1.,..,n）について、
r_x = r_{1,x} + r_{2,x} + r_{3,x} mod 2           ・・・(116)
となるr_{1,x}、r_{2,x}、r_{3,x}を用いた(2,3)閾値型RSSで分散された値が記憶されているものとする。
【０２６７】
以下の処理は、３組の分散値保管装置１００,分解分散値保管装置２００、ビット結合秘密計算装置４００が実行する。
【０２６８】
以下の処理を、x = 1,…,n(xは下位からの桁数)に対して実行する。なお、c_{1} = 0、d_{1} = 0とする。
【０２６９】
＜ステップE1＞
まず、繰り込み秘密計算部４０５は、分解分散値保管装置２００から読み出された(2,3)閾値型RSSのnビットの分散情報rのx桁目rr_xの分散情報にc_{x}とd_{x}を繰り込む（排他的論理和により加算する）。この計算結果r_x'の分散情報を、部分分散情報抽出部３０２に入力し、r_x'をビット結合結果の分散情報のxビット目として分散値保管装置１００に記憶させる。
【０２７０】
なお、r_x'は、
r_{1,x}' + r_{2,x}' + r_{3,x}' = r_x' mod 2      ・・・ (117)
を満たすr_{1,x}'、r_{2,x}'、r_{3,x}'によって３つの装置に分散されているものとする。
【０２７１】
＜ステップE2＞
次に、部分分散情報抽出部４０２は、r_x'の分散情報から、r_{1,x}'に関する部分以外を0とみなした分散情報（r_{1,x}'の分散情報、部分分解情報ともいう）を出力する。
【０２７２】
＜ステップE3＞
次に、部分分散情報抽出部４０２は、r_x'の分散情報から、r_{2,x}'に関する部分以外を０とみなした分散情報（r_{2,x}'の分散情報、部分分解情報ともいう）を出力する。
【０２７３】
＜ステップE4＞
次に、部分分散情報抽出部４０２は、r_x'の分散情報から、r_{3,x}'に関する部分以外を０とみなした分散情報（r_{3,x}'の分散情報、部分分解情報ともいう）を出力する。
【０２７４】
＜ステップE5＞
次に、桁上がり秘密計算部４０４は、部分分散情報抽出部３０２によって生成された
r_{1,x}'、r_{2,x}'、r_{3,x}'       ・・・ (118)
の分散情報と、
x-1桁目から生じる２ビットの桁上がり
c_{x}、d_{x}                  ・・・ (119)
に関する分散情報を
入力とし、５組の入力から発生する２ビットの桁上がり
c_{x + 1}、d_{x + 1}            ・・・ (120)
の分散情報を計算する秘密計算を実行し、繰り込み秘密計算部４０５に入力する。
【０２７５】
本実施形態によれば、ビット結合処理を行うように構成したものである。実施形態５は、逐次的に実行する場合に比べて、処理時間を削減できる。
【０２７６】
図１１は、前記実施形態１−５の装置１０、１０Ａ、１０Ｂ、２０、２０Ａを、コンピュータ装置５００で実現した構成を例示する図である。図１１を参照すると、コンピュータ装置５００は、プロセッサ５０１、記憶装置５０２、表示装置５０３、通信インタフェース５０４を備える。記憶装置５０２は、ハードディスクドライブ（HDD）、半導体メモリ（例えば、ソリッドステートドライブ（SSD）、ダイナミックランダムアクセスメモリ（DRAM）、スタティックランダムアクセスメモリ（SRAM）、読み出し専用のリードオンリメモリ（ROM）、電気的に消去プログラム可能なリードオンリメモリ（Electrically Erasable Programmable Read-Only Memory）、コンパクトディスク（CD）、デジタルバーサタイルディスク（DVD）等のいずれか、または複数の組み合わせから構成され、プロセッサ５０１で実行されるプログラムを格納する。通信インタフェース５０４は、他の装置への分散情報の送信、受信等の通信を行う。プロセッサ５０１は、記憶装置５０２に格納されてプログラムを実行することで、前記実施形態１−５の各装置１０、１０Ａ、１０Ｂ、２０、２０Ａの機能を実現する。記憶装置５０２は、分散値保管装置１００、分解分散値保管装置２００を含む構成としてもよい。
【０２７７】
上記した本実施形態を用いることで、(2,3)閾値型RSSで分散された値を、各ビットが(2,3)閾値型RSSで分散された値に変換することができる。また、その逆を効率的に実行することができる。この処理が可能となると、値の秘密計算と、ビットの秘密計算を組み合わせた複雑な処理を効率的に実行することが可能となる。
【０２７８】
なお、上記の非特許文献１−３の各開示を、本書に引用をもって繰り込むものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素（各請求項の各要素、各実施例の各要素、各図面の各要素等を含む）の多様な組み合わせ乃至選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【０２７９】
上記した態様（形態）、実施形態、実施例は例えば以下のように付記される（ただし、以下に制限されない）。
【０２８０】
(付記１)
２のべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散する加算分散部と、
前記加算分散部による前記２つの値の和を分散した値と、前記加算分散部が用いた前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部と、
を備える、ことを特徴とする秘密計算装置。
【０２８１】
(付記２)
前記ビット分解秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値のうち、前記１つを除いて０とし、前記１つの値の分散情報を生成する部分分散情報抽出部を備え、
前記全加算器秘密計算部は、
前記加算分散部で生成され配布された前記２つの値の和の分散情報と、
前記部分分散情報抽出部で生成した前記１つの値の分散情報について、全加算器の秘密計算を用いた加算処理を実行し、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする付記１に記載の秘密計算装置。
【０２８２】
(付記３)
2のnべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関してw= r1+r2+r3 mod 2^nを満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^n  （mod は剰余演算、＾はべき乗演算）と、
r123 = r12 + r3 mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する全加算器秘密計算部を備える、ことを特徴とする秘密計算装置。
【０２８３】
(付記４)
前記ビット分解秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値の各々について、各１つ以外を０とする分散情報をそれぞれ生成する部分分散情報抽出部を備え、
前記全加算器秘密計算部は、
前記部分分散情報抽出部で生成した３つの分散情報の２つの値に関して、下位桁から順に全加算器の秘密計算を実行し、結果の列を前記２つの値の分散情報とし、
前記２つの値の和の分散情報と、前記１つの値の分散情報について、全加算器の秘密計算を用いた、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする付記３に記載の秘密計算装置。
【０２８４】
(付記５)
2を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値の列を保管する分解分散値保管装置と、
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
ビット結合秘密計算装置と、
を備え、
前記ビット結合秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット）のうち、第ｘビット（ｘ=1,...,n)の値w_xに関して、
w_x= r_{1,x}+r_{2,x}+r_{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
r12 =r_{1,n}||…||r_{1,1}+ r_{2,n}||…||r_{2,1} mod 2^n  （mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,x}、r_{2,x}、r{3,x}は、r1、r2、r3の第xビットを表す）と
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分散値保管装置に記憶する全加算器秘密計算部を備える、ことを特徴とする秘密計算装置。
【０２８５】
(付記６)
前記ビット結合秘密計算装置は、
前記分解分散値保管装置の記憶する前記値w_xから、
前記r_{1,n}||…||r_{1,1}に関する部分以外を０とみなした分散情報、
前記r_{2,n}||…||r_{2,1}に関する部分以外を０とみなした分散情報、
前記r_{3,n}||…||r_{3,1}に関する部分以外を０とみなした分散情報、
を、それぞれ、
前記r_{1,n}||…||r_{1,1}、
前記r_{2,n}||…||r_{2,1}、
前記r_{3,n}||…||r_{3,1}の分散情報として出力する部分分散情報抽出部を備える、ことを特徴とする付記５に記載の秘密計算装置。
【０２８６】
(付記７)
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
ビット分解秘密計算装置と、
を備え、
前記ビット分解秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w= r_1+r_2+r_3 mod 2^nを満たすr1、r2、r3を用い、
i=1,2,3について、
r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてｘ桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する桁上がり秘密計算部と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する繰り込み秘密計算部を備える、ことを特徴とする秘密計算装置。
【０２８７】
(付記８)
前記桁上がり秘密計算部は、
c_{x+1}を [(r_{1,x} XOR r_{2,x} XOR 1) AND (r_{1,x} XOR r_{3,x})] XOR r_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR z_{x})] XOR z_{x}
の秘密計算によって計算する、ことを特徴とする付記７に記載の秘密計算装置。
【０２８８】
（付記９）
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
ビット結合秘密計算装置と、
を備え、
前記ビット結合秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（ｎビット）として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
xを下位桁からの桁数として、ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として前記分散値保管装置に記憶する桁上がり秘密計算部と、を備えることを特徴とする秘密計算装置。
【０２８９】
（付記１０）
前記桁上がり秘密計算部は、
c_{x+1}を [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}の秘密計算によって計算する、ことを特徴とする付記９に記載の秘密計算装置。
【０２９０】
（付記１１）
前記ビット結合秘密計算装置は、
前記分解分散値保管装置から読み出された(2,3)閾値型RSSのrの分散情報のx桁目r_xと、前記桁上がり秘密計算部から入力された前記x桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、これら３値の排他的論理和を計算する秘密計算を実行し、計算結果r_x'をx桁目の分散情報として分散値保管装置に記憶する繰り込み秘密計算部と、
前記r_x'の分散情報から、i=1,2,3についてr_{i,x}'に関する部分以外を0とみなした分散情報を出力する部分分散情報抽出部と、
を備え、
前記桁上がり秘密計算部は、前記部分分散情報抽出部によって生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、前記繰り込み秘密計算部へ供給する、ことを特徴とする付記９又は１０に記載の秘密計算装置。
【０２９１】
（付記１２）
付記１乃至１１のいずれかに記載の秘密計算装置を３組備えた秘密計算装システム。
【０２９２】
（付記１３）
２のべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えた秘密計算装置を３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散し、
前記分散情報のうち前記２つの値の和を分散した値と、前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し計算結果を、ビット分解分散値として、前記分解分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【０２９３】
(付記１４)
前記秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値のうち、前記１つを除いて０とし、前記１つの値の分散情報を生成し、
前記２つの値の和の分散情報と、生成した前記１つの値の分散情報について、全加算器の秘密計算を用いた加算処理を実行し、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする付記１３に記載の秘密計算方法。
【０２９４】
（付記１５）
２のべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えた秘密計算装置を３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n
を満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^n  （mod は剰余演算、＾はべき乗演算）と、
r123 = r12 + r3 mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する、ビット分解分散値として、前記分解分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【０２９５】
(付記１６)
前記秘密計算装置は、
(2,3)閾値型RSSの前記分散情報を構成する３つの値の各々について、各１つ以外を０とする分散情報をそれぞれ生成し、
前記生成した３つの分散情報の２つの値に関して、下位桁から順に全加算器の秘密計算を実行し、結果の列を前記２つの値の分散情報とし、
前記２つの値の和の分散情報と、前記１つの値の分散情報について、全加算器の秘密計算を用いた、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する、ことを特徴とする付記１５に記載の秘密計算方法。
【０２９６】
（付記１７）
前記秘密計算装置は、前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット）のうち、第xビット（ｘ=1,...,n)の値w_xに関して、
w_x= r_{1,x}+r_{2,x}+r_{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
r12 =r_{1,n}||…||r_{1,1}+ r_{2,n}||…||r_{2,1} mod 2^n  （mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,x}、r_{2,x}、r{3,x}は、r1、r2、r3の第xビットを表す）と
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分散値保管装置に記憶する、ことを特徴とする付記１６に記載の秘密計算方法。
【０２９７】
(付記１８)
前記秘密計算装置は、
前記分解分散値保管装置の記憶する前記値w_xから、
前記r_{1,n}||…||r_{1,1}に関する部分以外を０とみなした分散情報、
前記r_{2,n}||…||r_{2,1}に関する部分以外を０とみなした分散情報、
前記r_{3,n}||…||r_{3,1}に関する部分以外を０とみなした分散情報、
を、それぞれ、
前記r_{1,n}||…||r_{1,1}、
前記r_{2,n}||…||r_{2,1}、
前記r_{3,n}||…||r_{3,1}の分散情報として出力する部分分散情報抽出部を備える、ことを特徴とする付記１７に記載の秘密計算方法。
【０２９８】
(付記１９)
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、を備えた秘密計算装置を３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w= r_1+r_2+r_3 mod 2^nを満たすr1、r2、r3を用い、
i=1,2,3について、
r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてｘ桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算し、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する、ことを特徴とする秘密計算方法。
【０２９９】
(付記２０)
前記秘密計算装置と、
c_{x+1}を [(r_{1,x} XOR r_{2,x} XOR 1) AND (r_{1,x} XOR r_{3,x})] XOR r_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR z_{x})] XOR z_{x}
の秘密計算によって計算する、ことを特徴とする付記１９に記載の秘密計算方法。
【０３００】
（付記２１）
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、を備えた秘密計算装置が３組で秘密計算システムを構成し、
前記秘密計算装置は、
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として前記分散値保管装置に記憶することを特徴とする秘密計算方法。
【０３０１】
（付記２２）
前記秘密計算装置は、
c_{x+1}を [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}の秘密計算によって計算する、ことを特徴とする付記２１に記載の秘密計算方法。
【０３０２】
（付記２３）
前記秘密計算装置は、
前記分解分散値保管装置から読み出された(2,3)閾値型RSSのrの分散情報のx桁目r_xと、前記桁上がり秘密計算部から入力された前記x桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、これら３値の排他的論理和を計算する秘密計算を実行し、計算結果r_x'をx桁目の分散情報として前記分散値保管装置に記憶する繰り込み秘密計算処理と、
前記r_x'の分散情報から、i=1,2,3についてr_{i,x}'に関する部分以外を0とみなした分散情報を出力する部分分散情報抽出処理を実行し、
前記生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、前記繰り込み秘密計算処理に供給する、ことを特徴とする付記２１又は２２に記載の秘密計算方法。
【０３０３】
（付記２４）
２のべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
を備えたコンピュータ装置に
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n （mod は剰余演算、＾はべき乗演算）を満たすr1、r2、3を用い、
前記分散情報のうち２つの値について、法2^n上の和をとり、前記和を(2,3)閾値型RSSによって分散する処理（加算分散処理）と、
前記加算分散処理による前記２つの値の和を分散した値と、前記加算分散処理が用いた前記２つの値以外の残りの１つの値の分散情報との和を、全加算器の秘密計算を用いて、各桁毎に計算し計算結果を、ビット分解分散値として、前記分解分散値保管装置に記憶する処理（全加算器秘密計算処理）を実行させるプログラム。
【０３０４】
(付記２５)
(2,3)閾値型RSSの前記分散情報を構成する３つの値のうち、前記１つを除いて０とし、前記１つの値の分散情報を生成する部分分散情報抽出処理を、
前記生成され配布された前記２つの値の和の分散情報と、
前記部分分散情報抽出処理で生成した前記１つの値の分散情報について、全加算器の秘密計算を用いた加算処理を実行し、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する処理（前記全加算器秘密計算処理）と、を前記コンピュータ装置に実行させる、付記２４に記載のプログラム。
【０３０５】
(付記２６)
2のnべき乗を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
を備えたコンピュータ装置に
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、値wに関して、
w= r1+r2+r3 mod 2^n
を満たすr1、r2、r3を用い、
r12 = r1+r2 mod 2^n  （mod は剰余演算、＾はべき乗演算）と、
r123 = r12 + r3 mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分解分散値保管装置に記憶する処理（全加算器秘密計算処理）を実行させるプログラム。
【０３０６】
(付記２７)
(2,3)閾値型RSSの前記分散情報を構成する３つの値の各々について、各１つ以外を０とする分散情報をそれぞれ生成する部分分散情報抽出処理と、
前記部分分散情報抽出処理で生成した３つの分散情報の２つの値に関して、下位桁から順に全加算器の秘密計算を実行し、結果の列を前記２つの値の分散情報とし、
前記２つの値の和の分散情報と、前記１つの値の分散情報について、全加算器の秘密計算を用いた、桁毎の計算結果の分散情報を結合した値を、前記分解分散値保管装置に記憶する処理（前記全加算器秘密計算処理）と、を前記コンピュータ装置に実行させる付記２６に記載のプログラム。
【０３０７】
(付記２８)
2を法とする(2,3)閾値型RSS（Replicated Secret Sharing:複製秘密分散）で分散された値の列を保管する分解分散値保管装置と
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
を備えたコンピュータ装置に
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列（nビット）のうち、第xビット（x=1,...,n)の値w_xに関して、
w_x= r_{1,x}+r_{2,x}+r_{3,x} mod 2を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
r12 =r_{1,n}||…||r_{1,1}+ r_{2,n}||…||r_{2,1} mod 2^n  （mod は剰余演算、＾はべき乗演算、||はビット連結、r_{1,x}、r_{2,x}、r{3,x}は、r1、r2、r3の第xビットを表す）と
r123 = r12 + r_{3,n}||…||r_{3,1} mod 2^n
の秘密計算を全加算器の秘密計算によって各桁毎に計算し、計算結果を前記分散値保管装置に記憶する処理（全加算器秘密計算処理）を実行させるプログラム。
【０３０８】
(付記２９)
前記分解分散値保管装置の記憶する前記値w_xから、
前記r_{1,n}||…||r_{1,1}に関する部分以外を０とみなした分散情報、
前記r_{2,n}||…||r_{2,1}に関する部分以外を０とみなした分散情報、
前記r_{3,n}||…||r_{3,1}に関する部分以外を０とみなした分散情報、
を、それぞれ、
前記r_{1,n}||…||r_{1,1}、
前記r_{2,n}||…||r_{2,1}、
前記r_{3,n}||…||r_{3,1}の分散情報として出力する部分分散情報抽出処理を前記コンピュータ装置に実行させる付記２８に記載のプログラム。
【０３０９】
(付記３０)
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
を備えたコンピュータ装置に
前記分散値保管装置が記憶する(2,3)閾値型RSSの分散情報として、nビットの値wに関して、
w= r_1+r_2+r_3 mod 2^nを満たすr1、r2、r3を用い、
i=1,2,3について、
r_{i,x}をr_iのxビット目とし、
１桁目の桁上がり入力c_{1}、d_{1}を0とし、
xを下位桁からの桁数として、x=1,...,n について
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}
についてｘ桁のビット毎の加算した際の２ビットの桁上がりとして、
c_{x+1}、d_{x+1}を秘密計算する桁上がり秘密計算処理と、
r_{1,x}、r_{2,x}、r_{3,x}、c_{x}、d_{x}の排他的論理和に基づく分散情報を、xビット目のビット分解された値の分散情報として、前記分解分散値保管装置に記憶する繰り込み秘密計算処理と、を実行させるプログラム。
【０３１０】
(付記３０)
前記桁上がり秘密計算処理は、
c_{x+1}を [(r_{1,x} XOR r_{2,x} XOR 1) AND (r_{1,x} XOR r_{3,x})] XOR r_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR z_{x})] XOR z_{x}
の秘密計算によって計算する、ことを特徴とする付記２９に記載のプログラム。
【０３１１】
（付記３１）
2を法とする(2,3)閾値型RSSで分散された値の列を保管する分解分散値保管装置と、
2のnべき乗を法とする(2,3)閾値型RSSで分散された値を保管する分散値保管装置と、
を備えたコンピュータ装置に
前記分解分散値保管装置が記憶するn個の(2,3)閾値型RSSの分散情報の列nビット)として、1ビット値w_xに関して、
w_x= r{1,x}+r{2,x}+r{3,x} mod 2
を満たすr_{1,x}、r_{2,x}、r{3,x}を用い、
c_{1},d_{1}を0とし、
ｘ=1,..,nについて、
w_xとc_{x}とd_{x}の排他的論理和をv_{x}とし、
v_{x}の分散情報を構成する(2,3)閾値型RSSの分散情報をv_{1,x}、v_{2,x}、v_{3,x}として、
v_{x}と、v_{1,x}、v_{2,x}、v_{3,x}、c_{x}、d_{x}について、ビット毎の加算した際の２ビットの桁上がりであるc_{x+1}、d_{x+1}を計算する秘密計算を実行し、v_{x}の分散情報を、x桁目の分散情報として前記分散値保管装置に記憶する桁上がり秘密計算処理を実行させるプログラム。
【０３１２】
（付記３２）
前記桁上がり秘密計算処理は、
c_{x+1}を [(v_{1,x} XOR v_{2,x} XOR 1) AND (v_{1,x} XOR v_{3,x})] XOR v_{3,x}
の秘密計算によって計算し、
d_{x+1}を [(c_{x} XOR d_{x} XOR 1) AND (c_{x} XOR v_{x})] XOR v_{x}の秘密計算によって計算する、付記３１に記載のプログラム。
【０３１３】
（付記３３）
前記分解分散値保管装置から読み出された(2,3)閾値型RSSのrの分散情報のx桁目r_xと、前記桁上がり秘密計算部から入力された前記x桁目の分散情報に関する２ビットの桁上がりの分散情報を入力とし、これら３値の排他的論理和を計算する秘密計算を実行し、計算結果r_x'をx桁目の分散情報として分散値保管装置に記憶する繰り込み秘密計算処理と、
前記r_x'の分散情報から、i=1,2,3についてr_{i,x}'に関する部分以外を0とみなした分散情報を出力する部分分散情報抽出処理と、
前記部分分散情報抽出処理によって生成された(2,3)閾値型RSSの分散情報の３組のx桁目と、x-1桁目から生じる２ビットの桁上がりに関する分散情報を入力として、５組の入力から発生する２ビットの桁上がりを計算する秘密計算を実行し、前記繰り込み秘密計算部へ供給する前記桁上がり秘密計算処理と、
を実行させる付記３１又は３２に記載のプログラム。
【符号の説明】
【０３１４】
１０、１０Ａ、１０Ｂ  秘密計算装置（ビット分解を行う秘密計算装置）
２０、２０Ａ  秘密計算装置（ビット結合を行う秘密計算装置）
１００  分散値保管装置
１０１  第１分散値保管部
１０２  第２分散値保管部
２００  分解分散値保管装置
２０１  第１分解分散値保管部
２０２  第２分解分散値保管部
３００、３００Ａ、３００Ｂ  ビット分解秘密計算装置
３０１  加算分散部
３０２  部分分散情報抽出部
３０３  全加算器秘密計算部
３０４  桁上がり秘密計算部
３０５  繰りこみ秘密計算部
４００、４００Ａ  ビット結合秘密計算装置
４０２  部分分散情報抽出部
４０３  全加算器秘密計算部
４０４  桁上がり秘密計算部
４０５  繰りこみ秘密計算部
５００  装置
５０１  プロセッサ
５０２  記憶装置
５０３  表示装置
５０４  通信インタフェース
【図１】
2019087317.tif 000003
【図２】
2019087317.tif 000004
【図３】
2019087317.tif 000005
【図４】
2019087317.tif 000006
【図５】
2019087317.tif 000007
【図６】
2019087317.tif 000008
【図７】
2019087317.tif 000009
【図８】
2019087317.tif 000010
【図９】
2019087317.tif 000011
【図１０】
2019087317.tif 000012
【図１１】
2019087317.tif 000013
【国際調査報告】
2019087317.tif 000014
2019087317.tif 000015
2019087317.tif 000016
2019087317.tif 000017