(57)【要約】【課題】分散計算における演算量を低減できる分散計算装置及び分散計算システムを提供する。【解決手段】ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法によりｎ個の秘密情報から生成された分散情報を用いて、分散計算する分散計算部３０５−ｉを有する。分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、分散計算部３０５−ｉが分散計算に用いる分散情報をＹｐとしたときに、分散情報は、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の値をＸ＝ΣＸｊαｊ；０≦ｊ≦Ｌ−１で表されるＸとするときに、ｈＸ（Ｉｊ）＝Ｘｊ；０≦ｊ≦Ｌ−１を満たすｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成し、この多項式ｈＸ（ｘ）から、Ｙｐ＝ｈＸ（ｍｐ）なる有限体ＧＦ（ｑ）上の値を計算することによって生成された情報である。【選択図】        図４
2004287333.tif 000002
【特許請求の範囲】
【請求項１】
分散計算を行う分散計算装置であって、
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により１又は複数個の秘密情報から生成された分散情報を用いて、分散計算する分散計算手段を有し、
この分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、上記分散計算手段が分散計算に用いる分散情報をＹｐとしたときに、上記分散情報は、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊαｊ；０≦ｊ≦Ｌ−１
で表されるＸとするときに、次式
ｈＸ（Ｉｊ）＝Ｘｊ；０≦ｊ≦Ｌ−１
を満たすｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成し、
上記多項式ｈＸ（ｘ）から、
Ｙｐ＝ｈＸ（ｍｐ）
なる有限体ＧＦ（ｑ）上の値を計算することによって生成された情報である
ことを特徴とする分散計算装置。
【請求項２】
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いて秘密情報から生成された分散情報を受信する分散情報受信手段をさらに有し、
上記分散計算手段が分散計算に用いる分散情報が、上記分散情報受信手段で受信された分散情報を含む
ことを特徴とする請求項１に記載の分散計算装置。
【請求項３】
分散計算を行う分散計算装置であって、
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により、秘密情報から分散情報を生成する秘密分散計算手段を有し、
上記秘密分散計算手段が、
上記分散情報が配布される他の分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、メンバＩＤがｍｐである上記分散情報をＹｐとし、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊαｊ；０≦ｊ≦Ｌ−１
で表されるＸとするときに、次式
ｈＸ（Ｉｊ）＝Ｘｊ；０≦ｊ≦Ｌ−１
を満たすｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成する多項式生成手段と、
上記多項式ｈＸ（ｘ）から、
Ｙｐ＝ｈＸ（ｍｐ）
なる有限体ＧＦ（ｑ）上の値を計算することによって生成する分散情報生成手段とを有する
ことを特徴とする分散計算装置。
【請求項４】
上記秘密情報を保持する秘密情報記憶手段をさらに有することを特徴とする請求項３に記載の分散計算装置。
【請求項５】
上記秘密分散計算手段で生成された分散情報を他の分散計算装置へ送信する送信手段をさらに有することを特徴とする請求項３又は４のいずれかに記載の分散計算装置。
【請求項６】
他の分散計算装置からの分散情報を受信する受信手段をさらに有することを特徴とする請求項３から５までのいずれかに記載の分散計算装置。
【請求項７】
上記秘密分散計算手段で生成したこの分散計算装置自身に対する分散情報、及び、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により他の分散計算装置で生成され上記受信手段で受信された分散情報を用いて、分散計算する分散計算手段をさらに有することを特徴とする請求項６に記載の分散計算装置。
【請求項８】
上記分散計算手段の計算結果、及び、他の分散計算装置の分散計算手段からの計算結果Ｚ’ｉから、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行って、拡大体ＧＦ（ｑＬ）上の値
Ｚ＝ΣＺｊαｊ（ｊは、０≦ｊ≦Ｌ−１である整数）を得る秘密再構成手段をさらに有し、
上記秘密再構成手段は、次式
【数１】
2004287333.tif 000053
のような線形結合を行う線形結合手段を有する
ことを特徴とする請求項１、２、７のいずれかに記載の分散計算装置。
【請求項９】
上記分散計算手段が、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体ＧＦ（ｑＬ）上の２つの値であるＡ及びＢの加算の分散加算を実行する場合に、この分散計算装置自身が保持する上記Ａ及びＢに対する分散情報の加算を行う加算手段を有する
ことを特徴とする請求項１、２、７のいずれかに記載の分散計算装置。
【請求項１０】
上記分散計算手段で、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の定数Ｄと、拡大体ＧＦ（ｑＬ）上の値Ａとの乗算の分散定数乗算をする場合には、
この分散計算装置自身が保持する値Ａに対する分散情報ａｉ、定数Ｄ、及び、メンバＩＤを用いて、拡大体ＧＦ（ｑＬ）上の乗算
Ｃ＝Ｄ×ａｉ＝ΣＣｊαｊ；０≦ｊ≦Ｌ−１
となるＣｊの分散情報であるＥｉ，ｊ（０≦ｊ≦Ｌ−１）を求める拡大体乗算手段と、
上記拡大体乗算手段の計算結果であるＥｉ，ｊを、さらにランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散して分散情報であるＦｉ，ｐを生成する第２の秘密分散計算手段と、
上記第２の秘密分散計算手段で生成した分散情報であるＦｉ，ｐを送信する第２の送信手段と、
他の分散計算装置の第２の送信手段から分散情報であるＦｐ，ｉを受信する第２の受信手段と、
上記第２の秘密分散計算手段から生成したこの分散計算装置自身に対する分散情報であるＦｉ，ｉ、及び、その第２の受信手段で受信した分散情報であるＦｐ，ｉをすべて加算する第２の加算手段と、
を有することを特徴とする請求項１、２、７のいずれかに記載の分散計算装置。
【請求項１１】
上記分散計算手段で、有限体ＧＦ（ｑ）を生成多項式
ｇ（ｘ）＝Σｇｉｘｉ；０≦ｉ≦Ｌ
を用いてＬ次拡大した拡大体で生成元がαである、拡大体ＧＦ（ｑＬ）上の値Ａ及びＢの乗算
Ｃ＝ＡＢ＝ΣＣｊαｊ；０≦ｊ≦Ｌ−１
の分散乗算をする場合には、
この分散計算装置自身が保持する値Ａ及びＢに対する分散情報ａｉ及びｂｉの有限体ＧＦ（ｑ）上の乗算
ｃｉ＝ａｉ×ｂｉ
を行う乗算手段と、
他の分散計算装置の分散情報記憶手段に保持されている値Ａ及びＢの分散情報であるａｐ及びｂｐの積ａｉ×ｂｐ及びａｐ×ｂｉの分割情報であるｄｉ，ｐ及びｅｉ，ｐを紛失通信を用いて求める紛失通信計算手段と、
上記乗算手段の乗算結果であるｃｉ、その紛失通信計算手段の計算結果であるｄｉ，ｐ及びｅｉ，ｐ、メンバＩＤ、及び、生成多項式の係数であるｇｉを用いて、Ｃの各次数の係数であるＣｊの分散情報であるＥｉ，ｊ（０≦ｊ≦Ｌ−１）を求める分散情報計算手段と、
上記分散情報計算手段の計算結果であるＥｉ，ｊを、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散して分散情報であるＦｉ，ｐを生成する第３の秘密分散手段と、
上記第３の秘密分散手段で生成した分散情報であるＦｉ，ｐを送信する第３の送信手段と、
他の分散計算装置の第３の送信手段から分散情報であるＦｐ，ｉを受信する第３の受信手段と、
上記第３の秘密分散手段から生成したこの装置自身に対する分散情報であるＦｉ，ｉ、及び、その第３の受信手段で受信した分散情報であるＦｐ，ｉをすべて加算する第３の加算手段と
を有することを特徴とする請求項１、２、７のいずれかに記載の分散計算装置。
【請求項１２】
上記秘密分散計算手段における上記多項式生成手段は、
有限体ＧＦ（ｑ）上のｋ−Ｌ個の乱数であるＲＸ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を生成する乱数生成手段と、
上記乱数であるＲＸ，ｊ、及び、予め決められたｋ個の有限体ＧＦ（ｑ）上の値であるＩｊ（０≦ｊ≦ｋ−１）を用いて、
【数２】
2004287333.tif 000054
のような式で表される多項式を生成するｋ−１次多項式生成手段と
を有することを特徴とする請求項３から７までのいずれかに記載の分散計算装置。
【請求項１３】
上記請求項１から１２までのいずれかに記載の分散計算装置と同じ構成を持つ複数個の分散計算装置と、
上記複数個の分散計算装置から出力される計算結果を受け取って、受け取った計算結果から、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行う秘密再構成装置と
を有することを特徴とする分散計算システム。
【請求項１４】
上記請求項１から１２までのいずれかに記載の分散計算装置と同じ構成を持つ複数個の分散計算装置を有し、
上記複数個の分散計算装置のうち、少なくとも１以上は、
他の分散計算装置の分散計算手段からの計算結果を受け取り、この装置自身の分散計算手段の計算結果と、他の分散計算装置の分散計算手段から受け取った計算結果から、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行って、拡大体ＧＦ（ｑＬ）上の値
Ｚ＝ΣＺｊαｊ；０≦ｊ≦Ｌ−１
を得る秘密再構成手段を有する
ことを特徴とする分散計算システム。
【請求項１５】
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いて、分散計算に用いる分散情報を生成する秘密分散計算装置をさらに有し、
分散計算手段を持つ上記分散計算装置のうちすべては、その秘密分散計算装置からの分散情報を受信する分散情報受信手段を有する
ことを特徴とする請求項１３又は１４のいずれかに記載の分散計算システム。
【請求項１６】
分散計算を行う分散計算装置であって、
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により１又は複数個の秘密情報から生成された分散情報を用いて、分散計算する分散計算手段を有し、
この分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、上記分散計算手段が分散計算に用いる分散情報をＹｐとしたときに、上記分散情報は、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαで生成多項式がｇ（ｘ）である拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊ  αｊ；０≦ｊ≦Ｌ−１
で表されるＸとし、ＲＸ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を乱数とするときに、次式
【数３】
2004287333.tif 000055
で表されるｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成し、
上記多項式ｈＸ（ｘ）から、
Ｙｐ＝ｈＸ（ｍｐ）
なる有限体ＧＦ（ｑ）上の値を計算することによって生成された情報である
ことを特徴とする分散計算装置。
【請求項１７】
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いて秘密情報から生成された分散情報を受信する分散情報受信手段をさらに有し、
上記分散計算手段が分散計算に用いる分散情報が、上記分散情報受信手段で受信された分散情報を含む
ことを特徴とする請求項１６に記載の分散計算装置。
【請求項１８】
分散計算を行う分散計算装置であって、ランプ型（Ｌ、ｋ、ｎ）しきい値秘密分散法により、秘密情報から分散情報を生成する秘密分散計算手段を有し、
上記秘密分散計算手段が、
上記分散情報が配布される補記あの分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、メンバＩＤがｍｐである上記分散情報をＹｐとし、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαで生成多項式がｇ（ｘ）である拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊ  αｊ；０≦ｊ≦Ｌ−１
で表されるＸとし、ＲＸ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を乱数とするときに、次式
【数４】
2004287333.tif 000056
で表されるｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成する多項式生成手段と、
上記多項式ｈＸ（ｘ）から、
Ｙｐ＝ｈＸ（ｍｐ）
なる有限体ＧＦ（ｑ）上の値を計算することによって生成する分散情報生成手段とを有する
ことを特徴とする分散計算装置。
【請求項１９】
上記秘密情報を保持する秘密情報記憶手段をさらに有することを特徴とする請求項１８に記載の分散計算装置。
【請求項２０】
上記秘密分散計算手段で生成された分散情報を他の分散計算装置へ送信する送信手段をさらに有することを特徴とする請求項１８又は１９のいずれかに記載の分散計算装置。
【請求項２１】
他の分散計算装置からの分散情報を受信する受信手段をさらに有することを特徴とする請求項１８から２０までのいずれかに記載の分散計算装置。
【請求項２２】
上記秘密分散計算手段で生成したこの分散計算装置自身に対する分散情報、及び、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により他の分散計算装置で生成され上記受信手段で受信された分散情報を用いて、分散計算する分散計算手段をさらに有する特徴とする請求項２１に記載の分散計算装置。
【請求項２３】
上記分散計算手段の計算結果、及び、他の分散計算装置の分散計算手段からの計算結果Ｚ’ｉから、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行って、拡大体ＧＦ（ｑＬ）上の値
Ｚ＝ΣＺｊ  αｊ（ｊは、０≦ｊ≦Ｌ−１である整数）
を得る秘密再構成手段をさらに有し、
上記秘密再構成手段は、メンバＩＤより生成した行列
Ｅ＝（ｅｊｉ）、ｅｊｉ＝ｍｊｉ−１（ｉ、ｊ＝１，２，…，ｎ）
の逆行列Ｅ−１と、ｔ次の多項式の係数を表すベクトルに対して、拡大体ＧＦ（ｑＬ）の生成多項式ｇ（ｘ）の剰余を与えるような行列Ｇより、次式のような行列
Ｇ  Ｅ−１＝（ｒｊｉ）
を満たすｒｊｉを計算する復元情報生成手段と、
その復元情報生成手段で生成したｒｊｉ、及び、Ｚ’ｉから、
【数５】
2004287333.tif 000057
のような計算を行う有限体演算手段と、
を有することを特徴とする請求項１６、１７、２２のいずれかに記載の分散計算装置。
【請求項２４】
上記分散計算手段が、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体ＧＦ（ｑＬ）上の２つの値であるＡ及びＢの加算の分散加算を実行する場合に、この分散計算装置自身が保持する上記Ａ及びＢに対する分散情報の加算を行う加算手段を有する
ことを特徴とする請求項１６、１７、２２のいずれかに記載の分散計算装置。
【請求項２５】
上記分散計算手段で、有限体ＧＦ（ｑ）をＬ次拡大した拡大体ＧＦ（ｑＬ）上の値Ａ及びＢの乗算の分散乗算をする場合には、
この分散計算装置自身が保持する値Ａ及びＢに対する分散情報ａｉ及びｂｉの有限体ＧＦ（ｑ）上の乗算
ｃｉ＝ａｉ×ｂｉ
を行う乗算手段と、
上記乗算手段の結果であるｃｉを、さらに（ｋ’，ｎ）しきい値秘密分散法で分散して分散情報であるｃｉ，ｐを生成する第２の秘密分散計算手段と、
上記第２の秘密分散計算手段で生成した分散情報であるｃｉ，ｐを送信する第２の送信手段と、
他の分散計算装置の第２の送信手段からの分散情報であるｃｐ，ｉを受信する第２の受信手段と、
第２の秘密分散計算手段から生成したこの分散計算装置自身に対する分散情報であるｃｉ，ｉ、及び、その第２の受信手段で受信した分散情報であるｃｐ，ｉを、しきい値がｋで、同じ秘密情報を復元するような分散情報に変換する中間情報変換手段と、
その中間情報変換手段の計算結果を送信する第３の送信手段と、
他の分散装置の第３の送信手段からの計算結果を受信する第３の受信手段と、
その中間情報変換手段のこの分散計算装置自身に対する計算結果と、第３の受信手段で受信した計算結果を（ｋ’，ｎ）しきい値秘密分散法の秘密再構成を行う秘密復元処理手段と、
を有することを特徴とする請求項１６、１７、２２のいずれかに記載の分散計算装置。
【請求項２６】
上記中間情報変換手段は、
メンバＩＤから生成される、秘密分散に利用される第１の行列と、
ランダムな２（ｋ−１）次多項式を初期値とする多項式
ｈ（ｘ）＝Σｈｊ  ｘｊ；０≦ｊ≦２（ｋ−１）
と、
拡大体ＧＦ（ｑＬ）の生成多項式ｇ（ｘ）を多項式ｈ（ｘ）の最高次数の係数倍した多項式と、の差分多項式を計算することを繰り返すことを、次数が（ｋ−１）次になるまで続け、得られた（ｋ−１）次多項式の係数を元の多項式の係数ｈｊの線形結合で表すという方法で生成した第２の行列と、
メンバＩＤから生成される、秘密復元に利用される第３の行列と、
の３つの行列の積で表される変換行列により変換する
ことを特徴とする請求項２５に記載の分散計算装置。
【請求項２７】
上記分散計算手段で、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体ＧＦ（ｑＬ）上の定数Ｄが、次式
Ｄ＝ΣＤｊ  αｊ；０≦ｊ≦Ｌ−１
で表されるとし、この定数Ｄと、拡大体ＧＦ（ｑＬ）上の値Ａとの乗算の分散定数乗算をする場合には、
あらかじめ決められた値ＲＤ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を用いて、次式
【数６】
2004287333.tif 000058
で表されるｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＤ（ｘ）を生成し、
上記多項式ｈＤ（ｘ）から、
ｄｉ＝ｈＤ（ｍｉ）
なる有限体ＧＦ（ｑ）上の値を計算することによって、この分散計算装置自身に対する定数Ｄの分散情報ｄｉを生成する定数情報生成手段と、
その定数情報生成手段で生成した分散情報ｄｉとこの分散計算装置自身が保持する値Ａに対する分散情報ａｉを用いた分散乗算を実行する分散乗算手段と、
を有することを特徴とする請求項１６、１７、２２のいずれかに記載の分散計算装置。
【請求項２８】
上記請求項１６から２７までのいずれかに記載の分散計算装置と同じ構成を持つ複数個の分散計算装置と、
上記複数個の分散計算装置から出力される計算結果を受け取って、受け取った計算結果から、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行う秘密再構成装置と
を有することを特徴とする分散計算システム。
【請求項２９】
上記請求項１６から２７までのいずれかに記載の分散計算装置と同じ構成を持つ複数個の分散計算装置を有し、
上記複数個の分散計算装置のうち、少なくとも１以上は、
他の分散計算装置の分散計算手段からの計算結果を受け取り、この装置自身の分散計算手段の計算結果と、他の分散計算装置の分散計算手段から受け取った計算結果から、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行って、拡大体ＧＦ（ｑＬ）上の値
Ｚ＝ΣＺｊ  αｊ；０≦ｊ≦Ｌ−１
を得る秘密再構成手段を有する
ことを特徴とする分散計算システム。
【請求項３０】
ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いて、分散計算に用いる分散情報を生成する秘密分散計算装置をさらに有し、
分散計算手段を持つ上記分散計算装置のうちすべては、その秘密分散計算装置からの分散情報を受信する分散情報受信手段を有する
ことを特徴とする請求項２８又は２９のいずれかに記載の分散計算システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、複数の分散計算装置が保持する秘密情報から生成された分散情報を用いる分散計算方法を実施する分散計算システム、及び、この分散計算システムの一部を構成する分散計算装置に関するものである。
【０００２】
【従来の技術】
現在、暗号の技術分野では、マルチパーティ・プロトコルと呼ばれる、分散計算方法が実現されている。ここで、一般的なマルチパーティ・プロトコルについて説明する。今、ｎ人のメンバ（ｎ個の演算装置としてもよい）より構成されるネットワークがあるとして、メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）を持つそれぞれのメンバが、他のメンバには知られたくない秘密情報Ｘｉ（ｉ＝１，２，…，ｎ）を保持しているものとする。ある関数ｆが与えられたときに、各メンバは各自の秘密情報Ｘｉを秘密にしたまま、その関数Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）を計算して、求めるべき値Ｚを算出しようとする。なお、関数ｆは、例えば、すべての秘密情報Ｘｉを足し合わせる関数Ｚ＝Ｘ１＋Ｘ２＋…＋Ｘｎであったり、すべての秘密情報Ｘｉのうち最大の値を出力する関数Ｚ＝ｍａｘ｛Ｘ１，Ｘ２，…，Ｘｎ｝であったりする。
【０００３】
このように、各メンバが、ネットワーク上で、各自の秘密情報Ｘｉ自体を一切漏らさないで、お互いになんらかの通信を行い、最終的に値Ｚを計算し得る機能を実現するプロトコルを、関数ｆに関するマルチパーティ・プロトコルと呼ぶ。上記機能は、関数ｆの計算を行う信頼できる第三者のセンターを設け、各メンバが各自の秘密情報をこのセンターへ秘密に送信することにより実現できるが、ここでは、そのようなセンターがない場合を説明する。
【０００４】
図２は、マルチパーティ・プロトコルの概念説明図である。図２の例においては、メンバ（参加者）人数を３人とし、それぞれのメンバＩＤ（ＩＤ情報）をＡ，Ｂ，Ｃとし、それぞれが保持する秘密情報をＸＡ，ＸＢ，ＸＣとする。メンバＩＤ＿Ａ，Ｂ，Ｃ、及び、秘密情報ＸＡ，ＸＢ，ＸＣなどの値は、ある有限体ＧＦ（ｑ）（ｑは、素数又は素数のべき乗の値）上の値とし、マルチパーティ・プロトコルで分散計算しようとする関数ｆ（ＸＡ，ＸＢ，ＸＣ）内の演算（加算及び乗算）は、有限体ＧＦ（ｑ）上の演算とする。以降、特に断りがない限り、演算は、有限体ＧＦ（ｑ）上で行うものとする。
【０００５】
関数ｆ（ＸＡ，ＸＢ，ＸＣ）のマルチパーティ・プロトコルによる分散計算を行う際に、まず、各メンバは、自分の保持する秘密情報を（ｋ，ｎ）しきい値秘密分散法で分散する（図２に符号▲１▼で示される処理）。（ｋ，ｎ）しきい値秘密分散法は、情報Ｘをｎ個に分散させ、そのｎ個の分散情報のうちｋ個（ｋ≦ｎ）の分散情報が集まれば、情報Ｘを復元することができ、ｋ−１個以下の分散情報しか集まらないときには、情報Ｘについてなんら知ることができない、といった秘密分散法である。図２の場合には、ｎは３であり、ｋは２又は３である。
【０００６】
次に、各メンバは、自分の秘密情報を分散した分散情報をそれぞれ他のメンバに配布する（図２に符号▲２▼で示される処理）。これらの分散情報を配布する際には、どの２人のメンバ間にも、その２人のメンバ以外には通信内容を秘密とすることができる秘密通信路が確立されているものとする。次に、それら配布された分散情報を用いて、関数ｆ（ＸＡ，ＸＢ，ＸＣ）で定められる計算方法で、各メンバが分散計算を行う（図２に符号▲３▼で示される処理）。この分散計算の際には、各メンバ同士が情報交換を行うこともある。この各メンバが保持する分散計算の計算結果Ｚ’Ａ，Ｚ’Ｂ，Ｚ’Ｃはそれぞれ、最終的な計算結果Ｚ＝ｆ（ＸＡ，ＸＢ，ＸＣ）を秘密分散した分散情報となっている。したがって、最終的に、各メンバが持っている分散計算の計算結果Ｚ’Ａ，Ｚ’Ｂ，Ｚ’Ｃを集め、（ｋ，ｎ）しきい値秘密分散法の秘密再構成を行うと、最終的な計算結果Ｚを得ることができる（図２の符号▲４▼で示される処理）。
【０００７】
次に、図２に示されるマルチパーティ・プロトコルを、ｎ人のメンバに拡張した場合について説明する。各メンバのメンバＩＤをｍｉ（ｉ＝１，２，…，ｎ）、メンバＩＤがｍｉであるメンバの保持する秘密情報をＸｉ（ｉ＝１，２，…，ｎ）とする。各メンバは、各自が保持する秘密情報を（ｋ，ｎ）しきい値秘密分散法で分散する。ここでの（ｋ，ｎ）しきい値秘密分散法は、Ｓｈａｍｉｒ法（シャミア法：Ｓｈａｍｉｒ’ｓ  ｍｅｔｈｏｄ）（例えば、非特許文献１参照）を用いるものとする。
【０００８】
メンバＩＤがｍｉであるメンバは、次式（１）のようなｋ−１次多項式ｈｘｉ（ｘ）を生成し、この式を用いて秘密情報を分散する。
【数７】
2004287333.tif 000003
上記式（１）において、Ｒｘｉ，１，Ｒｘｉ，２，…，Ｒｘｉ，ｋ−１は、メンバＩＤがｍｉであるメンバが決める乱数であり、有限体ＧＦ（ｑ）上の値からｋ−１個選択されたものである。
【０００９】
メンバＩＤがｍｉであるメンバで計算され、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに配布される分散情報を、Ｙｉ，ｐと表わす場合に、分散情報Ｙｉ，ｐは、上記式（１）の関数を用いて、次式（２）のように計算することができる。
【数８】
2004287333.tif 000004
【００１０】
各メンバが他のメンバから分散情報を受け取ると、結果として、メンバＩＤがｍｉであるメンバは、ｎ個の分散情報Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉを保持することになる。これら各メンバが保持する分散情報Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉを用いて、すなわち、各メンバが協力して、所望の分散計算Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）を行う。
【００１１】
ここでは、各メンバが行う分散計算として、分散加算の場合と分散乗算の場合を説明する。上記式（１）に示されるような多項式を用いて、秘密情報Ａ及びＢを秘密分散させ、メンバＩＤがｍｉであるメンバが、分散情報ａｉ及びｂｉを既に持っている状態を考える。この場合、秘密情報Ａ及びＢと分散情報ａｉ及びｂｉとの関係は、次式（３）及び（４）のようになる。
【数９】
2004287333.tif 000005
ここで、ＲＡ，ｊ（ｊ＝１，２，…，ｋ−１）及びＲＢ，ｊ（ｊ＝１，２，…，ｋ−１）は乱数である。
【００１２】
各メンバが分散情報ａｉ及びｂｉから計算を行って、秘密情報Ｃ（＝Ａ＋Ｂ）を秘密分散させた値ｃｉをメンバＩＤがｍｉであるメンバが持つようにする計算処理を「分散加算」と呼ぶ。また、各メンバが分散情報ａｉ及びｂｉから計算を行って、秘密情報Ｃ（＝Ａ×Ｂ）を秘密分散させた値ｃｉをメンバＩＤがｍｉであるメンバが持つようにする計算処理を「分散乗算」と呼ぶ。さらに、ある定数Ｄと秘密情報Ａとの乗算結果Ｃ（＝Ｄ×Ａ）を秘密分散させた値ｃｉをメンバＩＤがｍｉであるメンバが持つようにする計算処理を「分散定数乗算」と呼ぶ。上記のような、任意の分散情報の分散加算、分散定数乗算、及び、分散乗算が可能になると、加算、定数乗算、及び、乗算を含む任意の関数Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）は、分散計算が可能となる。以降では、上記式（１）のような多項式により秘密情報Ａ及びＢを秘密分散させ、各メンバが、分散情報ａｉ及びｂｉを既に持っている状態を考え、各メンバが分散情報ａｉ及びｂｉから計算を行って、Ｃ＝ｆ（Ａ，Ｂ）を秘密分散させた値ｃｉを求める処理を説明する。
【００１３】
まず、マルチパーティ・プロトコルにおける分散加算（加算計算）を次式（５）を用いて説明する。
Ｃ＝ｆ（Ａ，Ｂ）＝Ａ＋Ｂ    …（５）
メンバＩＤがｍｉであるメンバは、すでに秘密情報Ａ及びＢの分散情報ａｉ及びｂｉを持っているものとする。これら分散情報ａｉ及びｂｉは、任意のメンバの秘密情報の分散情報（Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉ）のいずれかでもよいし、分散計算した途中結果の値でもよい。分散加算においては、分散情報同士の足し算を行うことで、計算結果Ｃの分散情報ｃｉ（ｉ＝１，２，…，ｎ）を得ることができる。例えば、メンバＩＤがｍｉであるメンバは、次式（６）のような計算を行い、計算結果ｃｉを得る。
ｃｉ＝ａｉ＋ｂｉ    …（６）
【００１４】
次に、マルチパーティ・プロトコルにおける分散定数乗算（定数乗算計算）を次式（７）を用いて説明する。
Ｃ＝ｆ（Ａ）＝Ｄ×Ａ    …（７）
ここで、Ｄは、有限体ＧＦ（ｑ）上の定数であり、どのメンバにも既知な値とする。例えば、メンバＩＤがｍｉであるメンバは、次式（８）のような計算を行い、計算結果ｃｉを得る。
ｃｉ＝Ｄ×ａｉ    …（８）
【００１５】
次に、マルチパーティ・プロトコルにおける分散乗算（乗算計算）を次式（９）を用いて説明する。
Ｃ＝ｆ（Ａ，Ｂ）＝Ａ×Ｂ    …（９）
分散乗算においては、次の２通りの方法があり、ここでの説明では、それらの方式をそれぞれ方式▲１▼、方式▲２▼と記述することにする。方式▲１▼では、各メンバは、次のようなステップＳ１０１〜Ｓ１０３を行う。ここでは、メンバＩＤがｍｉであるメンバが実行する処理を記述する。ステップＳ１０１において、分散情報同士の乗算ｃｉ，ｉ＝ａｉ×ｂｉを行う。
【００１６】
次のステップＳ１０２において、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの。）である他のメンバの値との乗算ａｉ×ｂｐ及びａｐ×ｂｉの結果に相当するものが得られるように通信及び計算処理をする。すなわち、次式（１０）となるような、メンバＩＤがｍｉであるメンバが乗算結果ｃｉ，ｐを持つことができ、メンバＩＤがｍｐであるメンバが乗算結果ｃｐ，ｉを持つことができるように、計算と通信を行う。
ａｉ×ｂｐ＋ａｐ×ｂｉ＝ｃｉ，ｐ＋ｃｐ，ｉ    …（１０）
このように、他のメンバとの情報のやりとりを行うことにより、他のメンバの値との乗算ａｉ×ｂｐ及びａｐ×ｂｉの結果に相当する式（１０）が得られるようにするが、他のメンバの値ａｐ及びｂｐが分からないように、また、自分の値ａｉ及びｂｉが、他のメンバに分からないように、紛失通信を行う。「紛失通信」とは、送信側が、Ｍ個の情報を符号化（暗号化）して送信するが、受信側においては、そのうち一つしか受け取る（意味のあるように復号が可能となる）ことができず、また、送信側においては、受信側がどの情報を受け取った（意味のあるように復号が可能となった）かを知ることができない通信方法をいう。
【００１７】
次の、ステップＳ１０３においては、ステップＳ１０２の結果に、メンバＩＤから計算される係数ｒｐを乗算して足し合わせることにより、次式（１１）及び（１２）で示される、乗算結果Ｃの分散情報ｃｉ（ｉ＝１，２，…，ｎ）を得る。
【数１０】
2004287333.tif 000006
【００１８】
また、方式▲２▼では、各メンバは、次のようなステップＳ２０１〜Ｓ２０５を行う。ここでは、メンバＩＤがｍｉであるメンバが実行する処理を記述する。ステップＳ２０１において、分散情報同士の乗算ｃ’ｉ＝ａｉ×ｂｉを行う。
【００１９】
次のステップＳ２０２において、ステップＳ２０１で求めたｃ’ｉを（ｋ’，ｎ）しきい値秘密分散法を用いて分散し、分散情報ｃ’ｉ，ｐ（ｐ＝１，２，…，ｎでｐ≠ｉであるもの）をメンバＩＤがｍｐである他のメンバへ配布する。また、他のメンバから、分散情報ｃ’ｐ，ｉ（ｐ＝１，２，…，ｎでｐ≠ｉであるもの）を受け取る。
【００２０】
次のステップＳ２０３において、Ｃ’ｉ＝（ｃ’１，ｉ、ｃ’２，ｉ、…、ｃ’ｎ，ｉ）に変換行列ＥＰＥ−１を掛け合わせることにより、Ｄｉ＝（ｄ１，ｉ、ｄ２，ｉ、…、ｄｎ，ｉ）に変換する。行列Ｅは、メンバＩＤから計算される行列であり、
Ｅ＝（ｅｉｊ）＝（ｍｉｊ−１）  （ｉ，ｊ＝１、２、…、ｎ）
となるようなｎ×ｎ行列であり、その逆行列をＥ−１とする。また、行列Ｐは、次式のようにベクトルのｋ＋１番目以降の値を０とするような変換を行うｎ×ｎ行列である。
Ｐ（ｘ１、ｘ２、…、ｘｎ）ｔ
＝（ｘ１、ｘ２、…、ｘｋ、０、…、０）    …（８０）
【００２１】
次のステップＳ２０４において、ステップＳ２０３で求めたｄｐ，ｉ（ｐ＝１，２，…，ｎでｐ≠ｉであるもの）を、メンバＩＤがｍｐである他のメンバへ配布する。また、他のメンバから、計算結果ｄｉ，ｐ（ｐ＝１，２，…，ｎでｐ≠ｉであるもの）を受け取る。
【００２２】
次のステップＳ２０５において、ステップＳ２０３、Ｓ２０４で得たｄｉ，ｐ（ｐ＝１，２，…，ｎ）を分散情報として、（ｋ’、ｎ）しきい値秘密分散法の秘密再構成を行うことにより、乗算結果Ｃの分散情報ｃｉ（ｉ＝１、２、…、ｎ）を得る。
【００２３】
このように分散乗算においては、分散加算の場合のように簡単には計算できないが、紛失通信を用いると計算可能となる。上記のように、各メンバ同士が秘密通信、紛失通信を行って計算処理をすると、入力値を公開せずに、与えられた関数ｆ（加算と乗算で構成される関数）の計算を行うことができる。
【００２４】
Ｓｈａｍｉｒ法に代表される通常の（ｋ，ｎ）しきい値秘密分散法においては、秘密情報をｎ個の分散情報に符号化し、ｋ（≦ｎ）個以上の分散情報が集まれば、もとの秘密情報を復元することができるが、ｋ−１個以下であると、その秘密情報については全く知ることができないという性質を、多項式補間を用いることにより実現している。
【００２５】
具体的には、次式（１３）のようなｋ−１次多項式ｈＳ（ｘ）を用いてもとの秘密情報を分散する。
【数１１】
2004287333.tif 000007
ここで、Ｓは、もとの秘密情報であり、ＲＳ，１，ＲＳ，２，…，ＲＳ，ｋ−１は、分配者が決める乱数である。
【００２６】
分配するｎ人の各メンバには、メンバＩＤとして、ｍ１，ｍ２，…，ｍｎが付与されているものとし、メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）に対する分散情報Ｓｉは、上記式（１３）を用いて、次式（１４）のように計算することができる。
【数１２】
2004287333.tif 000008
【００２７】
ここでは、メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）、秘密情報Ｓ、分散情報Ｓｉ（ｉ＝１，２，…，ｎ）、乱数ＲＳ，１，ＲＳ，２，…，ＲＳ，ｋ−１などの値は、それぞれ、ある有限体ＧＦ（ｑ）（ｑは、素数又は素数のべき乗の値）上の値とし、演算（加算及び乗算）は、それぞれ、有限体ＧＦ（ｑ）上の演算とする。また、上記式（１３）より、次式（１５）という関係式が成り立つ。
ｈＳ（０）＝Ｓ    …（１５）
【００２８】
もとの秘密情報Ｓを、各メンバに配布した分散情報から再構成する場合には、分散情報を分配したメンバのうち、ｔ人（ｋ≦ｔ）を集めてきて、そのメンバＩＤと分散情報を持ち寄り、次式（１６）及び（１７）で計算することで達成できる。
【数１３】
2004287333.tif 000009
ここで、ｍ’１，ｍ’２，…，ｍ’ｔは、集まったメンバのメンバＩＤであり、Ｓ’１，Ｓ’２，…，Ｓ’ｔは、集まったメンバが保持する分散情報である。
【００２９】
このＳｈａｍｉｒ法に代表される通常の（ｋ，ｎ）しきい値秘密分散法においては、もとの秘密情報Ｓとその分散情報Ｓｉ（ｉ＝１，２，…，ｎ）は、ともに有限体ＧＦ（ｑ）上の値であり、分散情報Ｓｉ（ｉ＝１，２，…，ｎ）の情報量は、もとの秘密情報Ｓの情報量よりも小さくすることができない性質がある。
【００３０】
【非特許文献１】
岡本龍明他、「現代暗号」（産業図書）、第２１４−２１６ページ及び第２２７−２３６ページ
【非特許文献２】
ジー・アール・ブラクレイ及びキャサリン・メドウズ、「セキュリティ・オブ・ランプ・スキームズ」、プロスィージャ・オブ・クリプト’８８、レクチャー・ノーツ・イン・コンピュータ・サイエンス４０３、スプリンガー・ベルラグ、、第２４２−２６８ページ、１９９０年（Ｇ．Ｒ．ＢＬＡＫＬＥＹ  ＡＮＤ  ＣＡＴＨＥＲＩＮＥ  ＭＥＡＤＯＷＳ，“ＳＥＣＵＲＩＴＹ  ＯＦ  ＲＡＭＰ  ＳＣＨＥＭＥＳ”，  ＰＲＯＣ．  ＯＦ  ＣＲＹＰＴＯ  ’８８，  ＬＥＣＴＵＲＥ  ＮＯＴＥＳ  ＩＮ  ＣＯＭＰＵＴＥＲ  ＳＣＩＥＮＣＥ  ４０３，  ＳＰＲＩＮＧＥＲ−ＶＥＲＬＡＧ，  ｐｐ．  ２４２−２６８  （１９９０）
【００３１】
【発明が解決しようとする課題】
しかしながら、上記した従来のマルチパーティ・プロトコルによる分散計算においては、通常の（ｋ，ｎ）しきい値秘密分散法を用いて、それぞれの秘密情報の秘密分散を行っているため、各メンバにおける分散計算においては、その秘密情報と同じ情報量、すなわち、同じ大きさの有限体上における演算を行う必要がある。このため、秘密情報をｎ人に分散して演算しているにもかかわらず、メンバそれぞれの分散演算処理における、演算量、演算回路に必要な回路規模、演算に必要な記憶容量、演算時間等の演算コストを下げることができないといった問題があった。
【００３２】
そこで、本発明は上記したような従来技術の課題を解決するためになされたものであり、その目的は、分散計算における演算量を低減することができる分散計算装置及び分散計算システムを提供することである。
【００３３】
【課題を解決するための手段】
本発明に係る分散計算装置は、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により１又は複数個（通常は２個以上であるが、１個の場合も有りうる。）の秘密情報から生成された分散情報を用いて、分散計算する分散計算手段を有し、この分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、上記分散計算手段が分散計算に用いる分散情報をＹｐとしたときに、上記分散情報は、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の値を次式Ｘ＝ΣＸｊαｊ；０≦ｊ≦Ｌ−１を満たすＸとするときに、次式ｈＸ（Ｉｊ）＝Ｘｊ；０≦ｊ≦Ｌ−１を満たすｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成し、上記多項式ｈＸ（ｘ）から、Ｙｐ＝ｈＸ（ｍｐ）なる有限体ＧＦ（ｑ）上の値を計算することによって生成された情報であることを特徴としている。
【００３４】
また、本発明に係る他の分散計算装置は、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により、秘密情報から分散情報を生成する秘密分散計算手段を有し、上記秘密分散計算手段が、上記分散情報が配布される他の分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、メンバＩＤがｍｐである上記分散情報をＹｐとし、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαである拡大体ＧＦ（ｑＬ）上の値を次式Ｘ＝ΣＸｊαｊ；０≦ｊ≦Ｌ−１を満たすＸとするときに、次式ｈＸ（Ｉｊ）＝Ｘｊ；０≦ｊ≦Ｌ−１を満たすｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成する多項式生成手段と、上記多項式ｈＸ（ｘ）から、Ｙｐ＝ｈＸ（ｍｐ）なる有限体ＧＦ（ｑ）上の値を計算することによって生成する分散情報生成手段とを有することを特徴としている。
【００３５】
また、本発明に係る他の分散計算装置は、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法により１又は複数個（通常は２個以上であるが、１個の場合も有りうる。）の秘密情報から生成された分散情報を用いて、分散計算する分散計算手段を有し、この分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、上記分散計算手段が分散計算に用いる分散情報をＹｐとしたときに、上記分散情報は、
有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαで生成多項式がｇ（ｘ）である拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊ  αｊ；０≦ｊ≦Ｌ−１
で表されるＸとし、ＲＸ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を乱数とするときに、次式
【数１４】
2004287333.tif 000010
で表されるｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成し、
上記多項式ｈＸ（ｘ）から、
Ｙｐ＝ｈＸ（ｍｐ）
なる有限体ＧＦ（ｑ）上の値を計算することによって生成された情報であることを特徴としている。
【００３６】
また、本発明に係る他の分散計算装置は、ランプ型（Ｌ、ｋ、ｎ）しきい値秘密分散法により、秘密情報から分散情報を生成する秘密分散計算手段を有し、上記秘密分散計算手段が、上記分散情報が配布される補記あの分散計算装置が保持するメンバＩＤをｍｐ（ｐ≦ｎ）とし、メンバＩＤがｍｐである上記分散情報をＹｐとし、有限体ＧＦ（ｑ）をＬ次拡大した拡大体で生成元がαで生成多項式がｇ（ｘ）である拡大体ＧＦ（ｑＬ）上の値を次式
Ｘ＝ΣＸｊ  αｊ；０≦ｊ≦Ｌ−１
で表されるＸとし、ＲＸ，ｊ（０≦ｊ≦ｋ−Ｌ−１）を乱数とするときに、次式
【数１５】
2004287333.tif 000011
で表されるｋ−１次の有限体ＧＦ（ｑ）上の多項式ｈＸ（ｘ）を生成する多項式生成手段と、上記多項式ｈＸ（ｘ）から、Ｙｐ＝ｈＸ（ｍｐ）なる有限体ＧＦ（ｑ）上の値を計算することによって生成する分散情報生成手段とを有することを特徴としている。
【００３７】
【発明の実施の形態】
本発明においては、従来技術のマルチパーティ・プロトコルによる分散計算において用いていた、Ｓｈａｍｉｒ法に代表される通常の（ｋ，ｎ）しきい値秘密分散法に代えて、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いる。それにより、各メンバに必要な演算は、もとの秘密情報の有限体の大きさよりも小さい有限体上で行うことができ、演算コストを下げることができる。
【００３８】
先ず、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法について説明する。Ｓｈａｍｉｒ法に代表される通常の（ｋ，ｎ）しきい値秘密分散法は、ｎ個の分散情報の内のｋ−１個の分散情報しか集まらない場合には、その分散情報のもとの秘密情報については、全く知ることができない方法である。これに対し、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法は、あるパラメータＬ（１≦Ｌ≦ｋ≦ｎ）を導入し、各分散情報Ｓｉ（ｉ＝１，２，…，ｎ）の情報量を、もとの秘密情報Ｓの１／Ｌに減らすことにより、ｎ個の分散情報の内のｋ−ｄ（１≦ｄ≦Ｌ−１）個の分散情報が集まったときには、ｋ個の分散情報が集まっていなくても、もとの秘密情報についての何らかの情報が漏れる性質を持つ。
【００３９】
Ｓｈａｍｉｒ法をランプ型に拡張した方式は、例えば、上記非特許文献２に記載されている。その方式においては、まず、もとの秘密情報Ｓは、次式（１８）で示されるようなベクトル値とする。
Ｓ＝（Ｓ０，Ｓ１，…，ＳＬ−１）    …（１８）
また、Ｓ０，Ｓ１，…，ＳＬ−１はそれぞれ、有限体ＧＦ（ｑ）上の値とし、ＲＳ２，０，ＲＳ２，１，…，ＲＳ２，ｋ−Ｌ−１はそれぞれ、分配者が決める乱数で有限体ＧＦ（ｑ）上の値である。また、予め、Ｉ０，Ｉ１，…，Ｉｋ−１のｋ個の有限体ＧＦ（ｑ）上の値を決めておく。そして、次式（１９）及び（２０）のようなｋ−１次多項式ｈＳ２（ｘ）を用いて秘密情報を秘密分散する。
【００４０】
【数１６】
2004287333.tif 000012
【００４１】
分散情報が配布されるｎ人の各メンバには、メンバＩＤとして、ｍ１，ｍ２，…，ｍｎが付与されているものとし、メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）に対する分散情報Ｘｉは、次式（２１）のように計算する。
Ｘｉ＝ｈＳ２（ｍｉ）    …（２１）
【００４２】
ここでは、演算（加算及び乗算）は、それぞれ、有限体ＧＦ（ｑ）上の演算とする。したがって、分散情報Ｘｉは、有限体ＧＦ（ｑ）上の値である。以降、特に断りがない限り、演算は、有限体ＧＦ（ｑ）上で行うものとする。また、上記式（１９）より、次式（２２）の関係式が成り立つ。
ｈＳ２（Ｉ０）＝Ｓ０
ｈＳ２（Ｉ１）＝Ｓ１
…
ｈＳ２（ＩＬ−１）＝ＳＬ−１        …（２２）
【００４３】
各メンバに配布した分散情報Ｘｉから、もとの秘密情報Ｓ＝（Ｓ０，Ｓ１，…，ＳＬ−１）を再構成する場合には、分散情報を分配したメンバのうち、ｋ人以上のｔ人（ｋ≦ｔ）のメンバを集めてきて、そのメンバＩＤと分散情報を持ち寄り、次式（２３）及び（２４）で計算すると、もとの秘密情報Ｓ＝（Ｓ０，Ｓ１，…，ＳＬ−１）を求めることができる。なお、次式（２３）及び（２４）において、ｍ’１，ｍ’２，…，ｍ’ｔは、集まったメンバのメンバＩＤであり、Ｘ’１，Ｘ’２，…，Ｘ’ｔは、メンバＩＤがｍ’１，ｍ’２，…，ｍ’ｔであるメンバの保持する分散情報である。
【００４４】
【数１７】
2004287333.tif 000013
【００４５】
【数１８】
2004287333.tif 000014
【００４６】
このランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法においては、もとの秘密情報Ｓ＝（Ｓ０，Ｓ１，…，ＳＬ−１）は、その分散情報Ｘｉ（ｉ＝１，２，…，ｎ）のＬ倍の情報量を持つことができる。すなわち、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法には、分散情報Ｘｉ（ｉ＝１，２，…，ｎ）の情報量を、もとの秘密情報Ｓの情報量の１／Ｌとすることができる性質がある。
【００４７】
≪第１の実施形態≫
［第１の実施形態の構成］
本発明の第１の実施形態においては、ｎ人のメンバ（ｎ個の分散計算装置としてもよい）が、それぞれ秘密情報を持ち、それらの秘密情報を引数とした関数ｆの計算結果を求めるため、分散計算を行う場合を説明する。ｎ人のメンバには、メンバを識別するための情報であるメンバＩＤとして、ｍ１，ｍ２，…，ｍｎが割り当てられている。メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）は、それぞれ有限体ＧＦ（ｑ）（ｑは、素数又は素数のべき乗）上の値である。
【００４８】
また、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバは、秘密情報Ｘｉ（ｉ＝１，２，…，ｎ）を持っているものとする。ここで、メンバが保持する秘密情報Ｘｉ（ｉ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）のＬ次拡大体ＧＦ（ｑＬ）上の値であり、有限体ＧＦ（ｑ）上の値Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１で表すことができる。有限体ＧＦ（ｑ）をＬ次拡大して拡大体ＧＦ（ｑＬ）を生成したときの生成多項式（既約多項式）をｇ（ｘ）とし、ｇ（ｘ）＝０の解の一つをαとすると、秘密情報Ｘｉは、次式（２５）で記述することができる。
Ｘｉ＝Ｘｉ，０＋Ｘｉ，１α＋…＋Ｘｉ，Ｌ−１αＬ−１    …（２５）
また、秘密情報Ｘｉは、ベクトル表現を用いて、次式（２６）のように記述することができる。
Ｘｉ＝（Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１）    …（２６）
【００４９】
図１は、第１の実施形態に係る分散計算方法を実施する構成（分散計算システム）を示すブロック図である。第１の実施形態においては、加算のみから構成されている関数を用いた分散計算を行う。図１に示されるように、第１の実施形態の分散計算方法（マルチパーティ・プロトコル）を実施する構成は、ｎ個（２≦ｎ）の分散処理部（分散計算装置）１０１−ｉ（ｉ＝１，２，…，ｎ）と、秘密再構成計算部１０２と、個々の分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）の秘密通信路１０３とを有する。各分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）は、メンバＩＤがｍｉであるメンバが担当する演算を実行する。ｎ個の分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）からの出力が、秘密再構成計算部１０２への入力となる。
【００５０】
分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）（分散処理部の全体を示す場合には、符号１０１を用いる。）は、各メンバが分散計算する部分である。分散処理部１０１は、図２に符号▲１▼で示される秘密情報の分散を行ったり、図２に符号▲３▼で示される分散計算を行う。各分散処理部１０１−ｉ（ｉ＝１、２，…，ｎ）は、他の分散処理部１０１−ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）と秘密通信路１０３で接続されている。この秘密通信路１０３は、通信している２人のメンバ以外には通信内容を秘密とすることができるような通信路である。また、各分散処理部１０１−ｉ（ｉ＝１、２，…，ｎ）からの出力は、秘密再構成計算部１０２へ入力される。
【００５１】
秘密再構成計算部１０２は、各メンバの分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）からの出力を受け取り、受け取ったｎ個の値を、ｎ個の分散情報としたときの秘密の再構成を行う計算をし、その再構成されたもとの秘密を出力する。秘密再構成計算部１０２に入力されるｎ個の分散情報は、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散されている情報である。
【００５２】
図３は、図１の秘密再構成計算部１０２の構成を示すブロック図である。図３に示されるように、秘密再構成計算部１０２は、線形結合部２０１を有する。線形結合部２０１は、秘密再構成計算部１０２への入力を受け取り、メンバＩＤ＿ｍｉから計算される係数を用いて、それらの入力の線形結合計算を行い、その計算結果を出力する。線形結合部２０１からの出力が、秘密再構成計算部１０２の出力となる。ここで、各メンバの分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）から出力される値（すなわち、秘密再構成計算部１０２へ入力される値）をＺ’ｉ（ｉ＝１，２，…，ｎ）とし、メンバＩＤ＿ｍｉから計算される係数をｒ０，ｉ，ｒ１，ｉ，…，ｒＬ−１，ｉ（ｉ＝１，２，…，ｎ）とする。このとき、秘密再構成計算部１０２は、次式（２７）及び（２８）の計算を行い、その結果Ｚ＝（Ｚ０，Ｚ１，…，ＺＬ−１）を出力する。
【００５３】
【数１９】
2004287333.tif 000015
【００５４】
【数２０】
2004287333.tif 000016
【００５５】
上記式（２７）及び（２８）における各演算は、有限体ＧＦ（ｑ）上で行う。なお、以降の説明においては、断りがない限り、演算は、有限体ＧＦ（ｑ）上で行うものとする。
【００５６】
各メンバの分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）における処理は、各メンバがそれぞれ他のメンバにはその処理の内容が分からないように行う。秘密再構成計算部１０２における処理は、処理を統合するセンター（すなわち、センターが管理する演算装置）のようなものが行ってもよいし、集まったメンバのうち、だれか１人、又は、複数人（すなわち、集まったメンバのいずれかが管理する演算装置）で行ってもよい。ただし、計算結果Ｚを必要としているメンバが行うのが望ましい。
【００５７】
図４は、図１の分散処理部１０１−ｉ（ｉ＝１，２，…，ｎ）の構成を示すブロック図である。図４に示されるように、分散処理部１０１−ｉは、秘密情報記憶部３０１−ｉと、秘密分散計算部３０２−ｉと、送信部３０３−ｉと、受信部３０４−ｉと、分散計算部３０５−ｉとを有する。秘密情報記憶部３０１−ｉからの出力が秘密分散計算部３０２−ｉへ入力され、秘密分散計算部３０２−ｉからの出力が送信部３０３−ｉ及び分散計算部３０５−ｉへ入力される。送信部３０３−ｉは、秘密通信路１０３へ情報を送信する。また、秘密通信路１０３から受け取る情報は、受信部３０４−ｉへ入力され、受信部３０４−ｉからの出力が分散計算部３０５−ｉへ入力される。分散計算部３０５−ｉからの出力が、分散処理部１０１−ｉの出力となる。
【００５８】
秘密情報記憶部３０１−ｉは、メンバＩＤがｍｉであるメンバが保持する秘密情報Ｘｉを保持しており、この秘密情報Ｘｉを秘密分散計算部３０２−ｉへ出力する。メンバが保持する秘密情報（すなわち、秘密情報記憶部３０１−ｉに保持されている秘密情報）Ｘｉは有限体ＧＦ（ｑ）のＬ次拡大体ＧＦ（ｑＬ）上の値であり、生成元α及び有限体ＧＦ（ｑ）上の値Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１を用いて、次式のように記述することができる。
Ｘｉ＝Ｘｉ，０＋Ｘｉ，１α＋…＋Ｘｉ，Ｌ−１αＬ−１
【００５９】
秘密分散計算部３０２−ｉへは、メンバＩＤがｍｉであるメンバが保持する秘密情報Ｘｉが入力される。秘密分散計算部３０２−ｉは、入力された秘密情報Ｘｉをランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法（Ｌ≦ｋ≦ｎ）を用いて分散し、送信部３０３−ｉ、及び、秘密通信路１０３を経由して他のメンバに配布する。メンバが保持する秘密情報Ｘｉは拡大体ＧＦ（ｑＬ）上の値である。秘密分散計算部３０２−ｉで生成される分散情報をＹｉ，ｐ（ｐ＝１，２，…，ｎ）とすると、自分自身に対する分散情報Ｙｉ，ｉは、分散計算部３０５−ｉへ出力され、その他の分散情報Ｙｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）は送信部３０３−ｉへ出力される。メンバが保持する秘密情報Ｘｉは拡大体ＧＦ（ｑＬ）上の値であり、その分散情報Ｙｉ，ｐは、その有限体ＧＦ（ｑ）上の値である。
【００６０】
送信部３０３−ｉは、秘密分散計算部３０２−ｉからの出力Ｙｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それを秘密通信路１０３を通して他の各メンバ（メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）であるメンバ）に送信する。なお、Ｙｉ，ｐは、メンバＩＤがｍｉであるメンバからメンバＩＤがｍｐであるメンバに送信される分散情報である。
【００６１】
受信部３０４−ｉは、他の各メンバの送信部３０３−ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）から送信される情報Ｙｐ，ｉ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それを分散計算部３０５−ｉへ出力する。なお、Ｙｐ，ｉは、メンバＩＤがｍｐであるメンバからメンバＩＤがｍｉであるメンバに送信される分散情報である。
【００６２】
分散計算部３０５−ｉは、秘密分散計算部３０２−ｉから、秘密情報Ｘｉの分散情報であるＹｉ，ｉを受け取る。さらに、受信部３０４−ｉから、他のメンバから配布された、秘密情報Ｘｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）の分散情報Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉ（分散情報Ｙｉ，ｉ以外のもの）を受け取る。分散計算部３０５−ｉは、受け取ったｎ個の分散情報Ｙｐ，ｉ（ｐ＝１，２，…，ｎ）を用いて分散計算を行い、求めるべき計算結果（最終の計算結果）Ｚの分散情報（中間の計算結果）Ｚ’ｉを出力する。
【００６３】
分散計算部３０５−ｉは、関数Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）に従った演算をするために、一つ若しくは複数の分散加算部を有する。例えば、
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝Ｘ１＋Ｘ２＋…＋Ｘｎ
（すなわち、秘密情報の総和）を計算させようとする場合には、分散計算部３０５−ｉは、図６に示されるような構成（ｎ−１個の分散加算部５０１−１，５０１−２，…，５０１−（ｎ−１）からなる）になる。また、
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ＸＭ＋ＸＮ
（すなわち、ある特定の秘密情報の和）を計算させようとする場合には、分散計算部３０５−ｉは、図７に示されるような構成（１個の分散加算部６０１からなる）になる。
【００６４】
図５は、第１の実施形態における秘密分散計算部３０２−ｉ（ｉ＝１，２，…，ｎ）の構成を示すブロック図である。図５に示されるように、秘密分散計算部３０２−ｉは、多項式生成部４０１−ｉと、分散情報生成部４０２−ｉとを有する。また、多項式生成部４０１−ｉは、乱数生成部４０３−ｉと、（ｋ−１）次多項式生成部４０４−ｉとを有する。秘密分散計算部３０２−ｉへの入力は、多項式生成部４０１−ｉへ入力され、多項式生成部４０１−ｉからの出力が、分散情報生成部４０２−ｉへ入力される。分散情報生成部４０２−ｉからの出力が、秘密分散計算部３０２−ｉからの出力となる。また、多項式生成部４０１−ｉへの入力は、（ｋ−１）次多項式生成部４０４−ｉへ入力され、乱数生成部４０３−ｉからの出力も（ｋ−１）次多項式生成部４０４−ｉへ入力される。（ｋ−１）次多項式生成部４０４−ｉからの出力が、多項式生成部４０１−ｉからの出力となる。
【００６５】
多項式生成部４０１−ｉは、Ｌ個の有限体ＧＦ（ｑ）上の値Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１を受け取り、それらの値から、次式（２９）を満たすｋ−１次多項式ｈＸｉ（ｘ）を生成し、その生成した多項式ｈＸｉ（ｘ）を表現する情報を出力する。
ｈＸｉ（Ｉ０）＝Ｘｉ，０
ｈＸｉ（Ｉ１）＝Ｘｉ，１
…
ｈＸｉ（ＩＬ−１）＝Ｘｉ，Ｌ−１    …（２９）
ただし、Ｉ０，Ｉ１，…，ＩＬ−１は、メンバＩＤと重複しない値で、予め決められている有限体ＧＦ（ｑ）上の値とする。
【００６６】
分散情報生成部４０２−ｉは、多項式ｈＸｉ（ｘ）を受け取り、次式（３０）で示す有限体ＧＦ（ｑ）上のｎ個の値Ｙｉ，ｐ（ｐ＝１，２，…，ｎ）を生成して出力する。
Ｙｉ，ｐ＝ｈＸｉ（ｍｐ）    …（３０）
ここで、ｐ＝１，２，…，ｎであり、Ｙｉ，ｐは、メンバＩＤがｍｉであるメンバからメンバＩＤがｍｐであるメンバに対して配布される分散情報を示す。
【００６７】
乱数生成部４０３−ｉは、有限体ＧＦ（ｑ）上のｋ−Ｌ個の乱数ＲＸｉ，０，ＲＸｉ，１，…，ＲＸｉ，ｋ−Ｌ−１を生成して出力する。
【００６８】
（ｋ−１）次多項式生成部４０４−ｉは、秘密分散計算部３０２−ｉへの入力であるメンバが保持する秘密情報Ｘｉ、及び、乱数生成部４０３−ｉからの乱数ＲＸｉ，０，ＲＸｉ，１，…，ＲＸｉ，ｋ−Ｌ−１を受け取り、次式（３１）及び（３２）で示されるようなｋ−１次多項式ｈＸ（ｘ）を生成し、その生成した多項式ｈＸ（ｘ）を表現する情報を出力する。
【００６９】
【数２１】
2004287333.tif 000017
【００７０】
なお、メンバが保持する秘密情報Ｘｉは拡大体ＧＦ（ｑＬ）上の値であり、前述したように、生成元α及び有限体ＧＦ（ｑ）上の値Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１を用いて
Ｘｉ＝Ｘｉ，０＋Ｘｉ，１α＋…＋Ｘｉ，Ｌ−１αＬ−１
の形で記述することができる。また、上記式（３１）及び（３２）は、メンバＩＤがｍｉであるメンバの（ｋ−１）次多項式生成部４０４−ｉが生成する多項式ｈＸ（ｘ）である。
【００７１】
図８は、図６又は図７の分散加算部５０１又は６０１の構成を示すブロック図である。図８を用いて、分散計算部３０５−ｉの構成要素となる、分散加算部５０１又は６０１の構成を説明する。図８に示されるように、分散加算部５０１又は６０１は、加算部７０１を有する。加算部７０１は、２つの入力（有限体ＧＦ（ｑ）上の値）を受け取り、それらの有限体ＧＦ（ｑ）上の加算をした値を出力する。入力値をａ及びｂとすると、その出力ｃは、次式（３３）のようになる。
ｃ＝ａ＋ｂ    …（３３）
上記式（３３）は、有限体ＧＦ（ｑ）上の演算（加算）である。
【００７２】
分散情報ａ及びｂは、それぞれ、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成式（上記式（２７）及び（２８））を行うと、拡大体ＧＦ（ｑＬ）上の値
Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）
Ｂ＝（Ｂ０，Ｂ１，…，ＢＬ−１）
になる。ここで、Ａ０，Ａ１，…，ＡＬ−１，Ｂ０，Ｂ１，…，ＢＬ−１はそれぞれ、有限体ＧＦ（ｑ）上の値である。分散加算部５０１又は６０１から出力される分散情報ｃは、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行うと、
Ｃ＝Ａ＋Ｂ    …（３４）
となる拡大体ＧＦ（ｑＬ）上の値Ｃ＝（Ｃ０，Ｃ１，…，ＣＬ−１）となる。ここで、Ｃ０，Ｃ１，…，ＣＬ−１はそれぞれ、有限体ＧＦ（ｑ）上の値である。上記式（３４）は、拡大体ＧＦ（ｑＬ）上の演算（加算）である。
【００７３】
［第１の実施形態の動作］
図９は、第１の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。分散計算を行うための各メンバはｎ人であり、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバは、秘密情報Ｘｉを持っている。メンバＩＤ＿ｍｉは有限体ＧＦ（ｑ）上の値であり、秘密情報Ｘｉは拡大体ＧＦ（ｑＬ）上の値である。また、メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）は、メンバ全員に公開されている。分散計算に用いる有限体ＧＦ（ｑ）、ランプ型秘密分散法のパラメータＬ、有限体ＧＦ（ｑ）から拡大体ＧＦ（ｑＬ）へ拡大するのに用いる既約多項式ｇ（ｘ）、その生成元α、及び、分散計算させたい関数ｆ（Ｘ１，Ｘ２，…，Ｘｎ）は、予め決められているものとする。関数ｆ（Ｘ１，Ｘ２，…，Ｘｎ）は、拡大体ＧＦ（ｑＬ）上の演算で、第１の実施形態においては、拡大体ＧＦ（ｑＬ）上の加算（例えば、ＸＡ＋ＸＢ）のみで構成されているものとする。
【００７４】
図９に示されるように、まず、各メンバが保持する秘密情報を、ランプ型（Ｌ，ｋ，ｈ）秘密分散法を用いて分散し、他のメンバに配布する（ステップＳ８０１）。ステップＳ８０１は、図４の秘密分散計算部３０２−ｉにおける動作を示しており、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバの保持する秘密情報Ｘｉから、上記式（３０）を用いて、分散情報Ｙｉ，ｐ（ｐ＝１，２，…，ｎ）を計算し、メンバＩＤがｍｐであるメンバに対して配布する。
【００７５】
次に、各メンバは、自分自身の秘密情報の分散情報、及び、他のメンバから配布された分散情報を用いて、関数ｆの分散計算を行う（ステップＳ８０２）。ステップＳ８０２は、図４の分散計算部３０５−ｉにおける動作を示しており、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、関数ｆ（Ｘ１，Ｘ２，…，Ｘｎ）で指示される通りの分散計算を行う。例えば、
ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ＸＡ＋ＸＢ
である場合には、メンバＩＤがｍｉであるメンバは、配布された結果自分が保持する分散情報ＹＡ，ｉ及びＹＢ，ｉから、次の分散加算計算
Ｚ’ｉ＝ＹＡ，ｉ＋ＹＢ，ｉ
を実行する。この分散加算計算の計算結果（中間の計算結果）Ｚ’ｉは、拡大体ＧＦ（ｑＬ）上の計算結果（最終の計算結果）Ｚ（ここで、Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ＸＡ＋ＸＢである。）の分散情報（すなわち、ランプ型（Ｌ，ｋ，ｎ）秘密分散法で分散された分散情報）となっている。
【００７６】
次の、ステップＳ８０３において、各メンバが計算した計算結果Ｚ’ｉから、関数ｆの計算結果Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）を、ランプ型（Ｌ，ｋ，ｎ）秘密分散法に基づいて秘密再構成する。ステップＳ８０３は、図１の秘密再構成計算部１０２における動作を示しており、メンバＩＤがｍｉであるメンバがステップＳ８０２で計算した結果Ｚ’ｉ（ｉ＝１，２，…，ｎ）から、上記式（２７）を用いて計算し、関数ｆの計算結果Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）を得ることができる。
【００７７】
図１０は、分散加算における動作を示すフローチャートである。例えば、拡大体ＧＦ（ｑＬ）上の値Ａ及びＢの加算を行う場合を考える。図１０に示されるように、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、自身が保持する情報Ａ及びＢの分散情報ａｉ及びｂｉより、その和ｃｉ＝ａｉ＋ｂｉを計算して出力する（ステップＳ９０１）。
【００７８】
［第１の実施形態の効果］
以上に説明したように、第１の実施形態によれば、関数ｆ（ただし、関数ｆは、加算のみの関数）に対するマルチパーティ・プロトコル（各メンバの保持する秘密情報を公開しないまま、各メンバが分散計算を行うことにより、関数ｆの計算結果を得るプロトコル）において、関数ｆにおける拡大体ＧＦ（ｑＬ）上の計算を、各メンバの分散演算処理においては、その拡大体よりも小さな有限体ＧＦ（ｑ）上の計算のみを行うことで、達成することができる。このため、メンバそれぞれの分散演算処理における、演算量、演算回路に必要な回路規模、演算に必要な記憶容量、演算時間等の演算コストを削減することができる。
【００７９】
≪第２の実施形態≫
第１の実施形態においては、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いた、マルチパーティ・プロトコルによる分散計算の、分散加算方法について説明したが、第２の実施形態においては、マルチパーティ・プロトコルによる分散計算の、分散定数乗算方法を説明する。第１の実施形態と同様に、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いていることから、従来のマルチパーティ・プロトコルによる分散計算と比較すると、各メンバに必要な演算は、もとの秘密情報の有限体の大きさよりも小さい有限体上で行うことができ、演算コストを下げることができる。
【００８０】
［第２の実施形態の構成］
第１の実施形態と同様に、第２の実施形態においては、ｎ人のメンバ（ｎ個の分散計算装置でもよい）が、それぞれ秘密情報を持ち、それらの秘密情報を引数とした関数ｆの計算結果を求めるため、分散計算を行う場合を説明する。ｎ人のメンバには、メンバＩＤとして、ｍ１，ｍ２，…，ｍｎが割り当てられている。メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）は、それぞれ有限体ＧＦ（ｑ）（ｑは素数又は素数のべき乗）上の値である。
【００８１】
また、メンバＩＤがｍｉであるメンバは、秘密情報Ｘｉを持っているものとする。ここで、メンバが保持する秘密情報Ｘｉ（ｉ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）のＬ次拡大体ＧＦ（ｑＬ）上の値であり、有限体ＧＦ（ｑ）上の値Ｘｉ，０，Ｘｉ，１，…、Ｘｉ，Ｌ−１で表すことができる。有限体ＧＦ（ｑ）をＬ次拡大して拡大体ＧＦ（ｑＬ）を生成したときの生成多項式（既約多項式）をｇ（ｘ）とし、生成元をαとする。
【００８２】
第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）は、第１の実施形態のものと同様に、図１のようになる。第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）が第１の実施形態のものと異なる点は、分散処理部１０１−ｉの構成及び動作である。
【００８３】
図１１は、第２の実施形態における分散処理部（分散計算装置）１０１−ｉ（ｉ＝１，２，…，ｎ）の構成を示すブロック図である。図１１に示されるように、第２の実施形態における分散処理部１０１−ｉは、秘密情報記憶部１００１−ｉと、秘密分散計算部１００２−ｉと、送信部１００３−ｉと、受信部１００４−ｉと、分散計算部１００５−ｉとを有する。秘密情報記憶部１００１−ｉからの出力が秘密分散計算部１００２−ｉへ入力され、秘密分散計算部１００２−ｉからの出力が送信部１００３−ｉ及び分散計算部１００５−ｉへ入力される。送信部１００３−ｉは、秘密通信路１０３へ情報を送信する。また、秘密通信路１０３から受け取る情報は、受信部１００４−ｉへ入力され、受信部１００４−ｉからの出力が分散計算部１００５−ｉへ入力される。分散計算部１００５−ｉからの出力が、第２の実施形態における分散処理部１０１−ｉの出力となる。
【００８４】
第２の実施形態における秘密情報記憶部１００１−ｉ、秘密分散計算部１００２−ｉ、送信部１００３−ｉ、及び受信部１００４−ｉは、第１の実施形態における秘密情報記憶部３０１−ｉ、秘密分散計算部３０２−ｉ、送信部３０３−ｉ、及び受信部３０４−ｉと、構成及び動作が同じである。しかし、第２の実施形態における分散計算部１００５−ｉは、第１の実施形態における分散計算部３０５−ｉと、構成及び動作が異なる。
【００８５】
第２の実施形態における分散計算部１００５−ｉは、分散加算に加えて、分散定数乗算を行うので、秘密通信路１０３を介して他のメンバの分散処理部１０１−ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）との通信を行う手段を有している。分散計算部１００５−ｉは、秘密分散計算部１００２−ｉから、秘密情報Ｘｉの分散情報Ｙｉ，ｉを受け取る。さらに、受信部１００４−ｉから、他のメンバから配布された、秘密情報Ｘｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）の分散情報Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉを受け取る。これらｎ個の分散情報Ｙｐ，ｉ（ｐ＝１，２，…ｎ）を用いて分散計算を行い、計算結果（最終の計算結果）Ｚの分散情報（中間の計算結果）Ｚ’ｉを出力する。分散計算部１００５−ｉは、関数Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）に従って、一つ若しくは複数の分散定数乗算部と０以上若しくは複数の分散加算部とを有する。例えば、
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ｔ１Ｘ１＋ｔ２Ｘ２＋…＋ｔｎＸｎ
（秘密情報の線形結合計算）を計算させようとする場合には、分散計算部１００５−ｉは、図１２に示されるような構成（ｎ個の分散定数乗算部１１０１（１１０１−１，１１０１−２，…，１１０１−ｎ）と、ｎ−１個の分散加算部１１０２（１１０２−１，１１０２−２，…，１１０２−（ｎ−１））からなる）になる。
【００８６】
図１３は、図１２の分散定数乗算部１１０１の構成を示すブロック図である。図１３を用いて、分散計算部１００５−ｉの構成要素となる、分散定数乗算部１１０１の構成を説明する。図１３に示されるように、分散定数乗算部１１０１は、拡大体乗算部１２０１と、秘密分散計算部１２０２と、送信部１２０３と、受信部１２０４と、加算部１２０５とを有する。拡大体乗算部１２０１は、分散定数乗算部１１０１への入力を受け取る。拡大体乗算部１２０１からの出力は秘密分散計算部１２０２へ入力され、秘密分散計算部１２０２からの出力が送信部１２０３及び加算部１２０５へ入力される。送信部１２０３は、秘密通信路１０３へ情報を送信する。また、秘密通信路１０３から受け取る情報は、受信部１２０４へ入力され、受信部１２０４からの出力が加算部１２０５へ入力される。加算部１２０５からの出力が、分散定数乗算部１１０１の出力となる。
【００８７】
分散定数乗算部１１０１は、２つの入力（有限体ＧＦ（ｑ）上の値及び拡大体ＧＦ（ｑＬ）上の定数）を受け取る。ここで、拡大体ＧＦ（ｑＬ）上の値
Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）
及び、拡大体ＧＦ（ｑＬ）上の定数
Ｄ＝（Ｄ０，Ｄ１，…，ＤＬ−１）
の乗算Ｃ＝Ｄ×Ａを分散計算する場合を考える。ここで、Ａ０，Ａ１，…，ＡＬ−１，Ｄ０，Ｄ１，…，ＤＬ−１はそれぞれ、有限体ＧＦ（ｑ）上の値である。このとき、分散定数乗算部１１０１への入力は、値Ａの（メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバの保持する）分散情報ａｉ及び拡大体ＧＦ（ｑＬ）上の定数Ｄである。以降、分散定数乗算部１１０１は、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバの分散計算部１００５−ｉに含まれているものとして説明する。
【００８８】
拡大体乗算部１２０１は、分散定数乗算部１１０１への入力である、分散情報ａｉ及び拡大体ＧＦ（ｑＬ）上の定数Ｄ＝（Ｄ０，Ｄ１，…，ＤＬ−１）を受け取り、まず、次式（３５）で示される２Ｌ−１個の値Ｅ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を計算する。
【００８９】
【数２２】
2004287333.tif 000018
ここで、ｒｊ，ｉ（ｊ＝０，１，…，Ｌ−１）は、上記式（２８）で表される、メンバＩＤから計算される係数である。
【００９０】
一方、拡大体ＧＦ（ｑＬ）上における乗算を可能とするために、下記の式（３７）で示す有限体ＧＦ（ｑ）上の値ｇｊ，ｈ（ｊ＝０，１，…，Ｌ−１；  ｈ＝０，１，…，Ｌ−１）は、拡大体演算用に予め計算し保持しておくようにしておく。拡大体ＧＦ（ｑＬ）を生成するときの生成多項式ｇ（ｘ）を下記の式（３６）で示す。
【００９１】
【数２３】
2004287333.tif 000019
【００９２】
【数２４】
2004287333.tif 000020
【００９３】
これら保持しておいたｇｊ，ｈ（ｊ＝０，１，…，Ｌ−１；  ｈ＝０，１，…，Ｌ−１）、はじめに計算した上記式（３５）のＥ’ｉ，ｈ（ｈ＝０，１，…，Ｌ−１）、及び、上記式（２８）で表されるメンバＩＤから計算される係数ｒｊ，ｉ（ｊ＝０，１，…，Ｌ−１）を用いて、次式（３８）を計算する。
【００９４】
【数２５】
2004287333.tif 000021
【００９５】
ここで、Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）は、拡大体乗算部１２０１からの出力である。拡大体乗算部１２０１からの出力Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）は、秘密分散計算部１２０２へ入力される。
【００９６】
例えば、Ｌ＝２、ｇ（ｘ）＝ｘ２＋ｘ＋１の場合には、上記式（３７）から、ｇｊ，ｈ（ｊ＝０，１，…，Ｌ−１；  ｈ＝０，１，…，Ｌ−１）は、
ｇ０，０＝１
ｇ０，１＝１
ｇ１，０＝−１
ｇ１，１＝−１    …（３９）
となり、拡大体乗算部１００１（メンバＩＤがｍｉであるメンバのもの）は、下記の式（４０）によりＥｉ＝（Ｅｉ，０，Ｅｉ，１）を計算し、出力する。
【００９７】
【数２６】
2004287333.tif 000022
【００９８】
秘密分散計算部１２０２は、拡大体乗算部１２０１からの出力Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を受け取る。この拡大体乗算部１２０１からの出力Ｅｉは、拡大体ＧＦ（ｑＬ）上の値である。秘密分散計算部１２０２は、受け取った値Ｅｉを、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法（ｋ≦ｎ）を用いて分散し、送信部１２０３、及び、秘密通信路１０３を経由して他のメンバに配布する。秘密分散計算部１２０２は、図５に示される秘密分散計算部３０２−ｉと同様な構成をしており、入力される値が秘密情報Ｘｉ＝（Ｘｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１）に代えて、値Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）が入力される。このとき、（ｋ−１）次多項式生成部４０４−ｉで生成される多項式は、次式（４１）になる。
【００９９】
【数２７】
2004287333.tif 000023
【０１００】
ここで、Ｈｊ（ｘ）は上記式（３２）のものである。同様に、分散情報生成部４０２−ｉで生成される、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎ）であるメンバに対して配布する分散情報Ｆｉ，ｐは、上記式（４１）を用いて、次式（４２）で算出する。
Ｆｉ，ｐ＝ｈＥｉ（ｍｐ）    …（４２）
分散情報Ｆｉ，ｐは、その有限体ＧＦ（ｑ）上の値である。
【０１０１】
自分自身に対する分散情報Ｆｉ，ｉは、加算部１２０５へ出力し、その他の分散情報Ｆｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を送信部１２０３及び秘密通信路１０３を経由して各メンバに配布する。
【０１０２】
送信部１２０３は、秘密分散計算部１２０２からの出力Ｆｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それを秘密通信路１０３を通して他の各メンバに送信する。
【０１０３】
受信部１２０４は、他の各メンバ（メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）であるメンバ）の送信部１２０３から送信される情報Ｆｐ，ｉ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それを加算部１２０５へ出力する。
【０１０４】
送信部１２０３及び受信部１２０４は、他のメンバの分散処理部１０１−ｐとの送受信する機能を持っており、分散処理部１０１−ｉにおける送信部１００３−ｉ及び受信部１００４−ｉと共通化した構成にしてもよい。
【０１０５】
加算部１２０５は、秘密分散計算部１２０２からの出力Ｆｉ，ｉを受け取る。さらに、加算部１２０５は、受信部１２０４から、他のメンバの秘密分散計算部１２０２からの出力Ｆ１，ｉ，Ｆ２，ｉ，…，Ｆｎ，ｉを受け取る。これらｎ個の分散情報Ｆｐ，ｉ（ｐ＝１，２，…，ｎ）を、次式（４３）のようにすべて加算（有限体ＧＦ（ｑ）上の加算）し、その計算結果ｃｉを出力する。
ｃｉ＝Ｆ１，ｉ＋Ｆ２，ｉ＋…＋Ｆｎ，ｉ    …（４３）
【０１０６】
この加算部１２０５からの出力ｃｉが、分散定数乗算部１１０１の出力となる。分散定数乗算部１１０１への入力を分散情報ａｉ（ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行うと、拡大体ＧＦ（ｑＬ）上の値Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）になる）、及び、定数Ｄ＝（Ｄ０，Ｄ１，…，ＤＬ−１）とすると、そのとき分散定数乗算部１１０１から出力される分散情報ｃｉは、メンバでランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成行うと、
Ｃ＝Ｄ×Ａ    …（４４）
となる拡大体ＧＦ（ｑＬ）上の値Ｃ＝（Ｃ０，Ｃ１，…，ＣＬ−１）となる。ここで、Ｃ０，Ｃ１，…，ＣＬ−１は、有限体ＧＦ（ｑ）上の値である。また、上記式（４４）は、拡大体ＧＦ（ｑＬ）上の演算（乗算）である。
【０１０７】
［第２の実施形態の動作］
図１４は、第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。図１４に示されるように、第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作は、上記した第１の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作と類似している。しかし、第１の実施形態のステップＳ８０２（図９）において分散加算のみしか行わなかったが、第２の実施形態のステップＳ１３０２（図１４）おいては、分散定数乗算をも行う点が相違する。
【０１０８】
図１４を用いて、第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を説明する。なお、第１の実施形態と異なるステップＳ１３０２のみを説明する。図１４に示されるように、ステップＳ１３０２においては、各メンバは、自分自身の秘密情報の分散情報、及び、他のメンバから配布された分散情報を用いて、関数ｆの分散計算を行う。ステップＳ１３０２は、図１１の分散計算部１００５−ｉにおける動作を示しており、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、関数ｆ（Ｘ１，Ｘ２，…，Ｘｎ）で指示される通りの分散計算を行う。この関数ｆは、第１の実施形態においては、加算のみしか扱わなかったが、第２の実施形態においては、定数乗算も扱う。例えば、ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ｔＡＸＡ＋ｔＢＸＢ
（ｔＡ，ｔＢは、拡大体ＧＦ（ｑＬ）上の定数）である場合には、メンバＩＤがｍｉであるメンバは、配布された結果自分が保持する分散情報ＹＡ，ｉ及びＹＢ，ｉから、ｔＡ及びＹＡ，ｉを入力とする分散定数乗算計算（分散定数乗算部１１０１の動作）、及び、ｔＢ及びＹＢ，ｉを入力とする分散定数乗算計算（分散定数乗算部１１０１の動作）を行って、その２つの出力の加算を行って計算結果（中間の計算結果）Ｚ’ｉを求める。その計算結果Ｚ’ｉは、拡大体ＧＦ（ｑＬ）上の計算結果（最終の計算結果）
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ｔＡＸＡ＋ｔＢＸＢ
の分散情報（すなわち、ランプ型（Ｌ，ｋ，ｎ）秘密分散法で分散された分散情報）となっている。
【０１０９】
図１５は、第２の実施形態における分散定数乗算の動作を示すフローチャートである。例えば、拡大体ＧＦ（ｑＬ）上の値Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）、及び、定数Ｄ＝（Ｄ０，Ｄ１，…，ＤＬ−１）の乗算を行う場合を考える。
【０１１０】
まず、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、自身が保持する情報Ａの分散情報ａｉ、及び、定数Ｄより、上記式（３８）を用いて、Ｅｉ＝（Ｅｉ，０、Ｅｉ，１，…，Ｅｉ，Ｌ−１）を求める（ステップＳ１４０１）。ステップＳ１４０１は、図１３の拡大体乗算部１２０１における動作を表している。
【０１１１】
次に、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、ステップＳ１４０１で計算した値Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）をランプ型（Ｌ，ｋ，ｎ）秘密分散法を用いて分散情報Ｆｉ，ｐ（ｐ＝１，２，…，ｎ）を作り、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）である他のメンバに分散情報Ｆｉ，ｐを配布する（ステップＳ１４０２）。ステップＳ１４０２は、図１３の秘密分散計算部１２０２及び送信部１２０３における動作を示している。
【０１１２】
次に、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、ステップＳ１４０２の動作により受け取った分散情報Ｆｐ，ｉ（ｐ＝１，２，…，ｎ）をすべて加算し（上記式（４３））、値ｃｉを求めて出力する（ステップＳ１４０３）。ステップＳ１４０３は、図１３の受信部１２０４及び加算部１２０５における動作を示している。
【０１１３】
［第２の実施形態の効果］
以上に説明したように、第２の実施形態によれば、第１の実施形態と同様に、関数ｆ（ただし、関数ｆは、加算及び定数乗算のみからなる関数）に対するマルチパーティ・プロトコル（各メンバの保持する秘密情報を公開しないまま、各メンバが分散計算を行うことにより、関数ｆの計算結果を得るプロトコル）において、関数ｆにおける拡大体ＧＦ（ｑＬ）上の計算を、各メンバの分散演算処理においては、その拡大体よりも小さな有限体ＧＦ（ｑ）上の計算のみを行うことで、達成することができる。このため、メンバそれぞれの分散演算処理における、演算量、演算回路に必要な回路規模、演算に必要な記憶容量、演算時間等の演算コストを削減することができる。
【０１１４】
また、第１の実施形態とは異なり、第２の実施形態においては、分散加算計算だけでなく、分散定数乗算計算も可能となる。
【０１１５】
≪第３の実施形態≫
第１の実施形態においては、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いた、マルチパーティ・プロトコルによる分散計算の、分散加算方法についてついて説明したが、第３の実施形態においては、マルチパーティ・プロトコルによる分散計算の、分散乗算方法を説明する。第１及び第２の実施形態と同様に、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法を用いていることから、従来のマルチパーティ・プロトコルによる分散計算と比較すると、各メンバに必要な演算は、もとの秘密情報の有限体の大きさよりも小さい有限体上で行うことができ、演算コストを下げることができる。
【０１１６】
［第３の実施形態の構成］
第１及び第２の実施形態と同様に、第３の実施形態においては、ｎ人のメンバ（ｎ個の分散計算装置でもよい）が、それぞれ秘密情報を持ち、それらの秘密情報を引数とした関数ｆの計算結果を求めるため、分散計算を行う場合を説明する。ｎ人のメンバには、メンバＩＤとして、ｍ１，ｍ２，…，ｍｎが割り当てられている。メンバＩＤ＿ｍｉ（ｉ＝１，２，…，ｎ）は、それぞれ有限体ＧＦ（ｑ）（ｑは、素数又は素数のべき乗）上の値である。
【０１１７】
また、メンバＩＤがｍｉであるメンバは、秘密情報Ｘｉを持っているものとする。ここで、メンバが保持する秘密情報Ｘｉ（ｉ＝１，２，…，ｎ）は、有限体ＧＦ（ｑ）のＬ次拡大体ＧＦ（ｑＬ）上の値であり、有限体ＧＦ（ｑ）上の値であるＸｉ，０，Ｘｉ，１，…，Ｘｉ，Ｌ−１で表すことができる。有限体ＧＦ（ｑ）をＬ次拡大して拡大体ＧＦ（ｑＬ）を生成したときの生成多項式（既約多項式）をｇ（ｘ）とし、生成元をαとする。
【０１１８】
第３の実施形態に係る分散計算方法を実施する構成（分散計算システム）は、第１及び第２の実施形態のものと同様に、図１のようになる。第３の実施形態に係る分散計算方法を実施する構成（分散計算システム）が第１の実施形態のものと異なる点は、分散処理部１０１−ｉの構成及び動作である。
【０１１９】
第３の実施形態における分散処理部（分散計算装置）１０１−ｉ（ｉ＝１，２，…，ｎ）の構成は、第２の実施形態のものと同様に図１１のようになる。第３の実施形態における分散処理部１０１−ｉが、第２の実施形態のものと異なる点は、分散計算部１００５−ｉの構成及び動作である。
【０１２０】
第３の実施形態における分散計算部１００５−ｉは、分散加算（第１の実施形態）及び分散定数乗算（第２の実施形態）に加えて、分散乗算を行うので、第２の実施形態のものと同様に、秘密通信路１０３を介して他のメンバの分散処理部１０１−ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）との通信を行う手段を有している。分散計算部１００５−ｉは、秘密分散計算部１００２−ｉから、秘密情報Ｘｉの分散情報Ｙｉ，ｉを受け取る。さらに、受信部１００４−ｉから、他のメンバから配布された、秘密情報Ｘｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）の分散情報Ｙ１，ｉ，Ｙ２，ｉ，…，Ｙｎ，ｉを受け取る。これらｎ個の分散情報Ｙｐ，ｉ（ｐ＝１，２，…，ｎ）を用いて、分散計算を行い、計算結果（最終の計算結果）Ｚの分散情報（中間の計算結果）Ｚ’ｉを出力する。分散計算部１００５−ｉは、関数Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）に従って、一つ若しくは複数の分散乗算部、０以上若しくは複数の分散加算部、及び、０以上若しくは複数の分散定数乗算部からなる。例えば、
Ｚ＝ｆ（Ｘ１、Ｘ２，…，Ｘｎ）
＝（ｔ１Ｘ１＋ｔ２Ｘ２＋…＋ｔｎＸｎ）×ＸＭ
（秘密情報の線形結合計算とメンバＩＤがｍＭであるメンバの保持する秘密情報との乗算）を計算させようとする場合には、分散計算部１００５−ｉは、図１６のような構成（ｎ個の分散定数乗算部１５０１、ｎ−１個の分散加算部１５０２、１個の分散乗算部１５０３からなる）になる。また、
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝ＸＭ×ＸＮ
（メンバＩＤがｍＭ、ｍＮであるメンバの保持する秘密情報同士の乗算）を計算させようとする場合には、分散計算部１００５−ｉは、図１７のような構成（１個の分散乗算部１６０１からなる）になる。
【０１２１】
図１８は、図１６の分散乗算部１５０３又は図１７の分散乗算部１６０１の構成を示すブロック図である。図１８を用いて、第３の実施形態における分散計算部１００５−ｉの構成要素となる、分散乗算部１５０３，１６０１の構成を説明する。図１８に示されるように、分散乗算部１５０３，１６０１は、乗算部１７０１と、紛失通信計算部１７０２と、分散情報計算部１７０３と、秘密分散計算部１７０４と、送信部１７０５と、受信部１７０６と、加算部１７０７とを有する。分散乗算部１５０３，１６０１への入力は、乗算部１７０１、及び、紛失通信計算部１７０２へ入力される。乗算部１７０１は、分散乗算部１５０３，１６０１への入力を受け取り、分散情報計算部１７０３へ出力する。また、紛失通信計算部１７０２は、分散乗算部１５０３，１６０１への入力を受け取り、分散情報計算部１７０３へ出力する。分散情報計算部１７０３は、乗算部１７０１、及び、紛失通信計算部１７０２からの出力を受け取り、分散情報計算部１７０３からの出力が秘密分散計算部１７０４へ入力される。秘密分散計算部１７０４からの出力は送信部１７０５及び加算部１７０７へ入力される。送信部１７０５は、秘密通信路１０３へ情報を送信する。また、秘密通信路１０３から受け取る情報は、受信部１７０６へ入力され、受信部１７０６からの出力が加算部１７０７へ入力される。加算部１７０７からの出力が、分散乗算部１５０３，１６０１の出力となる。
【０１２２】
分散乗算部１５０３，１６０１は、２つの入力（有限体ＧＦ（ｑ）上の値）を受け取る。拡大体ＧＦ（ｑＬ）上の値Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）、及び、Ｂ＝（Ｂ０，Ｂ１，…，ＢＬ−１）の乗算Ｃ＝Ａ×Ｂを分散計算しようとする場合を考える。ここで、Ａ０，Ａ１，…，ＡＬ−１，Ｂ０，Ｂ１，…，ＢＬ−１は、有限体ＧＦ（ｑ）上の値である。このとき、分散乗算部１５０３，１６０１への入力は、値Ａ及びＢの（メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバの保持する）分散情報ａｉ及びｂｉである。分散情報ａｉ及びｂｉは、有限体ＧＦ（ｑ）上の値である。以降、分散乗算部１５０３，１６０１は、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバの分散計算部１００５−ｉに含まれるものとして説明する。乗算部１７０１は、分散乗算部１５０３，１６０１への入力である分散情報ａｉ及びｂｉを受け取り、それらの乗算ｃ’ｉ＝ａｉ×ｂｉ（有限体ＧＦ（ｑ）上の乗算）を行い、乗算結果ｃ’ｉを、分散情報計算部１７０３へ出力する。
【０１２３】
紛失通信計算部１７０２は、分散乗算部１５０３，１６０１への入力ａｉ及びｂｉを受け取り、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）である他のメンバの紛失通信計算部１７０２への入力値との乗算、すなわち、ａｉ×ｂｐ及びａｐ×ｂｉの結果に相当するもの（乗算結果そのものではない）が得られるように通信及び計算処理をする。すなわち、
ａｉ×ｂｐ＝ｄｉ，ｐ，＋ｄｐ，ｉ    …（４５）
ａｐ×ｂｉ＝ｅｉ，ｐ，＋ｅｐ，ｉ    …（４６）
となるような、ｄｉ，ｐ及びｅｉ，ｐをメンバＩＤがｍｉであるメンバが保持することができ、ｄｐ，ｉ及びｅｐ，ｉをメンバＩＤがｍｐであるメンバが、それぞれ保持することができるように、計算及び通信を行う。紛失通信計算部１７０２は、それぞれｎ−１個の値ｄｉ，ｐ（ｐ＝１，２，…ｎであり、ｐ≠ｉであるもの）及びｅｉ，ｐ（ｐ＝１，２，…ｎであり、ｐ≠ｉであるもの）を算出し、分散情報計算部１７０３へ出力する。
【０１２４】
分散情報計算部１７０３は、乗算部１７０１からの出力ｃ’ｉと、紛失通信計算部１７０２からの出力ｄｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）及びｅｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それらを用いて、まず、次式（４７）により、値Ｇｕ，ｖ（ｕ＝１，２，…，Ｌ−１；ｖ＝１，２，…，Ｌ−１）を計算する。
【０１２５】
【数２８】
2004287333.tif 000024
【０１２６】
ただし、上記式（４７）において、ｒｕ，ｉ（ｕ＝０，１，…，Ｌ−１）は、上記式（２８）で表される、メンバＩＤから計算される係数である。
【０１２７】
次に、次式（４８）のような２Ｌ−１個の値Ｅ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を計算する。
【数２９】
2004287333.tif 000025
【０１２８】
次に、次式（４９）により、分散情報計算部１７０３からの出力Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を計算する。
【数３０】
2004287333.tif 000026
【０１２９】
ただし、ｇｊ，ｈ（ｊ＝０，１，…，Ｌ−１；  ｈ＝０，１，…，Ｌ−１）は、上記式（３７）で表される、拡大体ＧＦ（ｑＬ）の生成多項式ｇ（ｘ）の係数から計算される値である。分散情報計算部１７０３からの出力Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）は、秘密分散計算部１７０４へ入力される。
【０１３０】
例えば、Ｌ＝２、ｇ（ｘ）＝ｘ２＋ｘ＋１の場合には、出力Ｅｉ＝（Ｅｉ，０，Ｅｉ，１）は、次式（５０）により、計算される。
【数３１】
2004287333.tif 000027
【０１３１】
第３の実施形態における秘密分散計算部１７０４、送信部１７０５、受信部１７０６、及び、加算部１７０７は、分散定数乗算部１１０１（第２の実施形態）の秘密分散計算部１２０２、送信部１２０３、受信部１２０４、及び、加算部１２０５とそれぞれ同様なものである。
【０１３２】
秘密分散計算部１７０４からの出力Ｆｉ，ｉ（秘密分散計算部１７０４へ入力されるＥｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）の自分自身への分散情報）は、加算部１７０７へ出力され、さらに、秘密分散計算部１７０４からの出力Ｆｉ，ｐ（秘密分散計算部１７０４へ入力されるＥ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）のメンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）であるメンバへの分散情報）は送信部１７０５へ出力される。
【０１３３】
送信部１７０５は、秘密分散計算部１７０４からの出力を秘密通信路１０３を通して他のメンバの受信部１７０６へ送信する。また、受信部１７０６は、他のメンバの送信部１７０５から出力Ｆｐ，ｉ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を秘密通信路１０３を通して受信し、その受信した値を加算部１７０７へ出力する。加算部１７０７は、秘密分散計算部１７０４からの出力Ｆｉ，ｉ、及び、受信部１７０６からの出力Ｆｐ，ｉ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を受け取り、それらの加算を行い、その計算結果ｃｉを出力する。加算部１７０７からの出力が、分散乗算部１５０３，１６０１からの出力となる。送信部１７０５及び受信部１７０６は、他のメンバの分散処理部１０１−ｐとの送受信する機能を持っており、分散処理部１０１−ｉにおける送信部１００３−ｉ及び受信部１００４−ｉと共通化した構成にしてもよい。
【０１３４】
図１９は、図１８の紛失通信計算部１７０２の構成を示すブロック図である。図１９を用いて、紛失通信計算部１７０２の構成を説明する。紛失通信計算部１７０２は、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）であるメンバの分散計算部１００５−ｉに含まれるものとして説明する。
【０１３５】
図１９に示されるように、紛失通信計算部１７０２は、ｉ−１個の通信計算受信部１８０１−ｐ（ｐ＝１，２，…，ｉ−１）と、ｉ−１個の通信計算受信部１８０２−ｐ（ｐ＝１，２，…，ｉ−１）、ｎ−ｉ個の通信計算送信部１８０３−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）と、ｎ−ｉ個の通信計算送信部１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）とを有する。紛失通信計算部１７０２へ入力される２つの入力のうち、一つは、通信算受信部１８０１−ｐ（ｐ＝１，２，…，ｉ−１）及び通信計算送信部１８０３−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）へ、他の一つは、通信計算受信部１８０２−ｐ（ｐ＝１，２，…，ｉ−１）及び通信算送信部１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）へ入力される。通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）、及び、通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）からの出力が、紛失通信計算部１７０２からの出力となる。通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）、及び通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）は、秘密通信路１０３を通して、他のメンバとの情報のやりとりを行うことにより、前述の通り、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）である他のメンバの値との乗算、すなわち、ａｉ×ｂｐ及びａｐ×ｂｉの結果に相当するもの（乗算結果そのものではない）が得られるようにするが、他のメンバの値ａｐ及びｂｐが分からないように、また、自分の値ａｉ及びｂｉが、他のメンバに分からないように、紛失通信というものを行う。前述した通り、紛失通信とは、送信側が、Ｍ個の情報を符号化（暗号化）して送信するが、受信側においては、そのうち一つしか受け取る（意味のあるように復号が可能となる）ことができず、また、送信側においては、受信側がどの情報を受け取った（意味のあるように復号が可能となった）かを知ることができない通信方法をいうことにする。この実施形態においては、法ｑのもとでの離散対数を計算することが困難であることを利用して、紛失通信を構成する。
【０１３６】
通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）、及び、通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）は、ｉの値によって、通信計算受信部又は通信計算送信部を持たなかったりする。例えば、ｉ＝１の場合には、通信計算受信部を持たず、２×（ｎ−１）個の通信計算送信部を持つ。また、ｉ＝ｎの場合には、通信計算送信部を持たず、２×（ｎ−１）個の通信計算受信部を持つことになる。また、他のメンバとの送受信の関係は、メンバＩＤがｍｉであるメンバの通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）からは、それぞれ、秘密通信路１０３を通して、メンバＩＤがｍｐであるメンバの通信計算受信部１８０１−ｉ，１８０２−ｉのそれぞれへ情報が渡される。図２０及び図２１で詳細を説明する。
【０１３７】
図２０は、図１９の通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）の構成を示すブロック図である。図２０を用いて、通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）の構成を説明する。図２０に示されるように、通信計算受信部１８０１−ｐ，１８０２−ｐ（ｐ＝１，２，…，ｉ−１）は、インデックス計算送信部１９０１と、受信復元部１９０２とを有する。通信計算受信部１８０１−ｐは、紛失通信計算部１７０２への２つの入力のうち一つの入力を受け取り、通信計算受信部１８０２−ｐは、他の一つの入力を受け取る。ここでは、通信計算受信部１８０１−ｐへの入力をａｉとし、通信計算受信部１８０２−ｐへの入力をｂｉとする。通信計算受信部１８０１−ｐと１８０２−ｐは、内部的に同じ構造なので、ここでは、通信計算受信部１８０１−ｐについて説明し、通信算受信部１８０２−ｐに相当する説明は、括弧〔  〕内に記述する。通信計算受信部１８０１−ｐ  〔１８０２−ｐ〕  への入力は、インデックス計算送信部１９０１へ入力される。インデックス計算送信部１９０１からの出力は、受信復元部１９０２へ入力される。受信復元部１９０２からの出力が通信計算受信部１８０１−ｐ  〔１８０２−ｐ〕  からの出力となる。
【０１３８】
インデックス計算送信部１９０１は、通信計算受信部１８０１−ｐ  〔１８０２−ｐ〕  への入力ａｉ  〔ｂｉ〕  を受け取り、次式（５１）で示す計算を施して、ａ’ｉ，ｐ  〔ｂ’ｉ，ｐ〕  を計算し、秘密通信路１０３を通して、メンバＩＤがｍｐであるメンバへ送信する（ｐ＝１，２，…，ｉ−１）。
【数３２】
2004287333.tif 000028
【０１３９】
上記式（５１）において、ｈ及びｇは、有限体ＧＦ（ｑ）の２つの生成元とし、ｒＡｉ，ｐ  〔ｒＢｉ，ｐ〕  は、乱数として有限体ＧＦ（ｑ）上の値を選ぶ。また、インデックス計算送信部１９０１は、上記式（５１）で用いた乱数ｒＡｉ，ｐ  〔ｒＢｉ，ｐ〕  を受信復元部１９０２へ出力する。
【０１４０】
受信復元部１９０２は、メンバＩＤがｍｐ（ｐ＝１，２，…，ｉ−１）であるメンバからｑ個（ｑは有限体ＧＦ（ｑ）の要素数）の情報を受け取り、ａｉ番目の情報ｄ’ｉ，ｐ  〔ｂｉ番目の情報ｅ’ｉ，ｐ〕  を、次式（５２）で計算することにより、目的とする値ｄｉ，ｐ  〔ｅｉ，ｐ〕  を計算する。受信復元部１９０２は、それ以外の受け取った情報は、メンバＩＤがｍｉであるメンバにとっては、乱数に見える。
【０１４１】
【数３３】
2004287333.tif 000029
【０１４２】
値ｄ’ｉ，ｐ  〔ｅ’ｉ，ｐ〕  は、２つの情報ｄ’１，ｉ，ｐ及びｄ’２，ｉ，ｐ〔ｅ’１，ｊ，ｐ及びｅ’２，ｉ，ｐ〕  から成っているものとする。計算される値ｄｉ，ｐ  〔ｅｉ，ｐ〕  が、受信復元部１９０２の出力となり、通信計算受信部１８０１−ｐ  〔１８０２−ｐ〕  からの出力となる。
【０１４３】
図２１は、図１９の通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）の構成を示すブロック図である。図２１を用いて、通信計算送信部１８０３−ｐ，１８０４−ｐの構成を説明する。図２１に示されるように、通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）は、乱数生成部２００１と、有限体要素生成部２００２と、乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）とを有する。
【０１４４】
通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｔ）への入力は、乱数生成部２００１及び有限体要素生成部２００２からの出力とともに、乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）へ入力される。乱数生成部２００１からの出力が、通信計算送信部１８０３−ｐ，１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）からの出力となる。通信計算送信部１８０３−ｐは、紛失通信計算部１７０２の２つの入力のうち一つの入力を受け取り、通信計算送信部１８０４−ｐは、他の一つの入力を受け取る。ここでは、通信計算送信部１８０３−ｐへの入力をａｉ、通信計算送信部１８０４−ｐへの入力をｂｉとおく。通信計算送信部１８０３−ｐ，１８０４−ｐは、内部的に同じ構造なので、ここでは、通信計算送信部１８０３−ｐについて説明し、通信計算送信部１８０４−ｐに相当する説明は、括弧〔  〕内に記述する。
【０１４５】
図２１に示される乱数生成部２００１は、有限体ＧＦ（ｑ）上の値の乱数を生成して出力する。乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）へは、同じ乱数が出力される。乱数生成部２００１からの出力が通信計算送信部１８０３−ｐ  〔１８０４−ｐ〕  （ｐ＝ｉ＋１，ｉ＋２，…，ｎ）からの出力となる。
【０１４６】
図２１に示される有限体要素生成部２００２は、有限体ＧＦ（ｑ）上の値を０，１，…，ｑ−１と、順次生成し、それぞれ、乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）へ出力する。すなわち、乗数計算送信部２００３−１へは０を、乗数計算送信部２００３−２へは１を、乗数計算送信部２００３−ｊへはｊ−１を、乗数計算送信部２００３−ｑへはｑ−１を、出力する。
【０１４７】
図２１に示される乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）は、通信計算送信部１８０３−ｐ  〔１８０４−ｐ〕  （ｐ＝ｉ＋１，ｉ＋２，…，ｎ）から入力される値ａｉ  〔ｂｉ〕  、乱数生成部２００１から乱数を、有限体要素生成部２００２から対応する有限体要素ａ−１を、秘密通信路１０３を通してメンバＩＤがｍｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）であるメンバからの情報（他のメンバの通信計算受信部１８０１−ｉ  〔１８０２−ｉ〕  のインデックス計算送信部１９０１から出力）ａ’ｐ，ｉ  〔ｂ’ｐ，ｉ〕  を、受け取り、それらの入力から計算をして、計算結果を出力する。乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）からの出力、合計ｑ個の出力は、秘密通信１０３を通して、ａの値の小さい順に、メンバＩＤがｍｐ（ｐ＝ｉ＋１、ｉ＋２，…，ｎ）であるメンバへ送信する。今、乱数生成部２００１からの出力をｄｉ，ｐ  〔ｅｉ，ｐ〕  とする。また、秘密通信路１０３を通して受信する値を、ａ’ｐ，ｉ（通信計算送信部１８０３−ｐに相当）  〔ｂ’ｐ，ｉ（通信計算送信部１８０４−ｐに相当）〕とする。有限体要素生成部２００２から乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）へは、ａ−１が入力される。乗数計算送信部２００３−ａ（ａ＝１，２，…，ｑ）は、次式（５３）〜（５５）の計算を行い、ｄ’ｐ，ｉ，ａ  〔ｅ’ｐ，ｉ，ａ〕  をそれぞれ計算し（ｄ’ｐ，ｉ，ａ〔ｅ’ｐ，ｉ，ａ〕  は式（５２）の説明で述べたように２つの値からなる）、秘密通信路１０３を通してナンバＩＤがｍｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）であるメンバへ、ａ＝１，２，…，ｑの順に送信する。
【０１４８】
【数３４】
2004287333.tif 000030
【０１４９】
ここで、ｋＡａ  〔ｋＢａ（ａ＝１，２，…，ｑ）〕  は、それぞれ、ｑ個の有限体ＧＦ（ｑ）上の値の乱数である。これらの出力ｄ’ｐ，ｉ，ａ又はｅ’ｐ，ｉ，ａを秘密通信路１０３を通して、メンバＩＤがｍｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）であるメンバの通信計算受信部１８０１−ｉ  〔通信計算受信部１８０２−ｉ〕  が受け取ると、受け取ったメンバは、ａ＝ａｐ  〔ｂｐ〕  に相当するａ番目の情報ｄ’ｐ，ｉ＝ｄ’ｐ，ｉ，ａ〔ｅ’ｐ，ｉ＝ｅ’ｐ，ｉ，ａ〕  を式（５２）で復号することができる（それ以外の受け取った情報は、メンバＩＤがｍｐであるメンバにとっては、乱数に見える）。
【０１５０】
図２１で示される乱数生成部２００１からの出力ｄｉ，ｐ  〔ｅｉ，ｐ〕  が通信計算送信部１８０３−ｐ  〔１８０４−ｐ〕  （ｐ＝ｉ＋１，ｉ＋２，…，ｎ）からの出力となる。
【０１５１】
図１８のような構成の分散乗算部１５０３，１６０１への入力を分散情報ａｉ及びｂｉ（ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成を行うと、それぞれ、拡大体ＧＦ（ｑＬ）上の値Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）及びＢ＝（Ｂ０，Ｂ１，…，ＢＬ−１）になる）とすると、そのとき分散乗算部１５０３，１６０１から出力される分散情報ｃｉは、メンバでランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法の秘密再構成行うと、
Ｃ＝Ａ×Ｂ    …（５６）
となる拡大体ＧＦ（ｑＬ）上の値Ｃ＝（Ｃ０，Ｃ１，…，ＣＬ−１）となる。ここで、Ｃ０，Ｃ１，…，ＣＬ−１は、有限体ＧＦ（ｑ）上の値である。式（５６）は、拡大体ＧＦ（ｑＬ）上の演算（乗算）である。
【０１５２】
［第３の実施形態の動作］
図２２は、第３の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。第３の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作は、図２２に示されるように、上記した第１及び第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作と類似している。しかし、第１の実施形態のステップＳ８０２（図９）において分散加算のみ、第２の実施形態のステップＳ１３０２（図１４）においては分散加算と分散定数乗算のみしか行わなかったが、第３の実施形態のステップＳ２１０２（図２２）おいては、分散乗算をも行う点が相違する。
【０１５３】
図２２を用いて、第３の実施形態の分散計算法を実施する構成（分散計算システム）の動作を説明する。なお、第１及び第２の実施形態と異なるステップＳ２１０２のみを説明する。図２２に示されるように、ステップＳ２１０２においては、各メンバは、自分自身の秘密情報の分散情報、及び、他のメンバから配布された分散情報を用いて、関数ｆの分散計算を行う。ステップＳ２１０２は、図１１の分散計算部１００５−ｉにおける動作を示しており、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、関数ｆ（Ｘ１，Ｘ２，…，Ｘｎ）で指示される通りの分散計算を行う。この関数ｆは、第１の実施形態においては加算のみ、第２の実施形態においては、加算と定数乗算しか扱わなかったが、第３の実施形態においては、乗算も取り扱う。例えば、
ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝（ｔＡＸＡ＋ｔＢＸＢ）×ＸＣ
（ｔＡ及びｔＢは、拡大体ＧＦ（ｑＬ）上の定数）である場合には、メンバＩＤがｍｉであるメンバは、配布された結果自分が保持する分散情報ＹＡ，ｉ、ＹＢ，ｉ、及び、Ｙｃ，ｉから、ｔＡ及びＹＡ，ｉを入力とする分散定数乗算計算（分散定数乗算部１１０１の動作）、ｔＢ及びＹＢ，ｉを入力とする分散定数乗算計算（分散定数乗算部１１０１の動作）を行って、その２つの出力の分散加算（分散加算部５０１，６０１の動作）を行い、さらに、その加算結果とＹｃ，ｉとの分散乗算計算（分散乗算部１５０３，１６０１の動作）を行ってＺ’ｉを求める。その計算結果Ｚ’ｉは、拡大体ＧＦ（ｑＬ）上の計算結果
Ｚ＝ｆ（Ｘ１，Ｘ２，…，Ｘｎ）＝（ｔＡＸＡ＋ｔＢＸＢ）×ＸＣ
の（ランプ型（Ｌ，ｋ，ｎ）秘密分散法で分散された）分散情報となっている。
【０１５４】
図２３は、第３の実施形態における分散乗算における動作を示すフローチャートである。例えば、拡大体ＧＦ（ｑＬ）上の値Ａ＝（Ａ０，Ａ１，…，ＡＬ−１）、Ｂ＝（Ｂ０、Ｂ１，…，ＢＬ−１）の乗算を行う場合を考える。まず、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、自身が保持する値Ａ及びＢの分散情報ａｉ及びｂｉより、その積ｃ’ｉ＝ａｉ×ｂｉ、及び、紛失通信を用いて、上記式（４５）及び（４６）にあるような値ｄｉ，ｐ及びｅｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を求める（ステップＳ２２０１）。ステップＳ２２０１は、図１８における乗算部１７０１（値ｃ’ｉを求める）、及び、紛失通信計算部１７０２（値ｄｉ，ｐ及びｅｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）を求める）における動作を表している。
【０１５５】
次に、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、ステップＳ２２０１で計算した値ｃ’ｉ及びｄｉ，ｐ，ｅｉ，ｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）から、式（４９）を用いて、Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を求める（ステップＳ２２０２）。ステップＳ２２０２は、図１８の分散情報計算部１７０３における動作を示している。
【０１５６】
次に、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、ステップＳ２２０２で計算した値Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）をランプ型（Ｌ，ｋ，ｎ）秘密分散法を用いて分散情報Ｆｉ，ｐ（ｐ＝１，２，…，ｎ）を作り、メンバＩＤがｍｐ（ｐ＝１，２，…，ｎであり、ｐ≠ｉであるもの）である他のメンバに分散情報Ｆｉ，ｐを配布する（ステップＳ２２０３）。ステップＳ２２０３は、図１８の秘密分散計算部１７０４及び送信部１７０５における動作を示している。
【０１５７】
次に、メンバＩＤがｍｉ（ｉ＝１，２，…，ｎ）である各メンバは、ステップＳ２２０３の動作により受け取った分散情報Ｆｉ，ｐ（ｐ＝１，２，…，ｎ）をすべて加算し（上記式（４３））、値ｃｉを求めて出力する（ステップＳ２２０４）。ステップＳ２２０４は、図１８の受信部１７０６及び加算部１７０７における動作を示している。
【０１５８】
［第３の実施形態の効果］
以上に説明したように、第３の実施形態によれば、第１及び第２の実施形態と同様に、関数ｆ（ただし、関数ｆは、加算、定数乗算、及び、乗算からなる関数）に対するマルチパーティ・プロトコル（各メンバの保持する秘密情報を公開しないまま、各メンバが分散計算を行うことにより、関数ｆの計算結果を得るプロトコル）において、関数ｆにおける拡大体ＧＦ（ｑＬ）上の計算を、各メンバの分散演算処理においては、その拡大体よりも小さな有限体ＧＦ（ｑ）上の計算のみを行うことで、達成することができる。このため、メンバそれぞれの分散演算処理における、演算量、演算回路に必要な回路規模、演算に必要な記憶容量、演算時間等の演算コストを削減することができる。
【０１５９】
また、第１及び第２の実施形態とは異なり、第３の実施形態においては、分散加算計算、分散定数乗算計算だけでなく、分散乗算計算も可能となる。
【０１６０】
なお、第１〜第３の実施形態においての「メンバ」は、必ずしも１人の人間である必要はなく、秘密情報を保持し、計算手段（分散秘密再構成計算部）を構成要素として持つ装置とすることもできる。すなわち、１人の人間が、上記装置を複数個持って処理を進めることができる。この場合には、１人の人間が、複数のメンバとなる。また、１台の上記装置を複数の人間が管理して処理を進めることもできる。この場合は、複数の人間が、１人のメンバとなる。
【０１６１】
≪第４の実施形態≫
第１〜３の実施形態において、各メンバにおける分散計算部３０５−ｉ、又は、１００５−ｉにおける分散計算に用いる分散情報は、必ずしもメンバの保有する秘密Ｘｉの分散情報でなくとも分散計算は可能である。すなわち、外部（センタのようなものを仮定してもよい）から、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散された分散情報を、目的とする関数ｆの計算に必要な分だけいくつか（メンバの数ｎよりも多くてもよい）与えられ、それを用いて分散計算するような分散処理部を構成することが可能である。そのような分散処理部を用いた分散計算方法を実施する構成（分散計算システム）の構成を図２４に示し、その分散処理部（分散計算装置）の構成を図２５（ａ）及び（ｂ）に示す。
【０１６２】
図２４に示されるように、第４の実施形態の秘密計算方法を実施する構成（分散計算システム）は、秘密分散送信部２３０１と、ｎ個の分散処理部２３０２−ｉ（ｉ＝１，２，…，ｎ）と、秘密再構成計算部２３０３とを有する。
【０１６３】
秘密分散送信部２３０１は、関数ｆへ入力する拡大体ＧＦ（ｑＬ）上の値の、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散した分散情報を求め、各分散処理部２３０２−ｉ（ｉ＝１，２，…，ｎ）へ出力する。例えば、Ｄ＝ｆ（Ａ，Ｂ，Ｃ）（Ａ，Ｂ，Ｃ，Ｄは、拡大体ＧＦ（ｑＬ）上の値）を分散計算させる場合には、秘密分散送信部２３０１は、Ａ，Ｂ，Ｃをランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法で分散し、その分散情報ａｉ，ｂｉ，ｃｉ（ｉ＝１，２，…，ｎ）を、各分散処理部２３０２−ｉへ出力する。
【０１６４】
図２５（ａ）及び（ｂ）に示されるように、各分散処理部２３０２−ｉは、秘密分散送信部２３０１からの出力を受信する分散情報受信部２４０６−ｉを持ち、その分散情報受信部２４０６−ｉで受信した分散情報を分散計算部２４０５−ｉへ出力する。
【０１６５】
分散計算部２４０５−ｉは、所望の関数ｆに、定数乗算及び乗算が含まれている場合には、他の分散処理部２３０２−ｉと秘密通信を行う秘密通信路１０３が備わっており、分散情報受信部２４０６−ｉから受け取った値、及び、受信部２４０４−ｉから受け取った値（図２５（ａ）の場合）を用いて、関数ｆの分散計算を行う。分散計算部２４０５−ｉの構成は、第１〜第３の実施形態のものと同様であり、分散計算結果を出力する。この分散計算部２４０５−ｉからの出力は、秘密再構成計算部２３０３へ入力される。秘密情報記憶部２４０１−ｉ、秘密分散計算部２４０２−ｉ、送信部２４０３−ｉ、及び、受信部２４０４−ｉは、第１〜第３の実施形態のものと同様である。また、分散情報受信部２４０６−ｉは、受信部２４０４−ｉと同等な機能を持つため、分散情報受信部２４０６−ｉの機能を受信部２４０４−ｉに持たせ、受信機能を一つのみ持つ構成とすることも可能である。
【０１６６】
図２４に示される秘密再構成計算部２３０３は、第１〜第３の実施形態の秘密再構成計算部と同様なものであり、最終的な関数ｆの計算結果を出力する。第１〜第３の実施形態のものと同様に、秘密再構成計算部２３０３における処理は、処理を統合するセンターのようなものが行ってもよいし、集まったメンバのうち、だれか１人、又は、複数人で行ってもよい。ただし、計算結果Ｚを必要としているメンバが行うのが望ましい。また、最終的な秘密再構成の処理（秘密再構成計算部２３０３の動作）は、誰か１以上の複数のメンバの分散処理部が行ってもよいので、そのような構成の分散処理部の構成を、図２６及び図２７（ａ）及び（ｂ）に示す。これは、第１〜第３の実施形態の分散処理部、及び、図２５（ａ）及び（ｂ）に示す分散処理部に、秘密再構成計算部が追加された形になる。図２６及び図２７（ａ）及び（ｂ）の構成においては、分散処理部自身で最終的な計算結果Ｚを再構成することができるので、分散計算部２５０５−ｉからの出力Ｚ’ｉは、必要に応じて、分散処理部から外への出力として、出力するか否かを選択することができる。そのため、図２６及び図２７（ａ）及び（ｂ）においては、分散計算部２５０５−ｉからの出力を、破線の矢印で描いている。図２６及び図２７（ａ）及び（ｂ）の構成を持つ分散処理部が１以上の複数個含まれていれば、図１及び図２４の構成を持つ分散計算システムにおける、秘密再構成計算部１０２及び２３０３を備えなくても、最終の計算結果Ｚを得ることが可能となる。
【０１６７】
また、第２の実施形態において、図１３の拡大体乗算部１２０１の構成の説明において、式（３５）でＥ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を計算した後、式（３８）のＥｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を計算するようにしていたが、Ｌ＝２等の例を挙げている通り、式（４０）のように、Ｅ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を求めずに、直接Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を求めるようにしてもよい。
【０１６８】
また、同様に、第３の実施形態において、図１８の分散情報計算部１７０３の構成の説明で、式（４７）でＧｕ，ｖ（ｕ＝０，１，２，…，Ｌ−１；  ｖ＝０，１，２，…，Ｌ−１）、さらに、式（４８）でＥ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を計算した後、式（４９）のＥｉ＝（Ｅｉ，０、Ｅｉ，１，…，Ｅｉ，Ｌ−１）を計算するようにしていたが、Ｌ＝２の例を挙げている通り、式（５０）のようにＧｕ，ｖ（ｕ＝０，１，２，…，Ｌ−１；  ｖ＝０，１，２，…，Ｌ−１）、及び、Ｅ’ｉ，０，Ｅ’ｉ，１，…，Ｅ’ｉ，２（Ｌ−１）を求めずに、直接Ｅｉ＝（Ｅｉ，０，Ｅｉ，１，…，Ｅｉ，Ｌ−１）を求めるようにしてもよい。
【０１６９】
第３の実施形態における、紛失通信計算部１７０２において、▲１▼通信計算受信部１８０１−ｐ（ｐ＝１，２，…，ｉ−１）を通信計算送信部に置き換え、さらに、通信計算送信部１８０３−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）を通信計算受信部に置き換えた構成、又は、▲２▼通信計算受信部１８０２−ｐ（ｐ＝１，２，…，ｉ−１）を通信計算送信部に置き換え、さらに、通信計算送信部１８０４−ｐ（ｐ＝ｉ＋１，ｉ＋２，…，ｎ）を通信計算受信部に置き換えた構成、又は、▲３▼通信計算受信部をすべて通信計算送信部に、さらに、通信計算送信部をすべて通信計算受信部に置き換えた構成、などの構成でも、同じ動作や効果を得ることができる。
【０１７０】
第３の実施形態における、紛失通信計算部１７０２において、通信計算送信部１８０１−ｐ（又は１８０２−ｐ）と通信計算受信部１８０３−ｊ（又は１８０４−ｊ）との間の秘密通信路１０３における情報のやり取りは、式（５１）や式（５３）〜（５５）のように、暗号化されたような情報、すなわち、法ｑのもとにおける離散対数を計算することが困難であること利用して送りたい情報を隠蔽している情報なので、とくに秘密に通信しなくても、メンバの秘密情報や分散計算の途中結果などが露呈されることはない。式（５１）においては、送りたい情報ａｉ（又はｂｉ）を有限体ＧＦ（ｑ）の生成元ｈのべき数として隠蔽し、式（５３）〜（５５）で得られる情報から得るべき必要な情報ａｉ（ａ−１）−ｄｉ，ｐ（又はｂｉ（ａ−１）−ｅｉ，ｐ）は、式（５１）で用いた乱数ｒＡｐ，ｉ（又はｒＢｐ，ｉ）を知らないと算出できないようになっている。したがって、上記における通信においては、秘密通信路ではなく、放送型の通信路や盗聴される可能性のある通信路で通信してもよい。
【０１７１】
≪第５の実施形態≫
本発明の第５〜第７の実施形態に係る分散計算においては、第１〜第４の実施形態と同様に、従来用いられている（ｋ，ｎ）しきい値秘密分散法に代えて、ランプ型秘密分散法（すなわち、ランプ型（Ｌ，ｋ，ｎ）しきい値秘密分散法）を用いる。以下の説明においては、秘密情報や乱数などの変数はすべてある有限体ＧＦ（ｑ）上の元であるとする。第１〜第４の実施形態では、しきい値ｋと分散情報の個数ｎとの間にはｋ≦ｎと言う関係が成り立っていたが、第５〜第７の実施形態では、２ｋ−１≦ｎという関係が成り立っているものとする。
【０１７２】
第１〜第４の実施形態においては、式（１９）のようなｋ−１次多項式を利用して分散情報を計算していたが、第５〜第７の実施形態においては、次式（５７）のような（ｋ−１）次多項式を利用して分散情報を計算する。
【数３５】
2004287333.tif 000031
【０１７３】
ここで、Ｓ０，Ｓ１，…，ＳＬ−１はそれぞれ、秘密情報であり、Ｒ０，…，Ｒｋ−Ｌ−１はそれぞれ、ランダムな値である。また、ｇ（ｘ）は、Ｌ次の既約多項式であり、第１〜第４の実施形態における、式（３６）の生成多項式ｇ（ｘ）に相当するものである。この既約多項式は予め与えられるものとする。メンバＩＤ（すなわち、ＩＤ情報）ｗｉをもっているメンバ（すなわち、参加者）に渡す分散情報はｆ（ｗｉ）となる。各メンバが持っているメンバＩＤ＿ｗｉは公開されているものとする。第１〜第４の実施形態では、メンバＩＤをｍｉ（ｉ＝１，２，…，ｎ）と表記していたが、第５〜第７の実施形態では、メンバＩＤをｗｉ（ｉ＝０，１，…，ｎ−１）と表記し、メンバＩＤがｗｉであるメンバのことを、メンバＰｉと呼ぶことにする。
【０１７４】
第５〜第７の実施形態においては、秘密情報（Ｓ０，…，ＳＬ−１）を既約多項式ｇ（ｘ）を利用して有限体ＧＦ（ｑ）のＬ次拡大体ＧＦ（ｑＬ）の値として扱う。つまり、方程式ｇ（ｘ）＝０の解をαとしたときに、
Ｓ＝ＳＬ−１αＬ−１＋…＋Ｓ１α＋Ｓ０
と表す。これより、秘密情報に関する計算は、有限体ＧＦ（ｑＬ）上の演算で表すことができ、これはｇ（ｘ）を法とする多項式の加算や乗算で実現することができる。
【０１７５】
メンバＩＤがｗｉであるメンバＰｉ（ｉ＝０，…，ｎ−１）に、それぞれｆ（ｗｉ）を分散情報として渡す。このときの分散情報のサイズは、秘密情報の１／Ｌとなっている。秘密情報の復元は、（ｋ，ｎ）しきい値法と同様に、多項式を復元し、さらにその後、ｍｏｄ  ｇ（ｘ）を計算する。
【０１７６】
［第５の実施形態の構成］
以下、第５の実施形態においてはランプ型秘密分散を利用した分散計算について説明する。特に、分散計算の具体例として、分散加算を行うものとする。この点から、第５の実施形態は、上記第１の実施形態と類似した内容となるが、分散情報の生成方法が異なる。
【０１７７】
第５の実施形態は、秘密分散及び秘密復元（再構成）、また分散計算を行うシステムについて説明する。特に、分散計算の具体例として、分散加算を行うものとする。以下、分散計算において、秘密情報をＡ＝（Ａ０，…，ＡＬ−１）及びＢ＝（Ｂ０，…，ＢＬ−１）とする。そして、メンバＩＤがｗｊであるメンバがもつ分散情報は、次式（５８）を用いて、それぞれａ（ｗｊ）及びｂ（ｗｊ）とする。
【数３６】
2004287333.tif 000032
【０１７８】
このとき、分散情報の和を表す多項式は次式（５９）のようになる。
【数３７】
2004287333.tif 000033
【０１７９】
これより、次式（６０）が得られる。
【数３８】
2004287333.tif 000034
【０１８０】
この式に、ｘ＝αを代入すると、右辺は拡大体ＧＦ（ｑＬ）における加算を表している。したがって、
ｃｊ＝ａ（ｗｊ）＋ｂ（ｗｊ）
は秘密情報Ａ及びＢの和である値Ｃ（＝Ａ＋Ｂ）の分散情報を表している。したがって、分散加算においては、メンバＰｊは、持っている分散情報の和を計算すればよい。
【０１８１】
第５の実施形態に係る分散計算システムの構成は、図１、又は、図２４にある、第１〜第４の実施形態に係る分散計算システムと同様なものになる。第５の実施形態は、第１〜第４の実施形態とは、分散情報を生成するランプ型秘密分散法が異なることから、それぞれの構成要素、秘密分散送信部２３０１、分散処理部１０１，２３０２、及び秘密再構成計算部１０２，２３０３の内部の構成や動作が異なる。図２８は、第５の実施形態に係る分散計算装置（図１、図２４の分散計算処理部１０１，２３０２に相当する）の構成を示すブロック図である。図２８に示されるように、第５の実施形態に係る分散計算装置は、秘密分散部分３００１と、分散計算部分３００２と、秘密復元部分３００３と、秘密通信路１０３とを有する。図２８に示される秘密分散部分３００１は、秘密分散部３１０１と、送信部３１０２とを有する。また、図２８に示される分散計算部分３００２は、受信部３１０３と、記憶部３１０４と、分散計算部３１０５と、送信部３１０６とを有する。さらに、図２８に示される秘密復元部分３００３は、受信部３１０７と、秘密復元部３１０８とを有する。分散計算装置は、秘密分散部分３００１、分散計算部分３００２、及び、秘密復元部分３００３のうち、いずれか１つ又は２つしか持たない場合もありうる（後の図３１〜図３３で説明する）。
【０１８２】
秘密分散部３１０１は、秘密情報についてランプ型秘密分散を実行して分散情報を計算する。送信部３１０２は、他のメンバとそれぞれ秘密通信路１０３でつながっており、一対一の秘密通信を行う。そして、計算結果を他のメンバに配布する。その結果、各メンバは分散情報を得る。
【０１８３】
受信部３１０３は、他のメンバ若しくはメンバとは別に設けられたセンターから上記分散情報を受け取る。この結果、メンバは分散情報を保持する。記憶部３１０４は、秘密分散で得られた分散情報及び分散計算の結果を保持する。分散計算部３１０５は、記憶部３１０４で保持されている分散情報について計算を行う。そして、秘密情報についての任意の演算結果の分散情報を得る。
【０１８４】
第５の実施形態においては、分散計算部３１０５は、秘密情報の和の分散情報を求める場合について示す。一般に、分散計算部３１０５は、第５の実施形態で示す分散加算、後述する第６の実施形態で示す分散乗算、及び、後述する第７の実施形態で示す分散定数乗算の組み合わせで構成される。送信部３１０６は、分散計算の結果を配布する。ここで、送信部３１０６についても、秘密通信路１０３を介して、分散情報の配布を行う。ここで、受信部３１０３、記憶部３１０４、分散計算部３１０５、送信部３１０６は、各メンバが持っている。
【０１８５】
受信部３１０７は、他のメンバから分散計算結果を受け取る。秘密復元部３１０８は、全てのメンバから受け取った分散情報を用いて秘密情報の復元（再構成）をする。送信部３１０２と送信部３１０６、及び受信部３１０３と受信部３１０７は、メンバが同時に持つ際は、共通化した構成にしてもよい。
【０１８６】
図２９は、図２８の秘密分散部３１０１の構成を示すブロック図である。図２９に示されるように、秘密分散部３１０１は、乱数生成部３１１１と、有限体演算部３１１２とを有する。乱数生成部３１０１は、秘密分散計算を行う際に利用する乱数を生成する。有限体演算部３１１２は、秘密情報、メンバのメンバＩＤ、上記生成された乱数、及び既約多項式から分散情報を生成する。
【０１８７】
図３０は、図２８の秘密復元部３１０８の構成を示すブロック図である。図３０に示されるように、秘密復元部３１０８は、復元情報生成部３１２１と、有限体演算部３１２２とを有する。復元情報生成部３１２１は、メンバＩＤ及び既約多項式から秘密復元に利用する情報を生成する。有限体演算部３１２２は、上記生成した情報及び分散情報から秘密情報の復元計算を行う。
【０１８８】
図２８に示される秘密分散部分３００１は、秘密分散を行う部分である。図２８に示される分散計算部分３００２は、分散情報を受け取って、分散計算を実行する部分である。図２８に示される秘密復元部分３００３は、最後に、分散計算結果を集めて、もとの秘密情報の計算結果を復元する部分である。図２８に示される秘密分散部分３００１である秘密分散部３１０１及び送信部３１０２は、各メンバが持っていてもよいし、メンバとは独立したセンターが持っていてもよい。図２８に示される秘密復元部分３００３である受信部３１０７及び秘密復元部３１０８は、少なくとも１人のメンバが持っていてもよいし、メンバとは独立したセンターが行ってもよい。
【０１８９】
以下、メンバが保持する秘密情報について分散計算を行い、計算結果をメンバが得る場合についての分散計算システムの構成を図３１に示す。「参加者」で示しているブロックが、各メンバの分散計算装置であり、図では２つしか描かれていないが、実際にはｎ個存在する。各参加者はそれぞれ、秘密分散部分３００１、分散計算部分３００２、及び、秘密復元部分３００３を有している。また、メンバが保持する秘密情報についての分散計算を行い、センターが計算結果を得る場合についての分散計算システムの構成を図３２に示す。図３２は、図１の分散計算システムと同様な構成図である。「参加者」で示しているブロックが、各メンバの分散計算装置であり、図では２つしか描かれていないが、実際にはｎ個存在する。また、「センター」で示しているブロックが、最終的に計算結果を復元する部分であり、図１の秘密再構成計算部１０２に相当する部分である。各参加者はそれぞれ、秘密分散部分３００１、及び、分散計算部分３００２を有している。また、センターが持っている秘密情報についての分散計算を行い、センターが計算結果を得る場合についての分散計算システムの構成を図３３に示す。図３３は、図２４の分散計算システムと同様な構成図である。「参加者」で示しているブロックは、各メンバの分散計算装置であり、図では２つしか描かれていないが、実際にはｎ個存在する。また、上部の「センター」で示しているブロック（秘密分散部３１０１、及び、送信部３１０２からなる部分）は、秘密情報を分散する部分であり、図２４の秘密分散送信部２３０１に相当する部分である。また、下部の「センター」で示しているブロック（秘密復元部３１０８、及び、受信部３１０７からなる部分）は、最終的に計算結果を復元する部分であり、図２４の秘密再構成計算部２３０３に相当する部分である。各参加者はそれぞれ、分散計算部分３００２を有している。
【０１９０】
［第５の実施形態の動作］
第５の実施形態においては、ランプ型秘密分散法を利用した分散計算について手順を示す。分散計算の具体例として、各メンバが保持する秘密情報から秘密分散を行って分散情報を得て、分散情報から元の秘密情報の和を求める手順を示す。
【０１９１】
最初に秘密分散における動作を示す。秘密情報をＳ＝（Ｓ０，Ｓ１，…，ＳＬ−１）とする。秘密情報Ｓ＝（Ｓ０，Ｓ１，…，ＳＬ−１）及びランダムに生成した値Ｒ０，…，Ｒｋ−Ｌ−１と、次式（６１）
【数３９】
2004287333.tif 000035
のような多項式を用いて、次式（６２）に示される、メンバＰｊ向けの分散情報ｓｊを生成する。
【数４０】
2004287333.tif 000036
【０１９２】
この計算は、次のようなｎ×ｎ行列
Ｅ＝（ｅｉｊ）
ｅｉｊ＝ｗｉｊ（ｉ＝０，…，ｎ−１；  ｊ＝０，…，ｎ−１）
を用いて、
（ｓ０，…，ｓｎ−１）ｔ
＝Ｅ（ｆ０，ｆ１，…，ｆｋ−１，０，…，０）ｔ
のように表すことができる。そして、分散情報ｓｊをメンバＰｊに渡す。
【０１９３】
秘密復元のために集まった分散情報をｔ個（ｔ≧ｋ）とする。まず、秘密復元の各メンバＰ’ｊから分散情報ｓ’ｊ及び各メンバのメンバＩＤ  ｗ’ｊ（ｊ＝０，…，ｔ−１）を受け取っておく。そして、次式（６３）の連立方程式から、多項式の係数ｆ０，ｆ１，…，ｆｋ−１を求める。
ｓ’ｊ＝ｆｋ−１ｗ’ｊ ｋ−１＋…＋ｆ１ｗ’ｊ＋ｆ０    …（６３）
ここで、ｊ＝０，…，ｔ−１である。
【０１９４】
そして、得られた多項式について、既約多項式ｇ（ｘ）による剰余（次式（６４）を計算する。
【数４１】
2004287333.tif 000037
得られた多項式の係数が復元された秘密情報にあたる。
【０１９５】
この計算は、以下に示すような行列を利用した計算と等価である。既約多項式ｇ（ｘ）を法とする多項式の剰余算を表す行列をＧとしておく。そして、メンバのメンバＩＤ＿ｗ’ｉから、ｔ×ｔ行列
Ｅ’＝（ｅ’ｉｊ）
ｅ’ｉｊ＝ｗ’ｉｊ（ｉ＝０，…，ｔ−１；  ｊ＝０，…，ｔ−１）を生成する。行列Ｇ、及び、行列Ｅ’の逆行列Ｅ’−１より、行列Ｒ＝ＧＥ’−１＝（ｒｉｊ）を計算する。このようにして得られたｒｉｊを用いて、次式（６５）の計算を実行する。
【数４２】
2004287333.tif 000038
その結果得られるＳ０，…，ＳＬ−１が復元された秘密情報である。
【０１９６】
ここで、行列Ｇの生成方法について説明する。行列Ｇは、（ｔ−１）次多項式
ｈ（ｘ）＝ｈｔ−１ｘｔ−１＋…＋ｈ１ｘ＋ｈ０
を既約多項式
ｇ（ｘ）＝ｘＬ＋…＋ｇ１ｘ＋ｇ０
で割った余りである、次式（６６）
【数４３】
2004287333.tif 000039
より、次式（６７）のようにして行列Ｇを得る。
【０１９７】
【数４４】
2004287333.tif 000040
【０１９８】
例えば、ＧＦ（３１）、ｔ＝１６、既約多項式ｇ（ｘ）＝ｘ３＋ｘ＋３の場合において、行列Ｇを計算した結果は以下のようになる。１５次多項式（式（６８）を以下のように定義する。
【数４５】
2004287333.tif 000041
【０１９９】
既約多項式ｇ（ｘ）を法とした剰余算の結果は次式（６９）のようになる。
【数４６】
2004287333.tif 000042
【０２００】
これより、行列Ｇは次式（７０）のようになる。
【数４７】
2004287333.tif 000043
【０２０１】
次に、分散計算における動作を説明する。第５の実施形態においては具体例として分散加算について説明する。メンバＰｊは秘密情報Ａ及びＢの分散情報ａｊ及びｂｊを持っているものとする。分散加算においては、各メンバが保持する分散情報の和を計算すればよい。つまり、各メンバが保持する秘密情報の和Ａ＋Ｂの分散情報を求めるためには、メンバＰｊは分散情報の和ａｊ＋ｂｊを計算すればよい。
【０２０２】
［第５の実施形態の効果］
以上に説明したように、各メンバの行う演算は、もとの秘密情報が定義される有限体（上記説明においてはＬ次拡大体）より小さな有限体で行うことができる。これより、各メンバはより少ない計算資源で秘密情報に関する加算を実行することが可能となる。
【０２０３】
≪第６の実施形態≫
本発明の第６の実施形態においては、具体例として分散乗算散について説明する。秘密情報をＡ＝（Ａ０，…，ＡＬ−１）及びＢ＝（Ｂ０，…，ＢＬ−１）とする。分散情報は以下の多項式（式（７１））から計算する。
【数４８】
2004287333.tif 000044
【０２０４】
このとき、分散情報の積を表す多項式は次式（７２）のようになる。
【数４９】
2004287333.tif 000045
【０２０５】
これより、次式（７３）が成り立つ。
【数５０】
2004287333.tif 000046
【０２０６】
これに、ｘ＝αを代入すると、これは拡大体ＧＦ（ｑＬ）上における乗算となっている。したがって、ａ（ｗｉ）ｂ（ｗｉ）は、２（ｋ−１）次多項式による値ＡＢの分散情報を表している。ただし、従来と同様に、秘密情報を変えないように、多項式の次数を下げる変換操作（ＢＰＢ−１）Ｃ＝Ｄが必要となる（従来技術の説明の分散乗算（方式▲２▼）におけるステップＳ２０３の処理に相当し、Ｃ＝（ａ（ｗ０）ｂ（ｗ０），ａ（ｗ１）ｂ（ｗ１），…，ａ（ｗｎ−１）ｂ（ｗｎ−１））である）。従来のＳｈａｍｉｒ法による（ｋ，ｎ）しきい値秘密分散法においては、秘密情報は多項式の定数項であった。したがって、行列Ｐは単にｋ次以上の項の係数を０とする演算（式（８０）を満たす行列Ｐ）でよい。
Ｐ（ｘ１、ｘ２、…、ｘｎ）ｔ
＝（ｘ１、ｘ２、…、ｘｋ、０、…、０）    …（８０）
【０２０７】
一方、ランプ型秘密分散法においては、秘密情報は式（６１）の多項式ｆ（ｘ）の
ＳＬ−１ｘＬ−１＋…＋Ｓ１ｘ＋Ｓ０
の部分、つまりｇ（ｘ）で割った余りである。これより、行列Ｐは、ｍｏｄ  ｇ（ｘ）において合同となるように多項式の次数を２（ｋ−１）次から（ｋ−１）次に下げる演算とすればよい。
【０２０８】
［第６の実施形態の構成］
第６の実施形態においては、第５の実施形態における分散計算について、秘密情報の積を計算する分散乗算を実現する装置について示す。しかし、同じように秘密情報の積を計算する分散乗算を実現する第３の実施形態とは、分散情報の生成方法が異なる（第３の実施形態では、式（１９）にあるようなｋ−１次多項式から分散情報を生成し、第６の実施形態では、式（５７）にあるようなｋ−１次多項式から分散情報を生成する）ことから、構成や動作は、全く異なったものとなっている。第６の実施形態においては、ある秘密情報Ａ，Ｂについての分散情報（ａ０，…，ａｎ−１），（ｂ０，…，ｂｎ−１）が与えられており、分散情報（ａ０，…，ａｎ−１），（ｂ０，…，ｂｎ−１）から秘密情報の積Ｄ（＝ＡＢ）の分散情報（ｄ０，…，ｄｎ−１）を計算する。
【０２０９】
図３４は、分散乗算を行う場合における、分散計算部の構成を示すブロック図である。図３４に示されるように、分散乗算計算部３２００は、乗算部３２０１と、秘密分散処理部３２０２と、分散情報変換部３２０３と、秘密復元処理部３２０４とを有する。乗算部３２０１においては、メンバが保持する分散情報の積を計算する。秘密分散処理部３２０２においては、乗算部で計算した値について秘密分散を行う。ここでは、ランプ型秘密分散法ではなく、（ｋ，ｎ）しきい値秘密分散を用いて分散情報を生成する（このときのしきい値は、秘密分散部３１０１におけるランプ型（Ｌ，ｋ，ｎ）秘密分散法におけるしきい値ｋとは異なる値ｋ’（ｋ’≦ｎ）でもよい）。分散情報変換部３２０３においては、秘密分散処理部３２０２で得られた第２の分散情報について、変換を行う。秘密復元処理部３２０４においては、分散情報変換部３２０３で計算した結果について秘密復元処理を行う。乗算結果を他のメンバと交換し、その結果得られた分散情報を復元する。ここでは、秘密分散処理部３２０２と同様に、（ｋ，ｎ）しきい値法を用いて秘密復元の計算を行う（このときのしきい値は、秘密分散処理部３２０２におけるしきい値と同じ値を用いる）。
【０２１０】
［第６の実施形態の動作］
第６の実施形態においては、分散計算によって、秘密情報Ａ，Ｂの分散情報ａｉ（ｉ＝０，…，ｎ−１）及びｂｉ（ｉ＝０，…，ｎ−１）から、秘密情報の積ＡＢの分散情報を計算する手順を示す。分散乗算においては、各メンバの保持する分散情報の積を変換しなければならない。そして、変換の際にはメンバ間で分散情報に関するやり取りが必要である。
【０２１１】
処理の手順は図３５のようになる。ここで、メンバＰｊ（ｊ＝０，…，ｎ−１）は、各メンバのメンバＩＤ＿ｗｉ（ｉ＝０，…，ｎ−１）及び、分散情報ａｊ及びｂｊを受け取っているものとする。以下においては、便宜上行列を利用して説明する。
【０２１２】
図３５に示されるように、ステップ１において、メンバＰｉは分散情報の積ｃｉ＝ａｉｂｉを計算する。この分散情報の積ｃｉは秘密情報Ａ及びＢの積ＡＢの分散情報となるが、秘密分散を行う多項式の次数が２（ｋ−１）であり、都合が悪い。そこで、以下のステップにおいては、秘密分散、配布（ステップ２、３）、変換処理（ステップ４）、計算結果の分散情報の交換、及び、計算結果の復元（ステップ５、６）の処理を行うことによって、得られた分散情報を、しきい値がｋとなるように変換を行う。
【０２１３】
ステップ２において、メンバＰｉは分散情報の積ｃｉについて秘密分散を行う。ここにおける秘密分散は（ｋ’，ｎ）しきい値法（ｋ’≦ｎ）を利用する。メンバＰｉは、分散情報の積ｃｉ及び乱数からランダムなｋ’−１次の多項式（式（７４））を生成し、分散情報ｃｉ，ｊ（ｊ＝０，…，ｎ−１）を計算する。
【数５１】
2004287333.tif 000047
ここで、Ｒｉ，ｍ（ｍ＝１，…，ｋ’−１）はメンバＰｉがランダムに生成する数値である。
【０２１４】
これは、次のようなｎ×ｎ行列Ｅ＝（ｅｉｊ）を用いて、次式（７５）のように表すことができる。
【数５２】
2004287333.tif 000048
【０２１５】
ステップ３において、他のメンバと通信を行って、分散情報ｃｉ，ｊを交換する。メンバＰｉは、上記計算した（ｃｉ，０，…，ｃｉ，ｎ−１）について、ｃｉ，ｊ（ｊ＝０，…，ｎ−１であり、ｊ≠ｉであるもの）を、メンバＰｊに配布する。この結果、メンバＰｊは（ｃ０，ｊ，…，ｃｎ−１，ｊ）を受け取る。
【０２１６】
ステップ４において、ＰｊはＣｊ＝（ｃ０，ｊ，…，ｃｎ−１，ｊ）（２（ｋ−１）次多項式由来）を、Ｄｊ＝（ｄ０，ｊ，…，ｄｎ−１，ｊ）（（ｋ−１）次多項式由来）に変換する。変換は、例えば、以下のように生成される行列Ｐ及び行列Ｅを用いた際の、Ｄｊ＝（ＥＰＥ−１）Ｃｊと等価な計算である。つまり、ＥＰＥ−１＝（ｐｉｊ）について、ｄｉｊ＝Σｋ  ｐｉｋｃｋｊ（ｉ＝０，…，ｎ−１）を計算する。
【０２１７】
ここで、行列Ｐは、秘密分散における多項式を２（ｋ−１）次から（ｋ−１）次に下げるような変換であり、ｍｏｄ  ｇ（ｘ）において合同となるように多項式の次数を下げる演算である。図３６に、変換行列Ｐの生成方法の一例を示す。そして、具体的に、ＧＦ（３１）、ｋ＝８（これは、秘密分散部３１０１におけるランプ型秘密分散のしきい値である）、ｎ＝１６、既約多項式ｇ（ｘ）＝ｘ３＋ｘ＋３の場合において、行列Ｐを計算した結果は以下のようになる。１４次（２（ｋ−１）次に相当）多項式を次式（７６）のように定義する。
【数５３】
2004287333.tif 000049
【０２１８】
上記演算の結果、７次に次数を下げたｍｏｄ  ｇ（ｘ）において合同な多項式は次式（７７）のようになる。
【数５４】
2004287333.tif 000050
【０２１９】
これより、行列Ｐは次式（７８）のようになる。
【０２２０】
【数５５】
2004287333.tif 000051
【０２２１】
ステップ５において、他のメンバと通信を行って、情報ｄｉ，ｊを交換する。メンバＰｊは情報ｄｉ，ｊ（ｉ＝０，…，ｎ−１；  ｉ≠ｊ）をＰｉに配布する。この結果、メンバＰｉは（ｄｉ，０，…，ｄｉ，ｎ−１）を受け取る。
【０２２２】
ステップ６において、メンバＰｉは秘密復元の計算を行う。メンバＰｉは（ｄｉ，０，…，ｄｉ，ｎ−１）から情報Ａ，Ｂの積ＡＢの分散情報であるｄｉを式（７９）により計算する。ここでの復元操作は（ｋ’，ｎ）しきい値法における秘密復元を行う。
【数５６】
2004287333.tif 000052
【０２２３】
以上の計算を行うことで、しきい値がｋであるような、秘密情報の積ＡＢの分散情報ｄｉを得ることができる。
【０２２４】
［第６の実施形態の効果］
以上に説明したように、各メンバの行う演算は、もとの秘密情報が定義される有限体（上記説明においてはＬ次拡大体）より小さな有限体で行うことができる。これより、第５の実施形態の加算に加えて、乗算についても同様に、各メンバはより少ない計算資源で実行することが可能となる。
【０２２５】
≪第７の実施形態≫
［第７の実施形態の構成］
本発明の第７の実施形態においては、メンバ間で共有している定数Ｃと、秘密情報Ｓとの定数倍ＣＳの分散情報を計算する。しかし、同じように秘密情報の定数の積を計算する分散定数乗算を実現する第２の実施形態とは、分散情報の生成方法が異なる（第２の実施形態では、式（１９）にあるようなｋ−１次多項式から分散情報を生成し、第７の実施形態では、式（５７）にあるようなｋ−１次多項式から分散情報を生成する）ことから、構成や動作は、全く異なったものとなっている。（ｋ，ｎ）しきい値法を利用した定数倍については、自分の保持する分散情報を定数倍することで得られるが、本発明においては、定数は拡大体ＧＦ（ｑＬ）の元となりうる。このとき、定数倍の結果の分散情報が基礎体の元となるように分散計算を行う必要がある。
【０２２６】
第７の実施形態の分散定数乗算を行う場合における、分散計算部の構成を示すブロック図は、図３７のようになる。図３７において、分散定数算乗算部は、分散乗算装置３２００（図３４）及び定数情報生成部３３０１とを有する。定数情報生成部３３０１は、拡大体ＧＦ（ｑＬ）で定義された、メンバ間で共通の定数とメンバＩＤから定数の分散情報を生成する。そして、分散乗算装置は、秘密情報Ｓの分散情報と、上記定数情報生成部３３０１で生成された定数Ｃの分散情報との積を分散乗算計算部３２００で計算する。
【０２２７】
［第７の実施形態の動作］
秘密情報Ｓに対する、メンバＰｊの保持する分散情報をｓｊとする。拡大体ＧＦ（ｑＬ）で表される定数Ｃ＝（Ｃ０，…，ＣＬ−１）から、以下のようにして情報ｃｊを計算する。
ｃｊ＝Ｃ０＋Ｃ１ｗｊ＋…＋ＣＬ−１ｗｊＬ−１
定数Ｃはメンバ間で共有しているので、メンバＰｊは、自分の持つべき情報ｃｊを生成することができる。
【０２２８】
以下、分散乗算と同様の手順によって、情報ｃｊと分散情報ｓｊとをもとに、定数乗算ＣＳの分散情報を計算することができる。
【０２２９】
このとき、次数の変換は（ｋ＋Ｌ−２）次から（ｋ−１）次への変換となるので、図３６における行列Ｐの生成において、２（ｋ−１）の部分をｋ＋Ｌ−２と置き換えた図３８のようになる。この分散乗算における行列Ｐにおける非ゼロ部分をより少なくすることができ、演算量を少なくすることができる。
【０２３０】
［第７の実施形態の効果］
以上に説明したように、第５及び第６の実施形態の加算及び乗算に加えて、メンバ間で共有している、拡大体ＧＦ（ｑＬ）で表される定数についての定数倍についても同様に、各メンバはより少ない計算資源で実行することが可能となる。
【０２３１】
【発明の効果】
以上に説明したように、本発明によれば、関数ｆにおける拡大体ＧＦ（ｑＬ）上の計算を、各メンバの分散演算処理においては、その拡大体ＧＦ（ｑＬ）よりも小さな有限体ＧＦ（ｑ）上の計算のみを行うことで、達成することができるので、メンバそれぞれの分散演算処理における、演算量、演算回路に必要な回路規模、演算に必要な記憶容量、演算時間等の演算コストを削減することができるという効果がある。
【図面の簡単な説明】
【図１】本発明の第１の実施形態に係る分散計算方法を実施する構成（分散計算システム）を示すブロック図である。
【図２】マルチパーティ・プロトコルの概念説明図である。
【図３】図１の秘密再構成計算部の構成を示すブロック図である。
【図４】図１の分散処理部（分散計算装置）の構成を示すブロック図である。
【図５】図４の秘密分散計算部の構成を示すブロック図である。
【図６】図４の分散計算部の例（その１）の構成を示すブロック図である。
【図７】図４の分散計算部の例（その２）の構成を示すブロック図である。
【図８】図６又は図７の分散加算部の構成を示すブロック図である。
【図９】本発明の第１の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。
【図１０】本発明の第１の実施形態おける分散加算の動作を示すフローチャートである。
【図１１】本発明の第２の実施形態に係る分散処理部（分散計算装置）の構成を示すブロック図である。
【図１２】図１１の分散計算部の構成を示すブロック図である。
【図１３】図１２の分散定数乗算部の構成を示すブロック図である。
【図１４】本発明の第２の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。
【図１５】本発明の第２の実施形態における分散定数乗算の動作を示すフローチャートである。
【図１６】本発明の第３の実施形態における分散計算部（その１）の構成を示すブロック図である。
【図１７】本発明の第３の実施形態における分散計算部（その２）の構成を示すブロック図である。
【図１８】図１６及び図１７の分散乗算部の構成を示すブロック図である。
【図１９】図１８の紛失通信計算部の構成を示すブロック図である。
【図２０】図１９の通信計算受信部の構成を示すブロック図である。
【図２１】図１９の通信計算送信部の構成を示すブロック図である。
【図２２】本発明の第３の実施形態に係る分散計算方法を実施する構成（分散計算システム）の動作を示すフローチャートである。
【図２３】本発明の第３の実施形態における分散乗算の動作を示すフローチャートである。
【図２４】本発明の第４の実施形態に係る分散計算方法を実施する構成（分散計算システム）を示すブロック図である。
【図２５】（ａ）及び（ｂ）のそれぞれは、図２４の分散処理部（分散計算装置）の構成を示すブロック図である。
【図２６】図２５の分散処理部（分散計算装置）の変形例（その１）の構成を示すブロック図である。
【図２７】（ａ）及び（ｂ）のそれぞれは、図２５の分散処理部（分散計算装置）の変形例（その２）の構成を示すブロック図である。
【図２８】本発明の第５の実施形態に係る分散計算装置の構成を示すブロック図である。
【図２９】図２８の秘密分散部の構成を示すブロック図である。
【図３０】図２８の秘密復元部の構成を示すブロック図である。
【図３１】本発明の第５の実施形態に係る分散計算システム（その１）の構成を示すブロック図である。
【図３２】本発明の第５の実施形態に係る分散計算システム（その２）の構成を示すブロック図である。
【図３３】本発明の第５の実施形態に係る分散計算システム（その３）の構成を示すブロック図である。
【図３４】第５〜第７の実施形態の分散計算部が分散乗算を行う場合の構成を示すブロック図である。
【図３５】第５〜第７の実施形態の分散計算部が分散乗算を行う場合の処理手順を示すフローチャートである。
【図３６】第５〜第７の実施形態における変換行列の生成手順の説明図である。
【図３７】本発明の第７の実施形態における分散定数乗算部の構成を示すブロック図である。
【図３８】第７の実施形態における変換行列の生成手順の説明図である。
【符号の説明】
１０１（１０１−１，…，１０１−ｎ）  分散処理部（分散計算装置）、
１０２  秘密再構成計算部、
１０３  秘密通信路、
２０１  線形結合部、
３０１−ｉ  秘密情報記憶部、
３０２−ｉ  秘密分散計算部、
３０３−ｉ  送信部、
３０４−ｉ  受信部、
３０５−ｉ  分散計算部、
４０１−ｉ  多項式生成部、
４０２−ｉ  分散情報生成部、
４０３−ｉ  乱数生成部、
４０４−ｉ  （ｋ−１）次多項式生成部、
５０１−１，…，５０１−（ｎ−１）  分散加算部、
６０１  分散加算部、
７０１  加算部、
１００１−ｉ  秘密情報記憶部、
１００２−ｉ  秘密分散計算部、
１００３−ｉ  送信部、
１００４−ｉ  受信部、
１００５−ｉ  分散計算部、
１１０１−１，…，１１０１−ｎ  分散定数乗算部、
１１０２−１，…，１１０２−（ｎ−１）  分散加算部、
１２０１  拡大体乗算部、
１２０２  秘密分散計算部、
１２０３  送信部、
１２０４  受信部、
１２０５  加算部、
１５０１−１，…，１５０１−ｎ  分散定数乗算部、
１５０２−１，…，１５０２−（ｎ−１）  分散加算部、
１５０３  分散乗算部、
１６０１  分散乗算部、
１７０１  乗算部、
１７０２  紛失通信計算部、
１７０３  分散情報計算部、
１７０４  秘密分散計算部、
１７０５  送信部、
１７０６  受信部、
１７０７  加算部、
１８０１−１，…，１８０１−（ｉ−１）  通信計算受信部、
１８０２−１，…，１８０２−（ｉ−１）  通信計算受信部、
１８０３−（ｉ＋１），…，１８０３−ｎ  通信計算送信部、
１８０４−（ｉ＋１），…，１８０４−ｎ  通信計算送信部、
１９０１  インデックス計算送信部、
１９０２  受信復元部、
２００１  乱数生成部、
２００２  有限体要素生成部、
２００３−１，…，２００３−ｑ  乗数計算送信部、
２３０１  秘密分散送信部、
２３０２（２３０２−１，…，２３０２−ｎ）  分散処理部（分散計算装置）、
２３０３  秘密再構成計算部、
２４０１−ｉ  秘密情報記憶部、
２４０２−ｉ  秘密分散計算部、
２４０３−ｉ  送信部、
２４０４−ｉ  受信部、
２４０５−ｉ  分散計算部、
２４０６−ｉ  分散情報受信部、
２５０１−ｉ  秘密情報記憶部、
２５０２−ｉ  秘密分散計算部、
２５０３−ｉ  送信部、
２５０４−ｉ  受信部、
２５０５−ｉ  分散計算部、
２５０６−ｉ  分散情報受信部、
２５０７−ｉ  秘密再構成計算部、
３１０１  秘密分散部、
３１０２  送信部、
３１０３  受信部、
３１０４  記憶部、
３１０５  分散計算部、
３１０６  送信部、
３１０７  受信部、
３１０８  秘密復元部、
３１１１  乱数生成部、
３１１２  有限体演算部、
３１２１  復元情報生成部、
３１２２  有限体演算部、
３２００  分散乗算計算部、
３２０１  乗算部、
３２０２  秘密分散処理部、
３２０３  分散情報変換部、
３２０４  秘密復元処理部、
３３０１  定数情報生成部、
Ｘｉ  分散計算装置が保持する秘密情報、
Ｙｉ，ｊ  秘密情報Ｘｉから生成された分散情報、
Ｚ’ｉ  分散情報Ｙｉ，ｊから生成された情報（秘密Ｚの分散情報）、
Ｚ  もとの秘密、
ｈＸｉ（ｘ）  分散計算装置が生成する多項式、
ｍ１，ｍ２，…，ｍｎ  メンバＩＤ。
【図１】
2004287333.tif 000059
【図２】
2004287333.tif 000060
【図３】
2004287333.tif 000061
【図４】
2004287333.tif 000062
【図５】
2004287333.tif 000063
【図６】
2004287333.tif 000064
【図７】
2004287333.tif 000065
【図８】
2004287333.tif 000066
【図９】
2004287333.tif 000067
【図１０】
2004287333.tif 000068
【図１１】
2004287333.tif 000069
【図１２】
2004287333.tif 000070
【図１３】
2004287333.tif 000071
【図１４】
2004287333.tif 000072
【図１５】
2004287333.tif 000073
【図１６】
2004287333.tif 000074
【図１７】
2004287333.tif 000075
【図１８】
2004287333.tif 000076
【図１９】
2004287333.tif 000077
【図２０】
2004287333.tif 000078
【図２１】
2004287333.tif 000079
【図２２】
2004287333.tif 000080
【図２３】
2004287333.tif 000081
【図２４】
2004287333.tif 000082
【図２５】
2004287333.tif 000083
【図２６】
2004287333.tif 000084
【図２７】
2004287333.tif 000085
【図２８】
2004287333.tif 000086
【図２９】
2004287333.tif 000087
【図３０】
2004287333.tif 000088
【図３１】
2004287333.tif 000089
【図３２】
2004287333.tif 000090
【図３３】
2004287333.tif 000091
【図３４】
2004287333.tif 000092
【図３５】
2004287333.tif 000093
【図３６】
2004287333.tif 000094
【図３７】
2004287333.tif 000095
【図３８】
2004287333.tif 000096