(57)【要約】  加算が容易であり乗算に必要な通信と計算の量が少ない秘密計算を実現する。秘密計算システムは、３台の秘密計算装置を備えている。第i番目の秘密計算装置（i = 1, 2, 3）は、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持する保持部と、S[i]とS'[i]の論理積を求める第１の乗算部と、T[i]とT'[i]の論理積を求める第２の乗算部と、第１の乗算部が求めた論理積と、第２の乗算部が求めた論理積との差を求める第１の減算部と、を備えている。
2017038761.tif 000002
【特許請求の範囲】
【請求項１】
３台の秘密計算装置を備えた秘密計算システムであって、
第i番目の秘密計算装置（i = 1, 2, 3）は、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持する保持部と、
S[i]とS'[i]の論理積を求める第１の乗算部と、
T[i]とT'[i]の論理積を求める第２の乗算部と、
前記第１の乗算部が求めた論理積と、前記第２の乗算部が求めた論理積との差を求める第１の減算部と、を有する、
ことを特徴とする秘密計算システム。
【請求項２】
R[1], R[2], R[3]およびR'[1], R'[2], R'[3]を、R[1] + R[2] + R[3] = 0 mod Q（Qは3と互いに素な整数である）, R'[1] + R'[2] + R'[3] = 0 mod Qを満たすnビットの乱数とした場合、前記分散値は、
(S[1], T[1]) = (R[1], R[3] - W mod Q), 
(S[2], T[2]) = (R[2], R[1] - W mod Q), 
(S[3], T[3]) = (R[3], R[2] - W mod Q), 
(S'[1], T'[1]) = (R'[1], R'[3] - W' mod Q), 
(S'[2], T'[2]) = (R'[2], R'[1] - W' mod Q), 
(S'[3], T'[3]) =  (R'[3], R'[2] - W' mod Q)である、
請求項１に記載の秘密計算システム。
【請求項３】
前記保持部は、前記第１および第２の乗算部ならびに前記第１の減算部を用いて算出された局所積要素U[i] = (S[i]・S'[i] - T[i]・T'[i])/3 mod Q（Qは3と互いに素な整数）を保持し、
前記第i番目の秘密計算装置（i = 1, 2, 3）は、それぞれ、V[1], V[2], V[3]を、V[1] + V[2] + V[3] = 0 mod Qを満たすnビットの乱数とした場合、
U[i]とV[i]の和X[i]を求める加算部と、
前記加算部によって算出された和X[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するとともに、第(i mod 3 + 1)番目の秘密計算装置の前記加算部によって算出された和X[i mod 3 + 1]を受信する通信部と、
前記和X[i]および前記和X[i mod 3 + 1]を用いた加減算に基づいて、積W・W'の分散値(S"[i], T"[i])を算出する加減算部と、を備える、
請求項１または２に記載の秘密計算システム。
【請求項４】
前記分散値は(S"[i], T"[i]) = (X[i] - X[i mod 3 + 1] mode Q, -2X[i] - X[i mod 3 + 1])である、
請求項３に記載の秘密計算システム。
【請求項５】
前記第i番目の秘密計算装置（i = 1, 2, 3）は、それぞれ、
Kビット（Kは自然数）の鍵L[i]を生成する鍵生成部と、
Kビットの鍵からnNビット（Nは自然数）の乱数を生成する疑似乱数生成部と、
nNビットの２つの数からnビットごとに抽出してmod Q（Qは3と互いに素な整数）上の差を算出する第２の減算部と、を備え、
前記通信部は、前記鍵L[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するとともに、第(i mod 3 + 1)番目の秘密計算装置の前記鍵生成部によって算出された鍵L[i mod 3 + 1]を受信し、
前記疑似乱数生成部は、前記鍵L[i]に基づいて第１の疑似乱数を生成するとともに、前記鍵L[i mod 3 + 1]に基づいて第２の疑似乱数を生成し、
前記第２の減算部は、前記第１の疑似乱数および前記第２の疑似乱数をnビットごとに抽出してmod Q上の差を算出する、
請求項１ないし４のいずれか１項に記載の秘密計算システム。
【請求項６】
前記i番目の秘密計算装置（i = 1, 2, 3）の前記加算部は、前記第２の減算部によって算出された値を前記乱数V[i]として使用する、
請求項５に記載の秘密計算システム。
【請求項７】
請求項１ないし６のいずれか１項に記載の秘密計算システムに含まれる一の秘密計算装置。
【請求項８】
３台の秘密計算装置を用いた秘密計算方法であって、
第i番目の秘密計算装置（i = 1, 2, 3）が、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持するステップと、
S[i]とS'[i]の論理積を第１の論理積として求めるステップと、
T[i]とT'[i]の論理積を第２の論理積として求めるステップと、
前記第１の論理積と、前記第２の論理積との差を求めるステップと、を含む、
ことを特徴とする秘密計算方法。
【請求項９】
R[1], R[2], R[3]およびR'[1], R'[2], R'[3]を、R[1] + R[2] + R[3] = 0 mod Q（Qは3と互いに素な整数）, R'[1] + R'[2] + R'[3] = 0 mod Qを満たすnビットの乱数とした場合、前記分散値は、
(S[1], T[1]) = (R[1], R[3] - W mod Q), 
(S[2], T[2]) = (R[2], R[1] - W mod Q), 
(S[3], T[3]) = (R[3], R[2] - W mod Q), 
(S'[1], T'[1]) = (R'[1], R'[3] - W' mod Q), 
(S'[2], T'[2]) = (R'[2], R'[1] - W' mod Q), 
(S'[3], T'[3]) =  (R'[3], R'[2] - W' mod Q)である、
請求項８に記載の秘密計算方法。
【請求項１０】
前記第i番目の秘密計算装置（i = 1, 2, 3）が、それぞれ、前記求めた差を用いて算出された局所積要素U[i] = (S[i]・S'[i] - T[i]・T'[i])/3 mod Q（Qは3と互いに素な整数）を保持するステップと、
V[1], V[2], V[3]を、V[1] + V[2] + V[3] = 0 mod Qを満たすnビットの乱数とした場合、
U[i]とV[i]の和X[i]を求めるステップと、
前記算出された和X[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するステップと、
第(i mod 3 + 1)番目の秘密計算装置によって算出された和X[i mod 3 + 1]を受信するステップと、
前記和X[i]および前記和X[i mod 3 + 1]を用いた加減算に基づいて、積W・W'の分散値(S"[i], T"[i])を算出するステップと、を含む、
請求項８または９に記載の秘密計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
［関連出願についての記載］
本発明は、日本国特許出願：特願２０１５−１６９９９２号（２０１５年８月３１日出願）に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、秘密計算装置、秘密計算システム、および、秘密計算方法に関し、特に、複数の秘密計算装置が互いに通信しつつ与えられた関数の出力を計算し、所定の数の秘密装置の間でデータを共有しない限り、関数に対する入力および出力の情報を得ることができない秘密計算システム、かかる秘密計算システムを構成する秘密計算装置、および、秘密計算システムによる秘密計算方法に関する。
【背景技術】
【０００２】
非特許文献１には、ある体上の値である、秘密Sを、この体上の多項式FでF(0) = Sを満たす多項式Fを用いて複数の装置に分散する秘密計算方法が記載されている。【０００３】
また、非特許文献２には、装置の数が２つの場合における秘密計算方法に関する記載がある。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Tal Rabin, Michael Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract)," STOC 1989, pp. 73-85.
【非特許文献２】Oded Goldreich, Ronen Vainish, "How to Solve any Protocol Problem - An Efficiency Improvement," CRYPTO 1987, pp. 73-86.
【発明の概要】
【発明が解決しようとする課題】
【０００５】
非特許文献１、２の全開示内容は、本書に引用をもって繰り込み記載されているものとする。以下の分析は、本発明者によってなされたものである。【０００６】
非特許文献１に記載された方法では、ある体上の値（秘密S）を、この体上の多項式FでF(0) = Sを満たす多項式Fを使用して複数の装置に分散する。ここで、装置の数をN、装置の個数がK未満であれば関数の入力や出力に関する情報を得ることができないものとする。また、各装置に対して、この体上の異なる値が割り当てられているものとする。具体的に、装置iに割り当てられている体の値をX[i]とする（i = 1, …, N）。秘密Aをこれらの複数の装置に分散するとき、i番目の装置にはF(0) = Aなるランダムに選ばれた(K - 1)次多項式Fに関するF[i] := F(X[i])を配布する。秘密Bに関しても、同様にG(0) = Bなる(K - 1)次多項式Gに関するG[i] := G(X[i])をi番目の装置に配布する。K個以上の装置が集まると、(K - 1)次多項式F, G（すなわち、FやGの係数）を求めることができる。すなわち、F(0)やG(0)を計算することが可能となり、秘密A, Bが求められる。【０００７】
このとき、A + Bを分散した値を計算するには、i番目の装置は H[i] = F[i] + G[i]を計算する。この値はFとGのそれぞれ対応する係数を足したものを係数とする多項式Hに、X[i]を代入して得られるH(X[i])である。したがって、AやBと同様に、A + Bも複数の装置で分散したものとなる。AやBの場合と同様に、K個以上の装置が集まれば(K - 1)次多項式H（すなわち、多項式Hの係数）を求めることができる。すなわち、H(0)を計算することが可能となり、秘密A + Bが求められる。【０００８】
また、2K ≦ N + 1の場合、A*Bを分散した値を計算するには、i番目の装置は H[i] = F[i]*G[i]を計算する。この値は2K次多項式H(X) = F(X)*G(X)にX[i]を代入して得られるH(X[i])である。したがって、AやBと同様に、A*Bも複数の装置で分散したものとなる。ただし、AやBの場合とは異なり、Hの次数は2Kとなる。したがって、2K個以上の装置が集まると、2K次多項式H（すなわち、多項式Hの係数）を求めることができ、H(0)を計算することが可能になる。ここで、A*Bの分散方法は、AやBとは分散のされ方が異なる。A*BをAやBと同様に(K - 1)次多項式を用いた形で分散するには、i番目の装置がH[i]から(K - 1)次多項式Gを生成して、他のj番目の装置にG(X[j])を配布する方法が用いられる。このようにして、加算と乗算から成るすべての関数を計算することが可能となる。【０００９】
非特許文献１に記載された方法によると、体上の乗算と加算が容易に行われる。ただし、条件として2K  ≦  N  +  １が課される。また、Kが2以上でなければ、単独の装置で秘密を求めることができる。そこで、Nを３以上とする必要がある。異なるiについてX[i]は異なる値でなければならないため、利用できる体にGF(2)は含まれない。利用できる体にGF(2)が含まれないため、加算を用いて排他的論理和とすることはできない。【００１０】
非特許文献２には、装置の数が２つの場合の方法に関する記述がある。この方法では、２つの装置がビット、すなわちGF(2)上のある要素bを分散して保持する場合、b + c = b mod 2となるbとcを、それぞれの装置で分散して保持する。かかる方法を使用すると、あるビットAとあるビットBを装置１と装置２で分散する場合、A = C + D mod 2, B = E + F mod 2として、装置１はCとEを、装置２はDとFを保持する。このとき、AとBの排他的論理和GはG = A + B mod 2となり、これらの装置１と装置２との分散は、それぞれ、H = C + E mod 2とJ = D + F mod 2とすることができる。それぞれの装置は、他の装置と通信することなく、分散された２つの値の排他的論理和の分散を少ない計算量で計算することができる。【００１１】
同様に、AとBが分散されて保持されている場合、この２つのビットの論理積 K = A・Bのそれぞれの分散、すなわちL + M = K mod 2なるLとMを、装置１がLを得るとともに装置２がMを得るように行うには、次のようにする。装置１は、Lをランダムに生成する。このとき、M = (C + D)・(E + F) = L mod 2である。そこで、装置２が持つ値DとFに応じて、装置１はMの値を知ることなく、(D, F)=(0, 0)ならM = (C + 0)・(E + 0) + L mod 2を、(D, F)=(0, 1)ならM = (C + 0)・(1 + E)+L mod 2を、(D, F)=(1, 0)ならM = (1 + C)・(E + 0) + L mod 2 を、(D, F)=(1, 1)ならM = (1 + C)・(1 + E) + L mod 2 を装置２に返す。すなわち、装置１は、装置２の入力に依存する値を装置２に送付する。装置１が装置２の入力を知ることができないようにする方法は、装置１と装置２の間のoblivious transferと呼ばれる技術によって実現される。しかし、かかる技術によると、装置１、２において多くの計算と通信が必要とされる。【００１２】
非特許文献１に記載された方法によると、少ない通信と少ない計算量で論理積を分散して計算することが可能となる。しかし、非特許文献１に記載された方法によると、排他的論理和を分散して計算する際にも、論理積の計算のときと同様に、通信と若干の計算が必要とされる。【００１３】
一方、非特許文献２に記載された方法によると、排他的論理和を分散して計算する際に通信を要しないという利点がある。しかし、非特許文献２に記載された方法によると、論理積については、通信も計算も必要となる。【００１４】
したがって、ビット、すなわちGF(2) の元の排他的論理和を、複数の装置で分散したまま計算しつつ、これらの装置間に通信が発生せず、ビットの論理積も少ない通信量と計算量で分散したまま計算できるようにすることが望まれる。これを実現することにより、任意の関数を論理ゲートに分解し、排他的論理和と論理積で記述することにより、この関数を複数の装置で分散したまま、かつ、いずれの装置もデータを知る（計算する）ことなく高速に計算することが可能となる。【００１５】
本発明の目的は、加算が容易であり乗算に必要な通信と計算の量が少ない秘密計算を実現する秘密計算システム、秘密計算装置、および、秘密計算方法を提供することにある。
【課題を解決するための手段】
【００１６】
本発明の第１の態様に係る秘密計算システムは、３台の秘密計算装置を備えている。第i番目の秘密計算装置（i = 1, 2, 3）は、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持する保持部を有する。また、第i番目の秘密計算装置は、S[i]とS'[i]の論理積を求める第１の乗算部と、T[i]とT'[i]の論理積を求める第２の乗算部とを有する。さらに、第i番目の秘密計算装置は、前記第１の乗算部が求めた論理積と、前記第２の乗算部が求めた論理積との差を求める第１の減算部を有する。【００１７】
本発明の第２の態様に係る秘密計算装置は、上記の秘密計算システムに含まれる一の秘密計算装置である。【００１８】
本発明の第３の態様に係る秘密計算方法は、３台の秘密計算装置を用いた秘密計算方法である。秘密計算方法は、第i番目の秘密計算装置（i = 1, 2, 3）が、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持するステップを含む。また、秘密計算方法は、S[i]とS'[i]の論理積を第１の論理積として求めるステップと、T[i]とT'[i]の論理積を第２の論理積として求めるステップとを含む。さらに、秘密計算方法は、前記第１の論理積と、前記第２の論理積との差を求めるステップを含む。
【発明の効果】
【００１９】
本発明に係る秘密計算システム、秘密計算装置、および、秘密計算方法によると、加算が容易であり乗算に必要な通信と計算の量が少ない秘密計算を実現することができる。
【図面の簡単な説明】
【００２０】
【図１】一実施形態に係る秘密計算システムの構成を例示するブロック図である。
【図２】第１の実施形態に係る秘密計算システムの構成を示す図である。
【図３】第１の実施形態に係る秘密計算システムにおける秘密計算装置の構成を例示するブロック図である。
【図４】第２の実施形態に係る秘密計算システムにおける秘密計算装置の構成を例示するブロック図である。
【発明を実施するための形態】
【００２１】
はじめに、一実施形態の概要について説明する。なお、この概要に付記する図面参照符号は、専ら理解を助けるための例示であり、本発明を図示の態様に限定することを意図するものではない。
【００２２】
図１は、一実施形態に係る秘密計算システム１００の構成を例示するブロック図である。図１を参照すると、秘密計算システム１００は、３台の秘密計算装置１０、２０、３０を備えている。ここでは、秘密計算装置１０、２０、３０を、それぞれ、第１番目〜第３番目の秘密計算装置とする。第i番目の秘密計算装置（i = 1, 2, 3）は、nビット（nは任意の自然数）の数WおよびnビットのW'の分散値として、それぞれ、(S[i], T[i])および(S'[i], T'[i])を保持する保持部１２と、S[i]とS'[i]の論理積を求める第１の乗算部１４と、T[i]とT'[i]の論理積を求める第２の乗算部１６と、第１の乗算部１４が求めた論理積と、第２の乗算部１６が求めた論理積との差を求める第１の減算部１８と、を有する。
【００２３】
また、R[1], R[2], R[3]およびR'[1], R'[2], R'[3]を、R[1] + R[2] + R[3] = 0 mod Q, R'[1] + R'[2] + R'[3] = 0 mod Qを満たすnビットの乱数とした場合、分散値は、
(S[1], T[1]) = (R[1], R[3] - W mod Q), 
(S[2], T[2]) = (R[2], R[1] - W mod Q), 
(S[3], T[3]) = (R[3], R[2] - W mod Q), 
(S'[1], T'[1]) = (R'[1], R'[3] - W' mod Q), 
(S'[2], T'[2]) = (R'[2], R'[1] - W' mod Q), 
(S'[3], T'[3]) =  (R'[3], R'[2] - W' mod Q)とすることができる。ここで、Qは3と互いに素な整数（例えば、nを自然数としてQ = 2^n）である。
【００２４】
かかる秘密計算システムによると、第i番目の装置は第１、第２の乗算部および第１の減算部を用いて局所積要素U[i] = (T[i]・T’[i] - S[i]・S’[i])/3 mod Qを求めることができる。ここで、U[1] + U[2] + U[3] = WW’ mod Qであるから、３台の装置が協力することによって論理積W" = W・W’ mod Qを復元することができる。一実施形態の秘密計算システムによると、装置間で通信を行うことなく加算の計算が可能となり、少ない計算量で論理積の計算が可能となる。
【００２５】
＜実施形態１＞
次に、第１の実施形態に係る秘密計算システムについて、図面を参照して説明する。
【００２６】
図２は、本実施形態に係る秘密計算システム１００の構成を例示する図である。図２を参照すると、秘密計算システム１００は、３台の秘密計算装置１０、２０、３０を備えている。
【００２７】
図３は、秘密計算装置１０の構成を例示するブロック図である。秘密計算装置２０、３０も、秘密計算装置１０と同様の構成を有する。図３を参照すると、秘密計算装置１０は、局所乗算部３６、積再分配部３８、および、通信部２４を備えている。局所乗算部３６は、保持部１２、乗算部１４、１６、および、減算部１８を備えている。一方、積再分配部３８は、加算部２２および加減算部２６を備えている。
【００２８】
秘密計算装置１０、２０、３０は、値Wを分散して保持する。１以上の整数であるnに対して、R[1] + R[2] + R[3] = 0 mod Qなる３つのランダムに選ばれた数R[1], R[2], R[3]を用いて、秘密計算装置１０の保持部１２は(R[1], R[3] - W mod Q)を保持する。同様に、秘密計算装置２０の保持部１２は(R[2], R[1] - W mod Q)を保持し、秘密計算装置３０の保持部１２は(R[3], R[2] - W mod Q)を保持する。ここで、Qは3と互いに素な整数（例えば、nを自然数としてQ = 2^n）である。
【００２９】
３台の秘密計算装置１０、２０、３０のうちの２台が協力するとWを復元することができる。一般性を失うことなく、秘密計算装置１０と秘密計算装置２０が協力する場合に、かかる復元方法を説明することができる。すなわち、秘密計算装置１０の保持部１２が保持するR[1]と、秘密計算装置２０の保持部１２が保持するR[1] - W mod Qを用いて、W = R[1] - (R[1] - W) mod Qを計算することで、値Wを復元することができる。
【００３０】
（通信を伴わない加算）
次に、秘密計算装置１０、２０、３０の間での通信を行うことなく、加算が可能であることを説明する。ビットWとW’がそれぞれ秘密計算装置１０、２０、３０に分散されているときに、分散されたままで、これらの加算を計算するには、以下のようにする。
【００３１】
ここで、ビットWは、次のように秘密計算装置１０、２０、３０に分散されているものとする。すなわち、R[1] + R[2] + R[3] = 0 mod 2を満たす３つのランダムに選ばれたビットR[1], R[2], R[3]を用いて、秘密計算装置１０の保持部１２は(S[1], T[1]) := (R[1], W + R[2] mod 2)を保持する。同様に、秘密計算装置２０の保持部１２は(S[2], T[2]) := (R[2], W + R[3] mod 2)を保持し, 秘密計算装置３０の保持部１２は(S[3], T[3]) = (R[3], W + R[1] mod 2) を保持する。
【００３２】
一方、ビットW'は次のように秘密計算装置１０、２０、３０に分散されているものとする。すなわち、R’[1] + R’[2] + R’[3] = 0 mod 2なる３つのランダムに選ばれたビットR'[1], R'[2], R'[3]を用いて、秘密計算装置１０の保持部１２は(S’[1], T’[1]) =(R’[1], W’ + R’[2] mod 2)を保持する。同様に、秘密計算装置２０の保持部１２は(S’[2], T’[2]) := (R’[2], W’ + R’[3] mod 2)を保持し, 秘密計算装置３０の保持部１２は(S’[3], T’[3]) := (R’[3], W’ + R’[1] mod 2)を保持するものとする。
【００３３】
このとき、秘密計算装置１０は(S"[1], T"[1]) = (S[1] + S’[1] mod 2, T[1] + T’[1] mod 2)を計算する。同様に、秘密計算装置２０は(S"[2], T"[2]) = (S[2] + S’[2] mod 2, T[2] + T’[2] mod 2)を計算する。また、秘密計算装置３０は(S"[3], T"[3]) = (S[3] + S’[3] mod 2, T[3] + T’[3] mod 2)を計算する。秘密計算装置１０、２０、３０は、それぞれの計算結果をもってW" = W + W’ mod 2を分散して保持したとする。これらの結果から、元のWまたはW’と同様に、W"を復元することが可能となる。したがって、秘密計算装置１０、２０、３０の間で通信を行うことなく、加算を計算することができる。
【００３４】
（否定）
次に、否定の計算について説明する。ビットWが装置１０、２０、３０に分散されているときに、分散されたままでビットWの否定を計算するには、次のようにする。
【００３５】
ビットWは、次のように秘密計算装置１０、２０、３０に分散されているものとする。すなわち、R[1] + R[2] + R[3] = 0 mod 2なる３つのランダムに選ばれたビットR[1], R[2], R[3]を用いて、秘密計算装置１０の保持部１２は(S[1], T[1]) := (R[1], W + R[2] mod 2)を保持する。同様に、秘密計算装置２０の保持部１２は(S[2], T[2]) := (R[2], W + R[3] mod 2)を保持する。また、秘密計算装置３０の保持部１２は(S[3], T[3]) = (R[3], W + R[1] mod 2)を保持する。
【００３６】
このとき、秘密計算装置１０は(S’[1], T’[1]) = (S[1], T[1] + 1 mod 2)を計算する。同様に、秘密計算装置２０は(S’[2], T’[2]) = (S[2], T[2] + 1 mod 2)を計算する。また、秘密計算装置３０は(S’[3], T’[3]) = (S[3], T[3] + 1 mod 2)を計算する。秘密計算装置１０、２０、３０は、それぞれの計算結果をもってW’ = W + 1 mod 2を分散して保持したとする。これらの結果から、元のWと同様にW’を復元することができる。したがって、秘密計算装置１０、２０、３０の間で通信を行うことなく、否定を計算することができる。
【００３７】
（論理積）
次に、論理積の計算について説明する。論理積の計算において、図３に示した局所乗算部３６および積再分配部３８を使用する。ビットWとW’がそれぞれ、秘密計算装置１０、２０、３０に分散されているときに、分散されたままでこれらの論理積W" = W・W' mod Qを計算するには、次のようにする。
【００３８】
ビットWは、次のように秘密計算装置１０、２０、３０に分散されているものとする。すなわち。R[1] + R[2] + R[3] = 0 mod Qなる３つのランダムに選ばれた数R[1], R[2], R[3]を用いて、秘密計算装置１０の保持部１２は(S[1], T[1]) :=(R[1], R[3] - W mod Q)を保持する。同様に、秘密計算装置２０の保持部１２は(S[2], T[2]) := (R[2], R[1] - W mod 2)を保持する。また、秘密計算装置３０の保持部１２は(S[3], T[3]) = (R[3], R[2] - W mod Q)を保持する。
【００３９】
一方、ビットW'は次のように秘密計算装置１０、２０、３０に分散されているものとする。すなわち、R’[1] + R’[2] + R’[3] = 0 mod Q なる３つのランダムに選ばれた数R'[1], R'[2], R'[3]を用いて、秘密計算装置１０の保持部１２は(S’[1], T’[1]) = (R’[1], R’[3] - W’ mod Q)を保持する。同様に、秘密計算装置２０の保持部１２は(S’[2], T’[2]) := (R’[2], R’[1] - W’ mod Q)を保持する。また、秘密計算装置３０の保持部１２は(S’[3], T’[3]) := (R’[3], R’[2] - W’ mod Q)を保持する。
【００４０】
このとき、秘密計算装置１０の局所乗算部３６において、乗算部１４は、保持部１２が保持する第１入力第１要素S[1]と第２入力第１要素S’[1]の論理積を求めて減算部１８に出力する。一方、乗算部１６は、第１入力第２要素T[2]と第２入力第２要素T’[1]の論理積を求めて減算部１８に出力する。減算部１８は、乗算部１４、１６からの出力に基づいて、局所積要素U[1] = (T[1]・T’[1] - S[1]・S’[1])/3 mod Qを算出する。
【００４１】
同様に、秘密計算装置２０の局所乗算部３６は局所積要素U[2] = (T[2]・T’[2]-S[2]・S’[2])/3 mod Qを算出する。また、秘密計算装置３０の局所乗算部３６は局所積要素U[3] = (T[3]・T’[3] - S[3]・S’[3])/3 mod Qを算出する。秘密計算装置１０、２０、３０は、それぞれの計算結果をもってW" = W・W’ mod Qを分散して保持したとする。
【００４２】
このとき、各秘密計算装置が算出した局所積要素のみから、元のWあるいはW’と同様に、論理積W"も復元することはできない。各秘密計算装置が算出した局所積要素から直接論理積W"を復元するには、W" = U[1] + U[2] + U[3] mod Qと計算すればよい。論理積W"の復元が可能であることは、次の計算によって示される。
【００４３】
U[1] + U[2] + U[3] 
= {(T[1]・T’[1] - S[1]・S’[1]) + (T[2]・T’[2] - S[2]・S’[2]) + (T[3]・T’[3] - S[3]・S’[3])}/3 mod Q
= {-S[1]S’[1] + (R[3] - W)(R’[3] - W’) - S[2]S’[2] + (R[1] - W)(R’[1] - W’) - S[3]S’[3] + (R[2] - W)(R’[2] - W’)}/3 mod Q
= {-R[1]R’[1] + R[3]R’[3] - R[3]W’ - W R’[3] + WW’
- R[2]R’[2] + R[1]R’[1] - R[1]W’ - W R’[1] + WW’
- R[3]R’[3] + R[2]R’[2] - R[2]W’ - W R’[2] + WW’}/3 mod Q
= 3WW’/3 mod Q
= WW’ mod Q
【００４４】
なお、Qと3は互いに素であることから、mod Q上での3の逆数は必ず計算することができる。
【００４５】
以上より、(U[1], U[2], U[3])はW・W’を３つの値に分散したものとなる。同様に、(U’[1],U’[2],U’[3])がZ = U’[1] + U’[2] + U’[3] mod QなるZを３つの値に分散したものであるとき、W・W’ + Z mod Qは、(U[1] + U’[1] mod Q, U[2] + U’[2] mod Q, U[3] + U’[3] mod Q)の３つの値に分散される。秘密計算装置１０がU[1]とU’[1]を保持し、秘密計算装置２０がU[2]とU’[2]を保持し、秘密計算装置３０がU[3]とU’[3]を保持しているとする。この場合、新たに分散された値は、それぞれの秘密計算装置が他の秘密計算装置と通信することなく計算することができる。すなわち、ある関数がmodQ上の和と積で構成されている場合、次の積の入力となるまでの間、何度でも互いに通信することなく和の計算を実行することができる。積を計算した結果を用いた積を計算する場合、次の処理を実施すればよい。
【００４６】
論理積W"をWやW’と同様の形式で３台の秘密計算装置に分散するには、秘密計算装置１０、２０、３０の積再分配部３８を用いる。
【００４７】
ここでは、V[1] + V[2] + V[3] = 0 mod Qとなるランダムに選ばれたマスクV[1], V[2], V[3]が存在し、秘密計算装置１０にはマスクV[1]、秘密計算装置２０にはマスクV[2]、秘密計算装置３０にはマスクV[3]が予め渡されているものとする。
【００４８】
秘密計算装置１０、２０、３０は、渡されたマスクV[i]を積再分配部３８に入力する。秘密計算装置３０の加算部２２はX[3] = U[3] + V[3] mod Qのように局所積要素U[3]とマスクV[3]の和をとり、結果を第１和X[3]とする。また、秘密計算装置３０の通信部２４は、求めた第１和X[3]を秘密計算装置２０に送信する。同様に、秘密計算装置２０の加算部２２は第１和X[2] = U[2] + V[2] mod n^2を生成し、生成した第１和X[2]を秘密計算装置２０の通信部２４を介して秘密計算装置１０に送信する。また、秘密計算装置１０の加算部２２は第１和X[1] = U[1] + V[1] mod Qを生成し、生成した第１和X[1]を秘密通信装置１０の通信部２４を介して秘密計算装置３０に送信する。
【００４９】
秘密計算装置１０、２０、３０は、それぞれ、通信部２４から第１和X[2], X[3], X[1]を受け取り、受け取った第１和X[2], X[3], X[1]を加減算部２６に出力する。秘密計算装置１０、２０、３０は、それぞれの加算部２２が算出した第１和X[1], X[2], X[3]と、受信した第１和X[2], X[3], X[1]とを用いて、出力第１要素S"[i]と出力第２要素T"[i]を算出する。具体的には、秘密計算装置１０の加減算部２６は(S"[1], T"[1]) = (X[1] - X[2] mod Q, - 2X[1] - X[2] mod Q)を算出する。同様に、秘密計算装置２０の加減算部２６は(S"[2], T"[2]) = (X[2] - X[3] mod Q, - 2X[2] - X[3] mod Q)を算出する。また、秘密計算装置３０の加減算部２６は(S"[3], T"[3]) = (X[3] - X[1] mod Q, -2X[3] - X[1] mod Q)を算出する。
【００５０】
WとW’と同様に論理積W"の値を２台の秘密計算装置から復元できることは、一般性を失うことなく、秘密計算装置１０と秘密計算装置２０が協力する場合の復元方法に基づいて説明することができる。すなわち、秘密計算装置１０からの出力第１要素S"[1]と、秘密計算装置２０からの出力第２要素T"[2]を用いて、次のように論理積W"を復元することができる。
【００５１】
W・W’ = S"[1] - T"[2] mod Q 
= U[1] + V[1] + U[2] + U[3] + V[2] + V[3] mod Q 
= U[1] + U[2] + U[3] mod Q 
= W"
【００５２】
また、以下の計算から、論理積W"がWやW’と同様に分散されていることが分かる。
【００５３】
S"[1] + S"[2] + S"[3] mod Q 
= X[1] - X[2] + X[2] - X[3] + X[3] - X[1] mod Q
= 0 mod Q
【００５４】
（効果）
本実施形態に係る秘密計算システムを用いれば、３つの秘密計算装置に分散されて保持された２つの値のmod Q上の和を、これら秘密計算装置が互いに通信することなく計算し、３つの秘密計算装置に分散された形で保持することが可能となる。ここで、和の計算結果を保持する方法は、最初に２つのそれぞれのビットを保持する方法と同一である。
【００５５】
また、本実施形態の秘密計算システムによると、３つの秘密計算装置に分散されて保持された２つの値のmod Q上の積を、これら秘密計算装置が互いに通信しつつ計算することで、３つの秘密計算装置に分散された形で保持することが可能となる。このときに発生する通信量は全体として3nビットにすぎず、非特許文献２に記載された２つの装置間の秘密計算で必要とされる通信量と比較して格段に少ない。ここで、積の計算結果の値を保持する方法も、最初に２つ値をそれぞれ保持していたときの方法と同一である。
【００５６】
このように積と和との両方に関して、計算結果が計算の前のそれぞれの値の保持方法と同一の方法で保持される。これにより、計算結果に対して、さらに積や和の演算を続けることが可能となる。すなわち、本実施形態の秘密計算システムによると、mod Q上の和と積で記述される任意の関数を、データを分散したまま、３つの秘密計算装置を用いて少ない通信量で計算することが可能となる。
【００５７】
以上説明したように、本実施形態によれば、複数の秘密計算装置にデータを分散して各秘密計算装置にデータを隠ぺいしたままmod Q上の任意の多項式を計算することが可能になる。また、かかる計算に必要とされる通信量と計算量を関連技術と比較して削減することができる。かかる秘密計算システムによると、秘密計算装置上で秘密のデータを扱いつつ何らかのサービスを提供するときに、秘密計算装置の管理者がデータを盗み出すことを防止することにも寄与する。なぜなら、複数の秘密計算装置に対して異なる管理者を割り当てることにより、すべての秘密計算装置中のデータを参照することができる管理者が存在しなくなり、管理者を通じたデータの盗み出しを防止することができるからである。
【００５８】
＜実施形態２＞
次に、第２の実施形態に係る秘密計算システムについて、図面を参照して説明する。図４は、本実施形態の秘密計算システムにおける秘密計算装置１０の構成を例示するブロック図である。秘密計算装置２０、３０も、秘密計算装置１０と同様の構成を有する。
【００５９】
図４を参照すると、本実施形態では、秘密計算装置１０は、第１の実施形態の秘密計算装置１０（図３）に対して、さらにマスク生成部４２を備えている。マスク生成部４２は、鍵生成部２８、疑似乱数生成部３２、および、減算部３４を備えている。なお、本実施形態における局所乗算部３６および積再分配部３８の動作は、第１の実施形態におけるこれらの要素の動作と同様であるから、説明を省略する。
【００６０】
第１の実施形態では、秘密計算装置１０、２０、３０がそれぞれランダムなビットV[1], V[2], V[3]をマスクとして受け取り、V[1] + V[2] + V[3] = 0 mod Qを満たしているものと仮定した。このようなランダムなビットは、積を１つ計算するたびに一揃い必要とされる。したがって、大量の積を計算する場合、V[i,1] + V[i,2] + V[i,3] = 0 mod Q を満たすV[i,1], V[i,2], V[i,3]を多数のi = 1, …, Nに関して生成しておくことが望ましい。本実施形態では、マスク生成部４２を用いることにより、これを実現する。
【００６１】
ここで、Kを安全変数とする。秘密計算装置１０、２０、３０の鍵生成部２８は、それぞれ、Kビットの鍵L[1], L[2], L[3]を生成する。秘密計算装置１０の通信部２４は、生成された鍵L[1]を秘密計算装置３０に送信する。同様に、秘密計算装置２０の通信部２４は生成された鍵L[2]を秘密計算装置１０に送信する。また、秘密計算装置３０の通信部２４は生成された鍵L[3]を秘密計算装置２０へ送信する。
【００６２】
秘密計算装置１０、２０、３０の通信部２４は、それぞれ、秘密計算装置２０、３０、１０から鍵L[2], L[3], L[1]を受信する。以下では、受け取った鍵を受信鍵と呼ぶ。
【００６３】
疑似乱数生成部３２は、疑似乱数生成器PRGを有する。ここで、PRGはKビットの文字列からnNビットの文字列を出力する疑似乱数生成器である。秘密計算装置１０の疑似乱数生成部３２は鍵L[1]から第１疑似乱数PRG(L[1])を生成するとともに、受信鍵L[2]から第２疑似乱数PRG(L[2])を生成する。減算部３４は、第１疑似乱数PRG(L[1])および第２疑似乱数PRG(L[2])をnビット毎に分割して、それぞれmod Q上の差を求めることにより、nビットの乱数をN個生成する。ここで、最初からi番目のnビット乱数をV[i.1]とする(i = 1, …, N)。
【００６４】
同様に、秘密計算装置２０は疑似乱数生成部３２を用いて第１疑似乱数PRG(L[2])および第２疑似乱数PRG(L[3])を生成し、減算部３４を用いて第１疑似乱数PRG(L[2])と第２疑似乱数PRG(L[3])からnビットの乱数N個の列を生成する。ここで、最初からi番目のnビット乱数をV[i.2]とする(i = 1, …, N)。また、秘密計算装置３０は疑似乱数生成部３２を用いて第１疑似乱数PRG(L[3])および第２疑似乱数PRG(L[1])を生成し、減算部３４を用いて第１疑似乱数PRG(L[3])と第２疑似乱数PRG(L[1])から同様にnビットの乱数N個の列を生成する。ここで、最初からi番目のnビット乱数をV[i.3]とする(i = 1, …, N)。
【００６５】
秘密計算装置１０のマスク生成部４２は、生成した乱数V[i,1] (i = 1, …, N)を積再分配部３８の加算部２２に供給する。同様に、秘密計算装置２０のマスク生成部４２は、生成した乱数V[i,2]を積再分配部３８の加算部２２に供給する。また、秘密計算装置３０のマスク生成部４２は、生成した乱数V[i,3]を積再分配部３８の加算部２２に供給する。
【００６６】
本実施形態に係る秘密計算システムによると、第１の実施形態に係る秘密計算システムと同様の効果がもたらされる。さらに、本実施形態の秘密計算システムによると、マスク生成部によって生成されたマスクを利用することにより、大量の積の秘密計算を高速に実行することが可能となる。
【００６７】
なお、本発明において、下記の形態が可能である。
［形態１］
上記第１の態様に係る秘密計算システムのとおりである。
［形態２］
R[1], R[2], R[3]およびR'[1], R'[2], R'[3]を、R[1] + R[2] + R[3] = 0 mod Q（Qは3と互いに素な整数）, R'[1] + R'[2] + R'[3] = 0 mod Qを満たすnビットの乱数とした場合、前記分散値は、
(S[1], T[1]) = (R[1], R[3] - W mod Q), 
(S[2], T[2]) = (R[2], R[1] - W mod Q), 
(S[3], T[3]) = (R[3], R[2] - W mod Q), 
(S'[1], T'[1]) = (R'[1], R'[3] - W' mod Q), 
(S'[2], T'[2]) = (R'[2], R'[1] - W' mod Q), 
(S'[3], T'[3]) =  (R'[3], R'[2] - W' mod Q)である、
形態１に記載の秘密計算システム。
［形態３］
前記保持部は、前記第１および第２の乗算部ならびに前記第１の減算部を用いて算出された局所積要素U[i] = (S[i]・S'[i] - T[i]・T'[i])/3 mod Q（Qは3と互いに素な整数）を保持し、
前記第i番目の秘密計算装置（i = 1, 2, 3）は、それぞれ、V[1], V[2], V[3]を、V[1] + V[2] + V[3] = 0 mod Qを満たすnビットの乱数とした場合、
U[i]とV[i]の和X[i]を求める加算部と、
前記加算部によって算出された和X[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するとともに、第(i mod 3 + 1)番目の秘密計算装置の前記加算部によって算出された和X[i mod 3 + 1]を受信する通信部と、
前記和X[i]および前記和X[i mod 3 + 1]を用いた加減算に基づいて、積W・W'の分散値(S"[i], T"[i])を算出する加減算部と、を備える、
形態１または２に記載の秘密計算システム。
［形態４］
前記分散値は(S"[i], T"[i]) = (X[i] - X[i mod 3 + 1] mode Q, -2X[i] - X[i mod 3 + 1])である、
形態３に記載の秘密計算システム。
［形態５］
前記第i番目の秘密計算装置（i = 1, 2, 3）は、それぞれ、
Kビット（Kは自然数）の鍵L[i]を生成する鍵生成部と、
Kビットの鍵からnNビット（Nは自然数）の乱数を生成する疑似乱数生成部と、
nNビットの２つの数からnビットごとに抽出してmod Q（Qは3と互いに素な整数）上の差を算出する第２の減算部と、を備え、
前記通信部は、前記鍵L[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するとともに、第(i mod 3 + 1)番目の秘密計算装置の前記鍵生成部によって算出された鍵L[i mod 3 + 1]を受信し、
前記疑似乱数生成部は、前記鍵L[i]に基づいて第１の疑似乱数を生成するとともに、前記鍵L[i mod 3 + 1]に基づいて第２の疑似乱数を生成し、
前記第２の減算部は、前記第１の疑似乱数および前記第２の疑似乱数をnビットごとに抽出してmod Q上の差を算出する、
形態１ないし４のいずれか一に記載の秘密計算システム。
［形態６］
前記i番目の秘密計算装置（i = 1, 2, 3）の前記加算部は、前記第２の減算部によって算出された値を前記乱数V[i]として使用する、
形態５に記載の秘密計算システム。
［形態７］
上記第２の態様に係る秘密計算装置のとおりである。
［形態８］
上記第３の態様に係る秘密計算方法のとおりである。
［形態９］
R[1], R[2], R[3]およびR'[1], R'[2], R'[3]を、R[1] + R[2] + R[3] = 0 mod Q（Qは3と互いに素な整数）, R'[1] + R'[2] + R'[3] = 0 mod Qを満たすnビットの乱数とした場合、前記分散値は、
(S[1], T[1]) = (R[1], R[3] - W mod Q), 
(S[2], T[2]) = (R[2], R[1] - W mod Q), 
(S[3], T[3]) = (R[3], R[2] - W mod Q), 
(S'[1], T'[1]) = (R'[1], R'[3] - W' mod Q), 
(S'[2], T'[2]) = (R'[2], R'[1] - W' mod Q), 
(S'[3], T'[3]) =  (R'[3], R'[2] - W' mod Q)である、
形態８に記載の秘密計算方法。
［形態１０］
前記第i番目の秘密計算装置（i = 1, 2, 3）が、それぞれ、前記求めた差を用いて算出された局所積要素U[i] = (S[i]・S'[i] - T[i]・T'[i])/3 mod Q（Qは3と互いに素な整数）を保持するステップと、
V[1], V[2], V[3]を、V[1] + V[2] + V[3] = 0 mod Qを満たすnビットの乱数とした場合、
U[i]とV[i]の和X[i]を求めるステップと、
前記算出された和X[i]を第{(i + 1 mod 3) + 1}番目の秘密計算装置に送信するステップと、
第(i mod 3 + 1)番目の秘密計算装置によって算出された和X[i mod 3 + 1]を受信するステップと、
前記和X[i]および前記和X[i mod 3 + 1]を用いた加減算に基づいて、積W・W'の分散値(S"[i], T"[i])を算出するステップと、を含む、
形態８または９に記載の秘密計算方法。
［形態１１］
前記分散値は(S"[i], T"[i]) = (X[i] - X[i mod 3 + 1] mode Q, -2X[i] - X[i mod 3 + 1])である、
形態１０に記載の秘密計算方法。
【００６８】
なお、上記非特許文献の全開示内容は、本書に引用をもって繰り込み記載されているものとする。本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の全開示の枠内において種々の開示要素（各請求項の各要素、各実施形態の各要素、各図面の各要素等を含む）の多様な組み合わせ、ないし、選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。特に、本書に記載した数値範囲については、当該範囲内に含まれる任意の数値ないし小範囲が、別段の記載のない場合でも具体的に記載されているものと解釈されるべきである。
【符号の説明】
【００６９】
１０、２０、３０    秘密計算装置
１２    保持部
１４、１６    乗算部
１８、３４    減算部
２２    加算部
２４    通信部
２６    加減算部
２８    鍵生成部
３２    擬似乱数生成部
３６    局所乗算部
３８    積再分配部
４２    マスク生成部
１００    秘密計算システム
【図１】
2017038761.tif 000003
【図２】
2017038761.tif 000004
【図３】
2017038761.tif 000005
【図４】
2017038761.tif 000006
【国際調査報告】
2017038761.tif 000007
2017038761.tif 000008
2017038761.tif 000009
2017038761.tif 000010
2017038761.tif 000011
2017038761.tif 000012