(57)【要約】処理量を少なく保ったまま、参加者の悪意のある振る舞いに対して秘密を守ることが出来る事前計算装置を提供する。ビーバー三重子生成処理部は、秘密分散された二つの乱数と、この二つの乱数の積の秘密分散された積とから成る、秘密分散されたビーバー三重子を生成する。ビーバー三重子ランダム検査処理部は、秘密分散されたビーバー三重子をランダムに選び、他の事前計算装置と通信することでビーバー三重子を復元し、復元したビーバー三重子の最初の二つの要素の積が第三の要素となっていることを確認する。ビーバー三重子位置攪拌処理部は、復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成する。
2017099117.tif 000002
【特許請求の範囲】
【請求項１】
複数の他の事前計算装置と通信可能な事前計算装置であって、
秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理部と、
前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理部と、
前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理部と、
を備える事前計算装置。
【請求項２】
前記事前計算装置は、前記複数の他の事前計算装置と当該事前計算装置との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備え、
前記ビーバー三重子位置攪拌処理部は、前記復元しなかったビーバー三重子をランダムに並び替えて、新しいインデックスを付けて並び替えた後の秘密分散されたビーバー三重子を生成し、
前記事前計算装置は、
前記並び替えた後の秘密分散されたビーバー三重子に対してその秘密分散されたメッセージ認証子を、前記秘密分散されたメッセージ認証子の鍵を使用して、当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成するビーバー三重子メッセージ認証子生成処理部と、
前記並び替えた後の秘密分散されたビーバー三重子のランダムに選んだ係数による線形和を多数生成し、この多数生成した値を復元して復元された値を生成する処理と、前記秘密分散されたビーバー三重子のメッセージ認証子を前記係数による線形和を多数生成した値と、前記復元された値を前記秘密分散されたメッセージ認証子の鍵による線形和を多数生成した値とが同一であることを確認する処理とを実施するビーバー三重子メッセージ認証子検証処理部と、
を更に備える、請求項１に記載の事前計算装置。
【請求項３】
複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置であって、
ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データが入力される事前計算入力処理部と、
乗算されるべき二つの数の組の秘密分散データが複数個入力される入力処理部と、
前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理部と、
前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理部と、
を備えるベクトル乗算装置。
【請求項４】
前記ベクトル乗算装置は、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備え、
前記事前計算入力処理部は、メッセージ認証子付ビーバー三重子の秘密分散データを生成し、あるいは前記メッセージ認証子付ビーバー三重子の秘密分散データが入力され、
前記入力処理部は、前記乗算されるべき二つの数の組の秘密分散データを複数個に加えて、前記複数個の乗算されるべき二つの数の組それぞれに対するメッセージ認証子の秘密分散データをも入力され、
前記ベクトル乗算装置は、
前記補助ベクトルに対するメッセージ認証子の秘密分散データを、前記入力に対するメッセージ認証子の秘密分散データと前記ビーバー三重子に対するメッセージ認証子の秘密分散データとから生成する補助ベクトルメッセージ認証子生成処理部と、
前記補助ベクトルに対するメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データとから、前記補助ベクトルを検証する入力正当性確認処理部と、
前記ベクトル乗算結果のメッセージ認証子の秘密分散データを、前記ビーバー三重子のメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データと、前記ビーバー三重子の秘密分散データとから、出力メッセージ認証子として生成する出力メッセージ認証子生成処理部と、
を更に備える、請求項３に記載のベクトル乗算装置。
【請求項５】
複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置であって、
請求項３に記載のベクトル乗算装置を構成する、前記事前計算入力処理部、前記入力処理部、前記補助ベクトル生成処理部、および前記ベクトル乗算処理部を、それぞれ、複数個備え、
複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理部を備える、
ベクトル乗算装置。
【請求項６】
複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置であって、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備えるベクトル乗算装置において、
請求項４に記載のベクトル乗算装置を構成する、前記事前計算入力処理部、前記入力処理部、前記補助ベクトル生成処理部、前記ベクトル乗算処理部、前記補助ベクトルメッセージ認証子生成処理部、前記入力正当性確認処理部、および前記出力メッセージ認証子生成処理部を、それぞれ、複数個備え、
複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理部を備える、
ベクトル乗算装置。
【請求項７】
複数の他の事前計算装置と通信可能な事前計算装置において行われる事前計算方法であって、
ビーバー三重子生成処理部が、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成し、
ビーバー三重子ランダム検査処理部が、前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認し、
ビーバー三重子位置攪拌処理部が、前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成する、
事前計算方法。
【請求項８】
複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置において行われるベクトル乗算方法であって、
事前計算入力処理部が、ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データを入力し、
入力処理部が、乗算されるべき二つの数の組の秘密分散データを複数個入力し、
補助ベクトル生成処理部が、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成し、
ベクトル乗算処理部が、前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成する、
ベクトル乗算方法。
【請求項９】
前記事前計算入力処理部、前記入力処理部、前記補助ベクトル生成処理部、および前記ベクトル乗算処理部が、各処理を全て複数個実施し、
結果同一確認処理部が、複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する
請求項８に記載のベクトル乗算方法。
【請求項１０】
複数の他の事前計算装置と通信可能な事前計算装置のコンピュータを、
秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理手段、
前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理手段、および
前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理手段、
として機能させるための事前計算プログラムを記録したコンピュータ読取可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、事前計算装置、方法、およびコンピュータ読取可能な記録媒体、並びにベクトル乗算装置、および方法に関する。
【背景技術】
【０００２】
秘密計算方法とは、複数の秘密計算装置が互いに通信を介しながら計算することで、与えられた関数を計算する方法である。そして、秘密計算方法は、これらのいずれの秘密計算装置も十分な数の多装置間で互いに扱うデータを共有しない限り、関数への入力や出力に関する情報を得ることができない特徴を持つ。【０００３】
公知の秘密計算方法として、非特許文献１に挙げられる方法が知られている。【０００４】
非特許文献１に記載の方法では、ある体上の値である秘密Sを、この体上の多項式FでF(０)=Sとなるものを使って複数の装置に分散する。装置の数をN、秘密の個数がK未満であれば、関数の入力や出力に関する情報を得ることができないとする。この様な技術をこの技術分野では「秘密分散」という。装置毎に異なるこの体上の値が割り当てられているとし、i番目の装置に割り当てられている体の値をX[i]とする。ここで、１≦i≦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(0)やG(0)を計算することが可能になる。【０００８】
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(0)を計算することが可能になる。【００１０】
K*2 ≦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の次数は２Kとなるので、２K個以上の装置が集まれば２K次多項式を解くことが可能で、Hの係数を求めることができ、H(0)を計算することが可能になる。【００１１】
A*Bの分散方法は、秘密Aや秘密Bとは分散のされ方が異なる。これを同様に（K-1）次多項式を用いた形で分散するには、それぞれi番目の装置がH[i]からK-1次多項式Gを生成して、他のそれぞれj番目の装置にG(X[j])を配ることでなされる。このようにして、非特許文献１記載の方法では、加算と乗算からなる全ての関数を計算することができる。【００１２】
その他の公知の秘密計算方法として、非特許文献２に挙げられる方法が知られている。【００１３】
非特許文献２には、装置の数が二つの場合の方法に関する記述がある。この方法では、二つの装置がビット、すなわちガロア体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 と呼ばれる技術で実現される。しかしながら、この技術では、一般に両者に多くの計算と通信を要求する。【００１９】
非特許文献１と２に開示された秘密計算方法では、各装置が正直に振る舞うことを前提としている。【００２０】
これに対して、非特許文献３は、一定数以上の装置が正直に振る舞えば、その他の装置が悪意を持って振る舞っても、安全性が保たれる方法を記述している。ここで、「悪意を持って振る舞う」とは、互いに通信する時に、正しい値を他者に送らないことを意味する。また、「安全性が保たれる」とは、偽の値を送ることで他者の持つ秘密を得ることができないことを意味する。【００２１】
非特許文献３に開示された秘密計算方法においては、秘密とその秘密のメッセージ認証子の両方を秘密分散により保持し、両者に対して秘密計算を行った結果が、最終的な計算結果とそのメッセージ認証子になっていることを確認する。このことで、悪意ある参加者が秘密計算において偽の値を他者に送るという不正をしていないことが確認できる。上記秘密計算においては、乱数とそのメッセージ認証子の組を3組で、最初の二組を乗じた結果が三組目となるものを事前計算し、秘密計算による乗算部分においてこれを使う。この3組を事前計算するためには、準同型性を持つ暗号を用いる。
【先行技術文献】
【非特許文献】
【００２２】
【非特許文献１】Tal Rabin, Michael Ben-Or: Verifiable Secret Sharing and Multiparty Protocols with Honest Majority (Extended Abstract). STOC 1989: 73-85
【非特許文献２】Oded Goldreich, Ronen Vainish: How to Solve any Protocol Problem - An Efficiency Improvement. CRYPTO 1987: 73-86
【非特許文献３】Ivan Damgard, Valerio Pastro, Nigel P. Smart, Sarah Zakarias: Multiparty Computation from Somewhat Homomorphic Encryption. CRYPTO 2012: 643-662.
【発明の概要】
【発明が解決しようとする課題】
【００２３】
上記非特許文献１〜３に記述された方法には、それぞれ、次に述べるような問題がある。【００２４】
非特許文献１と２に記述された方法は、参加者の悪意ある振る舞いに対して秘密を守ることができないことが問題である。【００２５】
一方、非特許文献３に記述された方法は、事前計算には準同型暗号が必要であり、この処理時間が大きいことが問題である。【００２６】
したがって、処理量を少なく保ったまま、参加者の悪意のある振る舞いに対して秘密を守ることが課題である。【００２７】
本発明の目的は、上述したいずれかの課題を解決する事前計算装置、方法、およびコンピュータ読取可能な記録媒体、並びにベクトル乗算装置、方法、およびコンピュータ読取可能な記録媒体を提供することにある。
【課題を解決するための手段】
【００２８】
本発明の事前計算装置は、複数の他の事前計算装置と通信可能な事前計算装置であって、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理部と；前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理部と；前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理部と；を備える。【００２９】
本発明の事前計算方法は、複数の他の事前計算装置と通信可能な事前計算装置において行われる事前計算方法であって、ビーバー三重子生成処理部が、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成し；ビーバー三重子ランダム検査処理部が、前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認し；ビーバー三重子位置攪拌処理部が、前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成する。【００３０】
本発明の事前計算プログラムは、複数の他の事前計算装置と通信可能な事前計算装置のコンピュータを、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理手段；前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理手段；および前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理手段；として機能させる。【００３１】
また、本発明のベクトル乗算装置は、複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置であって、ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データが入力される事前計算入力処理部と；乗算されるべき二つの数の組の秘密分散データが複数個入力される入力処理部と；前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理部と；前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理部と；を備える。【００３２】
本発明のベクトル乗算方法は、複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置において行われるベクトル乗算方法であって、事前計算入力処理部が、ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データを入力し；入力処理部が、乗算されるべき二つの数の組の秘密分散データを複数個入力し；補助ベクトル生成処理部が、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成し；ベクトル乗算処理部が、前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成する。【００３３】
本発明のコンピュータ読取可能な記録媒体に記録されたベクトル乗算プログラムは、複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置のコンピュータを、ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データを入力する事前計算入力処理手段；乗算されるべき二つの数の組の秘密分散データを複数個入力する入力処理手段；前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理手段；および前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理手段；として機能させる。
【発明の効果】
【００３４】
本発明によれば、処理量を少なく保ったまま、参加者の悪意のある振る舞いに対して秘密を守ることができる。
【図面の簡単な説明】
【００３５】
【図１】本発明の第１の実施形態に係る事前計算システムを構成する事前計算装置のハードウェア構成を示すブロック図である。
【図２】図１に示される事前計算装置に使用されるデータ処理装置の動作を説明するためのフロー図である。
【図３】本発明の第２の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置のハードウェア構成を示すブロック図である。
【図４】図３に示されるベクトル乗算装置に使用されるテータ処理装置の動作を説明するためのフロー図である。
【図５】本発明の第３の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置のハードウェア構成を示すブロック図である。
【図６】図５に示されるベクトル乗算装置に使用されるテータ処理装置の動作を説明するためのフロー図である。
【図７】本発明の第４の実施形態に係る事前計算システムを構成する事前計算装置のハードウェア構成を示すブロック図である。
【図８】図７に示される事前計算装置に使用されるデータ処理装置の動作を説明するためのフロー図である。
【図９】本発明の第５の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置のハードウェア構成を示すブロック図である。
【図１０】図９に示されるベクトル乗算装置に使用されるテータ処理装置の動作を説明するためのフロー図である。
【図１１】本発明の第６の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置のハードウェア構成を示すブロック図である。
【図１２】図１１に示されるベクトル乗算装置に使用されるテータ処理装置の動作を説明するためのフロー図である。
【発明を実施するための形態】
【００３６】
（記号と定義の説明）
最初に、本発明の理解を容易するために、本発明において使用される演算子などの記号やその定義について説明する。
【００３７】
体Fを要素とする長さNのベクトル同士の演算を示す。二つのベクトルxとyがあり、それらの第i番目の要素をそれぞれx[i], y[i]とする。ベクトルxとy の加算結果をzとすると、zのi番目の要素をz[i]=x[i]+y[i]とする。
【００３８】
以下に記述される発明の文脈において、この加算方法は容易でよく知られているため、これ以上は記述しない。
【００３９】
ベクトルxとyの乗算結果をzとすると、zのi番目の要素を z[i]=x[i]y[i]とする。本発明はこの乗算に関する発明である。
【００４０】
上記ベクトルの加算と乗算が可能になれば、体Fの要素の加算と乗算を大量に同時に実行する場合に利用することができる。例えば、多項式PをN個の入力に対して計算したい場合を考える。この場合、多項式Pの変数の数だけベクトルを準備し、k番目の変数にk番目のベクトルを割り当て、それぞれのベクトルのi番目の要素に、i番目の入力の要素を割り振る。このとき、N個の入力に対する多項式Pの評価は、単一の多項式Pに対する長さNのベクトル複数の入力による評価となる。すなわち、多項式Pを構成するそれぞれの乗算や加算は、ベクトルの加算や乗算によって、全ての入力に対して同時に実行されることになる。
【００４１】
Mを安全変数、Nをベクトル長とする。本発明は特にM<<Nの場合に効率的である。Kを整数とする。本発明は特にM<<Kの場合に効率的である。vを検査率とする。L=N(K+M)/(1-v) とする。{M}は{1,…,M}を表し、｛N｝は{1,…,N}を表し、｛K｝は{1,…,K}を表し、{L}は{1,…,L}を表すとする。
【００４２】
Fを体とする。値x が(t,n)-秘密分散されていることを、<x>と表す。具体的には、各参加者が値xに関するあるデータを持っている状態で、かつ（t−１）以下の参加者がこれらのデータを持ち寄っても値xに関する情報は一切わからず、t以上の参加者がこれらのデータを持ち寄ると値xを復元できる状態である。
【００４３】
ここで各装置が持つデータをxの秘密分散のシェア、あるいはxのシェアと呼ぶ。この秘密分散は参加者が互いに通信することなく二つの(t,n)-秘密分散 <x>, <y>  から、x とyの積z=xy の(2t-1,n)-秘密分散を求めることができるとする。この結果を<<z>>=<x>** <y>と表すとする。<<z>>から、参加者間で通信することで<z>を得る方法があるとする。この処理を<z>=Reshare(<<z>>)と表す。
【００４４】
Open(<x>)を、<x>から全ての参加者がxを得る処理とする。この時、全てのt参加者の組み合わせに関するxの復元結果を得るとする。これは、一部の参加者が不正を働いた場合、一部の組み合わせでは正しい値が復元されない可能性があるからである。この全ての組み合わせに対して同じ値が得られなかった参加者は、不正を検知したとことを通知して動作を終了する。
【００４５】
Randomは、全ての参加者が参加することで(t,n)-秘密分散されたランダムな体Fの要素を生成する処理である。Random’は、公開されたランダムな体Fの要素を生成する処理である。公開された値a と秘密分散 <x>との積、a<x>＝<ax>  は通信を伴うことなく計算できるとする。Reshare, Random, Random’処理では各参加者は乱数を消費する。
【００４６】
全てのi  ∈{M}, j ∈ {N}  に関して<Γ[i,j]>  =Randomと生成してあるとする。ここで、i  ∈{M}, j ∈ {N}  に関する<Γ[i,j]>は、メッセージ認証子の鍵を秘密分散した値であり、秘密分散されたメッセージ認証子の鍵、または、メッセージ認証子の鍵の秘密分散データとも呼ばれる。
【００４７】
［実施形態１］
図１は、本発明の第１の実施形態に係る事前計算システムを構成する事前計算装置１０のハードウェア構成を示すブロック図である。図示の事前計算装置１０は、プログラム制御により動作するコンピュータで実現可能である。
【００４８】
図示の事前計算システムは、ビーバー(Beaver)三重子の安全な事前計算システムである。
【００４９】
事前計算システムは、互いに通信が可能な複数の事前計算装置１０から成るシステムである。
【００５０】
事前計算装置１０は、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）１１と、データを入力する入力装置１２と、データを出力する出力装置１３と、後述するプログラムやデータを記憶する記憶装置１４と、データを処理するデータ処理装置１５とを備えている。
【００５１】
通信Ｉ／Ｆ１１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ１１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ１１は、他の事前計算装置へデータを送信し、他の事前計算装置からデータを受信する。通信Ｉ／Ｆ１１は、受信したデータを、データ処理装置１５へ送出する機能をも有する。
【００５２】
入力装置１２は、キーボードやマウスなどから成る。入力装置１２は、オペレータの操作を検出して、その操作情報をデータ処理装置１５へ送出する機能を有する。
【００５３】
出力装置１３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置１３は、データ処理装置１５からの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【００５４】
記憶装置１４は、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置１４は、データ処理装置１５における各種処理に必要な処理情報（後述する）やプログラム１１１を記憶する機能を有する。
【００５５】
データ処理装置１５は、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置１５は、記憶装置１４からプログラム１１１を読み込んで、プログラム１１１に従ってデータを処理する各種処理部を実現する機能を有する。
【００５６】
データ処理装置１５で実現される主な処理部は、ビーバー三重子生成処理部１０１、ビーバー三重子ランダム検査処理部１０２、およびビーバー三重子位置攪拌処理部１０３から成る。
【００５７】
ビーバー三重子生成処理部１０１は、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を複数の事前計算装置１０が互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを複数の事前計算装置１０で秘密分散する機能を持つ。ビーバー三重子生成処理部１０１は、この機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成する。
【００５８】
記憶装置１４は、乱数１１２と、ビーバー三重子生成処理部１０１で生成された、ビーバー三重子の秘密分散データ１１３と、を保存する。ビーバー三重子の秘密分散データ１１３は、秘密分散されたビーバー三重子とも呼ばれる。
【００５９】
ビーバー三重子ランダム検査処理部１０２は、秘密分散されたビーバー三重子１１３をランダムに選び、互いに複数の事前計算装置１０が通信することでこれらのビーバー三重子を復元する。そして、ビーバー三重子ランダム検査処理部１０２は、復元したビーバー三重子の値を用いて、最初の二つの要素の積が第三の要素となっていることを確認する。
【００６０】
ビーバー三重子ランダム検査処理部１０２の検査の合否結果は、出力装置１３から出力される。
【００６１】
ビーバー三重子位置攪拌処理部１０３は、前記復元しなかったビーバー三重子をランダムに並び替え（すなわち、攪拌し）て、並び替えた後の秘密分散されたビーバー三重子を生成する。
【００６２】
記憶装置１４は、ビーバー三重子位置攪拌処理部１０３で攪拌された、攪拌済みビーバー三重子の秘密分散データ１１４を保存する。攪拌済みビーバー三重子の秘密分散データ１１４は、並び替えた後の秘密分散されたビーバー三重子とも呼ばれる。
【００６３】
次に、図２を参照して、図１のデータ処理装置１５の各処理部１０１〜１０３において行われる処理について更に詳細に説明する。
【００６４】
ビーバー三重子生成処理部１０１は、先ず、全てのj ∈ {L} に対して、<a[j]>  =  Randomと生成する。引き続いて、ビーバー三重子生成処理部１０１は、全てのj ∈ {L} に対して、<b[j]>  =  Randomと生成する。
【００６５】
そして、ビーバー三重子生成処理部１０１は、全てのj ∈ {L} に対して、<c[j]>  =  Reshare(<a[j]>**<b[j]>) と生成する。
【００６６】
ここで、全ての参加者が正直に振る舞ったならば、この時点で、 全てのj ∈ {L} に対して、正しい秘密分散されたビーバー三重子(<a[j]>, <b[j]>, <c[j]>)が生成されている。ここで言う「正しい」とは、a[j] b[j]=c[j] の関係が成り立っているということである。尚、秘密分散されたビーバー三重子は、ビーバー三重子の秘密分散データとも呼ばれる。
この処理はビーバー三重子生成処理（Ｓ１０１）と呼ばれる。
【００６７】
ビーバー三重子ランダム検査処理部１０２は、一定の割合vでj∈{L}を選び、Open(<c[j]>= Open(<a[j]>) Open(<b[j]>) が成り立つことを確認する。成り立たない組が見つかれば、ビーバー三重子ランダム検査処理部１０２は、不正を検知したとして終了する。
【００６８】
この関係はビーバー三重子として成立すべきであるため、関係の不成立は参加者の不正があったことを意味する。また、一定の割合vで検査しているため、特定のビーバー三重子が正しく作られていない時にこれが見つかる確率は、この一定の割合である。
【００６９】
さらに、ある一定の割合Fでビーバー三重子の生成で不正を働こうとすると、生成したビーバー三重子の数Lが多ければ多いほど、不正が見つかる可能性が高くなる。なぜなら、個数L個のビーバー三重子の内、L*f =F個のビーバー三重子が正しく生成されておらず,  L*v=V個検査した場合、不正が見つかる確率1-(1-F/L)Vは、Lが大きくなればなるほど１に近づくからである。よって、Lを大きくすればするほど、不正が発見されにくいためには、Fを小さくしなければならない。
この処理は、ビーバー三重子ランダム検査処理（Ｓ１０２）と呼ばれる。
【００７０】
ビーバー三重子位置攪拌処理部１０３は、全て確認されたら、残りのL-V の組をランダムに入れ替えて、それぞれ j∈{L-V},<a[j]>, <b[j]>, <c[j]>  とする。
【００７１】
上記入れ替えにより、例え不正なビーバー三重子が存在しても、その位置がランダムになる。
この処理は、ビーバー三重子位置攪拌処理（Ｓ１０３）と呼ばれる。
【００７２】
次に、本発明の第１の実施形態に係る事前計算システムの効果について説明する。ビーバー三重子の安全な事前計算により、誤ったビーバー三重子の割合が一定の値以下となる、ビーバー三重子の集合を作ることができる、という効果がある。
【００７３】
［実施形態２］
図３は、本発明の第２の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置２０のハードウェア構成を示すブロック図である。図示のベクトル乗算装置２０は、プログラム制御により動作するコンピュータで実現可能である。
【００７４】
図示のベクトル乗算システムは、ビーバー三重子を用いた隠然的に安全なベクトル乗算システムである。
【００７５】
ベクトル乗算システムは、互いに通信が可能な複数のベクトル乗算装置２０から成るシステムである。
【００７６】
ベクトル乗算装置２０は、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）２１と、データを入力する入力装置２２と、データを出力する出力装置２３と、後述するプログラムやデータを記憶する記憶装置２４と、データを処理するデータ処理装置２５とを備えている。
【００７７】
通信Ｉ／Ｆ２１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ２１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ２１は、他のベクトル乗算装置へデータを送信し、他のベクトル乗算装置からデータを受信する。通信Ｉ／Ｆ２１は、受信したデータを、データ処理装置２５へ送出する機能をも有する。
【００７８】
入力装置２２は、キーボードやマウスなどから成る。入力装置２２は、オペレータの操作を検出して、その操作情報をデータ処理装置２５へ送出する機能を有する。
【００７９】
出力装置２３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置２３は、データ処理装置２５からの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【００８０】
記憶装置２４は、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置２４は、データ処理装置２５における各種処理に必要な処理情報（後述する）やプログラム２１１を記憶する機能を有する。
【００８１】
データ処理装置２５は、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置２５は、記憶装置２４からプログラム２１１を読み込んで、プログラム２１１に従ってデータを処理する各種処理部を実現する機能を有する。
【００８２】
データ処理装置２５で実現される主な処理部は、事前計算入力処理部２０１、入力処理部２０２、補助ベクトル生成処理部２０３、およびベクトル乗算処理部２０４から成る。
【００８３】
事前計算入力処理部２０１は、ビーバー三重子の秘密分散データ２１２を生成し、あるいはこれを入力する。
【００８４】
記憶装置２４は、事前計算入力処理部２０１で生成あるいは入力された、ビーバー三重子の秘密分散データ２１２を保存する。このビーバー三重子の秘密分散データ２１２は、図１の記憶装置１４に保存されている、攪拌済みビーバー三重子の秘密分散データ１１４と同じである。
【００８５】
入力処理部２０２は、乗算されるべき二つの数の組の秘密分散データが複数個を入力する。
【００８６】
記憶装置２４は、入力処理部２０２から入力された、乗算されるデータの秘密分散データ２１３を保存する。この乗算されるデータの秘密分散データ２１３は、乗算されるべき二つの組の秘密分散データから成る。
【００８７】
補助ベクトル生成処理部２０３は、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、複数のベクトル乗算装置２０が互いに通信して開示した結果である補助ベクトル２１６を生成する。
【００８８】
記憶装置２４は、補助ベクトル生成処理部２０３で生成された、補助ベクトル２１６を保存する。
【００８９】
ベクトル乗算処理部２０４は、補助ベクトル２１６を用いて、前記ビーバー三重子の秘密分散データ２１２から、積の秘密分散データ２１５を生成する。
【００９０】
記憶装置２４は、ベクトル乗算処理部２０４で生成された、積の秘密分散データ２１５を保存する。積の秘密分散データは、ベクトル乗算結果の秘密分散データとも呼ばれる。
【００９１】
次に、図４を参照して、図３のデータ処理装置２５の各処理部２０１〜２０４において行われる処理について更に詳細に説明する。
【００９２】
｛N｝は{L-V}よりその部分集合として選ぶ。 
事前計算入力処理部２０１において、あるk  に関する前述のビーバー三重子の秘密分散データが入力されたとする。このkは省略する。すなわち、事前計算入力処理部２０１から、全ての j ∈ {N} に関する  <a[j]>, <b[j]>, <c[j]> が入力されているとする。
【００９３】
これらの値は、次の関係を満たしていることが期待されている。 
全てのj ∈{N}に関して、 c[j]=a[j] b[j]. 
この処理は、事前計算入力処理（Ｓ２０１）と呼ばれる。
【００９４】
入力処理部２０２において、乗算の対象として、j ∈{N} に関して、<x[j]>, <y[j]> が入力されるとする。 
この処理は、入力処理（Ｓ２０２）と呼ばれる。
【００９５】
補助ベクトル生成処理部２０３は、まず、全てのj ∈{N}に関して、d[j]  = Open(<x[j]> +<a[j]>) を生成する。
【００９６】
引き続いて、補助ベクトル生成処理部２０３は、全てのj ∈{N}に関して、e[j]  = Open(<y[j]> + <b[j]>)  を生成する。 
この処理は、補助ベクトル生成処理（Ｓ２０３）と呼ばれる。
【００９７】
ベクトル乗算処理部２０４は、全てのj ∈{N}に関して、<z[j]>=<c[j]>+ d[j]e[j] - e[j]<a[j]>- d[j]<b[j]> を生成する。
【００９８】
本処理がベクトルの乗算処理であり、安全性を保証することを忘れれば、この処理が実質的な目的である。 
この処理は、ベクトル乗算処理（Ｓ２０４）と呼ばれる。
【００９９】
次に、本発明の第２の実施形態に係るベクトル乗算システムの効果について説明する。ビーバー三重子の集合を、ビーバー三重子を用いた隠然的に安全なベクトル乗算方法で利用してベクトル乗算を行っているので、各乗算が正しく行われたことが、正しいビーバー三重子の割合と同じ割合で保証することができる、という効果がある。
【０１００】
［実施形態３］
図５は、本発明の第３の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置３０のハードウェア構成を示すブロック図である。図示のベクトル乗算装置３０は、プログラム制御により動作するコンピュータで実現可能である。
【０１０１】
図示のベクトル乗算システムは、ビーバー三重子を用いた安全なベクトル乗算システムである。
【０１０２】
ベクトル乗算システムは、互いに通信が可能な複数のベクトル乗算装置３０から成るシステムである。
【０１０３】
ベクトル乗算装置３０は、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）３１と、データを入力する入力装置３２と、データを出力する出力装置３３と、後述するプログラムやデータを記憶する記憶装置３４と、データを処理するデータ処理装置３５とを備えている。
【０１０４】
通信Ｉ／Ｆ３１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ３１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ３１は、他のベクトル乗算装置へデータを送信し、他のベクトル乗算装置からデータを受信する。通信Ｉ／Ｆ３１は、受信したデータを、データ処理装置３５へ送出する機能をも有する。
【０１０５】
入力装置３２は、キーボードやマウスなどから成る。入力装置３２は、オペレータの操作を検出して、その操作情報をデータ処理装置３５へ送出する機能を有する。
【０１０６】
出力装置３３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置３３は、データ処理装置３５からの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【０１０７】
記憶装置３４は、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置３４は、データ処理装置３５における各種処理に必要な処理情報（後述する）やプログラム３１１を記憶する機能を有する。
【０１０８】
データ処理装置３５は、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置３５は、記憶装置３４からプログラム３１１を読み込んで、プログラム３１１に従ってデータを処理する各種処理部を実現する機能を有する。
【０１０９】
データ処理装置３５で実現される主な処理部は、入力部３０１、ベクトル乗算部３０２、および結果同一確認処理部３０３から成る。
【０１１０】
入力部３０１は、第１乃至第Ｔ（Ｔは２以上の整数）の入力処理モジュール３０１−１〜３０１−Ｔから成る。第１乃至第Ｔの入力処理モジュール３０１−１〜３０１−Ｔの各々は、図３のデータ処理装置２５における事前計算処理部２０１と入力処理部２０２とから成る。
【０１１１】
ベクトル乗算部３０２は、第１乃至第Ｔのベクトル乗算モジュール３０２−１〜３０２−Ｔから成る。第１乃至第Ｔのベクトル乗算モジュール３０２−１〜３０２−Ｔの各々は、図３のデータ処理装置２５における、補助ベクトル生成処理部２０３と、ベクトル乗算処理部２０４とから成る。
【０１１２】
換言すれば、第１乃至第Ｔのベクトル乗算モジュール３０２−１〜３０２−Ｔの各々は、ビーバー三重子を用いた隠然的に安全なベクトル乗算方法を実施する。
【０１１３】
結果同一確認処理部３０３は、第１乃至第Ｔのベクトル乗算モジュール３０２−１〜３０２−Ｔの乗算結果が全て同一の値であることを確認する。
【０１１４】
記憶装置３４は、図３に図示された記憶装置２４に記憶された処理情報と同様の処理情報を記憶する。すなわち、記憶装置３４は、ビーバー三重子の秘密分散データ３１２、乗算されるデータの秘密分散データ３１３、積の秘密分散データ３１５、および補助ベクトル３１６を保存する。但し、記憶装置２４とは異なり、記憶装置３４は、それら情報をＴ個保存する。
【０１１５】
次に、図６を参照して、図５のデータ処理装置３５の各処理部３０１〜３０３において行われる処理について更に詳細に説明する。
【０１１６】
Tを重複数とする。 
入力部３０１では、一つの入力に対してT個の同じ値の入力が準備されているとする（Ｓ３０１）。ただし、それぞれの秘密分散は独立しており、同じ入力に対する各参加者が所持するデータは全て互いにランダムに分布するとする。
【０１１７】
ベクトル乗算部３０２は、前述の隠然的に安全な乗算方法をT個の入力に対して独立に適用する（Ｓ３０２）。
【０１１８】
適用後、結果同一確認処理部３０３は、結果が全て同一であることを次のように確認する。
【０１１９】
あるjに対するT個の結果が <z(1)[j]>,…, <z(T)[j]> であったとする。 
結果同一確認処理部３０３は、O=  Open(<z(u)[j]>=<z(u+1)[j]>) を全てのu=1,…,T-1 に対して確認する。 
この処理は、結果同一確認処理と呼ばれる（Ｓ３０３）。
【０１２０】
これらの確認も確率的な確認を多数行うことで、Open の数を減らすことができる。
【０１２１】
前述した第２の実施形態に係る隠然的に安全な方法では、ビーバー三重子が正しく生成されていなければ、答え乗算結果が正しいことは保証できなかった。一方、ビーバー三重子の検証方法から、ビーバー三重子が大量に作られていてかつ一定の割合を検査するならば、紛れ込ませることのできる不正なビーバー三重子の数は一定の小さな割合に留まった。
【０１２２】
それゆえ、本第３の実施形態では、複数の計算を同時に行い、それぞれの計算を異なるビーバー三重子で担保しているので、少なくとも一つの計算は正しいビーバー三重子で計算されるようになる確率を十分高くすることができる。その後、全ての計算が同一であることを確認すれば、全ての計算が正しいビーバー三重子による計算結果と同じになることが保証される。
【０１２３】
次に、本発明の第３の実施形態に係るベクトル乗算システムの効果について説明する。ビーバー三重子の集合を、ビーバー三重子を用いた安全なベクトル乗算方法で利用してベクトル乗算を行っているので、各乗算が正しく行われたことが、圧倒的な確率で保証できる、という効果がある。
【０１２４】
この計算で通信が必要な処理は、Rehash, Open, Rand である。これらの回数は、M<<N<<Kであることを考えると、隠然的に安全な方法で乗算一個当たり５回、安全な方法で５T回である。
【０１２５】
［実施形態４］
図７は、本発明の第４の実施形態に係る事前計算システムを構成する事前計算装置１０Ａのハードウェア構成を示すブロック図である。図示の事前計算装置１０Ａは、プログラム制御により動作するコンピュータで実現可能である。
【０１２６】
図示の事前計算システムは、メッセージ認証子付ビーバー(Beaver)三重子の安全な事前計算システムである。
【０１２７】
事前計算システムは、互いに通信が可能な複数の事前計算装置１０Ａから成るシステムである。複数の事前計算装置１０Ａは、これらの事前計算装置１０Ａの間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える。
【０１２８】
事前計算装置１０Ａは、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）１１と、データを入力する入力装置１２と、データを出力する出力装置１３と、後述するプログラムやデータを記憶する記憶装置１４Ａと、データを処理するデータ処理装置１５Ａとを備えている。
【０１２９】
通信Ｉ／Ｆ１１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ１１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ１１は、他の事前計算装置へデータを送信し、他の事前計算装置からデータを受信する。通信Ｉ／Ｆ１１は、受信したデータを、データ処理装置１５Ａへ送出する機能をも有する。
【０１３０】
入力装置１２は、キーボードやマウスなどから成る。入力装置１２は、オペレータの操作を検出して、その操作情報をデータ処理装置１５Ａへ送出する機能を有する。
【０１３１】
出力装置１３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置１３は、データ処理装置１５Ａからの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【０１３２】
記憶装置１４Ａは、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置１４Ａは、データ処理装置１５Ａにおける各種処理に必要な処理情報（後述する）やプログラム１１１Ａを記憶する機能を有する。
【０１３３】
データ処理装置１５Ａは、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置１５Ａは、記憶装置１４Ａからプログラム１１１Ａを読み込んで、プログラム１１１Ａに従ってデータを処理する各種処理部を実現する機能を有する。
【０１３４】
データ処理装置１５Ａで実現される主な処理部は、ビーバー三重子生成処理部１０１、ビーバー三重子ランダム検査処理部１０２、ビーバー三重子位置攪拌処理部１０３Ａ、ビーバー三重子メッセージ認証子生成処理部１０４、およびビーバー三重子メッセージ認証子検証処理部１０５から成る。
【０１３５】
すなわち、データ処理装置１５Ａは、図１に示されたデータ処理装置１５とは、ビーバー三重子メッセージ認証子生成処理部１０４とビーバー三重子メッセージ認証子検証処理部１０５とが新たに追加されていると共に、ビーバー三重子位置攪拌処理部１０３Ａでの処理内容が異なっている点において、相違している。
【０１３６】
ビーバー三重子生成処理部１０１は、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を複数の事前計算装置１０Ａが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを複数の事前計算装置１０Ａで秘密分散する機能を持つ。ビーバー三重子生成処理部１０１は、この機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成する。
【０１３７】
記憶装置１４Ａは、乱数１１２と、ビーバー三重子生成処理部１０１で生成された、ビーバー三重子の秘密分散データ１１３と、を保存する。ビーバー三重子の秘密分散データ１１３は、秘密分散されたビーバー三重子とも呼ばれる。
【０１３８】
ビーバー三重子ランダム検査処理部１０２は、秘密分散されたビーバー三重子１１３をランダムに選び、互いに複数の事前計算装置１０Ａが通信することでこれらのビーバー三重子を復元する。そして、ビーバー三重子ランダム検査処理部１０２は、復元したビーバー三重子の値を用いて、最初の二つの要素の積が第三の要素となっていることを確認する。
【０１３９】
ビーバー三重子ランダム検査処理部１０２の検査の合否結果は、出力装置１３から出力される。
【０１４０】
ビーバー三重子位置攪拌処理部１０３Ａは、前記復元しなかったビーバー三重子をランダムに並び替え（すなわち、攪拌し）て、新しいインデックスを付けて並び替えた後の秘密分散されたビーバー三重子を生成する。
【０１４１】
記憶装置１４Ａは、ビーバー三重子位置攪拌処理部１０３Ａで攪拌された、攪拌済みビーバー三重子の秘密分散データ１１４Ａを保存する。攪拌済みビーバー三重子の秘密分散データ１１４Ａは、並び替えた後の秘密分散されたビーバー三重子とも呼ばれる。
【０１４２】
記憶装置１４Ａは、前述したメッセージ認証子の鍵の秘密分散データ１１５を保存する。メッセージ認証子の鍵の秘密分散データ１１５は、秘密分散されたメッセージ認証子の鍵とも呼ばれる。
【０１４３】
ビーバー三重子メッセージ認証子生成処理部１０４は、乱数１１２とメッセージ認証子の鍵の秘密分散データ１１５とを用いて、前記並び替えた後の秘密分散されたビーバー三重子１１４Ａに対してその秘密分散されたメッセージ認証子を、複数の事前計算装置１０Ａが互いに通信することで生成する。
【０１４４】
記憶装置１４Ａは、攪拌済みビーバー三重子とそのメッセージ認証子の秘密分散データ１１６を保存する。攪拌済みビーバー三重子とそのメッセージ認証子の秘密分散データ１１６は、メッセージ認証子付ビーバー三重子の秘密分散データとも呼ばれる。したがって、メッセージ認証子付ビーバー三重子の秘密分散データ１１６は、秘密分散されたビーバー三重子と、秘密分散されたビーバー三重子のメッセージ認証子とから成る。
【０１４５】
ビーバー三重子メッセージ認証子検証処理部１０５は、次に述べるような、復元処理と、確認処理とを行う。復元処理では、ビーバー三重子メッセージ認証子検証処理部１０５は、前記並び替えた後の秘密分散されたビーバー三重子のランダムに選んだ係数による線形和を多数生成し、この多数生成した値を復元して復元された値を生成する。確信処理では、ビーバー三重子メッセージ認証子検証処理部１０５は、前記秘密分散されたビーバー三重子のメッセージ認証子を前記係数による線形和を多数生成した値と、前記復元された値を前記秘密分散されたメッセージ認証子の鍵による線形和を多数生成した値とが同一であることを確認する。
【０１４６】
ビーバー三重子メッセージ認証子検証処理部１０５の検証の合否結果は、出力装置１３から出力される。
【０１４７】
次に、図８を参照して、図７のデータ処理装置１５Ａの各処理部１０１〜１０５において行われる処理について更に詳細に説明する。
【０１４８】
ビーバー三重子生成処理部１０１は、先ず、全てのj ∈ {L} に対して、<a[j]>  =  Randomと生成する。引き続いて、ビーバー三重子生成処理部１０１は、全てのj ∈ {L} に対して、<b[j]>  =  Randomと生成する。
【０１４９】
そして、ビーバー三重子生成処理部１０１は、全てのj ∈ {L} に対して、<c[j]>  =  Reshare(<a[j]>**<b[j]>) と生成する。
【０１５０】
ここで、全ての参加者が正直に振る舞ったならば、この時点で、 全てのj ∈ {L} に対して、正しい秘密分散されたビーバー三重子(<a[j]>, <b[j]>, <c[j]>)が生成されている。ここで言う「正しい」とは、a[j] b[j]=c[j] の関係が成り立っているということである。尚、秘密分散されたビーバー三重子は、ビーバー三重子の秘密分散データとも呼ばれる。 
この処理はビーバー三重子生成処理（Ｓ１０１）と呼ばれる。
【０１５１】
ビーバー三重子ランダム検査処理部１０２は、一定の割合vでj∈{L}を選び、Open(<c[j]>= Open(<a[j]>) Open(<b[j]>) が成り立つことを確認する。成り立たない組が見つかれば、ビーバー三重子ランダム検査処理部１０２は、不正を検知したとして終了する。
【０１５２】
この関係はビーバー三重子として成立すべきであるため、関係の不成立は参加者の不正があったことを意味する。また、一定の割合vで検査しているため、特定のビーバー三重子が正しく作られていない時にこれが見つかる確率は、この一定の割合である。
【０１５３】
さらに、ある一定の割合Fでビーバー三重子の生成で不正を働こうとすると、生成したビーバー三重子の数Lが多ければ多いほど、不正が見つかる可能性が高くなる。なぜなら、個数L個のビーバー三重子の内、L*f =F個のビーバー三重子が正しく生成されておらず,  L*v=V個検査した場合、不正が見つかる確率1-(1-F/L)Vは、Lが大きくなればなるほど１に近づくからである。よって、Lを大きくすればするほど、不正が発見されにくいためには、Fを小さくしなければならない。 
この処理は、ビーバー三重子ランダム検査処理（Ｓ１０２）と呼ばれる。
【０１５４】
ビーバー三重子位置攪拌処理部１０３Ａは、まず、K’=K+Mとして、{K’}は{1,…,K’}とする。
【０１５５】
次に、ビーバー三重子位置攪拌処理部１０３Ａは、全て確認されたら、残りのN(K+M)=K’N の組をランダムに入れ替えて新しいインデックスを付け、それぞれ j∈{N}, k ∈{K’} に対して、<a[j,k]>, <b[j,k]>, <c[j,k]>とする。
【０１５６】
全ての j ∈ {N}, k ∈ {K’} に関して、全ての参加者が正直に振る舞っていれば<c[j,k]>=<a[j,k]><b[j,k]> が成り立つ。
【０１５７】
上記入れ替えにより、たとえ不正なビーバー三重子が存在しても、その位置がランダムになる。 
この処理は、ビーバー三重子位置攪拌処理（Ｓ１０３Ａ）と呼ばれる。
【０１５８】
ビーバー三重子メッセージ認証子生成処理部１０４は、まず、全てのi ∈ {M}, k ∈ {K’} に対して、<A[i,k]>  = Reshare(Σj∈{N}<Γ[i,j]>**<a[j,k]>) と生成する。同様に、ビーバー三重子メッセージ認証子生成処理部１０４は、全てのi ∈ {M}, k ∈ {K’} に対して、<B[i,k]>  = Reshare(Σj∈{N}<Γ[i,j]>**<b[j,k]>) と生成する。また、ビーバー三重子メッセージ認証子生成処理部１０４は、全てのi ∈ {M}, k ∈ {K’} に対して、<C[i,k] > = Reshare(Σj∈{N}<Γ[i,j]>**<c[j,k]>) と生成する。
【０１５９】
i ∈ {M}, k ∈ {K’} に対するA[i,k]  は、j ∈ {N}, k ∈ {K’} に対する a[j,k]  に対するメッセージ認証子である。 
i ∈ {M}, k ∈ {K’} に対するB[i,k]  は、j ∈ {N}, k ∈ {K’} に対する b[j,k]  に対するメッセージ認証子である。 
i ∈ {M}, k ∈ {K’} に対するC[i,k]  は、j ∈ {N}, k ∈ {K’} に対する c[j,k]  に対するメッセージ認証子である。 
ここで、メッセージ認証子の鍵はi ∈ {M}, j ∈ {N} に対するΓ[i,j]である。
【０１６０】
参加者が正直に振る舞っていれば、これらのメッセージ認証子が秘密分散されることになる。 
この処理は、ビーバー三重子メッセージ認証子生成処理（Ｓ１０４）と呼ばれる。
【０１６１】
ビーバー三重子メッセージ認証子検証処理部１０５は、まず、全てのm ∈ {M}, k ∈ {K’} に対して、Λ[m,k]  =  Random’と生成する。引き続いて、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのj ∈ {N}, m ∈ {M} に対して、a’[j,m]  =  Open(Σj∈{N} Λ[m,k] <a[j,k]>)と生成する。そして、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのi ∈ {M}, m ∈ {M} に対して、0 =  Open(Σk∈{K’} Λ[m,k] <A[i,k]>-Σj∈{N} <Γ[i,j]> a’[j,m]) であることを確認する。
【０１６２】
さらに、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのm ∈ {M}, k ∈ {K’} に対して、Ω[m,k]  =  Random’と生成する。引き続いて、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのj ∈ {N}, m ∈ {M} に対して、b’[j,m]  =  Open(Σj∈{N} Ω[m,k] <b[j,k]>)と生成する。そして、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのi ∈ {M}, m ∈ {M} に対して、0 =  Open(Σk∈{K’} Ω[m,k] <B[i,k]>-Σj∈{N} <Γ[i,j]> b’[j,m]) であることを確認する。
【０１６３】
さらにまた、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのm ∈ {M}, k ∈ {K’} に対して、Θ[m,k]  =  Random’と生成する。引き続いて、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのj ∈ {N}, m ∈ {M} に対して、c’[j,m]  =  Open(Σj∈{N} Θ[m,k] <c[j,k]>)と生成する。そして、ビーバー三重子メッセージ認証子検証処理部１０５は、全てのi ∈ {M}, m ∈ {M} に対して、0 =  Open(Σk∈{K’} Θ[m,k] <C[i,k]>-Σj∈{N} <Γ[i,j]> c’[j,m]) であることを確認する。
【０１６４】
ビーバー三重子メッセージ認証子検証処理部１０５は、k >K’-M :=K’’なる <a[j,k]>, <A[i,k]>, <b[j,k]>, <B[i,k]>, <c[j,k]>, <C[i.k]>  を全て削除する。
【０１６５】
j ∈ {N}, m ∈ {M} に関する a’[j,m], b’[j,m], c’[j,m] それぞれは、 全てのj ∈ {N}, k ∈ {K’} に関するa[j,k], b[j,k], c[j,k] それぞれのメッセージ認証子の重ね合わせである。
【０１６６】
メッセージ認証子の線形性より、0=Σk∈{K’} Λ[m,k] A[i,k]-Σj∈{N} Γ[i,j] a’[j,m], 0=Σk∈{K’} Λ[m,k] B[i,k]-Σj∈{N} Γ[i,j] b’[j,m], 0=Σk∈{K’} Λ[m,k] C[i,k]-Σj∈{N} Γ[i,j] c’[j,m] を確認することにより、全てのメッセージ認証子が正しいことが確認される。j ∈ {N}, m ∈ {M} に関する a’[j,m], b’[j,m], c’[j,m] が開示されるため、j ∈ {N}, k ∈ {K’} に関するa[j,k], b[j,k], c[j,k]  の関係が開示される。そのため、一部を削除することで、依存関係のないビーバー三重子の集合とする。 
この処理は、ビーバー三重子メッセージ認証子検証処理（Ｓ１０５）と呼ばれる。
【０１６７】
データ処理装置１５Ａの出力は、全てのj∈ {N}, k ∈{K} に関する, (a[j,k]>, <b[j,k]>, <c[j,k]>)と、全てのk ∈{K}, i∈{M} に関する,  (<A[i,k]>, <B[i,k]>, <C[i.k]>)  である。
【０１６８】
次に、本発明の第４の実施形態に係る事前計算システムの効果について説明する。メッセージ認証子付ビーバー三重子の安全な事前計算により、誤ったビーバー三重子の割合が一定の値以下となる、メッセージ認証付ビーバー三重子の集合を作ることができる、という効果がある。
【０１６９】
［実施形態５］
図９は、本発明の第５の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置２０Ａのハードウェア構成を示すブロック図である。図示のベクトル乗算装置２０Ａは、プログラム制御により動作するコンピュータで実現可能である。
【０１７０】
図示のベクトル乗算システムは、メッセージ認証子付ビーバー三重子を用いた隠然的に安全なベクトル乗算システムである。
【０１７１】
ベクトル乗算システムは、互いに通信が可能な複数のベクトル乗算装置２０Ａから成るシステムである。複数のベクトル乗算装置２０Ａは、これらのベクトル乗算装置２０Ａの間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える。
【０１７２】
ベクトル乗算装置２０Ａは、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）２１と、データを入力する入力装置２２と、データを出力する出力装置２３と、後述するプログラムやデータを記憶する記憶装置２４Ａと、データを処理するデータ処理装置２５Ａとを備えている。
【０１７３】
通信Ｉ／Ｆ２１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ２１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ２１は、他のベクトル乗算装置へデータを送信し、他のベクトル乗算装置からデータを受信する。通信Ｉ／Ｆ２１は、受信したデータを、データ処理装置２５Ａへ送出する機能をも有する。
【０１７４】
入力装置２２は、キーボードやマウスなどから成る。入力装置２２は、オペレータの操作を検出して、その操作情報をデータ処理装置２５Ａへ送出する機能を有する。
【０１７５】
出力装置２３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置２３は、データ処理装置２５Ａからの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【０１７６】
記憶装置２４Ａは、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置２４Ａは、データ処理装置２５Ａにおける各種処理に必要な処理情報（後述する）やプログラム２１１Ａを記憶する機能を有する。
【０１７７】
データ処理装置２５Ａは、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置２５Ａは、記憶装置２４Ａからプログラム２１１Ａを読み込んで、プログラム２１１Ａに従ってデータを処理する各種処理部を実現する機能を有する。
【０１７８】
データ処理装置２５Ａで実現される主な処理部は、事前計算入力処理部２０１Ａ、入力処理部２０２Ａ、補助ベクトル生成処理部２０３、ベクトル乗算処理部２０４、補助ベクトルメッセージ認証子生成処理部２０５、入力正当性確認処理部２０６、および出力メッセージ認証子生成処理部２０７から成る。
【０１７９】
すなわち、データ処理装置２５Ａは、図３に示したデータ処理装置２５とは、補助ベクトルメッセージ認証子生成処理部２０５と入力正当性確認処理部２０６と出力メッセージ認証子生成処理部２０７とが追加されていると共に、事前計算入力処理部２０１Ａおよび入力処理部２０２Ａでの処理内容が異なる点に関して、相違している。
【０１８０】
事前計算入力処理部２０１Ａは、メッセージ認証子付ビーバー三重子の秘密分散データ２１２Ａを生成し、あるいはこれを入力する。
【０１８１】
記憶装置２４Ａは、事前計算入力処理部２０１Ａで生成あるいは入力された、メッセージ認証子付ビーバー三重子の秘密分散データ２１２Ａを保存する。このメッセージ認証子付ビーバー三重子の秘密分散データ２１２Ａは、図７の記憶装置１４Ａに保存されている、攪拌済みビーバー三重子とそのメッセージ認証子の秘密分散データ１１６と同じである。
【０１８２】
入力処理部２０２Ａは、乗算されるべき二つの数の組の秘密分散データが複数個と、前記複数個の乗算されるべき二つの数の組それぞれに対するメッセージ認証子の秘密分散データとを入力する。
【０１８３】
記憶装置２４Ａは、入力処理部２０２Ａから入力された、乗算されるデータの秘密分散データ２１３Ａを保存する。この乗算されるデータの秘密分散データ２１３Ａは、乗算されるべき二つの組の秘密分散データと、それに対応するメッセージ認証子の秘密分散データとから成る。
【０１８４】
補助ベクトル生成処理部２０３は、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、複数のベクトル乗算装置２０Ａが互いに通信して開示した結果である補助ベクトル２１６を生成する。
【０１８５】
記憶装置２４Ａは、補助ベクトル生成処理部２０３で生成された、補助ベクトル２１６を保存する。
【０１８６】
ベクトル乗算処理部２０４は、補助ベクトル２１６を用いて、前記攪拌済みビーバー三重子の秘密分散データから、積の秘密分散データ２１５を生成する。
【０１８７】
記憶装置２４Ａは、ベクトル乗算処理部２０４で生成された、積の秘密分散データ２１５を保存する。積の秘密分散データは、ベクトル乗算結果の秘密分散データとも呼ばれる。
【０１８８】
補助ベクトルメッセージ認証子生成処理部２０５は、前記補助ベクトル２１６に対するメッセージ認証子の秘密分散データ２１７を、前記入力に対するメッセージ認証子の秘密分散データと前記ビーバー三重子に対するメッセージ認証子の秘密分散データとから生成する。
【０１８９】
記憶装置２４Ａは、補助ベクトルメッセージ認証子生成処理部２０５で生成された、補助ベクトルメッセージ認証子の秘密分散データ２１７を保存する。
【０１９０】
記憶装置２４Ａは、前述したメッセージ認証子の鍵の秘密分散データ２１８を保存している。このメッセージ認証子の鍵の秘密分散データ２１８は、図７に図示した記憶装置１４Ａに保存されている、メッセージ認証子の鍵の秘密分散データ１１５と同一である。
【０１９１】
入力正当性確認処理部２０６は、前記補助ベクトルに対するメッセージ認証子の秘密分散データ２１７と、前記補助ベクトル２１６と、前記メッセージ認証子の鍵の秘密分散データ２１８とから、前記補助ベクトル２１６を検証する。
【０１９２】
入力正当性確認処理部２０６における検査の合否結果は、出力装置２３から出力される。
【０１９３】
出力メッセージ認証子生成処理部２０７は、前記ベクトル乗算結果のメッセージ認証子の秘密分散データを、ビーバー三重子のメッセージ認証子の秘密分散データと、補助ベクトル２１６と、前記メッセージ認証子の鍵の秘密分散データ２１８と、ビーバー三重子の秘密分散データとから、出力メッセージ認証子２１９として生成する。
【０１９４】
記憶装置２４Ａは、出力メッセージ認証子生成処理部２０７から生成された、出力メッセージ認証子２１９を保存する。また、この出力メッセージ認証子２１９は、出力装置２３から出力される。
【０１９５】
次に、図１０を参照して、図９のデータ処理装置２５Ａの各処理部２０１Ａ〜２０７において行われる処理について更に詳細に説明する。
【０１９６】
事前計算入力処理部２０１Ａにおいて、あるk  に関する前述のメッセージ認証子付ビーバー三重子の秘密分散データが入力されたとする。このkは省略する。すなわち、事前計算入力処理部２０１Ａから、全ての j ∈ {N}, i ∈ {M} に関する  <a[j]>, <A[i]>, <b[j]>, <B[i]>, <c[j]>, <C[i]> が入力されているとする。
【０１９７】
これらの値は、次の関係を満たしていることが期待されている。
【０１９８】
全てのj ∈{N}, i  ∈ {M} に関して、 c[j]=a[j] b[j],  A[i]=Σj∈{N}Γ[i,j] a[j] , B[i]=Σj∈{N}Γ[i,j] b[j], C[i]=Σj∈{N}Γ[i,j] c[j]. 
この処理は、事前計算入力処理（Ｓ２０１Ａ）と呼ばれる。
【０１９９】
入力処理部２０２Ａにおいて、乗算の対象として、j ∈{N} に関して、<x[j]>, <y[j]> が入力されるとする。また、入力処理部２０２Ａにおいて、これらのメッセージ認証子として、i∈{M}に関して、<X[i]>, <Y[i]> が入力される。
【０２００】
これらは、すべてのi∈{M}に関して、X[i]=Σj∈{N}Γ[i,j] x[j] , Y[i]=Σj∈{N}Γ[i,j] y[j]  の関係を満たすことが期待されている。 
この処理は、入力処理（Ｓ２０２Ａ）と呼ばれる。
【０２０１】
補助ベクトル生成処理部２０３は、まず、全てのj ∈{N}に関して、d[j]  = Open(<x[j]> +<a[j]>) を生成する。
【０２０２】
引き続いて、補助ベクトル生成処理部２０３は、全てのj ∈{N}に関して、e[j]  = Open(<y[j]> + <b[j]>)  を生成する。 
この処理は、補助ベクトル生成処理（Ｓ２０３）と呼ばれる。
【０２０３】
ベクトル乗算処理部２０４は、全てのj ∈{N}に関して、<z[j]>=<c[j]>+ d[j]e[j] - e[j]<a[j]>- d[j]<b[j]> を生成する。
【０２０４】
本処理がベクトルの乗算処理であり、安全性を保証することを忘れれば、この処理が実質的な目的である。 
この処理は、ベクトル乗算処理（Ｓ２０４）と呼ばれる。
【０２０５】
補助ベクトルメッセージ認証子生成処理部２０５は、まず、全てのi ∈{M}に関して、<D[i]> = <X[i]>+ <A[i]> を生成する。
【０２０６】
引き続いて、補助ベクトルメッセージ認証子生成処理部２０５は、全てのi ∈{M}に関して、<E[i]> =<Y[i]>+<B[i]>  を生成する。
【０２０７】
ここで生成されたD[i], E[i]  は、d[i], e[i] のメッセージ認証子となっている。 
この処理は、補助ベクトルメッセージ認証子生成処理（Ｓ２０５）と呼ばれる。
【０２０８】
入力正当性確認処理部２０６は、まず、全てのi ∈{M}に関して、  0= Open(<D[i]>  -Σj∈{N} d[j]  <Γ[i,j]>) を確認する。
【０２０９】
引き続いて、入力正当性確認処理部２０６は、全てのi ∈{M}に関して、  0= Open(<E[i]>  -Σj∈{N} e[j]  <Γ[i,j]>) を確認する。
【０２１０】
補助ベクトルのメッセージ認証子が正しいことは、D[i]  -Σj∈{N} d[j]  Γ[i,j]=0, E[i]  -Σj∈{N} e[j]  Γ[i,j]=0 が成り立つことである。入力正当性確認処理部２０６は、これを秘密分散したまま計算し、結果を開示して確認している。これが確認されると、メッセージ認証子付ビーバー三重子が正しいものであったという仮定のもと、x[j]とy[j]のメッセージ認証子が正しかったことが確認される。 
この処理は、入力正当性確認処理（Ｓ２０６）と呼ばれる。
【０２１１】
出力メッセージ認証子生成処理部２０７は、全てのi ∈{M}に関して、 <Z[i]>=<C[i]>+Σj∈{N} d[j]e[j]  <Γ[i,j]> -Reshare(Σj∈{N} e[j](<Γ[i,j]>**<a[j]>)+ Σj∈{N} d[j](<Γ[i,j]>**<b[j]>)) を生成する。
【０２１２】
i ∈{M}に関する Z[i]は、出力z[j]に対するメッセージ認証子となっている。入力されたメッセージ認証子付ビーバー三重子が正しいものであれば、このメッセージ認証子は正しいものとなる。 
この処理は、出力メッセージ認証子生成処理（Ｓ２０７）と呼ばれる。
【０２１３】
次に、本発明の第５の実施形態に係るベクトル乗算システムの効果について説明する。メッセージ認証付ビーバー三重子の集合を、メッセージ認証子付ビーバー三重子を用いた隠然的に安全なベクトル乗算方法で利用してベクトル乗算を行っているので、各乗算が正しく行われたことが、正しいビーバー三重子の割合と同じ割合で保証することができる、という効果がある。
【０２１４】
［実施形態６］
図１１は、本発明の第６の実施形態に係るベクトル乗算システムを構成するベクトル乗算装置３０Ａのハードウェア構成を示すブロック図である。図示のベクトル乗算装置３０Ａは、プログラム制御により動作するコンピュータで実現可能である。
【０２１５】
図示のベクトル乗算システムは、メッセージ認証子付ビーバー三重子を用いた安全なベクトル乗算システムである。
【０２１６】
ベクトル乗算システムは、互いに通信が可能な複数のベクトル乗算装置３０Ａから成るシステムである。複数のベクトル乗算装置３０Ａは、これらのベクトル乗算装置３０Ａの間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える。
【０２１７】
ベクトル乗算装置３０Ａは、通信インターフェイス（以下、「通信Ｉ／Ｆ」と記す）３１と、データを入力する入力装置３２と、データを出力する出力装置３３と、後述するプログラムやデータを記憶する記憶装置３４Ａと、データを処理するデータ処理装置３５Ａとを備えている。
【０２１８】
通信Ｉ／Ｆ３１は、専用のデータ通信回線から成る。通信Ｉ／Ｆ３１は、通信ネットワーク（図示せず）を介してまたは無線によりデータを送受信する機能を有する。具体的には、通信Ｉ／Ｆ３１は、他のベクトル乗算装置へデータを送信し、他のベクトル乗算装置からデータを受信する。通信Ｉ／Ｆ３１は、受信したデータを、データ処理装置３５Ａへ送出する機能をも有する。
【０２１９】
入力装置３２は、キーボードやマウスなどから成る。入力装置３２は、オペレータの操作を検出して、その操作情報をデータ処理装置３５Ａへ送出する機能を有する。
【０２２０】
出力装置３３は、ＬＣＤ（Liquid Crystal Display）やＰＤＰ（Plasma Display Panel）などの表示装置やプリンタから成る。出力装置３３は、データ処理装置３５Ａからの指示に応じて、操作メニューなどの各種情報を表示したり、最終結果を印字出力する機能を有する。
【０２２１】
記憶装置３４Ａは、ハードディスクやリードオンリメモリ（ＲＯＭ）およびランダムアクセスメモリ（ＲＡＭ）などのメモリから成る。記憶装置３４Ａは、データ処理装置３５Ａにおける各種処理に必要な処理情報（後述する）やプログラム３１１Ａを記憶する機能を有する。
【０２２２】
データ処理装置３５Ａは、ＭＰＵ（micro processing unit）などのマイクロプロセッサや中央処理装置（ＣＰＵ）から成る。データ処理装置３５Ａは、記憶装置３４Ａからプログラム３１１Ａを読み込んで、プログラム３１１Ａに従ってデータを処理する各種処理部を実現する機能を有する。
【０２２３】
データ処理装置３５Ａで実現される主な処理部は、入力部３０１Ａ、ベクトル乗算部３０２Ａ、および結果同一確認処理部３０３から成る。
【０２２４】
入力部３０１Ａは、第１乃至第Ｔ（Ｔは２以上の整数）の入力処理モジュール３０１Ａ−１〜３０１Ａ−Ｔから成る。第１乃至第Ｔの入力処理モジュール３０１Ａ−１〜３０１Ａ−Ｔの各々は、図９のデータ処理装置２５Ａにおける事前計算処理部２０１Ａと入力処理部２０２Ａとから成る。
【０２２５】
ベクトル乗算部３０２Ａは、第１乃至第Ｔのベクトル乗算モジュール３０２Ａ−１〜３０２Ａ−Ｔから成る。第１乃至第Ｔのベクトル乗算モジュール３０２Ａ−１〜３０２Ａ−Ｔの各々は、図９のデータ処理装置２５Ａにおける、補助ベクトル生成処理部２０３と、ベクトル乗算処理部２０４と、補助ベクトルメッセージ認証子生成処理部２０５と、入力正当性確認処理部２０６と、出力メッセージ認証子生成処理部２０７とから成る。
【０２２６】
換言すれば、第１乃至第Ｔのベクトル乗算モジュール３０２Ａ−１〜３０２Ａ−Ｔの各々は、メッセージ認証子付ビーバー三重子を用いた隠然的に安全なベクトル乗算方法を実施する。
【０２２７】
結果同一確認処理部３０３は、第１乃至第Ｔのベクトル乗算モジュール３０２Ａ−１〜３０２Ａ−Ｔの乗算結果が全て同一の値であることを確認する。
【０２２８】
記憶装置３４Ａは、図９に図示された記憶装置２４Ａに記憶された処理情報と同様の処理情報を記憶する。すなわち、記憶装置３４Ａは、メッセージ認証子付ビーバー三重子の秘密分散データ３１２Ａ、乗算されるデータの秘密分散データ３１３Ａ、積の秘密分散データ３１５、補助ベクトル３１６、補助ベクトルメッセージ認証子の秘密分散データ３１７、メッセージ認証子の鍵の秘密分散データ３１８、および出力メッセージ認証子３１９を保存する。但し、記憶装置２４Ａとは異なり、記憶装置３４Ａは、それら情報をＴ個保存する。
【０２２９】
次に、図１２を参照して、図１１のデータ処理装置３５Ａの各処理部３０１Ａ〜３０３において行われる処理について更に詳細に説明する。
【０２３０】
Tを重複数とする。 
入力部３０１Ａでは、一つの入力に対してT個の同じ値の入力が準備されているとする（Ｓ３０１Ａ）。ただし、それぞれの秘密分散は独立しており、同じ入力に対する各参加者が所持するデータは全て互いにランダムに分布するとする。
【０２３１】
ベクトル乗算部３０２Ａは、前述の隠然的に安全な乗算方法をT個の入力に対して独立に適用する（Ｓ３０２Ａ）。
【０２３２】
適用後、結果同一確認処理部３０３は、結果が全て同一であることを次のように確認する。
【０２３３】
あるjに対するT個の結果が <z(1)[j]>,…, <z(T)[j]> であったとする。 
結果同一確認処理部３０３は、O=  Open(<z(u)[j]>=<z(u+1)[j]>) を全てのu=1,…,T-1 に対して確認する。 
この処理は、結果同一確認処理と呼ばれる（Ｓ３０３）。
【０２３４】
これらの確認も確率的な確認を多数行うことで、Open の数を減らすことができる。
【０２３５】
前述した第５の実施形態に係る隠然的に安全な方法では、ビーバー三重子が正しく生成されていなければ、答え乗算結果が正しいことは保証できなかった。一方、ビーバー三重子の検証方法から、ビーバー三重子が大量に作られていてかつ一定の割合を検査するならば、紛れ込ませることのできる不正なビーバー三重子の数は一定の小さな割合に留まった。
【０２３６】
それゆえ、本第６の実施形態では、複数の計算を同時に行い、それぞれの計算を異なるビーバー三重子で担保しているので、少なくとも一つの計算は正しいビーバー三重子で計算されるようになる確率を十分高くすることができる。その後、全ての計算が同一であることを確認すれば、全ての計算が正しいビーバー三重子による計算結果と同じになることが保証される。
【０２３７】
次に、本発明の第６の実施形態に係るベクトル乗算システムの効果について説明する。メッセージ認証付ビーバー三重子の集合を、メッセージ認証子付ビーバー三重子を用いた安全なベクトル乗算方法で利用してベクトル乗算を行っているので、各乗算が正しく行われたことが、圧倒的な確率で保証できる、という効果がある。
【０２３８】
この計算で通信が必要な処理は、Rehash, Open, Rand である。これらの回数は、M<<N<<Kであることを考えると、隠然的に安全な方法で乗算一個当たり５回、安全な方法で５T回である。
【０２３９】
次に、本発明の効果について説明する。
【０２４０】
以上説明した様に、本発明を用いれば、複数の装置にデータを分散して各装置にデータを隠ぺいしたまま乗算が可能になり、加算も既知の方法で可能なことを考えると、あわせて任意の関数を計算することが可能になる。また、参加装置が不正を働いたとしても、これを検知することができる。この計算に必要な通信量と計算量は小さい。この様なシステムは、ある装置で秘密のデータを扱ってなんらかのサービスを提供する時に、装置の管理者がデータを盗む出すことを防止する。なぜなら、複数の装置に異なる管理者を割り当てれば、一人で全ての装置中のデータを見ることのできる管理者がいなくなり、このような管理者を通じたデータの盗み出しを防止することに貢献するからである。
【０２４１】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、複数の構成要素の適宜な組合せにより種々の発明を形成できる。
【０２４２】
なお、本発明に記載した方法は、コンピュータに実行させることができる。この方法を実行させるプログラムは、フロッピー（登録商標）ディスク、ハードディスクなどの磁気ディスク、ＣＤ-ＲＯＭ（Compact Disc- Read Only Memory）、ＤＶＤ（digital versatile disc）などの光ディスク、光磁気ディスク（ＭＯ）、半導体メモリなどの記録媒体に格納して頒布することもできる。
【０２４３】
また、この記録媒体としては、プログラムを記憶でき、かつコンピュータが読み取り可能な記録媒体であれば、その記憶形式は何れの形態であってもよい。
【０２４４】
また、記録媒体からコンピュータにインストールされたプログラムの指示に基づきコンピュータ上で稼働しているオペレーティングシステムや、データベース管理ソフト、ネットワークソフト等のミドルウェアなどが各処理の一部を実行してもよい。
【０２４５】
さらに、本発明における記録媒体は、コンピュータと独立した媒体に限らず、ＬＡＮ（Local Area Network）やインターネットなどにより伝送されたプログラムをダウンロードして記憶または一時記憶した記録媒体も含まれる。
【０２４６】
また、記録媒体は１つに限らず、複数の媒体から上記実施形態における処理が実行される場合も本発明における記録媒体に含まれ、媒体構成は何れの構成であってもよい。
【０２４７】
本発明におけるコンピュータは、記録媒体に記憶されたプログラムに基づき各処理を実行するものであって、パソコンなどからなる装置、複数の装置がネットワーク接続されたシステムなどの何れの構成であってもよい。
【０２４８】
また、本発明におけるコンピュータとは、パソコンに限らず、情報処理機器に含まれる演算処理装置を含み、プログラムによって本発明の機能を実現することが可能な機器、装置である。
【０２４９】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０２５０】
（付記１）  複数の他の事前計算装置と通信可能な事前計算装置（１０；１０Ａ）であって、
秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理部（１０１）と、
前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理部（１０２）と、
前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理部（１０３；１０３Ａ）と、
を備える事前計算装置（１０；１０Ａ）。
【０２５１】
（付記２）  付記１に記載の事前計算装置（１０）を、複数個、通信可能に備える、ビーバー三重子の安全な事前計算システム。
【０２５２】
（付記３）  前記事前計算装置（１０Ａ）は、前記複数の他の事前計算装置と当該事前計算装置（１０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備え、
前記ビーバー三重子位置攪拌処理部（１０３Ａ）は、前記復元しなかったビーバー三重子をランダムに並び替えて、新しいインデックスを付けて並び替えた後の秘密分散されたビーバー三重子を生成し、
前記事前計算装置（１０Ａ）は、
前記並び替えた後の秘密分散されたビーバー三重子に対してその秘密分散されたメッセージ認証子を、前記秘密分散されたメッセージ認証子の鍵を使用して、当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成するビーバー三重子メッセージ認証子生成処理部（１０４）と、
前記並び替えた後の秘密分散されたビーバー三重子のランダムに選んだ係数による線形和を多数生成し、この多数生成した値を復元して復元された値を生成する処理と、前記秘密分散されたビーバー三重子のメッセージ認証子を前記係数による線形和を多数生成した値と、前記復元された値を前記秘密分散されたメッセージ認証子の鍵による線形和を多数生成した値とが同一であることを確認する処理とを実施するビーバー三重子メッセージ認証子検証処理部（１０５）と、
を更に備える、付記１に記載の事前計算装置（１０Ａ）。
【０２５３】
（付記４）  付記３に記載の事前計算装置（１０Ａ）を、複数個、通信可能に備える、メッセージ認証子付ビーバー三重子の安全な事前計算システム。
【０２５４】
（付記５）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（２０；２０Ａ）であって、
ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データが入力される事前計算入力処理部（２０１；２０１Ａ）と、
乗算されるべき二つの数の組の秘密分散データが複数個入力される入力処理部（２０２；２０２Ａ）と、
前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０；２０Ａ）とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理部（２０３）と、
前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理部（２０４）と、
を備えるベクトル乗算装置（２０；２０Ａ）。
【０２５５】
（付記６）  付記５に記載のベクトル乗算装置（２０）を、複数個、通信可能に備える、ビーバー三重子を用いた隠然的に安全なベクトル乗算システム。
【０２５６】
（付記７）  前記ベクトル乗算装置（２０Ａ）は、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備え、
前記事前計算入力処理部（２０１Ａ）は、メッセージ認証子付ビーバー三重子の秘密分散データを生成し、あるいは前記メッセージ認証子付ビーバー三重子の秘密分散データが入力され、
前記入力処理部（２０２Ａ）は、前記乗算されるべき二つの数の組の秘密分散データを複数個に加えて、前記複数個の乗算されるべき二つの数の組それぞれに対するメッセージ認証子の秘密分散データをも入力され、
前記ベクトル乗算装置（２０Ａ）は、
前記補助ベクトルに対するメッセージ認証子の秘密分散データを、前記入力に対するメッセージ認証子の秘密分散データと前記ビーバー三重子に対するメッセージ認証子の秘密分散データとから生成する補助ベクトルメッセージ認証子生成処理部（２０５）と、
前記補助ベクトルに対するメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データとから、前記補助ベクトルを検証する入力正当性確認処理部（２０６）と、
前記ベクトル乗算結果のメッセージ認証子の秘密分散データを、前記ビーバー三重子のメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データと、前記ビーバー三重子の秘密分散データとから、出力メッセージ認証子として生成する出力メッセージ認証子生成処理部（２０７）と、
を更に備える、付記５に記載のベクトル乗算装置（２０Ａ）。
【０２５７】
（付記８）  付記７に記載のベクトル乗算装置（２０Ａ）を、複数個、通信可能に備える、メッセージ認証子付ビーバー三重子を用いた隠然的に安全なベクトル乗算システム。
【０２５８】
（付記９）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（３０）であって、
付記５に記載のベクトル乗算装置（２０）を構成する、前記事前計算入力処理部（２０１）、前記入力処理部（２０２）、前記補助ベクトル生成処理部（２０３）、および前記ベクトル乗算処理部（２０４）を、それぞれ、複数個備え、
複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理部（３０３）を備える、
ベクトル乗算装置（３０）。
【０２５９】
（付記１０）  付記９に記載のベクトル乗算装置（３０）を、複数個、通信可能に備える、ビーバー三重子を用いた安全なベクトル乗算システム。
【０２６０】
（付記１１）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（３０Ａ）であって、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（３０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備えるベクトル乗算装置（３０Ａ）において、
付記７に記載のベクトル乗算装置（２０Ａ）を構成する、前記事前計算入力処理部（２０１Ａ）、前記入力処理部（２０２Ａ）、前記補助ベクトル生成処理部（２０３）、前記ベクトル乗算処理部（２０４）、前記補助ベクトルメッセージ認証子生成処理部（２０５）、前記入力正当性確認処理部（２０６）、および前記出力メッセージ認証子生成処理部（２０７）を、それぞれ、複数個備え、
複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理部（３０３）を備える、
ベクトル乗算装置（３０Ａ）。
【０２６１】
（付記１２）  付記１１に記載のベクトル乗算装置（３０Ａ）を、複数個、通信可能に備える、メッセージ認証子付ビーバー三重子を用いた安全なベクトル乗算システム。
【０２６２】
（付記１３）  複数の他の事前計算装置と通信可能な事前計算装置（１０）において行われる事前計算方法であって、
ビーバー三重子生成処理部（１０１）が、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成し、
ビーバー三重子ランダム検査処理部（１０２）が、前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認し、
ビーバー三重子位置攪拌処理部（１０３）が、前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成する、
事前計算方法。
【０２６３】
（付記１４）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（２０）において行われるベクトル乗算方法であって、
事前計算入力処理部（２０１）が、ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データを入力し、
入力処理部（２０２）が、乗算されるべき二つの数の組の秘密分散データを複数個入力し、
補助ベクトル生成処理部（２０３）が、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０）とが互いに通信して開示した結果である補助ベクトルを生成し、
ベクトル乗算処理部（２０４）が、前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成する、
ベクトル乗算方法。
【０２６４】
（付記１５）  前記事前計算入力処理部（２０１）、前記入力処理部（２０２）、前記補助ベクトル生成処理部（２０３）、および前記ベクトル乗算処理部（２０４）が、各処理を全て複数個実施し、
結果同一確認処理部（３０３）が、複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する
付記１４に記載のベクトル乗算方法。
【０２６５】
（付記１６）  複数の他の事前計算装置と通信可能な事前計算装置（１０Ａ）において行われる事前計算方法であって、前記複数の他の事前計算装置と当該事前計算装置（１０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える、事前計算装置（１０Ａ）の事前計算方法において、
ビーバー三重子生成処理部（１０１）が、秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成し、
ビーバー三重子ランダム検査処理部（１０２）が、前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認し、
ビーバー三重子位置攪拌処理部（１０３Ａ）が、前記復元しなかったビーバー三重子をランダムに並び替えて、新しいインデックスを付けて並び替えた後の秘密分散されたビーバー三重子を生成し、
ビーバー三重子メッセージ認証子生成処理部（１０４）が、前記並び替えた後の秘密分散されたビーバー三重子に対してその秘密分散されたメッセージ認証子を、前記秘密分散されたメッセージ認証子の鍵を使用して、当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成し、
ビーバー三重子メッセージ認証子検証処理部（１０５）が、前記並び替えた後の秘密分散されたビーバー三重子のランダムに選んだ係数による線形和を多数生成し、この多数生成した値を復元して復元された値を生成する処理と、前記秘密分散されたビーバー三重子のメッセージ認証子を前記係数による線形和を多数生成した値と、前記復元された値を前記秘密分散されたメッセージ認証子の鍵による線形和を多数生成した値とが同一であることを確認する処理とを実施する、
事前計算方法。
【０２６６】
（付記１７）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（２０Ａ）において行われるベクトル乗算方法であって、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える、ベクトル乗算装置（２０Ａ）のベクトル情報方法において、
事前計算入力処理部（２０１Ａ）が、メッセージ認証子付のビーバー三重子の秘密分散データを生成し、あるいは前記メッセージ認証子付のビーバー三重子の秘密分散データを入力し、
入力処理部（２０２Ａ）が、乗算されるべき二つの数の組の秘密分散データを複数個と、前記複数個の乗算されるべき二つの数の組それぞれに対するメッセージ認証子の秘密分散データとを入力し、
補助ベクトル生成処理部（２０３）が、前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０Ａ）とが互いに通信して開示した結果である補助ベクトルを生成し、
ベクトル乗算処理部（２０４）が、前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成し、
補助ベクトルメッセージ認証子生成処理部（２０５）が、前記補助ベクトルに対するメッセージ認証子の秘密分散データを、前記入力に対するメッセージ認証子の秘密分散データと前記ビーバー三重子に対するメッセージ認証子の秘密分散データとから生成し、
入力正当性確認処理部（２０６）が、前記補助ベクトルに対するメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データとから、前記補助ベクトルを検証し、
出力メッセージ認証子生成処理部（２０７）が、前記ベクトル乗算結果のメッセージ認証子の秘密分散データを、前記ビーバー三重子のメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データと、前記ビーバー三重子の秘密分散データとから、出力メッセージ認証子として生成する、
ベクトル乗算方法。
【０２６７】
（付記１８）  前記事前計算入力処理部（２０１Ａ）、前記入力処理部（２０２Ａ）、前記補助ベクトル生成処理部（２０３）、前記ベクトル乗算処理部（２０４）、前記補助ベクトルメッセージ認証子生成処理部（２０５）、前記入力正当性確認処理部（２０６）、および前記出力メッセージ認証子生成処理部（２０７）が、各処理を全て複数個実施し、
結果同一確認処理部（３０３）が、複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する
付記１７に記載のベクトル乗算方法。
【０２６８】
（付記１９）  複数の他の事前計算装置と通信可能な事前計算装置（１０）のコンピュータを、
秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理手段（１０１）、
前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理手段（１０２）、および
前記復元しなかったビーバー三重子をランダムに並び替えて、並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理手段（１０３）、
として機能させるための事前計算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２６９】
（付記２０）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（２０）のコンピュータを、
ビーバー三重子の秘密分散データを生成し、あるいは前記ビーバー三重子の秘密分散データを入力する事前計算入力処理手段（２０１）、
乗算されるべき二つの数の組の秘密分散データを複数個入力する入力処理手段（２０２）、
前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理手段（２０３）、および
前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理手段（２０４）、
として機能させるためのベクトル乗算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２７０】
（付記２１）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（３０）のコンピュータを、
付記２０に記載の、前記事前計算入力処理手段、前記入力処理手段、前記補助ベクトル生成処理手段、および前記ベクトル乗算処理手段として、それぞれ、複数個、機能させ、
更に、複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理手段、
として機能させるためのベクトル乗算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２７１】
（付記２２）  複数の他の事前計算装置と通信可能な事前計算装置（１０Ａ）であって、前記複数の他の事前計算装置と当該事前計算装置（１０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える、事前計算装置（１０Ａ）のコンピュータを、
秘密分散された二つの乱数を生成し、この二つの乱数の積の秘密分散された値を当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成することで、二つの乱数とそれらの積からなる三つ組みを当該事前計算装置と前記複数の他の事前計算装置とで秘密分散する機能を繰り返し使うことで、多数の秘密分散されたビーバー三重子を生成するビーバー三重子生成処理手段（１０１）、
前記秘密分散されたビーバー三重子をランダムに選び、互いに当該事前計算装置と前記複数の他の事前計算装置とが通信することでこれらのビーバー三重子を復元し、復元したビーバー三重子の値を用いて最初の二つの要素の積が第三の要素となっていることを確認するビーバー三重子ランダム検査処理手段（１０２）、
前記復元しなかったビーバー三重子をランダムに並び替えて、新しいインデックスを付けて並び替えた後の秘密分散されたビーバー三重子を生成するビーバー三重子位置攪拌処理手段（１０３Ａ）、
前記並び替えた後の秘密分散されたビーバー三重子に対してその秘密分散されたメッセージ認証子を、前記秘密分散されたメッセージ認証子の鍵を使用して、当該事前計算装置と前記複数の他の事前計算装置とが互いに通信することで生成するビーバー三重子メッセージ認証子生成処理手段（１０４）、および
前記並び替えた後の秘密分散されたビーバー三重子のランダムに選んだ係数による線形和を多数生成し、この多数生成した値を復元して復元された値を生成する処理と、前記秘密分散されたビーバー三重子のメッセージ認証子を前記係数による線形和を多数生成した値と、前記復元された値を前記秘密分散されたメッセージ認証子の鍵による線形和を多数生成した値とが同一であることを確認する処理とを実施するビーバー三重子メッセージ認証子検証処理手段（１０５）、
として機能させるための事前計算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２７２】
（付記２３）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（２０Ａ）であって、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（２０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備える、ベクトル乗算装置（２０Ａ）のコンピュータを、
メッセージ認証子付ビーバー三重子の秘密分散データを生成し、あるいは前記メッセージ認証子付ビーバー三重子の秘密分散データを入力する事前計算入力処理手段（２０１Ａ）、
乗算されるべき二つの数の組の秘密分散データを複数個と、前記複数個の乗算されるべき二つの数の組それぞれに対するメッセージ認証子の秘密分散データとを入力する入力処理手段（２０２Ａ）、
前記乗算されるべき二つの組の秘密分散データそれぞれに対して、前記ビーバー三重子の秘密分散データそれぞれの一つの要素を加算し、加算結果の秘密分散されたデータを、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置とが互いに通信して開示した結果である補助ベクトルを生成する補助ベクトル生成処理手段（２０３）、
前記補助ベクトルと前記ビーバー三重子の秘密分散データとから、ベクトル乗算結果の秘密分散データを生成するベクトル乗算処理手段（２０４）、
前記補助ベクトルに対するメッセージ認証子の秘密分散データを、前記入力に対するメッセージ認証子の秘密分散データと前記ビーバー三重子に対するメッセージ認証子の秘密分散データとから生成する補助ベクトルメッセージ認証子生成処理手段（２０５）、
前記補助ベクトルに対するメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データとから、前記補助ベクトルを検証する入力正当性確認処理手段（２０６）、および
前記ベクトル乗算結果のメッセージ認証子の秘密分散データを、前記ビーバー三重子のメッセージ認証子の秘密分散データと、前記補助ベクトルと、前記メッセージ認証子の鍵の秘密分散データと、前記ビーバー三重子の秘密分散データとから、出力メッセージ認証子として生成する出力メッセージ認証子生成処理手段（２０７）、
として機能させるためのベクトル乗算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２７３】
（付記２４）  複数の他のベクトル乗算装置と通信が可能なベクトル乗算装置（３０Ａ）であって、前記複数の他のベクトル乗算装置と当該ベクトル乗算装置（３０Ａ）との間で、メッセージ認証子の鍵を秘密分散して保持する機能を備えるベクトル乗算装置（３０Ａ）のコンピュータを、
付記２３に記載の、前記事前計算入力処理手段（２０１Ａ）、前記入力処理手段（２０２Ａ）、前記補助ベクトル生成処理手段（２０３）、前記ベクトル乗算処理手段（２０４）、前記補助ベクトルメッセージ認証子生成処理手段（２０５）、前記入力正当性確認処理手段（２０６）、および前記出力メッセージ認証子生成処理手段（２０７）として、それぞれ、複数個、機能させ、
更に、複数個の前記ベクトル乗算結果の秘密分散データが全て同一の値であることを確認する結果同一確認処理手段（３０３）、
として機能させるためのベクトル乗算プログラムを記録したコンピュータ読取可能な記録媒体。
【０２７４】
この出願は、２０１５年１２月１０日に出願された日本出願特願２０１５−２４１２５１を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【符号の説明】
【０２７５】
１０、１０Ａ  事前計算装置
１１  通信Ｉ／Ｆ
１２  入力装置
１３  出力装置
１４、１４Ａ  記憶装置
１５、１５Ａ  データ処理装置
１０１  ビーバー三重子生成処理部
１０２  ビーバー三重子ランダム検査処理部
１０３、１０３Ａ  ビーバー三重子位置攪拌処理部
１０４  ビーバー三重子メッセージ認証子生成処理部
１０５  ビーバー三重子メッセージ認証子検証処理部
１１１、１１１Ａ  プログラム
１１２  乱数
１１３  ビーバー三重子の秘密分散データ
１１４、１１４Ａ  攪拌済みビーバー三重子の秘密分散データ
１１５  メッセージ認証子の鍵の秘密分散データ
１１６  攪拌済みビーバー三重子とそのメッセージ認証子の秘密分散データ
２０、２０Ａ、３０、３０Ａ  ベクトル乗算装置
２１、３１  通信Ｉ／Ｆ
２２、３２  入力装置
２３、３３  出力装置
２４、２４Ａ、３４、３４Ａ  記憶装置
２５、２５Ａ、３５、３５Ａ  データ処理装置
２０１、２０１Ａ  事前計算入力処理部
２０２、２０２Ａ  入力処理部
２０３  補助ベクトル生成処理部
２０４  ベクトル乗算処理部
２０５  補助ベクトルメッセージ認証子生成処理部
２０６  入力正当性確認処理部
２０７  出力メッセージ認証子生成処理部
２１１、２１１Ａ、３１１、３１１Ａ  プログラム
２１２、３１２    ビーバー三重子の秘密分散データ
２１２Ａ、３１２Ａ  メッセージ認証子付ビーバー三重子の秘密分散データ
２１３、３１３  乗算されるデータの秘密分散データ
２１３Ａ、３１３Ａ  乗算されるデータの秘密分散データ
２１５、３１５  積の秘密分散データ
２１６、３１６  補助ベクトル
２１７、３１７  補助ベクトルメッセージ認証子の秘密分散データ
２１８、３１８  メッセージ認証子の鍵の秘密分散データ
２１９、３１９  出力メッセージ認証子
３０１  入力部
３０１Ａ  入力部
３０１−１〜３０１−Ｔ  入力処理モジュール
３０１Ａ−１〜３０１Ａ−Ｔ  入力処理モジュール
３０２  ベクトル乗算部
３０２Ａ  ベクトル乗算部
３０２−１〜３０２−Ｔ  ベクトル乗算モジュール
３０２Ａ−１〜３０２Ａ−Ｔ  ベクトル乗算モジュール
３０３    結果同一確認処理部
【図１】
2017099117.tif 000003
【図２】
2017099117.tif 000004
【図３】
2017099117.tif 000005
【図４】
2017099117.tif 000006
【図５】
2017099117.tif 000007
【図６】
2017099117.tif 000008
【図７】
2017099117.tif 000009
【図８】
2017099117.tif 000010
【図９】
2017099117.tif 000011
【図１０】
2017099117.tif 000012
【図１１】
2017099117.tif 000013
【図１２】
2017099117.tif 000014
【国際調査報告】
2017099117.tif 000015
2017099117.tif 000016
2017099117.tif 000017