(57)【要約】【課題】マルチパーティ・プロトコルの分散乗算におけるメンバ間の相互通信量を小さくすることができる分散乗算装置及び分散乗算システムを提供する。【解決手段】分散乗算装置は、マルチパーティ・プロトコルを実行するシステムを構成する第１乃至第ｎの分散計算装置のそれぞれに含まれる。分散乗算装置は、ｉｉ項計算部と、ｉｊ項計算部と、これらの出力を加算する多項加算部とを有する。ｉｊ項計算部は、項計算受信部１００２と項計算送信部を有する。項計算受信部１００２は、２値展開部１１０１と、ｌｏｇ２（ｑ−１）を小数点切り上げした個数（ｑｂ個）の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２と、多項加算部１１０３とを有する。項計算送信部は、乱数生成部と、ｑｂ個の送信情報生成部と、ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失送信部とを有する。分散乗算装置は、他の分散乗算装置と紛失通信しながら分散乗算を行う。【選択図】        図１
2004341766.tif 000002
【特許請求の範囲】
【請求項１】
マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う第１乃至第ｎ（ｎは２以上のある整数）の分散乗算装置のうちの１つである、第ｊ（ｊは１以上ｎ以下のある整数）の分散乗算装置であって、
有限体ＧＦ（ｑ）上の２つの値の分散情報が、上記第１乃至第ｎの分散乗算装置のそれぞれに２つずつ入力される場合に、
＜Ｉ＞  上記第ｊの分散計算装置へ入力される２つの分散情報を掛け合わせ、さらに、上記第１乃至第ｎの分散計算装置に固有のメンバＩＤから計算される係数を掛け合わせる第１の乗算手段と、
＜ＩＩ＞  上記第ｊの分散計算装置へ入力される一方の分散情報と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置へ入力される分散情報との所定の演算処理を紛失通信を通して行う第１の通信計算手段と、
＜ＩＩＩ＞  上記第ｊの分散計算装置へ入力される他方の分散情報と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置へ入力される分散情報との所定の演算処理を紛失通信を通して行う第２の通信計算手段と、
＜ＩＶ＞  上記第１の通信計算手段の出力と上記第２の通信計算手段の出力とを足し合わせる第１の加算手段と、
＜Ｖ＞  上記第１の加算手段の出力に、上記第１乃至第ｎの分散計算装置に固有のメンバＩＤから計算される係数を掛け合わせる第２の乗算手段と、
＜ＶＩ＞  上記第１の乗算手段の出力と、第２の乗算手段の出力とを足し合わせる第２の加算手段と
を有し、
＜ＶＩＩ＞  上記第１及び第２の通信計算手段それぞれが、紛失通信送信手段及び紛失通信受信手段のうちの少なくとも一方を有し、
＜ＶＩＩＩ＞  上記紛失通信送信手段が、
有限体ＧＦ（ｑ）上の乱数を、ｌｏｇ２（ｑ−１）を小数点切り上げした第１の個数生成する乱数生成手段と、
上記乱数生成手段からの出力と、上記第ｊの分散計算装置のこの紛失通信送信手段へ入力される２つの分散情報とから紛失送信情報を生成する送信情報生成手段と、
上記乱数生成手段から出力される第１の個数の乱数を足し合わせる第３の加算手段と、
第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置との間で紛失通信による送信を行う第１の個数の１−ｏｕｔ−ｏｆ−２紛失送信手段と
を有し、
＜ＩＸ＞  上記紛失通信受信手段が、
入力される分散情報を２値展開する２値展開手段と、
第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置から紛失通信により送信情報を受信する第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段と、
上記１−ｏｕｔ−ｏｆ−２紛失受信手段で受信した第１の個数の値を足し合わせる第４の加算手段と
を有する
ことを特徴とする分散乗算装置。
【請求項２】
マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う第１乃至第ｎ（ｎは２以上のある整数）の分散乗算装置のうちの１つである、第ｊ（ｊは１以上ｎ以下のある整数）の分散乗算装置であって、
有限体ＧＦ（ｑ）上の２つの値の分散情報が、上記第１乃至第ｎの分散乗算装置のそれぞれに２つずつ入力される場合に、
＜Ｉ＞  上記第ｊの分散計算装置へ入力される２つの分散情報を掛け合わせる第１の乗算手段と、
＜ＩＩ＞  上記第ｊの分散計算装置へ入力される一方の分散情報と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置へ入力される分散情報との所定の演算処理を紛失通信を通して行う第１の通信計算手段と、
＜ＩＩＩ＞  上記第ｊの分散計算装置へ入力される他方の分散情報と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置へ入力される分散情報との所定の演算処理を紛失通信を通して行う第２の通信計算手段と、
＜ＩＶ＞  上記第１の乗算手段の出力と、上記第１の通信計算手段の出力と、上記第２の通信計算手段の出力とを足し合わせる第１の加算手段と
を有し、
＜Ｖ＞  上記第１及び第２の通信計算手段が、紛失通信送信手段及び紛失通信受信手段の少なくとも一方を有し、
＜ＶＩ＞  上記紛失通信送信手段が、
有限体ＧＦ（ｑ）上の乱数を、ｌｏｇ２（ｑ−１）を小数点切り上げした第１の個数生成する乱数生成手段と、
上記乱数生成手段からの出力と、上記第ｊの分散計算装置のこの紛失通信送信手段へ入力される２つの分散情報とから紛失送信情報を生成する送信情報生成手段と、
上記乱数生成手段から出力される第１の個数の乱数を足し合わせる第３の加算手段と、
第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への紛失送信を行う第１の個数の１−ｏｕｔ−ｏｆ−２紛失送信手段と
を有し、
＜ＶＩＩ＞  上記紛失通信受信手段が、
入力される分散情報を２値展開する２値展開手段と、
第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置からの送信情報を紛失通信により受信する第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段と、
上記１−ｏｕｔ−ｏｆ−２紛失受信手段で受信した第１の個数の値を足し合わせる第４の加算手段と
を有する
ことを特徴とする分散乗算装置。
【請求項３】
マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う分散乗算システムであって、
請求項１に記載の分散乗算装置と同じ構成を有する分散乗算装置を複数有することを特徴とする分散乗算システム。
【請求項４】
マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う分散乗算システムであって、
請求項２に記載の分散乗算装置と同じ構成を有する分散乗算装置を複数有することを特徴とする分散乗算システム。
【請求項５】
マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う分散乗算システムであって、
＜Ｉ＞  項計算送信手段と、
＜ＩＩ＞  通信路と
＜ＩＩＩ＞  上記通信路を通して上記項計算送信手段との間で紛失通信をする項計算受信手段と
を有し、
＜ＩＶ＞  上記項計算送信手段が、
有限体ＧＦ（ｑ）上の乱数を、ｌｏｇ２（ｑ−１）を小数点切り上げした第１の個数生成する乱数生成手段と、
上記２つの値のうちの一方の値の分散情報のいずれかが入力され、その入力された分散情報と上記乱数生成手段で生成された乱数とを用いた演算によって第１の個数の２倍の第２の個数の送信情報を生成する送信情報生成手段と、
上記送信情報生成手段で生成された上記送信情報が２個入力され、その入力された送信情報を紛失通信により送信する第１の個数の１−ｏｕｔ−ｏｆ−２紛失送信手段と、
上記乱数生成手段により生成された第１の個数の乱数を足し合わせる第１の加算手段と
を有し、
＜Ｖ＞  上記項計算受信手段が、
上記２つの値のうちの他方の値の分散情報のいずれかが入力され、その入力された分散情報を２値展開し、第１の個数のビット信号を出力する２値展開手段と、
上記２値展開手段から出力されるビット信号が１個ずつ入力され、上記項計算送信手段からの送信情報を紛失通信により受信し、入力されたビット信号と上記受信した送信情報とを用いた演算により得られた信号を出力する第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段と、
上記第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段から出力された第１の個数の出力値を足し合わせる第２の加算手段と
を有し、
＜ＶＩ＞  上記紛失通信が、上記１−ｏｕｔ−ｏｆ−２紛失送信手段は２個の情報を符号化して送信するが、上記１−ｏｕｔ−ｏｆ−２紛失受信手段はそのうち１つしか受け取ることができず、且つ、上記１−ｏｕｔ−ｏｆ−２紛失送信手段は上記１−ｏｕｔ−ｏｆ−２紛失受信手段がいずれの情報を受け取ったかを知ることができない通信方式である
ことを特徴とする分散乗算システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、乗算計算を分散的に実行する分散乗算装置及び分散乗算システムに関するものである。
【０００２】
【従来の技術】
［マルチパーティ・プロトコルの説明］
マルチパーティ・プロトコルは、ある関数への入力値を公開せずに、その関数の計算を集まったメンバで協力して行う方式であり、分散計算とも呼ばれる（例えば、非特許文献１参照）。マルチパーティ・プロトコルには、大きく分けて２つの方式がある。方式〔１〕は、計算するために集まったメンバのうち、どの２人のメンバ間にも、その２人のメンバ以外には通信内容を秘密とすることができる秘密通信路が確立されていることを前提とする方式である。方式〔２〕は、計算するために集まったメンバ間の通信には、前述した秘密通信路による通信方法に加え、紛失通信と呼ばれる通信手法を用いる方式である。非特許文献１には、マルチパーティ・プロトコルの方式〔２〕における、バイナリ計算（ＮＯＴとＡＮＤの計算）の場合の説明が記載されている。本発明は方式〔２〕における有限体要素の乗算計算に関するものである。ここでは、方式〔２〕のバイナリ計算の場合を拡張した、有限体要素の計算（加算、定数乗算、及び、乗算の計算）について説明する。
【０００３】
図３は、マルチパーティ・プロトコルの概要を説明する図である。ここでは、マルチパーティ・プロトコルを実行するメンバ（すなわち、後述する図４又は図５の分散計算装置１０１）がｎ人いる場合を説明する。図３に示されるように、メンバのそれぞれは、メンバＩＤ  ｍｊ（ｊ＝１，２，…，ｎ）と、メンバ固有の秘密情報Ｘｊ（ｊ＝１，２，…，ｎ）とを保有している。各メンバは、次式（１）で示されるような関数計算結果Ｙをマルチパーティ・プロトコルを用いて分散計算し、最終的にその計算結果Ｙの分散情報Ｙｊ（ｊ＝１，２，…，ｎ）を得たいとする。
Ｙ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）    …（１）
【０００４】
ここで、各メンバのメンバＩＤ  ｍｊ及び秘密情報Ｘｊ（ｊ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）（ｑは素数又は素数のべき乗）上の値であるとする。また、式（１）の関数ｆでの演算は有限体ＧＦ（ｑ）上の演算であるとする。各メンバ固有の秘密情報Ｘｊ（ｊ＝１，２，…，ｎ）を、他のメンバに公開しないまま、関数計算結果Ｙ（の分散情報Ｙｊ（ｊ＝１，２，…，ｎ））を計算するために、マルチパーティ・プロトコルにおいては、まず、各メンバ固有の秘密情報Ｘｊ（ｊ＝１，２，…，ｎ）を、秘密分散法を用いて秘密分散し（図３の処理▲１▼）、他のメンバに配布する（図３の処理▲２▼）。
【０００５】
秘密分散法には、非特許文献１で説明されている（ｋ，ｎ）しきい値秘密分散法や、分散情報すべてを足し合わせるともとの秘密情報となるような秘密分散法（ここでは「加算秘密分散法」と呼ぶ。）などがある。以下の説明においては、図３の処理▲１▼において（ｋ，ｎ）しきい値秘密分散法を用いるマルチパーティ・プロトコルを方式〔２．１〕とし、図３の処理▲１▼において加算秘密分散法を用いるマルチパーティ・プロトコルを方式〔２．２〕とする。
【０００６】
（ｋ，ｎ）しきい値秘密分散法を用いる方式〔２．１〕の場合、メンバＩＤがｍｊであるメンバの秘密情報がＸｊであるとすると、このメンバは、乱数Ｒｊ，１、Ｒｊ，２、…、Ｒｊ，ｋ−１として有限体ＧＦ（ｑ）上の値をｋ−１個選んで、
ｆｊ（ｘ）
＝Ｘｊ＋Ｒｊ，１ｘ＋Ｒｊ，２ｘ２＋…＋Ｒｊ，ｋ−１ｘｋ−１    …（２）
なるｋ−１次の多項式（ｋ≦ｎ）を作る。
【０００７】
メンバＩＤがｍｊであるメンバは、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに対して配布する分散情報Ｘｊ，ｐを、式（２）を用いて次式（３）のように計算する（図３の処理▲１▼）。
2004341766.tif 000003
【０００８】
メンバＩＤがｍｊであるメンバは、計算した分散情報Ｘｊ，ｐを、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する（図３の処理▲２▼）。必要ならば、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバ以外には秘密となるよう、秘密通信路を用いてメンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する。ここで、式（２）及び式（３）は、有限体ＧＦ（ｑ）上の演算である。
【０００９】
加算秘密分散法を用いる方式〔２．２〕の場合、メンバＩＤがｍｊであるメンバの秘密情報をＸｊとすると、このメンバは、ＧＦ（ｑ）上の乱数をｎ−１個生成し、生成された乱数をＸｊ，ｉ（ｉ＝１，２，…，ｎでｉ≠ｊとなるもの）とし、次式（４）を計算して、ｎ個の分散情報Ｘｊ，ｐ（ｐ＝１，２，…，ｎ）を求める（図３の処理▲１▼）。
【数１】
2004341766.tif 000004
【００１０】
メンバＩＤがｍｊであるメンバは、計算した分散情報Ｘｊ，ｐを、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する（図３の処理▲２▼）。必要ならば、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバ以外には秘密となるよう、秘密通信路を用いてメンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布する。ここで、式（４）は有限体ＧＦ（ｑ）上の演算である。
【００１１】
このようにすると、（方式〔２．１〕及び方式〔２．２〕のどちらの場合でも）各メンバは、他の各メンバの秘密情報の分散情報を持っている状態になる。メンバＩＤがｍｊであるメンバは、他のメンバから配布された分散情報（及び自分自身の秘密情報の分散情報）として、Ｘ１，ｊ、Ｘ２，ｊ、…、Ｘｎ，ｊのｎ個の分散情報を持っていることになる。マルチパーティ・プロトコルにおいては、各メンバにおいて、各自持っている分散情報を用いて、与えられた式（１）の関数計算を行い、最終的に、計算結果であるＹの分散情報Ｙｊ（ｊ＝１，２，…，ｎ）を持っている状態にする。図３の分散計算部分（図３の処理▲３▼）において、任意の値の有限体加算、有限体定数乗算、有限体乗算を分散計算可能であるとすると、式（１）で示される関数計算で、それら有限体加算、有限体定数乗算、有限体乗算を用いた計算をマルチパーティ・プロトコルで計算できることになる。
【００１２】
［分散計算システムの説明］
図４は、分散計算システムの構成を示す図である。図４に示される分散計算システムは、複数の分散計算装置（即ち、複数のメンバ）１０１と、複数の分散計算装置１０１間を相互に接続する通信路１０２とを有する。各分散計算装置１０１には、メンバＩＤ  ｍｊ（ｊ＝１，２，…，ｎ）が割り当てられている。各分散計算装置１０１は、互いに協力し合って分散計算を行い、計算結果（厳密には、計算結果の分散情報）を求める。また、メンバのうち、どの２人のメンバ間にも、相互に通信できる通信路１０２が確立されている。
【００１３】
［分散計算装置１０１の説明］
図５は、分散計算装置１０１の構成を示すブロック図である。分散計算装置１０１は、各自が保有する秘密情報Ｘｊを秘密分散して他のメンバの分散計算装置１０１へ配布する秘密分散部２０１と、他のメンバの分散計算装置１０１からの分散情報を受け取って、それら分散情報を用いて分散計算を行う分散計算部（すなわち、分散計算装置）２０２からなる。
【００１４】
秘密分散部２０１は、方式〔２．１〕の場合には式（２）及び式（３）を用い、方式〔２．２〕の場合には式（４）を用いて、分散情報Ｘｊ，ｐ（ｐ＝１，２，…，ｎ）を計算し、メンバＩＤがｍｐであるメンバの分散計算装置１０１に分散情報Ｘｊ，ｐを配布する。分散計算部２０２は、式（１）の関数ｆにより構成が異なるが（例えば、後述する図６の構成）、関数ｆにおいて有限体加算が存在すれば、分散計算部は対応する分散加算部を持ち、関数ｆにおいて有限体定数乗算が存在すれば、分散計算部は対応する分散定数乗算部を持ち、関数ｆにおいて有限体乗算が存在すれば、分散計算部は対応する分散乗算部を持つ。
【００１５】
［分散加算の説明］
図７は、マルチパーティ・プロトコルにおける分散加算（足し算計算）を行う分散加算部の構成図である。分散加算部は、方式〔２．１〕及び方式〔２．２〕ともに同じ構成をとる。分散加算により、有限体ＧＦ（ｑ）上の値Ａ，Ｂの足し算Ｃ＝Ａ＋Ｂを行う場合を説明する。メンバＩＤがｍｊであるメンバは、値Ａ，Ｂの分散情報として、それぞれ分散情報Ａｊ，Ｂｊを持っているとし、分散加算部への入力を分散情報Ａｊ，Ｂｊとする。マルチパーティ・プロトコルにおいては、各メンバは、値Ａ，Ｂの分散情報同士の足し算を行うことで、計算結果Ｃの分散情報Ｃｊ（ｊ＝１，２，…，ｎ）を得ることができる。図７に示されるように、分散加算部は加算部３０１からなり、分散加算部へ入力される分散情報Ａｊ，Ｂｊは、加算部３０１へ入力され、次式（５）のような計算を行い、計算結果Ｃｊを出力する。加算部３０１からの出力が、分散加算部からの出力となる。
Ｃｊ＝Ａｊ＋Ｂｊ    …（５）
【００１６】
［分散定数乗算の説明］
図８は、マルチパーティ・プロトコルにおける分散定数乗算（定数の掛け算計算）を行う分散定数乗算部の構成図である。分散定数乗算部は、方式〔２．１〕及び方式〔２．２〕ともに同じ構成をとる。分散定数乗算により、有限体ＧＦ（ｑ）上の値Ａと定数Ｍとの掛け算Ｃ＝Ｍ・Ａを行う場合を説明する。メンバＩＤがｍｊであるメンバは、値Ａの分散情報として、それぞれＡｊを持っているとし、分散定数乗算部への入力を分散情報Ａｊ及び定数Ｍとする。マルチパーティ・プロトコルにおいては、各メンバは、値Ａの分散情報Ａｊと定数Ｍを掛け算することで、計算結果Ｃの分散情報Ｃｊ（ｊ＝１，２，…，ｎ）を得ることができる。図８に示されるように、分散定数乗算部は乗算部４０１からなり、分散定数乗算部へ入力される分散情報Ａｊ及び定数Ｍは、乗算部４０１へ入力され、次式（６）のような計算を行い、計算結果Ｃｊを出力する。乗算部４０１からの出力が分散定数乗算部からの出力となる。
Ｃｊ＝Ｍ・Ａｊ    …（６）
【００１７】
［分散乗算の説明］
図９は、マルチパーティ・プロトコルにおける分散乗算（掛け算計算）を行う分散乗算部の構成図である。分散乗算部は方式〔２．１〕及び方式〔２．２〕ともに同じ図９の構成をとるが、処理ブロックであるｊｊ項計算部５０１、及び、ｉｊ項計算部５０２の詳細構成及び動作が若干異なる。分散乗算により、有限体ＧＦ（ｑ）上の値Ａ，Ｂの掛け算Ｃ＝Ａ・Ｂを行いたいとする。メンバＩＤがｍｊであるメンバは、値Ａ，Ｂの分散情報として、それぞれＡｊ，Ｂｊを持っているとし、分散乗算部への入力を分散情報Ａｊ，Ｂｊとする。マルチパーティ・プロトコルでの分散乗算は、分散加算や分散定数乗算のように単純には計算することができない。図９に示されるように、分散乗算部は、ｊｊ項計算部５０１と、ｉｊ項計算部５０２と、多項加算部５０３とからなる。分散乗算部に入力される２つの入力は、ｊｊ項計算部５０１及びｉｊ項計算部５０２の両方に入力される。ｊｊ項計算部５０１からの出力及びｉｊ項計算部５０２からの出力は、多項加算部５０３に入力される。多項加算部５０３からの出力が、分散乗算部の出力となる。
【００１８】
方式〔２．１〕の場合、ｊｊ項計算部５０１は、分散乗算部に入力される２つの入力を受け取り、それらを乗算し、次式（７）で計算される係数ｒｊを乗算して、多項加算部５０３に出力する。
【数２】
2004341766.tif 000005
すなわち、ｊｊ項計算部５０１は、ｒｊ×Ａｊ×Ｂｊを計算して、出力する。
【００１９】
また、方式〔２．２〕の場合、ｊｊ項計算部５０１は、分散乗算部に入力される２つの入力を受け取り、それらを乗算して出力する。すなわち、ｊｊ項計算部５０１は、Ａｊ×Ｂｊを計算して、出力する。
【００２０】
ｉｊ項計算部５０２は、分散乗算部に入力される２つの入力を受け取り、受け取った入力と通信路１０２を通して他のメンバから受け取った情報から、実質的に他のメンバの値との乗算結果が得られるように計算をする。例えば、メンバＩＤがｍｊであるメンバは、分散乗算部に入力されるＡｊとＢｊの乗算Ａｊ×Ｂｊをｊｊ項計算部５０１で行うが、ｉｊ項計算部５０２においては、他のメンバ（メンバＩＤがｍｐ、ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の値との乗算、Ａｊ×Ｂｐ及びＡｐ×Ｂｊの結果に相当するもの（乗算結果そのものではない）が得られるようにする。ｉｊ項計算部５０２は、
Ａｊ×Ｂｐ＝Ｄｊ，ｐ＋Ｅｐ，ｊ    …（８）
Ａｐ×Ｂｊ＝Ｅｊ，ｐ＋Ｄｐ，ｊ    …（９）
となるような、Ｄｊ，ｐ及びＥｊ，ｐをメンバＩＤがｍｊであるメンバが、Ｄｐ，ｊ及びＥｐ，ｊをメンバＩＤがｍｐであるメンバが、それぞれ持つことができるように、計算を行う。
【００２１】
多項加算部５０３は、ｊｊ項計算部５０１及びｉｊ項計算部５０２からの出力を受け取り、それらを足し合わせて出力する。
【００２２】
［方式〔２．１〕の場合のｉｊ項計算部５０２の説明］
図１４を用いて、方式〔２．１〕の場合のｉｊ項計算部５０２の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバのｉｊ項計算部５０２の説明である。図１４に示されるように、ｉｊ項計算部５０２は、ｎ−１個の項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）と、ｎ−１個の項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）と、ｎ−１個の加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）と、ｎ−１個の係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）とを有する。ｉｊ項計算部５０２へ入力される２つの入力のうち、１つは、ｊ−１個の項計算受信部６０１−ｐ（ｐ＝１，２，…，ｊ−１）、及び、ｎ−ｊ個の項計算送信部６０２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）へ入力され、もう１つの入力は、ｎ−ｊ個の項計算受信部６０１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）、及び、ｊ−１個の項計算送信部６０２−ｐ（ｐ＝１，２，…，ｊ−１）へ入力される。
【００２３】
項計算受信部６０１−ｐ及び項計算受信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力は、加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）へ入力される。加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力は係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）へ入力される。係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力（全部でｎ−１個の出力）が、ｉｊ項計算部５０２からの出力となる。項計算受信部６０１−ｐ及び項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、通信路１０２を通して、他のメンバとの情報のやりとりを行うことにより、前述の通り、他のメンバ（メンバＩＤがｍｐ，ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の値との乗算、Ａｊ×Ｂｐ及びＡｐ×Ｂｊの結果に相当するもの（乗算結果そのものではない）が得られるようにするが、他のメンバの値Ａｐ，Ｂｐ（メンバＩＤがｍｐ、ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）が分からないように、また、自分の値Ａｊ，Ｂｊが、他のメンバに分からないように、紛失通信を行う。紛失通信とは、ここでは、送信側が、複数個の情報を符号化（暗号化）して送信するが、受信側では、そのうち１つしか受け取る（意味のあるように復号が可能となる）ことができず、また、送信側では、受信側がどの情報を受け取った（意味のあるように復号が可能となった）かを知ることができない通信方法をいう。
【００２４】
他のメンバとの送受信の関係は、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からは、それぞれ、通信路１０２を通して、メンバＩＤがｍｐであるメンバの項計算受信部６０１−ｊのそれぞれへ情報が渡される。項計算受信部６０１及び項計算送信部６０２の詳細は、後述する。
【００２５】
加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、項計算受信部６０１−ｐ、項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力を受け取り、それら２個の値を加算して、係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）へ出力する。項計算受信部６０１−ｐ（ｐ＝１，２，…，ｊ−１）又は項計算送信部６０２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）からの出力をＤｊ，ｐ、項計算受信部６０１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）又は項計算送信部６０２−ｐ（ｐ＝１，２，…，ｊ−１）からの出力をＥｊ，ｐとすると、加算部６０３−ｐでは、Ｄｊ，ｐ＋Ｅｊ，ｐを計算して、その計算結果を係数乗算部６０４−ｐへ出力する。
【００２６】
係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力を受け取り、次式（１０）で計算される係数ｒｐを乗算して出力する。
【数３】
2004341766.tif 000006
【００２７】
加算部６０３−ｐからの出力をＦｊ，ｐとすると、係数乗算部６０４−ｐは、ｒｐ×Ｆｊ，ｐを計算して、その計算結果を出力する。係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力（全部でｎ−１個の出力）が、ｉｊ項計算部５０２からの出力となる。
【００２８】
［方式〔２．２〕の場合のｉｊ項計算部５０２の説明］
次に、図１５を用いて、方式〔２．２〕の場合のｉｊ項計算部５０２の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバのｉｊ項計算部５０２での説明である。方式〔２．２〕のｉｊ項計算部５０２は、方式〔２．１〕のｉｊ項計算部５０２の構成（図１４）から、ｎ−１個の加算部６０３−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）及びｎ−１個の係数乗算部６０４−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）を取り除いたような構成をしており、ｎ−１個の項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）とｎ−１個の項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からなる。ｉｊ項計算部５０２へ入力される２つの入力のうち、１つは、ｊ−１個の項計算受信部６０１−ｐ（ｐ＝１，２，…，ｊ−１）、及び、ｎ−ｊ個の項計算送信部６０２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）へ入力され、もう１つの入力は、ｎ−ｊ個の項計算受信部６０１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）、及び、ｊ−１個の項計算送信部６０２−ｐ（ｐ＝１，２，…，ｊ−１）へ入力される。項計算受信部６０１−ｐ及び項計算受信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力（全部で２×（ｎ−１）＝２ｎ−２個の出力）が、ｉｊ項計算部５０２からの出力となる。項計算受信部６０１−ｐ及び項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、通信路１０２を通して、他のメンバとの情報のやりとりを行うことにより、前述の通り、他のメンバ（メンバＩＤがｍｐ、ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の値との乗算、Ａｊ×Ｂｐ及びＡｐ×Ｂｊの結果に相当するもの（乗算結果そのものではない）が得られるようにするが、他のメンバの値Ａｐ，Ｂｐ（メンバＩＤがｍｐ、ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）が分からないように、また、自分の値Ａｊ，Ｂｊが、他のメンバに分からないように、方式〔２．１〕の場合と同様、紛失通信を行う。
【００２９】
他のメンバとの送受信の関係は、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からは、それぞれ、通信路１０２を通して、メンバＩＤがｍｐであるメンバの項計算受信部６０１−ｊのそれぞれへ情報が渡される。
【００３０】
［項計算受信部６０１の説明］
次に、図１６を用いて、従来の項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の説明である。項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、方式〔２．１〕及び方式〔２．２〕ともに同じ構成をとる。項計算受信部６０１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１を有する。１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、対応する１−ｏｕｔ−ｏｆ−ｑ紛失送信部（後述する）と、前述した紛失通信を、通信路１０２を通して他のメンバと行う。１−ｏｕｔ−ｏｆ−ｑ紛失通信とは、ここでは、送信側が、ｑ個の情報を符号化（暗号化）して送信するが、受信側では、そのうち１つしか受け取る（意味のあるように復号が可能となる）ことができず、また、送信側では、受信側がどの情報を受け取った（意味のあるように復号が可能となった）かを知ることができない通信方法をいう。非特許文献１の紛失通信の説明では、１−ｏｕｔ−ｏｆ−２紛失通信（送信側の２つの情報のうち、どちらか１つが受信側へ届く）の説明をしているが、ここでは、それを拡張した１−ｏｕｔ−ｏｆ−ｑ（ｑ≧２）紛失通信について説明する。１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、対応する１−ｏｕｔ−ｏｆ−ｑ紛失送信部（メンバＩＤがｍｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）であるメンバの１−ｏｕｔ−ｏｆ−ｑ紛失送信部とする）と次のようなステップで、通信路１０２を通して通信を行う。
【００３１】
ただし、１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１に対応する１−ｏｕｔ−ｏｆ−ｑ紛失送信部のメンバ（メンバＩＤがｍｐ）の公開鍵暗号の公開鍵をｋｐ、対応する秘密鍵をｋｓ、暗号化関数をｅｐ、復号関数をｄｓとする。送信側であるメンバＩＤがｍｐであるメンバは、ｑ個の情報Ｍｉ（ｉ＝１，２，…，ｑ）を持ち、受信側であるメンバＩＤがｍｊであるメンバは、そのうち、β番目の情報Ｍβを受け取りたいとする。メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐ（ｐ＝１，２，…，ｊ−１）における１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、β＝Ａｊであり、メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、β＝Ｂｊである。
【００３２】
（ステップ１）メンバＩＤがｍｐであるメンバは、ｑ個の乱数ｒｉ（１≦ｉ≦ｑ）をメンバＩＤがｍｊであるメンバに送る。
【００３３】
（ステップ２）メンバＩＤがｍｊであるメンバは、乱数ｘを選び，Ｘ＝ｅｐ（ｘ）＋ｒβをメンバＩＤがｍｐであるメンバに送る。
【００３４】
（ステップ３）メンバＩＤがｍｐであるメンバは、ｑ個の値ｙｉ＝ｄｓ（Ｘ−ｒｉ）（１≦ｉ≦ｑ）を計算し、ｑ個の情報Ｃｉ＝Ｍｉ＋ｙｉ（１≦ｉ≦ｑ）をメンバＩＤがｍｊであるメンバに送る。
【００３５】
（ステップ４）メンバＩＤがｍｊであるメンバは、Ｍβ＝Ｃβ−ｘを得る。
【００３６】
また、特許文献１及び特許文献２にあるような紛失通信の方法も利用できる。１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、受信した情報を出力する。メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐ（ｐ＝１，２，…，ｊ−１）における１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、Ｄｊ，ｐ＝Ｍβ（β＝Ａｊ）を出力し、メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１は、Ｅｊ，ｐ＝Ｍβ（β＝Ｂｊ）を出力する。
【００３７】
［項計算送信部６０２の説明］
次に、図１７を用いて、従来の項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の説明である。項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、方式〔２．１〕及び方式〔２．２〕ともに同じ構成をとる。項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、乱数生成部８０１と、送信情報生成部８０２と、１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３とを有する。項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力は、乱数生成部８０１からの出力とともに、送信情報生成部８０２へ入力される。送信情報生成部８０２からの出力は、１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３へ入力される。乱数生成部８０１からの出力が、項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力となる。
【００３８】
乱数生成部８０１は、１つの乱数Ｒｊ，ｐを生成し、送信情報生成部８０２へ出力する。乱数生成部８０１からの出力が、項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力となる。メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｊ−１）における乱数生成部８０１は、生成した乱数を項計算送信部６０２−ｐからの出力Ｅｊ，ｐとし、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における乱数生成部８０１は、生成した乱数を項計算送信部６０２−ｐからの出力Ｄｊ，ｐとする。
【００３９】
送信情報生成部８０２は、項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力と、乱数生成部８０１からの出力を受け取り、それら受け取った情報から、ｑ個の情報Ｍｉ（ｉ＝１，２，…，ｑ）を１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３へ出力する。メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｊ−１）における１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０２は、項計算送信部６０２−ｐへの入力Ｂｊ、及び乱数生成部８０１からの出力Ｒｊ，ｐを受け取り、式（１２）を計算してｑ個の情報Ｍｉ（ｉ＝１，２，…，ｑ）を出力し、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０２は、項計算送信部６０２−ｐへの入力Ａｊ、及び乱数生成部８０１からの出力Ｒｊ，ｐを受け取り、式（１１）を計算してｑ個の情報Ｍｉ（ｉ＝１，２，…，ｑ）を出力する。
Ｍｉ＝Ａｊ×（ｉ−１）−Ｒｊ，ｐ    …（１１）
Ｍｉ＝Ｂｊ×（ｉ−１）−Ｒｊ，ｐ    …（１２）
【００４０】
１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３は、送信情報生成部８０２から、ｑ個の情報Ｍｉ（ｉ＝１，２，…，ｑ）を受け取り、前述したように、対応する１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１と通信路１０２を通して１−ｏｕｔ−ｏｆ−ｑ紛失通信を行う。
【００４１】
他のメンバとの送受信の関係は、メンバＩＤがｍｊであるメンバの項計算送信部６０２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３からは、それぞれ、通信路１０２を通して、メンバＩＤがそれぞれｍｐであるメンバの項計算受信部６０１−ｊの１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１へ情報が渡され、メンバＩＤがそれぞれｍｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）であるメンバの項計算送信部６０２−ｊの１−ｏｕｔ−ｏｆ−ｑ紛失送信部８０３からは、それぞれ、通信路１０２を通して、メンバＩＤがｍｊであるメンバの項計算受信部６０１−ｐの１−ｏｕｔ−ｏｆ−ｑ紛失受信部７０１へ情報が渡される。
【００４２】
［分散計算部２０２の構成例の説明］
上記のように、各メンバ同士が通信を行って計算処理をすると、入力値を公開せずに、与えられた関数（有限体の加算、定数乗算、乗算からなる）の計算を行うことができる。例えば、３人のメンバでマルチパーティ・プロトコルを実行する場合、
Ｙ
＝ｆ（Ｘ１，Ｘ２，Ｘ３）
＝Ｍ×Ｘ１×Ｘ２×Ｘ３×（Ｘ１＋Ｘ２＋Ｘ３）    …（１３）
のような関数計算をさせたいとすると、各自の分散計算装置１０１の分散計算部２０２は、図６のような構成となる（ただしＭは定数）。
【００４３】
【非特許文献１】
岡本龍明他著、「現代暗号」（産業図書）、２２７−２３６ページ及び２０９−２１９ページ
【特許文献１】
特開平１１−１４５９５１（段落０００２〜００１２）
【特許文献２】
特開２０００−１１５１５７（段落０００２〜００１２）
【００４４】
【発明が解決しようとする課題】
しかしながら、上記のようなマルチパーティ・プロトコルにおける分散乗算においては、乗算１回あたりの通信量が、１人のメンバあたり、ｎ×ｑ×ｌｏｇ２ｑビットもの大きさとなり、この通信を行うために、かなりの帯城が必要となるか、又は、通信時間が長くなるという問題があった。例えば、ｎ＝１０人、ｌｏｇ２ｑ＝１００ビット程度の有限体を考えると、通信量ｎ×ｑ×ｌｏｇ２ｑビットは、１０３３ビット（≒１０×２１００×１００ビット）程度の大きな値になっていた。
【００４５】
そこで、本発明は、上記したような従来技術の課題を解決するためになされたものであり、その目的は、マルチパーティ・プロトコルの分散乗算におけるメンバ間の相互通信量を小さくすることができる分散乗算装置及び分散乗算システムを提供することである。
【００４６】
【課題を解決するための手段】
本発明の分散乗算装置は、マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う第１乃至第ｎ（ｎは２以上のある整数）の分散乗算装置のうちの１つである、第ｊ（ｊは１以上ｎ以下の整数）の分散乗算装置であって、上記第１乃至第ｎの分散乗算装置に分散情報である第１入力及び第２入力がそれぞれ入力される場合に、
＜Ｉ＞  上記第ｊの分散計算装置への第１入力と第２入力を掛け合わせ、さらに、上記第１乃至第ｎの分散計算装置に固有のメンバＩＤから計算される係数を掛け合わせる第１の乗算手段と、
＜ＩＩ＞  上記第ｊの分散計算装置への第１入力と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への第２入力との乗算結果を得るための処理を紛失通信を通して行う第１の通信計算手段と、
＜ＩＩＩ＞  上記第ｊの分散計算装置への第２入力と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への第１入力の乗算結果を得るための処理を紛失通信を通して行う第２の通信計算手段と、
＜ＩＶ＞  上記第１の通信計算手段の出力と上記第２の通信計算手段の出力とを足し合わせる第１の加算手段と、
＜Ｖ＞  上記第１の加算手段の出力に、上記第１乃至第ｎの分散計算装置に固有のメンバＩＤから計算される係数を掛け合わせる第２の乗算手段と、
＜ＶＩ＞  上記第１の乗算手段の出力と、第２の乗算手段の出力とを足し合わせる第２の加算手段と
を有し、
＜ＶＩＩ＞  上記第１及び第２の通信計算手段それぞれが、紛失通信送信手段及び紛失通信受信手段のうちの少なくとも一方を有し、
＜ＶＩＩＩ＞  上記紛失通信送信手段が、有限体ＧＦ（ｑ）上の乱数を、ｌｏｇ２（ｑ−１）を小数点切り上げした第１の個数生成する乱数生成手段と、上記乱数生成手段からの出力と、上記第ｊの分散計算装置のこの紛失通信送信手段へ入力される２つの分散情報とから紛失送信情報を生成する送信情報生成手段と、上記乱数生成手段から出力される第１の個数の乱数を足し合わせる第３の加算手段と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置との間で紛失通信による送信を行う第１の個数の１−ｏｕｔ−ｏｆ−２紛失送信手段とを有し、＜ＩＸ＞  上記紛失通信受信手段が、入力される分散情報を２値展開する２値展開手段と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置から紛失通信により送信情報を受信する第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段と、上記１−ｏｕｔ−ｏｆ−２紛失受信手段で受信した第１の個数の値を足し合わせる第４の加算手段とを有するものである。
【００４７】
また、本発明の他の分散乗算装置は、マルチパーティ・プロトコルにより、有限体ＧＦ（ｑ）上の２つの値の分散乗算を行う第１乃至第ｎ（ｎは２以上のある整数）の分散乗算装置のうちの１つである、第ｊ（ｊは１以上ｎ以下の整数）の分散乗算装置であって、上記第１乃至第ｎの分散乗算装置に分散情報である第１入力及び第２入力がそれぞれ入力される場合に、
＜Ｉ＞  上記第ｊの分散計算装置への第１入力と第２入力を掛け合わせる第１の乗算手段と、
＜ＩＩ＞  上記第ｊの分散計算装置への第１入力と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への第２入力との乗算結果を得るための処理を紛失通信を通して行う第１の通信計算手段と、
＜ＩＩＩ＞  上記第ｊの分散計算装置への第２入力と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への第１入力との乗算結果を得るための処理を紛失通信を通して行う第２の通信計算手段と、
＜ＩＶ＞  上記第１の乗算手段の出力と、上記第１の通信計算手段の出力と、上記第２の通信計算手段の出力とを足し合わせる第１の加算手段と
を有し、
＜Ｖ＞  上記第１及び第２の通信計算手段が、紛失通信送信手段及び紛失通信受信手段の少なくとも一方を有し、
＜ＶＩ＞  上記紛失通信送信手段が、有限体ＧＦ（ｑ）上の乱数を、ｌｏｇ２（ｑ−１）を小数点切り上げした第１の個数生成する乱数生成手段と、上記乱数生成手段からの出力と、上記第ｊの分散計算装置のこの紛失通信送信手段へ入力される２つの分散情報とから紛失送信情報を生成する送信情報生成手段と、上記乱数生成手段から出力される第１の個数の乱数を足し合わせる第３の加算手段と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置への紛失送信を行う第１の個数の１−ｏｕｔ−ｏｆ−２紛失送信手段とを有し、
＜ＶＩＩ＞  上記紛失通信受信手段が、入力される分散情報を２値展開する２値展開手段と、第１乃至第（ｊ−１）及び第（ｊ＋１）乃至第ｎの分散乗算装置からの送信情報を紛失通信により受信する第１の個数の１−ｏｕｔ−ｏｆ−２紛失受信手段と、上記１−ｏｕｔ−ｏｆ−２紛失受信手段で受信した第１の個数の値を足し合わせる第４の加算手段とを有するものである。
【００４８】
【発明の実施の形態】
［実施の形態の構成］
本発明の実施の形態におけるシステム（図３及び図４）又は分散計算装置１０１（図４及び図５）は、その分散計算部２０２（図５）の分散乗算部９０３〜９０５（例えば、図６）を構成するｉｊ項計算部５０２（図９〜図１１）の項計算受信部１００１及び項計算送信部１００２（図１及び図２）の構成が、従来の分散計算装置のｉｊ項計算部５０２（図１４及び図１５）の項計算受信部６０１及び項計算送信部６０２（図１６及び図１７）の構成と相違する。この点を除いて、本発明の実施の形態におけるシステム（図３及び図４）又は分散計算装置１０１（図４及び図５）は、上記した従来のシステム又は分散計算装置と同じである。
【００４９】
本発明の実施の形態におけるシステム（図３及び図４）又は分散計算装置１０１（図４及び図５）は、従来の項計算受信部６０１及び項計算送信部６０２（図１６及び図１７）を改良して、項計算受信部１００１及び項計算送信部１００２（図１及び図２）にすることにより、マルチパーティ・プロトコルの分散乗算におけるメンバ間の相互通信量を小さくするものである。具体的言えば、本発明の実施の形態におけるシステム（図３及び図４）又は分散計算装置１０１（図４及び図５）の分散乗算部においては、掛け算する有限体ＧＦ（ｑ）上の値Ａをビット展開し、ビットごとに１−ｏｕｔ−ｏｆ−２紛失通信を用い、それを値Ａの（２進数表示の）桁数ｑｂ分だけ繰り返すように構成する（ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失受信部及びｑｂ個の１−ｏｕｔ−ｏｆ−２紛失送信部で処理をする）ことにより、分散乗算装置相互間の通信量を減少させている。
【００５０】
本発明の実施の形態における改良点は、マルチパーティ・プロトコルにおける分散乗算を実行する分散乗算システム又は分散計算装置１０１を構成する分散乗算部（図９）のｉｊ項計算部５０２（図１０又は図１１）であり、特に、項計算受信部１００１及び項計算送信部１００２である。これら改良点以外については、本発明の実施の形態の構成は、上記した従来技術の構成と同様である。したがって、以下の説明においては、従来技術の説明において用いた、図３〜図８をも参照する。また、以下の説明においては、本発明の実施の形態における改良点（すなわち、上記した従来技術との相違点）を中心に説明する。なお、本発明の実施の形態における分散加算部及び分散定数乗算部は、既に説明した従来技術の構成と同様である。また、本発明の実施の形態における項計算受信部１００１及び項計算送信部１００２は、方式〔２．１〕及び方式〔２．２〕の場合ともに、同じ構成となる。
【００５１】
図１は、本発明の実施の形態に係る分散乗算装置の項計算受信部１００１の構成を示すブロック図である。図１を用いて、項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の説明である。図１に示されるように、項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、２値展開部１１０１と、ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）と、多項加算部１１０３とを有する。
【００５２】
項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力は、２値展開部１１０１へ入力され、２値展開部１１０１からのｑｂ個の出力をそれぞれ１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）が受け取り、１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）からのｑｂ個の出力は、多項加算部１１０３へ入力される。多項加算部１１０３からの出力が、項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力となる。
【００５３】
２値展開部１１０１は、項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力を受け取り、その値を２値展開してｑｂ個の２値の値を生成し、最も低い桁（ＬＳＢ）の２値の値が１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−１に入力し、次に低い桁の２値の値が１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−２に入力するといったように、低い桁のほう（ＬＳＢ側）からの順番に、１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−１，１１０２−２，…，１１０２−ｑｂへ生成した２値の値を出力する。ｑｂは、本発明の実施の形態において前提としている有限体ＧＦ（ｑ）の要素数ｑから１を引いた値の底２における対数をとった値（小数点以下切り上げ）であり、次式（１４）のように計算する。
ｑｂ＝ｃｅｉｌ（ｌｏｇ２（ｑ−１））    …（１４）
ここで、ｃｅｉｌ（・）は、小数点以下切り上げの演算を表し、ｌｏｇ２（・）は、底２の対数をとることを表す。式（１４）のｑｂは、取り扱う値が必要とするビット数である。
【００５４】
メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）における２値展開部１１０１は、項計算受信部１００１−ｐへの入力Ａｊを受け取り、式（１５）の関係にあるＡｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を求め、求めた値Ａｊ，ｉ−１を１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉへ出力する。メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における２値展開部１１０１は、項計算受信部１００１−ｐへの入力Ｂｊを受け取り、式（１６）の関係にあるＢｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を求め、求めた値Ｂｊ，ｉ−１を１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉへ出力する。
【数４】
2004341766.tif 000007
式（１５）及び式（１６）におけるＡｊ，ｉ−１及びＢｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）は、それぞれＡｊ，Ｂｊを２値表現したときのｉ桁目の２値の値である。
【００５５】
１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）は、２値展開部１１０１からの出力Ａｊ，ｉ−１又はＢｊ，ｉ−１を受け取り、対応する１−ｏｕｔ−ｏｆ−２紛失送信部（後述する）と、１−ｏｕｔ−ｏｆ−２紛失通信（従来技術の欄で説明した１−ｏｕｔ−ｏｆ−ｑ紛失通信のｑ＝２の場合）を、通信路１０２を通して他のメンバと行う。１−ｏｕｔ−ｏｆ−２紛失通信とは、ここでは、送信側が、２個の情報を符号化（暗号化）して送信するが、受信側では、そのうち１つしか受け取る（意味のあるように復号が可能となる）ことができず、また、送信側では、受信側がどちらの情報を受け取った（意味のあるように復号が可能となった）かを知ることができない通信方法をいう。１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）は、受信した情報を出力する。
【００５６】
メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）における１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）は、メンバＩＤがｍｐであるメンバの項計算送信部１００２−ｉにおける対応する１−ｏｕｔ−ｏｆ−２紛失送信部（後述する）から送信されるＭｉ，β（β＝０又は１）のうち、β＝Ａｊ，ｉ−１のほうを受信してＤｊ，ｐ，ｉ−１として出力する。メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）は、メンバＩＤがｍｐであるメンバの項計算送信部１００２−ｉにおける対応する１−ｏｕｔ−ｏｆ−２紛失送信部（後述する）から送信されるＭｉ，β（β＝０又は１）のうち、β＝Ｂｊ，ｉ−１のほうを受信してＥｊ，ｐ，ｉ−１として出力する。
【００５７】
多項加算部１１０３は、１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）からそれぞれ１個ずつの出力、合計ｑｂ個の出力を受け取り、それらを足し合わせて、計算結果を出力する。多項加算部１１０３からの出力が、項計算受信部１００１−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の出力となる。メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）における多項加算部１１０３は、１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）からの出力Ｄｊ，ｐ，ｉ−１を受け取り、式（１７）の加算を計算してＤｊ，ｐとして出力する。メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における多項加算部１１０３は、１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）からの出力Ｅｊ，ｐ，ｉ−１を受け取り、式（１８）の加算を計算してＥｊ，ｐとして出力する。
【数５】
2004341766.tif 000008
【００５８】
図２は、本発明の実施の形態に係る分散乗算装置の項計算送信部１００２の構成を示すブロック図である。図２を用いて、項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の構成を説明する。ここでの説明は、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の説明である。項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）は、乱数生成部１２０１と、ｑｂ個の送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）と、ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）と、多項加算部１２０４とを有する。項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力、及び、乱数生成部１２０１からの出力は、送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）へ入力される。送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）からの出力は、１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）へ入力される。また、乱数生成部１２０１からの出力は、多項加算部１２０４へ入力される。多項加算部１２０４からの出力が、項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力となる。
【００５９】
乱数生成部１２０１は、ｑｂ個の有限体ＧＦ（ｑ）上の乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）を生成し、それぞれの乱数Ｒｊ，ｐ，ｉ−１を送信情報生成部１２０２−ｉへ出力するとともに、多項加算部１２０４へも出力する。
【００６０】
送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）は、項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）への入力と、乱数生成部１２０１からの出力を受け取り、それら受け取った情報から、２個の情報Ｍｉ，０とＭｉ，１を生成し、その２つの情報を１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）へ出力する。メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）における送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）は、項計算送信部１００２−ｐへの入力Ｂｊ、及び乱数生成部１２０１からの出力Ｒｊ，ｐ，ｉ−１を受け取り、式（２０）を計算して２個の情報Ｍｉ，０及びＭｉ，１を１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉへ出力する。メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における送信情報生成部１２０２−ｉ（ｉ＝１，２，…，ｑｂ）は、項計算送信部１００２−ｐへの入力Ａｊ、及び乱数生成部１２０１からの出力Ｒｊ，ｐ，ｉ−１を受け取り、式（１９）を計算して２個の情報Ｍｉ，０及びＭｉ，１を１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ出力する。
Ｍｉ，β
＝Ａｊ×β  ２（ｉ−１）−Ｒｊ，ｐ，ｉ−１（β＝０、１）  …（１９）
Ｍｉ，β
＝Ｂｊ×β  ２（ｉ−１）−Ｒｊ，ｐ，ｉ−１（β＝０、１）  …（２０）
【００６１】
１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）は、送信情報生成部１２０２−ｉから、２個の情報Ｍｉ，０及びＭｉ，１を受け取り、前述したように、対応する１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉと通信路１０２を通して１−ｏｕｔ−ｏｆ−２紛失通信を行う。
【００６２】
他のメンバとの送受信の関係は、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）の１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）からは、それぞれ、通信路１０２を通して、メンバＩＤがそれぞれｍｐであるメンバの項計算受信部１００１−ｉの１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉへ情報が渡され、メンバＩＤがそれぞれｍｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）であるメンバの項計算送信部１００２−ｉの１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）からは、それぞれ、通信路１０２を通して、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐの１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）へ情報が渡される。
【００６３】
多項加算部１２０４は、乱数生成部１２０１からｑｂ個の乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）を受け取り、それらをすべて加算して出力する。多項加算部１２０４からの出力が、項計算送信部１００２−ｐ（ｐ＝１，２，…，ｎでｐ≠ｊとなるもの）からの出力となる。メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）における多項加算部１２０４は、加算結果を項計算送信部１００２−ｐからの出力Ｅｊ，ｐ（式（２２））とし、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における多項加算部１２０４は、加算結果を項計算送信部１００２−ｐからの出力Ｄｊ，ｐ（式（２１））とする。
Ｄｊ，ｐ＝Ｒｊ，ｐ，０＋Ｒｊ，ｐ，１＋…＋Ｒｊ，ｐ，ｑｂ−１  …（２１）
Ｅｊ，ｐ＝Ｒｊ，ｐ，０＋Ｒｊ，ｐ，１＋…＋Ｒｊ，ｐ，ｑｂ−１  …（２２）
【００６４】
［実施の形態の動作］
図１２は、本発明の実施の形態の方式〔２．１〕の場合の分散乗算部の動作を示すフローチャートであり、メンバＩＤがｍｊ（ｊ＝１，２，…，ｎ）であるメンバの分散乗算部の動作を示している。分散乗算部への２つの入力をそれぞれＡｊ，Ｂｊとする。Ａｊ，Ｂｊは、メンバが持ち寄って、（ｋ，ｎ）しきい値秘密分散法の再構成を行なうと、それぞれＡ，Ｂになる分散情報である。まず、入力される分散情報Ａｊ，Ｂｊ、及びメンバＩＤから計算される係数ｒｊを掛け合わせる（ステップＳ１３０１）。ステップＳ１３０１は、図９の方式〔２．１〕の場合のｊｊ項計算部５０１における動作である。
【００６５】
また、ステップＳ１３０１は、ステップＳ１３０２〜Ｓ１３０５及びＳ１３１０からなる処理Ｓ１３１３及びステップＳ１３０６〜Ｓ１３０９及びＳ１３１１からなる処理Ｓ１３１４と、並列して行うことができる。ソフトウエア・プログラムのように直列に実行する場合には、ステップＳ１３０１、処理Ｓ１３１３、処理Ｓ１３１４は、どのような順番で実行してもよい。
【００６６】
ステップＳ１３０２においては、分散情報Ａｊを２値展開してｑｂ個の２値の値Ａｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を得る。これは、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の２値展開部１１０１における処理を示す。
【００６７】
次のステップＳ１３０３においては、メンバＩＤがｍｐ（ｐ＝１，２，…，ｊ−１）であるメンバから、Ａｊ，ｉ−１２ｉ−１Ｂｐ−Ｅｐ，ｊ，ｉ−１に相当するＤｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個、１−ｏｕｔ−ｏｆ−２紛失通信で受け取る。ステップＳ１３０３は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）における処理を示している。
【００６８】
次のステップＳ１３０４においては、ステップＳ１３０３で受け取ったＤｊ，ｐ，ｉ−１（ｐ＝１，２，…，ｊ−１、ｉ＝１，２，…，ｑｂ）を足し合わせて、Ｄｊ，ｐを得る。ステップＳ１３０４は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の多項加算部１１０３における動作を示している。
【００６９】
また、ステップＳ１３０２〜Ｓ１３０４からなる処理Ｓ１３１５と、ステップＳ１３０５は、並列して行うことができる。ソフトウエア・プログラムのように直列に実行する場合には、処理Ｓ１３１５及びステップＳ１３０５は、どのような順番で実行してもよい。
【００７０】
ステップＳ１３０５においては、ｐ＝１，２，…，ｊ−１に対し、それぞれ乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個生成し、それらを足し合わせてＥｊ，ｐ（ｐ＝１，２，…，ｊ−１）とする。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）の多項加算部１２０４における動作を示している。また、メンバＩＤがｍｐ（ｐ＝１，２，…，ｊ−１）であるメンバに対して、Ｍｉ，０（＝０Ｂｊ−Ｒｊ，ｐ，ｉ−１）及びＭｉ，１（＝２ｉ−１Ｂｊ−Ｒｊ，ｐ，ｉ−１）の２つの情報を生成して、１−ｏｕｔ−ｏｆ−２紛失通信で送信する。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）の送信情報生成部１２０２−ｉ及び１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）における動作を示している。
【００７１】
ステップＳ１３０６においては、分散情報Ｂｊを２値展開してｑｂ個の２値の値Ｂｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を得る。これは、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の２値展開部１１０１における処理を示す。
【００７２】
次のステップＳ１３０７においては、メンバＩＤがｍｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）であるメンバから、ＡＰＢｊ，ｉ−１２ｉ−１−Ｄｐ，ｊ，ｉ−１に相当するＥｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個、１−ｏｕｔ−ｏｆ−２紛失通信で受け取る。ステップＳ１３０７は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）における処理を示している。
【００７３】
次のステップＳ１３０８においては、ステップＳ１３０７で受け取ったＥｊ，ｐ，ｉ−１（ｐ＝ｊ＋１，ｊ＋２，…，ｎ、ｉ＝１，２，…，ｑｂ）を足し合わせて、Ｅｊ，ｐを得る。ステップＳ１３０８は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の多項加算部１１０３における動作を示している。
【００７４】
また、ステップＳ１３０６〜Ｓ１３０８からなる処理Ｓ１３１６と、ステッブＳ１３０９は、並列して行うことができる。ソフトウエア・プログラムのように直列に実行する場合には、処理Ｓ１３１６及びステップＳ１３０９は、どのような順番で実行してもよい。
【００７５】
ステップＳ１３０９においては、ｐ＝ｊ＋１，ｊ＋２，…，ｎに対し、それぞれ乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個生成し、それらを足し合わせてＤｊ，ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）とする。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の多項加算部１２０４における動作を示している。また、メンバＩＤがｍｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）であるメンバに対して、Ｍｉ，０（＝Ａｊ０−Ｒｊ，ｐ，ｉ−１）及びＭｉ，１（＝Ａｊ２ｉ−１−Ｒｊ，ｐ，ｉ−１）の２つの情報を生成して、１−ｏｕｔ−ｏｆ−２紛失通信で送信する。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の送信情報生成部１２０２−ｉ及び１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）における動作を示している。
【００７６】
処理Ｓ１３１５、及び、ステップＳ１３０５の次に、ステップＳ１３１０において、ステップＳ１３０４で得られたＤｊ，ｐと、ステップＳ１３０５で得られたＥｊ，ｐとを足し合わせ、メンバＩＤから計算される係数ｒｐを掛ける。すなわちｒｐ×（Ｄｊ，ｐ＋Ｅｊ，ｐ）（ｐ＝１，２，…，ｊ−１）を計算する。ステップＳ１３１０は、メンバＩＤがｍｊであるメンバのｉｊ項計算部５０２（図１０）の加算部６０３−ｐ、及び、係数乗算部６０４−ｐ（ｐ＝１，２，…，ｊ−１）における処理を示している。
【００７７】
また、処理Ｓ１３１６、及び、ステップＳ１３０９の次に、ステップＳ１３１１において、ステップＳ１３０８で得られたＥｊ，ｐと、ステップＳ１３０９で得られたＤｊ，ｐとを足し合わせ、メンバＩＤから計算される係数ｒｐを掛ける。すなわち、ｒｐ×（Ｄｊ，ｐ＋Ｅｊ，ｐ）（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）を計算する。ステップＳ１３１１は、メンバＩＤがｍｊであるメンバのｉｊ項計算部５０２（図１０）の加算部６０３−ｐ、及び、係数乗算部６０４−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）における処理を示している。
【００７８】
ステップＳ１３０１、処理Ｓ１３１３、及び、処理Ｓ１３１４の次に、ステップＳ１３１２において、ステップＳ１３０１で得られた１個の値（ｒｊ×Ａｊ×Ｂｊ）と、ステップＳ１３１０で得られたｊ−１個の値（ｒｐ×（Ｄｊ，ｐ＋Ｅｊ，ｐ）、ｐ＝１，２，…，ｊ−１）と、ステップＳ１３１１で得られたｎ−ｊ個の値（ｒｐ×（Ｄｊ，ｐ＋Ｅｊ，ｐ）、ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の、合計ｎ個の値を足し合わせて、それを分散乗算結果Ｃｊとして出力する。ステップＳ１３１２は、メンバＩＤがｍｊであるメンバの図９の方式〔２．１〕の多項加算部５０３における処理を示している。
【００７９】
図１３は、本発明の実施の形態の方式〔２．２〕の場合の分散乗算部の動作を示すフローチャートであり、メンバＩＤがｍｊ（ｊ＝１，２，…，ｎ）であるメンバの分散乗算部の動作を示している。分散乗算部への２つの入力をそれぞれＡｊ，Ｂｊとする。Ａｊ，Ｂｊは、メンバが持ち寄って、加算秘密分散法の再構成を行なうと、それぞれＡ，Ｂになる分散情報である。まず、入力される分散情報Ａｊ，Ｂｊを掛け合わせる（ステップＳ１４０１）。ステップＳ１４０１は、図９の方式〔２．２〕におけるｊｊ項計算部５０１における動作である。
【００８０】
また、ステップＳ１４０１は、ステップＳ１４０２〜Ｓ１４０４からなる処理Ｓ１４１１と、ステップＳ１４０５と、ステップＳ１４０６〜Ｓ１４０８からなる処理Ｓ１４１２と、ステップＳ１４０９とを、並列して行うことができる。ソフトウエア・プログラムのように直列に実行する場合には、ステップＳ１４０１、処理Ｓ１４１１、ステップＳ１４０５、処理Ｓ１４１２、及び、ステップＳ１４０９は、どのような順番で実行してもよい。
【００８１】
ステップＳ１４０２においては、分散情報Ａｊを２値展開してｑｂ個の２値の値Ａｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を得る。これは、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の２値展開部１１０１における処理を示す。
【００８２】
次のステップＳ１４０３においては、メンバＩＤがｍｐ（ｐ＝１，２，…，ｊ−１）であるメンバから、Ａｊ，ｉ−１２ｉ−１Ｂｐ−Ｅｐ，ｊ，ｉ−１に相当するＤｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個、１−ｏｕｔ−ｏｆ−２紛失通信で受け取る。ステップＳ１４０３は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）における処理を示している。
【００８３】
次にステップＳ１４０４においては、ステップＳ１４０３で受け取ったＤｊ，ｐ，ｉ−１（ｐ＝１，２，…，ｊ−１、ｉ＝１，２，…，ｑｂ）を足し合わせて、Ｄｊ，ｐを得る。ステップＳ１４０４は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝１，２，…，ｊ−１）の多項加算部１１０３における動作を示している。
【００８４】
ステップＳ１４０５においては、ｐ＝１，２，…，ｊ−１に対し、それぞれ乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個生成し、それらを足し合わせてＥｊ，ｐ（ｐ＝１，２，…，ｊ−１）とする。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）の多項加算部１２０４における動作を示している。また、メンバＩＤがｍｐ（ｐ＝１，２，…，ｊ−１）であるメンバに対して、Ｍｉ，０（＝０Ｂｊ−Ｒｊ，ｐ，ｉ−１）及びＭｉ，１（＝２ｉ−１Ｂｊ−Ｒｊ，ｐ，ｉ−１）の２つの情報を生成して、１−ｏｕｔ−ｏｆ−２紛失通信で送信する。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝１，２，…，ｊ−１）の送信情報生成部１２０２−ｉ及び１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）における動作を示している。
【００８５】
ステップＳ１４０６においては、分散情報Ｂｊを２値展開してｑｂ個の２値の値Ｂｊ，ｉ−１（ｉ＝１，２，…，ｑｂ）を得る。これは、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の２値展開部１１０１における処理を示す。
【００８６】
次のステップＳ１４０７においては、メンバＩＤがｍｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）であるメンバから、ＡＰＢｊ，ｉ−１２ｉ−１−Ｄｐ，ｊ，ｉ−１に相当するＥｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個、１−ｏｕｔ−ｏｆ−２紛失通信で受け取る。ステップＳ１４０７は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の１−ｏｕｔ−ｏｆ−２紛失受信部１１０２−ｉ（ｉ＝１，２，…，ｑｂ）における処理を示している。
【００８７】
次のステップＳ１４０８においては、ステップＳ１４０７で受け取ったＥｊ，ｐ，ｉ−１（ｐ＝ｊ＋１，ｊ＋２，…，ｎ、ｉ＝１，２，…，ｑｂ）を足し合わせて、Ｅｊ，ｐを得る。ステップＳ１４０８は、メンバＩＤがｍｊであるメンバの項計算受信部１００１−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の多項加算部１１０３における動作を示している。
【００８８】
ステップＳ１４０９においては、ｐ＝ｊ＋１，ｊ＋２，…，ｎに対し、それぞれ乱数Ｒｊ，ｐ，ｉ−１（ｉ＝１，２，…，ｑｂ）をｑｂ個生成し、それらを足し合わせてＤｊ，ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）とする。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の多項加算部１２０４における動作を示している。また、メンバＩＤがｍｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）であるメンバに対して、Ｍｉ，０（＝Ａｊ０−Ｒｊ，ｐ，ｉ−１）及びＭｉ，１（＝Ａｊ２ｉ−１−Ｒｊ，ｐ，ｉ−１）の２つの情報を生成して、１−ｏｕｔ−ｏｆ−２紛失通信で送信する。これは、メンバＩＤがｍｊであるメンバの項計算送信部１００２−ｐ（ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の送信情報生成部１２０２−ｉ及び１−ｏｕｔ−ｏｆ−２紛失送信部１２０３−ｉ（ｉ＝１，２，…，ｑｂ）における動作を示している。
【００８９】
ステップＳ１４０１、処理Ｓ１４１１、ステップＳ１４０５、処理Ｓ１４１２、及び、ステップＳ１４０９の次に、ステップＳ１４１０において、ステップＳ１４０１で得られた１個の値（Ａｊ×Ｂｊ）と、ステップＳ１４０４で得られたｊ−１個の値（Ｄｊ，ｐ、ｐ＝１，２，…，ｊ−１）と、ステップＳ１４０５で得られたｊ−１個の値（Ｅｊ，ｐ、ｐ＝１，２，…，ｊ−１）と、ステップＳ１４０８で得られたｎ−ｊ個の値（Ｅｊ，ｐ、ｐ＝ｊ＋１，ｊ＋２，…，ｎ）と、ステップＳ１４０９で得られたｎ−ｊ個の値（Ｄｊ，ｐ、ｐ＝ｊ＋１，ｊ＋２，…，ｎ）の、合計２ｎ−１個の値を足し合わせて、それを分散乗算結果Ｃｊとして出力する。ステップＳ１４１０は、メンバＩＤがｍｊであるメンバの図９の方式〔２．２〕の多項加算部５０３における処理を示している。
【００９０】
［実施の形態の効果］
以上説明したように、本発明の実施の形態によれば、ｉｊ項計算部５０２の項計算受信部１００１及び項計算送信部１００２において、掛け算する有限体の値を２値展開し、ビットごとに１−ｏｕｔ−ｏｆ−２紛失通信を用い、それを値の（２進数表示の）桁数ｑｂ分だけ繰り返す（ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失受信部、ｑｂ個の１−ｏｕｔ−ｏｆ−２紛失送信部で処理をする）ことにより、通信量を減少させることができる。このことにより、従来の分散乗算装置では、乗算１回あたりの通信量が、１人のメンバあたり、ｎ×ｑ×ｌｏｇ２ｑビットもの大きさとなっていたが、本発明の実施の形態の分散乗算装置を用いることにより、ｎ×（ｌｏｇ２ｑ）２ビットに減少させることができる。例えば、ｎ＝１０人、ｌｏｇ２ｑ＝１００ビット程度の有限体を考えると、従来の通信量は、１０３３ビット程度の大きさとなってしまっていたのを、本発明の実施の形態の場合の通信量は１０５ビット（＝ｎ×（ｌｏｇ２ｑ）２ビット）程度の大きさまで減少させることができる。
【００９１】
≪変形例≫
本発明の実施の形態においての「メンバ」は、必ずしも１人の人間である必要はなく、秘密情報と計算手段（分散計算部）を構成要素として持つ装置とすることもできる。すなわち、１人の人間が、上記装置を複数個持って処理を進めることができるし（この場合は、１人の人間が複数のメンバとなる）、１つの上記装置を複数の人間が持って処理を進めることもできる場合は、複数の人間が１人のメンバとなる。
【００９２】
【発明の効果】
以上説明したように、本発明によれば、分散乗算における紛失通信の通信量を減少させることができるという効果がある。
【図面の簡単な説明】
【図１】本発明の実施の形態に係る分散乗算装置の項計算受信部の構成を示すブロック図である。
【図２】本発明の実施の形態に係る分散乗算装置の項計算送信部の構成を示すブロック図である。
【図３】本発明の実施の形態及び従来の分散計算システムで実行されるマルチパーティ・プロトコルの説明図である。
【図４】本発明の実施の形態及び従来の分散計算システムの構成を示す図である。
【図５】本発明の実施の形態及び従来の分散計算装置の構成を示すブロック図である。
【図６】図５の分散計算部の構成を示すブロック図である。
【図７】図６の分散加算部の構成を示すブロック図である。
【図８】図６の分散定数乗算部の構成を示すブロック図である。
【図９】図６の分散乗算部の構成を示すブロック図である。
【図１０】本発明の実施の形態のｉｊ項計算部の構成（方式〔２．１〕の場合）を示すブロック図である。
【図１１】本発明の実施の形態のｉｊ項計算部の構成（方式〔２．２〕の場合）を示すブロック図である。
【図１２】本発明の実施の形態に係る分散乗算装置の動作（方式〔２．１〕の場合）を示すフローチャートである。
【図１３】本発明の実施の形態に係る分散乗算装置の動作（方式〔２．２〕の場合）を示すフローチャートである。
【図１４】従来の分散乗算装置におけるｉｊ項計算部の構成（方式〔２．１〕の場合）を示すブロック図である。
【図１５】従来の分散乗算装置におけるｉｊ項計算部の構成（方式〔２．２〕の場合）を示すブロック図である。
【図１６】従来の項計算受信部の構成を示すブロック図である。
【図１７】従来の項計算送信部の構成を示すブロック図である。
【符号の説明】
１０１  分散計算装置、
１０２  通信路、
２０１  秘密分散部、
２０２  分散計算部、
３０１  加算部、
４０１  乗算部、
５０１  ｊｊ項計算部、
５０２  ｉｊ項計算部、
５０３  多項加算部、
６０３−ｐ  加算部、
６０４−ｐ  係数乗算部
９０１，９０２  分散加算部、
９０３，９０４，９０５  分散乗算部（分散乗算装置）、
９０６  分散定数乗算部、
１００１  項計算受信部、
１００１−ｐ  メンバＩＤがｍｐであるメンバの項計算送信部と紛失通信する項計算受信部、
１００２  項計算送信部、
１００２−ｐ  メンバＩＤがｍｐであるメンバの項計算受信部と紛失通信する項計算送信部、
１１０１  ２値展開部、
１１０２−ｉ  １−ｏｕｔ−ｏｆ−２紛失受信部、
１１０３  多項加算部、
１２０１  乱数生成部、
１２０２−ｉ  送信情報生成部、
１２０３−ｉ  １−ｏｕｔ−ｏｆ−２紛失送信部、
１２０４  多項加算部、
ｍ１，ｍ２，…，ｍｎ  メンバＩＤ、
Ａ，Ｂ  有限体ＧＦ（ｑ）上の値、
Ａｊ，Ｂｊ  有限体ＧＦ（ｑ）上の値Ａ，Ｂの分散情報、
Ｄｊ，ｐ，Ｅｊ，ｐ  項計算受信部又は項計算送信部から出力される情報。
【図１】
2004341766.tif 000009
【図２】
2004341766.tif 000010
【図３】
2004341766.tif 000011
【図４】
2004341766.tif 000012
【図５】
2004341766.tif 000013
【図６】
2004341766.tif 000014
【図７】
2004341766.tif 000015
【図８】
2004341766.tif 000016
【図９】
2004341766.tif 000017
【図１０】
2004341766.tif 000018
【図１１】
2004341766.tif 000019
【図１２】
2004341766.tif 000020
【図１３】
2004341766.tif 000021
【図１４】
2004341766.tif 000022
【図１５】
2004341766.tif 000023
【図１６】
2004341766.tif 000024
【図１７】
2004341766.tif 000025