(57)【要約】  ３つのパーティ（計算装置）の協調計算により秘匿積和計算を行うのに際し、高速に計算することができ、かつ、実装が容易である方法を提供する。パーティＸが、パーティＸ乱数生成ステップとパーティＸ第１計算ステップとパーティＸ第２計算ステップとを実行し、パーティＹが、パーティＹ乱数生成ステップとパーティＹ第１計算ステップとパーティＹ第２計算ステップとを実行し、パーティＺが、パーティＺ乱数生成ステップとパーティＺ第１計算ステップとパーティＺ第２計算ステップとを実行する秘匿計算方法において、各パーティの計算処理を対称に構成する。
2012102203.tif 000002
【特許請求の範囲】
【請求項１】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａ0＝（a00，…，a0na0-1）、Ａ1＝（a10，…，a1na1-1）、及びＡ2＝（a20，…，a2na2-1）と、データ列Ｂ0＝（b00，…，b0nb0-1）、Ｂ1＝（b10，…，b1nb1-1）、及びＢ2＝（b20，…，b2nb2-1）との積和計算
【数１３９】
2012102203.tif 000141
を行うために用いる秘匿積和計算方法であって、
na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01i0,j1，e10i1,j0，e00i0,j0，e11i1,j1，e12i1,j2，e21i2,j1，e22i2,j2，e20i2,j0，e02i0,j2は任意の数とし、
パーティＸにデータ列Ａ0、Ａ1、Ｂ0、Ｂ1が、パーティＹにデータ列Ａ1、Ａ2、Ｂ1、Ｂ2が、パーティＺにデータ列Ａ2、Ａ0、Ｂ2、Ｂ0が、それぞれ入力され、
パーティＸが、数ｒXを生成し、パーティＹに送信するパーティＸ乱数生成ステップと、
パーティＸが、ｃXを
【数１４０】
2012102203.tif 000142
により計算し、パーティＺに送信するパーティＸ第１計算ステップと、
パーティＸが、パーティＺから数ｒzを、パーティＹからｃYを、それぞれ受信し、ｃ0とｃ1をそれぞれ、
【数１４１】
2012102203.tif 000143
により計算して出力するパーティＸ第２計算ステップと、
パーティＹが、数ｒYを生成し、パーティＺに送信するパーティＹ乱数生成ステップと、
パーティＹが、ｃYを
【数１４２】
2012102203.tif 000144
により計算し、パーティＸに送信するパーティＹ第１計算ステップと、
パーティＹが、パーティＸから数ｒXを、パーティＺからｃZを、それぞれ受信し、ｃ1とｃ2をそれぞれ、
【数１４３】
2012102203.tif 000145
により計算して出力するパーティＹ第２計算ステップと、
パーティＺが、数ｒZを生成し、パーティＸに送信するパーティＺ乱数生成ステップと、
パーティＺが、ｃZを
【数１４４】
2012102203.tif 000146
により計算し、パーティＹに送信するパーティＺ第１計算ステップと、
パーティＺが、パーティＹから数ｒYを、パーティＸからｃXを、それぞれ受信し、ｃ0とｃ2をそれぞれ、
【数１４５】
2012102203.tif 000147
により計算して出力するパーティＺ第２計算ステップと、
を実行する秘匿積和計算方法。
【請求項２】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）、Ａq_1＝（a1q_0，…，a1q_na1-1）、及びＡq_2＝（a2q_0，…，a2q_na2-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）、Ｂq_1＝（b1q_0，…，b1q_nb1-1）、及びＢq_2＝（b2q_0，…，b2q_nb2-1）との積和計算
【数１４６】
2012102203.tif 000148
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算方法であって、
ｍを１以上の整数、na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01q_i0,q_j1，e10q_i1,q_j0，e00q_i0,q_j0，e11q_i1,q_j1，e12q_i1,q_j2，e21q_i2,q_j1，e22q_i2,q_j2，e20q_i2,q_j0，e02q_i0,q_j2は任意の数とし、
パーティＸとＹは数ｓq_Zを、パーティＹとＺは数ｓq_Xを、パーティＺとＸは数ｓq_Yを、それぞれ予め共有し、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ａq_2、Ｂq_1、Ｂq_2が、パーティＺにデータ列Ａq_2、Ａq_0、Ｂq_2、Ｂq_0が、それぞれ入力され、
パーティＸが、数ｒq_Xを生成し、パーティＹに送信するパーティＸ第１乱数生成ステップと、
パーティＸが、ｃq_Xを
【数１４７】
2012102203.tif 000149
により計算し、パーティＺに送信するパーティＸ第１計算ステップと、
パーティＸが、パーティＺから数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信し、ｃq_0とｃq_1をそれぞれ、
【数１４８】
2012102203.tif 000150
により計算するパーティＸ第２計算ステップと、
パーティＹが、数ｒq_Yを生成し、パーティＺに送信するパーティＹ第１乱数生成ステップと、
パーティＹが、ｃq_Yを
【数１４９】
2012102203.tif 000151
により計算し、パーティＸに送信するパーティＹ第１計算ステップと、
パーティＹが、パーティＸから数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、
【数１５０】
2012102203.tif 000152
により計算するパーティＹ第２計算ステップと、
パーティＺが、数ｒq_Zを生成し、パーティＸに送信するパーティＺ第１乱数生成ステップと、
パーティＺが、ｃq_Zを
【数１５１】
2012102203.tif 000153
により計算し、パーティＹに送信するパーティＺ第１計算ステップと、
パーティＺが、パーティＹから数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、
【数１５２】
2012102203.tif 000154
により計算するパーティＺ第２計算ステップと、
パーティＸが、数列（αY1q_0，…，αY1q_na1-1）及び数ρxを生成してパーティＹに送信し、数列（αZ0q_0，…，αZ0q_na0-1）を生成してパーティＺに送信するパーティＸ第２乱数生成ステップと、
パーティＸが、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を計算してパーティＹに送信し、パーティＹから数列（αX1q_0，…，αX1q_na1-1）を、パーティＺから数列（αX0q_0，…，αX0q_na0-1）を、それぞれ受信し、（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）及び
【数１５３】
2012102203.tif 000155
を計算してパーティＺに送信するパーティＸ第３計算ステップと、
パーティＸが、パーティＹから（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）を、パーティＺからρZを、それぞれ受信し、
【数１５４】
2012102203.tif 000156
を計算してパーティＹに送信するパーティＸ第４計算ステップと、
パーティＸが、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を、それぞれ受信し、
【数１５５】
2012102203.tif 000157
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力するパーティＸ不正検知ステップと、
パーティＹが、数列（αZ2q_0，…，αZ2q_na2-1）及び数ρYを生成してパーティＺに送信し、数列（αX1q_0，…，αX1q_na1-1）を生成してパーティＸに送信するパーティＹ第２乱数生成ステップと、
パーティＹが、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を計算してパーティＺに送信し、パーティＸから数列（αY1q_0，…，αY1q_na1-1）を、パーティＺから数列（αY2q_0，…，αY2q_na2-1）を、それぞれ受信し、（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）及び
【数１５６】
2012102203.tif 000158
を計算してパーティＸに送信するパーティＹ第３計算ステップと、
パーティＹが、パーティＸから数ρXを、パーティＺから（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）を、それぞれ受信し、
【数１５７】
2012102203.tif 000159
を計算してパーティＺに送信するパーティＹ第４計算ステップと、
パーティＹが、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を、パーティＺからγZを、それぞれ受信し、
【数１５８】
2012102203.tif 000160
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力するパーティＹ不正検知ステップと、
パーティＺが、数列（αX0q_0，…，αX0q_na0-1）及び数ρZを生成してパーティＸに送信し、数列（αY2q_0，…，αY2q_na2-1）を生成してパーティＹに送信するパーティＺ第２乱数生成ステップと、
パーティＺが、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を計算してパーティＸに送信し、パーティＸから数列（αZ0q_0，…，αZ0q_na0-1）を、パーティＹから数列（αZ2q_0，…，αZ2q_na2-1）を、それぞれ受信し、（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）及び
【数１５９】
2012102203.tif 000161
を計算してパーティＹに送信するパーティＺ第３計算ステップと、
パーティＺが、パーティＸから（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）を、パーティＹから数ρYを、それぞれ受信し、
【数１６０】
2012102203.tif 000162
を計算してパーティＸに送信するパーティＺ第４計算ステップと、
パーティＺが、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を、それぞれ受信し、
【数１６１】
2012102203.tif 000163
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力するパーティＺ不正検知ステップと、
を実行する秘匿積和計算方法。
【請求項３】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）、Ａq_1＝（a1q_0，…，a1q_na1-1）、及びＡq_2＝（a2q_0，…，a2q_na2-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）、Ｂq_1＝（b1q_0，…，b1q_nb1-1）、及びＢq_2＝（b2q_0，…，b2q_nb2-1）との積和計算
【数１６２】
2012102203.tif 000164
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算方法であって、
ｍを１以上の整数、na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01q_i0,q_j1，e10q_i1,q_j0，e00q_i0,q_j0，e11q_i1,q_j1，e12q_i1,q_j2，e21q_i2,q_j1，e22q_i2,q_j2，e20q_i2,q_j0，e02q_i0,q_j2は任意の数とし、
パーティＸとＹは数ｓq_Zを、パーティＹとＺは数ｓq_Xを、パーティＺとＸは数ｓq_Yを、それぞれ予め共有し、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ａq_2、Ｂq_1、Ｂq_2が、パーティＺにデータ列Ａq_2、Ａq_0、Ｂq_2、Ｂq_0が、それぞれ入力され、
パーティＸが、数ｒq_Xを生成し、パーティＹに送信するパーティＸ第１乱数生成ステップと、
パーティＸが、ｃq_Xを
【数１６３】
2012102203.tif 000165
により計算し、パーティＺに送信するパーティＸ第１計算ステップと、
パーティＸが、パーティＺから数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信し、ｃq_0とｃq_1をそれぞれ、
【数１６４】
2012102203.tif 000166
により計算するパーティＸ第２計算ステップと、
パーティＹが、数ｒq_Yを生成し、パーティＺに送信するパーティＹ第１乱数生成ステップと、
パーティＹが、ｃq_Yを
【数１６５】
2012102203.tif 000167
により計算し、パーティＸに送信するパーティＹ第１計算ステップと、
パーティＹが、パーティＸから数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、
【数１６６】
2012102203.tif 000168
により計算するパーティＹ第２計算ステップと、
パーティＺが、数ｒq_Zを生成し、パーティＸに送信するパーティＺ第１乱数生成ステップと、
パーティＺが、ｃq_Zを
【数１６７】
2012102203.tif 000169
により計算し、パーティＹに送信するパーティＺ第１計算ステップと、
パーティＺが、パーティＹから数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、
【数１６８】
2012102203.tif 000170
により計算するパーティＺ第２計算ステップと、
パーティＸが、数ρxを生成してパーティＹに送信し、数列（αZ0q_0，…，αZ0q_na0-1）と数列（βZ0q_0，…，βZ0q_nb0-1）を生成してパーティＺに送信するパーティＸ第２乱数生成ステップと、
パーティＸが、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を計算してパーティＹに送信し、パーティＹから数列（αX1q_0，…，αX1q_na1-1）と数列（βX1q_0，…，βX1q_nb1-1）を受信し、
【数１６９】
2012102203.tif 000171
を計算してパーティＺに送信するパーティＸ第３計算ステップと、
パーティＸが、パーティＺからρZを受信し、
【数１７０】
2012102203.tif 000172
を計算してパーティＹに送信するパーティＸ第４計算ステップと、
パーティＸが、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を、それぞれ受信し、
【数１７１】
2012102203.tif 000173
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力するパーティＸ不正検知ステップと、
パーティＹが、数ρYを生成してパーティＺに送信し、数列（αX1q_0，…，αX1q_na1-1）と数列（βX1q_0，…，βX1q_nb1-1）を生成してパーティＸに送信するパーティＹ第２乱数生成ステップと、
パーティＹが、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を計算してパーティＺに送信し、パーティＺから数列（αY2q_0，…，αY2q_na2-1）と数列（βY2q_0，…，βY2q_nb2-1）を受信し、
【数１７２】
2012102203.tif 000174
を計算してパーティＸに送信するパーティＹ第３計算ステップと、
パーティＹが、パーティＸから数ρXを受信し、
【数１７３】
2012102203.tif 000175
を計算してパーティＺに送信するパーティＹ第４計算ステップと、
パーティＹが、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を、パーティＺからγZを、それぞれ受信し、
【数１７４】
2012102203.tif 000176
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力するパーティＹ不正検知ステップと、
パーティＺが、数ρZを生成してパーティＸに送信し、数列（αY2q_0，…，αY2q_na2-1）と数列（βY2q_0，…，βY2q_nb2-1）を生成してパーティＹに送信するパーティＺ第２乱数生成ステップと、
パーティＺが、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を計算してパーティＸに送信し、パーティＸから数列（αZ0q_0，…，αZ0q_na0-1）と数列（βZ0q_0，…，βZ0q_nb0-1）を受信し、
【数１７５】
2012102203.tif 000177
を計算してパーティＹに送信するパーティＺ第３計算ステップと、
パーティＺが、パーティＹから数ρYを受信し、
【数１７６】
2012102203.tif 000178
を計算してパーティＸに送信するパーティＺ第４計算ステップと、
パーティＺが、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を、それぞれ受信し、
【数１７７】
2012102203.tif 000179
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力するパーティＺ不正検知ステップと、
を実行する秘匿積和計算方法。
【請求項４】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）及びＡq_1＝（a1q_0，…，a1q_na1-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）及びＢq_1＝（b1q_0，…，b1q_nb1-1）との積和計算
【数１７８】
2012102203.tif 000180
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算方法であって、
ｍを１以上の整数、na0，na1，nb0，nb1を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１とし、
e01q_i0,q_j1，e10q_i1,q_j0は任意の数とし、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ｂq_1が、パーティＺにデータ列Ａq_0、Ｂq_0が、それぞれ入力され、
パーティＸが、数cq_１と数γ1と数列（α1q_0，…，α1q_nb0-1）と数列（β1q_0，…，β1q_na0-1）を生成してパーティＹに送信するパーティＸ乱数生成ステップと、
パーティＹが、数ｓqを生成してパーティＺに送信するパーティＹ乱数生成ステップと、
パーティＸが、cq_0とγ0を、
【数１７９】
2012102203.tif 000181
により計算し、パーティＺに送信するパーティＸ計算ステップと、
パーティＹが、パーティＸから数cq_１と数γ1と数列（α1q_0，…，α1q_nb0-1）と数列（β1q_0，…，β1q_na0-1）を受信し、数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´をそれぞれ、
【数１８０】
2012102203.tif 000182
により計算し、パーティＺに送信するパーティＹ計算ステップと、
パーティＺが、パーティＸからcq_0とγ0を、パーティＹから数ｓqと数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´を、それぞれ受信し、
【数１８１】
2012102203.tif 000183
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了する不正検知ステップと、
を実行し、不正検知ステップでの計算結果が０であればパーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する秘匿積和計算方法。
【請求項５】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データa0及びa1と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）及びＢq_1＝（b1q_0，…，b1q_nb1-1）との積和計算
【数１８２】
2012102203.tif 000184
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算方法であって、
ｍを１以上の整数、ｎを自然数、ｉ＝０，…，ｎ−１とし、
パーティＸにデータa0及びa1と、データ列Ｂq_0及びＢq_1とが、パーティＹにデータa1とデータ列Ｂq_1が、パーティＺにデータa0とデータ列Ｂq_0が、それぞれ入力され、
パーティＸが、数cq_１と数γ1と数列（α1q_0，…，α1q_n-1）と数β1を生成してパーティＹに送信するパーティＸ乱数生成ステップと、
パーティＹが、数ｓqを生成してパーティＺに送信するパーティＹ乱数生成ステップと、
パーティＸが、cq_0とγ0を、
【数１８３】
2012102203.tif 000185
により計算し、パーティＺに送信するパーティＸ計算ステップと、
パーティＹが、パーティＸから数cq_１と数γ1と数列（α1q_0，…，α1q_n-1）と数β1を受信し、数列（α0q_0，…，α0q_n-1）とβ0とγ´をそれぞれ、
【数１８４】
2012102203.tif 000186
により計算し、パーティＺに送信するパーティＹ計算ステップと、
パーティＺが、パーティＸからcq_0とγ0を、パーティＹから数ｓqと数列（α0q_0，…，α0q_n-1）とβ0とγ´を、それぞれ受信し、
【数１８５】
2012102203.tif 000187
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了する不正検知ステップと、
を実行し、不正検知ステップでの計算結果が０であればパーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する秘匿積和計算方法。
【請求項６】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａ0＝（a00，…，a0na0-1）、Ａ1＝（a10，…，a1na1-1）、及びＡ2＝（a20，…，a2na2-1）と、データ列Ｂ0＝（b00，…，b0nb0-1）、Ｂ1＝（b10，…，b1nb1-1）、及びＢ2＝（b20，…，b2nb2-1）との積和計算
【数１８６】
2012102203.tif 000188
を行うために用いる秘匿積和計算システムであって、
na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01i0,j1，e10i1,j0，e00i0,j0，e11i1,j1，e12i1,j2，e21i2,j1，e22i2,j2，e20i2,j0，e02i0,j2は任意の数とし、
パーティＸにデータ列Ａ0、Ａ1、Ｂ0、Ｂ1が、パーティＹにデータ列Ａ1、Ａ2、Ｂ1、Ｂ2が、パーティＺにデータ列Ａ2、Ａ0、Ｂ2、Ｂ0が、それぞれ入力され、
パーティＸは、パーティＸ乱数生成手段とパーティＸ第１計算手段とパーティＸ第２計算手段とを有し、パーティＸ乱数生成手段は、数ｒXを生成してパーティＹに送信し、パーティＸ第１計算手段は、ｃXを
【数１８７】
2012102203.tif 000189
により計算してパーティＺに送信し、パーティＸ第２計算手段は、パーティＺから数ｒzを、パーティＹからｃYを、それぞれ受信し、ｃ0とｃ1をそれぞれ、
【数１８８】
2012102203.tif 000190
により計算し、
パーティＹは、パーティＹ乱数生成手段とパーティＹ第１計算手段とパーティＹ第２計算手段とを有し、パーティＹ乱数生成手段は、数ｒYを生成してパーティＺに送信し、パーティＹ第１計算手段は、ｃYを
【数１８９】
2012102203.tif 000191
により計算してパーティＸに送信し、パーティＹ第２計算手段は、パーティＸから数ｒXを、パーティＺからｃZを、それぞれ受信し、ｃ1とｃ2をそれぞれ、
【数１９０】
2012102203.tif 000192
により計算し、
パーティＺは、パーティＺ乱数生成手段とパーティＺ第１計算手段とパーティＺ第２計算手段とを有し、パーティＺ乱数生成手段は、数ｒZを生成してパーティＸに送信し、パーティＺ第１計算手段は、ｃZを
【数１９１】
2012102203.tif 000193
により計算してパーティＹに送信し、パーティＺ第２計算手段は、パーティＹから数ｒYを、パーティＸからｃXを、それぞれ受信し、ｃ0とｃ2をそれぞれ、
【数１９２】
2012102203.tif 000194
により計算する
秘匿積和計算システム。
【請求項７】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）、Ａq_1＝（a1q_0，…，a1q_na1-1）、及びＡq_2＝（a2q_0，…，a2q_na2-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）、Ｂq_1＝（b1q_0，…，b1q_nb1-1）、及びＢq_2＝（b2q_0，…，b2q_nb2-1）との積和計算
【数１９３】
2012102203.tif 000195
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算システムであって、
ｍを１以上の整数、na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01q_i0,q_j1，e10q_i1,q_j0，e00q_i0,q_j0，e11q_i1,q_j1，e12q_i1,q_j2，e21q_i2,q_j1，e22q_i2,q_j2，e20q_i2,q_j0，e02q_i0,q_j2は任意の数とし、
パーティＸとＹは数ｓq_Zを、パーティＹとＺは数ｓq_Xを、パーティＺとＸは数ｓq_Yを、それぞれ予め共有し、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ａq_2、Ｂq_1、Ｂq_2が、パーティＺにデータ列Ａq_2、Ａq_0、Ｂq_2、Ｂq_0が、それぞれ入力され、
パーティＸは、パーティＸ第１乱数生成手段とパーティＸ第１計算手段とパーティＸ第２計算手段とパーティＸ第２乱数生成手段とパーティＸ第３計算手段とパーティＸ第４計算手段とパーティＸ不正検知手段とを有し、パーティＸ第１乱数生成手段は、数ｒq_Xを生成してパーティＹに送信し、パーティＸ第１計算手段は、ｃq_Xを
【数１９４】
2012102203.tif 000196
により計算してパーティＺに送信し、パーティＸ第２計算手段は、パーティＺから数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信してｃq_0とｃq_1をそれぞれ、
【数１９５】
2012102203.tif 000197
により計算し、パーティＸ第２乱数生成手段は、数列（αY1q_0，…，αY1q_na1-1）及び数ρxを生成してパーティＹに送信し、数列（αZ0q_0，…，αZ0q_na0-1）を生成してパーティＺに送信し、パーティＸ第３計算手段は、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を計算してパーティＹに送信し、パーティＹから数列（αX1q_0，…，αX1q_na1-1）を、パーティＺから数列（αX0q_0，…，αX0q_na0-1）を、それぞれ受信し、（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）及び
【数１９６】
2012102203.tif 000198
を計算してパーティＺに送信し、パーティＸ第４計算手段は、パーティＹから（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）を、パーティＺからρZを、それぞれ受信し、
【数１９７】
2012102203.tif 000199
を計算してパーティＹに送信し、パーティＸ不正検知手段は、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を、それぞれ受信し、
【数１９８】
2012102203.tif 000200
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力し、
パーティＹは、パーティＹ第１乱数生成手段とパーティＹ第１計算手段とパーティＹ第２計算手段とパーティＹ第２乱数生成手段とパーティＹ第３計算手段とパーティＹ第４計算手段とパーティＹ不正検知手段とを有し、パーティＹ第１乱数生成手段は、数ｒq_Yを生成してパーティＺに送信し、パーティＹ第１計算手段は、ｃq_Yを
【数１９９】
2012102203.tif 000201
により計算してパーティＸに送信し、パーティＹ第２計算手段は、パーティＸから数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、
【数２００】
2012102203.tif 000202
により計算し、パーティＹ第２乱数生成手段は、数列（αZ2q_0，…，αZ2q_na2-1）及び数ρYを生成してパーティＺに送信し、数列（αX1q_0，…，αX1q_na1-1）を生成してパーティＸに送信し、パーティＹ第３計算手段は、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を計算してパーティＺに送信し、パーティＸから数列（αY1q_0，…，αY1q_na1-1）を、パーティＺから数列（αY2q_0，…，αY2q_na2-1）を、それぞれ受信し、（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）及び
【数２０１】
2012102203.tif 000203
を計算してパーティＸに送信し、パーティＹ第４計算手段は、パーティＸから数ρXを、パーティＺから（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）を、それぞれ受信し、
【数２０２】
2012102203.tif 000204
を計算してパーティＺに送信し、パーティＹ不正検知手段は、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を、パーティＺからγZを、それぞれ受信し、
【数２０３】
2012102203.tif 000205
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力し、
パーティＺは、パーティＺ第１乱数生成手段とパーティＺ第１計算手段とパーティＺ第２計算手段とパーティＺ第２乱数生成手段とパーティＺ第３計算手段とパーティＺ第４計算手段とパーティＺ不正検知手段とを有し、パーティＺ第１乱数生成手段は、数ｒq_Zを生成してパーティＸに送信し、パーティＺ第１計算手段は、ｃq_Zを
【数２０４】
2012102203.tif 000206
により計算してパーティＹに送信し、パーティＺ第２計算手段は、パーティＹから数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、
【数２０５】
2012102203.tif 000207
により計算し、パーティＺ第２乱数生成手段は、数列（αX0q_0，…，αX0q_na0-1）及び数ρZを生成してパーティＸに送信し、数列（αY2q_0，…，αY2q_na2-1）を生成してパーティＹに送信し、パーティＺ第３計算手段は、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を計算してパーティＸに送信し、パーティＸから数列（αZ0q_0，…，αZ0q_na0-1）を、パーティＹから数列（αZ2q_0，…，αZ2q_na2-1）を、それぞれ受信し、（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）及び
【数２０６】
2012102203.tif 000208
を計算してパーティＹに送信し、パーティＺ第４計算手段は、パーティＸから（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）を、パーティＹから数ρYを、それぞれ受信し、
【数２０７】
2012102203.tif 000209
を計算してパーティＸに送信し、パーティＺ不正検知手段は、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を、それぞれ受信し、
【数２０８】
2012102203.tif 000210
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する
秘匿積和計算システム。
【請求項８】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）、Ａq_1＝（a1q_0，…，a1q_na1-1）、及びＡq_2＝（a2q_0，…，a2q_na2-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）、Ｂq_1＝（b1q_0，…，b1q_nb1-1）、及びＢq_2＝（b2q_0，…，b2q_nb2-1）との積和計算
【数２０９】
2012102203.tif 000211
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算システムであって、
ｍを１以上の整数、na0，na1，na2，nb0，nb1，nb2を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１とし、
e01q_i0,q_j1，e10q_i1,q_j0，e00q_i0,q_j0，e11q_i1,q_j1，e12q_i1,q_j2，e21q_i2,q_j1，e22q_i2,q_j2，e20q_i2,q_j0，e02q_i0,q_j2は任意の数とし、
パーティＸとＹは数ｓq_Zを、パーティＹとＺは数ｓq_Xを、パーティＺとＸは数ｓq_Yを、それぞれ予め共有し、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ａq_2、Ｂq_1、Ｂq_2が、パーティＺにデータ列Ａq_2、Ａq_0、Ｂq_2、Ｂq_0が、それぞれ入力され、
パーティＸは、パーティＸ第１乱数生成手段とパーティＸ第１計算手段とパーティＸ第２計算手段とパーティＸ第２乱数生成手段とパーティＸ第３計算手段とパーティＸ第４計算手段とパーティＸ不正検知手段とを有し、パーティＸ第１乱数生成手段は、数ｒq_Xを生成してパーティＹに送信し、パーティＸ第１計算手段は、ｃq_Xを
【数２１０】
2012102203.tif 000212
により計算してパーティＺに送信し、パーティＸ第２計算手段は、パーティＺから数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信してｃq_0とｃq_1をそれぞれ、
【数２１１】
2012102203.tif 000213
により計算し、パーティＸ第２乱数生成手段は、数ρxを生成してパーティＹに送信し、数列（αZ0q_0，…，αZ0q_na0-1）と数列（βZ0q_0，…，βZ0q_nb0-1）を生成してパーティＺに送信し、パーティＸ第３計算手段は、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を計算してパーティＹに送信し、パーティＹから数列（αX1q_0，…，αX1q_na1-1）と数列（βX1q_0，…，βX1q_nb1-1）を受信し、
【数２１２】
2012102203.tif 000214
を計算してパーティＺに送信し、パーティＸ第４計算手段は、パーティＺからρZを受信し、
【数２１３】
2012102203.tif 000215
を計算してパーティＹに送信し、パーティＸ不正検知手段は、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を、それぞれ受信し、
【数２１４】
2012102203.tif 000216
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力し、
パーティＹは、パーティＹ第１乱数生成手段とパーティＹ第１計算手段とパーティＹ第２計算手段とパーティＹ第２乱数生成手段とパーティＹ第３計算手段とパーティＹ第４計算手段とパーティＹ不正検知手段とを有し、パーティＹ第１乱数生成手段は、数ｒq_Yを生成してパーティＺに送信し、パーティＹ第１計算手段は、ｃq_Yを
【数２１５】
2012102203.tif 000217
により計算してパーティＸに送信し、パーティＹ第２計算手段は、パーティＸから数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、
【数２１６】
2012102203.tif 000218
により計算し、パーティＹ第２乱数生成手段は、数ρYを生成してパーティＺに送信し、数列（αX1q_0，…，αX1q_na1-1）と数列（βX1q_0，…，βX1q_nb1-1）を生成してパーティＸに送信し、パーティＹ第３計算手段は、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を計算してパーティＺに送信し、パーティＺから数列（αY2q_0，…，αY2q_na2-1）と数列（βY2q_0，…，βY2q_nb2-1）を受信し、
【数２１７】
2012102203.tif 000219
を計算してパーティＸに送信し、パーティＹ第４計算手段は、パーティＸから数ρXを受信し、
【数２１８】
2012102203.tif 000220
を計算してパーティＺに送信し、パーティＹ不正検知手段は、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を、パーティＺからγZを、それぞれ受信し、
【数２１９】
2012102203.tif 000221
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力し、
パーティＺは、パーティＺ第１乱数生成手段とパーティＺ第１計算手段とパーティＺ第２計算手段とパーティＺ第２乱数生成手段とパーティＺ第３計算手段とパーティＺ第４計算手段とパーティＺ不正検知手段とを有し、パーティＺ第１乱数生成手段は、数ｒq_Zを生成してパーティＸに送信し、パーティＺ第１計算手段は、ｃq_Zを
【数２２０】
2012102203.tif 000222
により計算してパーティＹに送信し、パーティＺ第２計算手段は、パーティＹから数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、
【数２２１】
2012102203.tif 000223
により計算し、パーティＺ第２乱数生成手段は、数ρZを生成してパーティＸに送信し、数列（αY2q_0，…，αY2q_na2-1）と数列（βY2q_0，…，βY2q_nb2-1）を生成してパーティＹに送信し、パーティＺ第３計算手段は、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を計算してパーティＸに送信し、パーティＸから数列（αZ0q_0，…，αZ0q_na0-1）と数列（βZ0q_0，…，βZ0q_nb0-1）を受信し、
【数２２２】
2012102203.tif 000224
を計算してパーティＹに送信し、パーティＺ第４計算手段は、パーティＹから数ρYを受信し、
【数２２３】
2012102203.tif 000225
を計算してパーティＸに送信し、パーティＺ不正検知手段は、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を、それぞれ受信し、
【数２２４】
2012102203.tif 000226
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する
秘匿積和計算システム。
【請求項９】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）及びＡq_1＝（a1q_0，…，a1q_na1-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）及びＢq_1＝（b1q_0，…，b1q_nb1-1）との積和計算
【数２２５】
2012102203.tif 000227
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算システムであって、
ｍを１以上の整数、na0，na1，nb0，nb1を自然数、i0＝０，…，na0−１、i1＝０，…，na1−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１とし、
e01q_i0,q_j1，e10q_i1,q_j0は任意の数とし、
パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹにデータ列Ａq_1、Ｂq_1が、パーティＺにデータ列Ａq_0、Ｂq_0が、それぞれ入力され、
パーティＸは、パーティＸ乱数生成手段とパーティＸ計算手段とを有し、パーティＸ乱数生成手段は、数cq_１と数γ1と数列（α1q_0，…，α1q_nb0-1）と数列（β1q_0，…，β1q_na0-1）を生成してパーティＹに送信し、パーティＸ計算手段は、cq_0とγ0を、
【数２２６】
2012102203.tif 000228
により計算してパーティＺに送信し、
パーティＹは、パーティＹ乱数生成手段とパーティＹ計算手段とを有し、パーティＹ乱数生成手段は、数ｓqを生成してパーティＺに送信し、パーティＹ計算手段は、パーティＸから数cq_１と数γ1と数列（α1q_0，…，α1q_nb0-1）と数列（β1q_0，…，β1q_na0-1）を受信し、数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´をそれぞれ、
【数２２７】
2012102203.tif 000229
により計算してパーティＺに送信し、
パーティＺは、不正検知手段を備え、パーティＸからcq_0とγ0を、パーティＹから数ｓqと数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´を、それぞれ受信し、
【数２２８】
2012102203.tif 000230
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、
不正検知手段での計算結果が０であれば、パーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する
秘匿積和計算システム。
【請求項１０】
パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データa0及びa1と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）及びＢq_1＝（b1q_0，…，b1q_nb1-1）との積和計算
【数２２９】
2012102203.tif 000231
を、ｑ＝０，…，ｍ−１の計ｍ組について、並列に行うために用いる秘匿積和計算システムであって、
ｍを１以上の整数、ｎを自然数、ｉ＝０，…，ｎ−１とし、
パーティＸにデータa0及びa1と、データ列Ｂq_0及びＢq_1とが、パーティＹにデータa1とデータ列Ｂq_1が、パーティＺにデータa0とデータ列Ｂq_0が、それぞれ入力され、
パーティＸは、パーティＸ乱数生成手段とパーティＸ計算手段とを有し、パーティＸ乱数生成手段は、数cq_１と数γ1と数列（α1q_0，…，α1q_n-1）と数β1を生成してパーティＹに送信し、パーティＸ計算手段は、cq_0とγ0を、
【数２３０】
2012102203.tif 000232
により計算してパーティＺに送信し、
パーティＹは、パーティＹ乱数生成手段とパーティＹ計算手段とを有し、パーティＹ乱数生成手段は、数ｓqを生成してパーティＺに送信し、パーティＹ計算手段は、パーティＸから数cq_１と数γ1と数列（α1q_0，…，α1q_n-1）と数β1を受信し、数列（α0q_0，…，α0q_n-1）とβ0とγ´をそれぞれ、
【数２３１】
2012102203.tif 000233
により計算し、パーティＺに送信し、
パーティＺは、不正検知手段を備え、パーティＸからcq_0とγ0を、パーティＹから数ｓqと数列（α0q_0，…，α0q_n-1）とβ0とγ´を、それぞれ受信し、
【数２３２】
2012102203.tif 000234
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、
不正検知手段での計算結果が０であればパーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する
秘匿積和計算システム。
【請求項１１】
処理が対称なパーティＸ、パーティＹ、パーティＺの３つの計算装置で協調して積和計算をする際に用いる前記計算装置であって、
いずれかの前記計算装置がパーティＰであるとしたとき、パーティＰがパーティＸである場合には、パーティＺがパーティＰ−、パーティＹがパーティＰ＋、符号0p、1pがそれぞれ０、１であるとし、パーティＰがパーティＹである場合には、パーティＸがパーティＰ−、パーティＺがパーティＰ＋、符号0p、1pがそれぞれ１、２であるとし、パーティＰがパーティＺである場合には、パーティＹがパーティＰ−、パーティＸがパーティＰ＋、符号0p、1pがそれぞれ２、０であるとし、
na0p，na1p，nb0p，nb1pを自然数、i0p＝０，…，na0p−１、i1p＝０，…，na1p−１、j0p＝０，…，nb0p−１、j1p＝０，…，nb1p−１とし、
e0p1pi0p,j1p，e1p0pi1p,j0p，e0p0pi0p,j0p，e1p1pi1p,j1pは任意の数とし、
前記パーティＰは、
数ｒPを生成してパーティＰ＋に送信する乱数生成手段と、
データ列Ａ0p＝（a0p0，…，a0pna0p-1）とデータ列Ａ1p＝（a1p0，…，a1pna1p-1）とデータ列Ｂ0p＝（b0p0，…，b0pnb0p-1）とデータ列Ｂ1p＝（b1p0，…，b1pnb1p-1）とが入力され、ｃPを
【数２３３】
2012102203.tif 000235
により計算してパーティＰ−に送信する第１計算手段と、
パーティＰ−から数ｒP-を、パーティＰ＋からｃP+を、それぞれ受信し、ｃ0pとｃ1pをそれぞれ、
【数２３４】
2012102203.tif 000236
により計算する第２計算手段と、
を備える計算装置。
【請求項１２】
処理が対称なパーティＸ、パーティＹ、パーティＺの３つの計算装置で協調して積和計算をする際に用いる前記計算装置であって、
いずれかの前記計算装置がパーティＰであるとしたとき、パーティＰがパーティＸである場合には、パーティＺがパーティＰ−、パーティＹがパーティＰ＋、符号0p、1p、2pがそれぞれ0、1、2であるとし、パーティＰがパーティＹである場合には、パーティＸがパーティＰ−、パーティＺがパーティＰ＋、符号0p、1p、2pがそれぞれ1、2、0であるとし、パーティＰがパーティＺである場合には、パーティＹがパーティＰ−、パーティＸがパーティＰ＋、符号0p、1p、2pがそれぞれ2、0、1であるとし、
ｍを１以上の整数、na0p，na1p，na2p，nb0p，nb1pを自然数、ｑ＝０，…，ｍ−１、i0p＝０，…，na0p−１、i1p＝０，…，na1p−１、i2p＝０，…，na2p−１、j0p＝０，…，nb0p−１、j1p＝０，…，nb1p−１とし、
e0p1pi0p,j1p，e1p0pi1p,j0p，e0p0pi0p,j0p，e1p1pi1p,j1pは任意の数とし、
パーティＰ−とＰは数ｓq_P+を、パーティＰとＰ＋は数ｓq_P-を、パーティＰ＋とＰ−は数ｓq_Pを、それぞれ予め共有し、
パーティＰは、
数ｒq_Pを生成してパーティＰ＋に送信する第１乱数生成手段と、
データ列Ａq_0p＝（a0pq_0，…，a0pq_na0p-1）とデータ列Ａq_1p＝（a1pq_0，…，a1pq_na1p-1）とデータ列Ｂq_0p＝（b0pq_0，…，b0pq_nb0p-1）とデータ列Ｂq_1p＝（b1pq_0，…，b1pq_nb1p-1）とが入力され、ｃq_Pを
【数２３５】
2012102203.tif 000237
により計算してパーティＰ−に送信する第１計算手段と、
パーティＰ−から数ｒq_P-を、パーティＰ＋からｃq_P+を、それぞれ受信してｃq_0pとｃq_1pをそれぞれ、
【数２３６】
2012102203.tif 000238
により計算する第２計算手段と、
数列（αP+1pq_0，…，αP+1pq_na1p-1）及び数ρPを生成してパーティＰ＋に送信し、数列（αP-0pq_0，…，αP-0pq_na0p-1）を生成してパーティＰ−に送信する第２乱数生成手段と、
（αP-0pq_0−ｓq_P-・a0pq_0，…，αP-0pq_na0p-1−ｓq_P-・a0pq_na0p-1）を計算してパーティＰ＋に送信し、パーティＰ＋から数列（αP1pq_0，…，αP1pq_na1p-1）を、パーティＰ−から数列（αP0pq_0，…，αP0pq_na0p-1）を、それぞれ受信し、（αP+1pq_0−ｓq_P+・a1pq_0，…，αP+1pq_na1p-1−ｓq_P+・a1pq_na1p-1）及び
【数２３７】
2012102203.tif 000239
を計算してパーティＰ−に送信する第３計算手段と、
パーティＰ＋から（αP-2pq_0−ｓq_P-・a2pq_0，…，αP-2pq_na2p-1−ｓq_P-・a2pq_na2p-1）を、パーティＰ−からρP-を、それぞれ受信し、
【数２３８】
2012102203.tif 000240
を計算してパーティＰ＋に送信する第４計算手段と、
パーティＰ＋からγP+を、パーティＰ-からγ´P+と（αP+2pq_0−ｓq_P+・a2pq_0，…，αP+2pq_na2p-1−ｓq_P+・a2pq_na2p-1）を、それぞれ受信し、
【数２３９】
2012102203.tif 000241
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0pとｃq_1pを出力する不正検知手段と、
を備える計算装置。
【請求項１３】
処理が対称なパーティＸ、パーティＹ、パーティＺの３つの計算装置で協調して積和計算をする際に用いる前記計算装置であって、
いずれかの前記計算装置がパーティＰであるとしたとき、パーティＰがパーティＸである場合には、パーティＺがパーティＰ−、パーティＹがパーティＰ＋、符号0p、1p、2pがそれぞれ0、1、2であるとし、パーティＰがパーティＹである場合には、パーティＸがパーティＰ−、パーティＺがパーティＰ＋、符号0p、1p、2pがそれぞれ1、2、0であるとし、パーティＰがパーティＺである場合には、パーティＹがパーティＰ−、パーティＸがパーティＰ＋、符号0p、1p、2pがそれぞれ2、0、1であるとし、
ｍを１以上の整数、na0p，na1p，na2p，nb0p，nb1p，nb2pを自然数、ｑ＝０，…，ｍ−１、i0p＝０，…，na0p−１、i1p＝０，…，na1p−１、i2p＝０，…，na2p−１、j0p＝０，…，nb0p−１、j1p＝０，…，nb1p−１、j2p＝０，…，nb2p−１とし、
e0p1pi0p,j1p，e1p0pi1p,j0p，e0p0pi0p,j0p，e1p1pi1p,j1pは任意の数とし、
パーティＰ−とＰは数ｓq_P+を、パーティＰとＰ＋は数ｓq_P-を、パーティＰ＋とＰ−は数ｓq_Pを、それぞれ予め共有し、
パーティＰは、
数ｒq_Pを生成してパーティＰ＋に送信する第１乱数生成手段と、
データ列Ａq_0p＝（a0pq_0，…，a0pq_na0p-1）とデータ列Ａq_1p＝（a1pq_0，…，a1pq_na1p-1）とデータ列Ｂq_0p＝（b0pq_0，…，b0pq_nb0p-1）とデータ列Ｂq_1p＝（b1pq_0，…，b1pq_nb1p-1）とが入力され、ｃq_Pを
【数２４０】
2012102203.tif 000242
により計算してパーティＰ−に送信する第１計算手段と、
パーティＰ−から数ｒq_P-を、パーティＰ＋からｃq_P+を、それぞれ受信してｃq_0pとｃq_1pをそれぞれ、
【数２４１】
2012102203.tif 000243
により計算する第２計算手段と、
数ρPを生成してパーティＰ＋に送信し、数列（αP-0pq_0，…，αP-0pq_na0p-1）と数列（βP-0pq_0，…，βP-0pq_nb0p-1）を生成してパーティＰ−に送信する第２乱数生成手段と、
（αP-0pq_0−ｓq_P-・a0pq_0，…，αP-0pq_na0p-1−ｓq_P-・a0pq_na0p-1）と（βP-0pq_0−ｓq_P-・b0pq_0，…，βP-0pq_na0p-1−ｓq_P-・b0pq_na0p-1）を計算してパーティＰ＋に送信し、パーティＰ＋から数列（αP1pq_0，…，αP1pq_na1p-1）と数列（βP1pq_0，…，βP1pq_nb1p-1）を受信し、
【数２４２】
2012102203.tif 000244
を計算してパーティＰ−に送信する第３計算手段と、
パーティＰ−からρP-を受信し、
【数２４３】
2012102203.tif 000245
を計算してパーティＰ＋に送信する第４計算手段と、
パーティＰ＋からγP+を、パーティＰ-からγ´P+と（αP+2pq_0−ｓq_P+・a2pq_0，…，αP+2pq_na2p-1−ｓq_P+・a2pq_na2p-1）と（βP+2pq_0−ｓq_P+・b2pq_0，…，βP+2pq_na2p-1−ｓq_P+・b2pq_na2p-1）を、それぞれ受信し、
【数２４４】
2012102203.tif 000246
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0pとｃq_1pを出力する不正検知手段と、
を備える計算装置。
【請求項１４】
請求項６乃至１０のいずれかに記載の秘匿積和計算システム又は請求項１１乃至１３のいずれかに記載の計算装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、秘密分散によりデータを秘匿しつつ、データ処理、特に乗算及び積和演算を行う秘匿積和計算方法、秘匿積和計算システム、計算装置、及びそれらのプログラムに関する。
【背景技術】
【０００２】
顧客情報や経営情報等、いわゆるセンシティブ情報の管理・運用においては、管理情報の多様化やクラウドコンピューティング等の情報処理基盤の変化に伴い、セキュリティ対策やプライバシーの配慮が一層重要な課題となっている。その中で、最近では情報を複数個所に分散させて情報漏洩を防ぐ、秘密分散技術の普及が進みつつある。更に、分散された情報を復元することなく指定された計算結果を導く秘匿関数計算（マルチパーティプロトコル）についても実用化を見据えて開発が進められている。秘密分散技術は、情報の保管時のセキュリティ対策としては有効であるが、利用時は一般に復元する必要があるため、漏洩リスクが高まる。秘匿関数計算は、このような漏洩リスクの存在を踏まえ、本来の入力値の代わりに分散された情報を計算の入力とでき、計算過程においても本来の入力値が一切復元されないため、秘密分散技術の機能を情報の利用時にも維持したより高度なセキュリティ技術といえる。【０００３】
情報を秘匿しつつ乗算及び積和演算を行う従来技術としては、乗算に関しては非特許文献１の乗算プロトコルが、また、積和演算に関しては乗算プロトコルと加算プロトコルとの複合利用が挙げられる。これらのプロトコルは、分散された入力値を復元することなく、３パーティ（３計算主体）の協調計算によって算術／論理演算の結果を導く３パーティ秘匿関数計算プロトコルである。３パーティ秘匿関数計算プロトコルでは、データをある定められた素数ｐ未満の自然数として扱う。データを秘匿するときには、そのデータをａとすれば、ａを以下の条件を満たすよう３つに分散する。
ａ＝ａ0＋ａ1＋ａ2 mod p
実際には乱数ａ0、ａ1を生成し、ａ2＝ａ−ａ0−ａ1とする。そして３パーティＸ、Ｙ、Ｚに対して、Ｘに（ａ0、ａ1）、Ｙに（ａ1、ａ2）、Ｚに（ａ2、ａ0）を送信する。すると、ａ1、ａ2が乱数であったため、Ｘ、Ｙ、Ｚのいずれのパーティもａの情報を持たないが、いずれか２パーティが集まればａを復元することができることとなる。【０００４】
秘匿が加法的な分散であるため、可換性から、分散値を加算してから復元しても、復元してから加算しても結果は等しい。すなわち、加算及び定数倍は分散したまま通信なしで行うことが可能である。そして、これに乗算が加われば論理回路を構成でき、いかなる計算を実行することも可能となる。この乗算は通信及び乱数生成が必要なので、３パーティ秘匿関数計算のボトルネックとなる。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】千田浩司、濱田浩気、五十嵐大、高橋克己、「軽量検証可能３パーティ秘匿関数計算の再考」、ＣＳＳ２０１０、２０１０年
【発明の概要】
【発明が解決しようとする課題】
【０００６】
３パーティ秘匿関数計算において、乗算、積和計算は通信及び乱数生成が必要なので、計算処理におけるボトルネックとなる。【０００７】
具体的には、従来の乗算プロトコルには、通信回数が２ラウンド必要である。また、３パーティそれぞれの計算量・通信量が対称でないため、パーティごとに異なるプログラムを実装する必要がある。したがって、実装コストが高くなる。さらに、計算量・通信量の最も重い部分がボトルネックとなる。また、積和計算は、一般に通信量が大きくなる。【０００８】
本発明の目的は、乗算、積和計算を高速に行うことができ、かつ、実装が容易な秘匿積和計算方法、秘匿積和計算システム、計算装置、及びそれらのプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明の秘匿積和計算方法は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａ0＝（a00，…，a0na0-1）、Ａ1＝（a10，…，a1na1-1）、及びＡ2＝（a20，…，a2na2-1）と、データ列Ｂ0＝（b00，…，b0nb0-1）、Ｂ1＝（b10，…，b1nb1-1）、及びＢ2＝（b20，…，b2nb2-1）との積和計算
【数１】
2012102203.tif 000003
（i0＝０，…，na0−１、i1＝０，…，na1−１、i2＝０，…，na2−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、j2＝０，…，nb2−１、ただし、na0，na1，na2，nb0，nb1，nb2は自然数）を行うために用いる秘匿積和計算方法であって、パーティＸ乱数生成ステップ、パーティＸ第１計算ステップ、パーティＸ第２計算ステップ、パーティＹ乱数生成ステップ、パーティＹ第１計算ステップ、パーティＹ第２計算ステップ、パーティＺ乱数生成ステップ、パーティＺ第１計算ステップ、及びパーティＺ第２計算ステップを実行する。【００１０】
処理に際し、パーティＸにはデータ列Ａ0、Ａ1、Ｂ0、Ｂ1が、パーティＹにはデータ列Ａ1、Ａ2、Ｂ1、Ｂ2が、パーティＺにはデータ列Ａ2、Ａ0、Ｂ2、Ｂ0が、それぞれ入力される。【００１１】
パーティＸ乱数生成ステップは、パーティＸが、数ｒXを生成し、パーティＹに送信する。【００１２】
パーティＸ第１計算ステップは、パーティＸが、ｃXを
【数２】
2012102203.tif 000004
（e01i0,j1とe10i1,j0は任意の数）により計算し、パーティＺに送信する。【００１３】
パーティＸ第２計算ステップは、パーティＸが、パーティＺから数ｒzを、パーティＹからｃYを、それぞれ受信し、ｃ0とｃ1をそれぞれ、
【数３】
2012102203.tif 000005
（e00i0,j0とe11i1,j1は任意の数）により計算して出力する。【００１４】
パーティＹ乱数生成ステップは、パーティＹが、数ｒYを生成し、パーティＺに送信する。【００１５】
パーティＹ第１計算ステップは、パーティＹが、ｃYを
【数４】
2012102203.tif 000006
（e12i1,j2とe21i2,j1は任意の数）により計算し、パーティＸに送信する。【００１６】
パーティＹ第２計算ステップは、パーティＹが、パーティＸから数ｒXを、パーティＺからｃZを、それぞれ受信し、ｃ1とｃ2をそれぞれ、
【数５】
2012102203.tif 000007
（e22i2,j2は任意の数）により計算して出力する。【００１７】
パーティＺ乱数生成ステップは、パーティＺが、数ｒZを生成し、パーティＸに送信する。【００１８】
パーティＺ第１計算ステップは、パーティＺが、ｃZを
【数６】
2012102203.tif 000008
（e20i2,j0とe02i0,j2は任意の数）により計算し、パーティＹに送信する。【００１９】
パーティＺ第２計算ステップは、パーティＺが、パーティＹから数ｒYを、パーティＸからｃXを、それぞれ受信し、ｃ0とｃ2をそれぞれ、
【数７】
2012102203.tif 000009
により計算して出力する。
【発明の効果】
【００２０】
本発明の秘匿積和計算方法、秘匿積和計算システム、計算装置、及びそれらのプログラムによれば、乗算、積和計算を高速に行うことができ、かつ、各パーティの処理が対称であるため容易にプログラムを実装できる。
【図面の簡単な説明】
【００２１】
【図１】秘匿積和計算システム１００の構成例を示す図。
【図２】秘匿積和計算システム１００の処理フロー例を示す図。
【図３】秘匿積和計算システム１００、２００の各パーティの内部構成例を示す図。
【図４】秘匿積和計算システム２００の構成例を示す図。
【図５】秘匿積和計算システム２００の処理フロー例を示す図。
【図６】秘匿積和計算システム３００の構成例を示す図。
【図７】秘匿積和計算システム３００の処理フロー例を示す図。
【図８】秘匿積和計算システム３００、４００、５００の各パーティの内部構成例を示す図。
【図９】秘匿積和計算システム４００、５００の構成例を示す図。
【図１０】秘匿積和計算システム４００、５００の処理フロー例を示す図。
【図１１】秘匿積和計算システム６００の構成例を示す図。
【図１２】秘匿積和計算システム６００の処理フロー例を示す図。
【図１３】秘匿積和計算システム６００、７００、８００の各パーティの内部構成例を示す図。
【図１４】秘匿積和計算システム７００、８００の構成例を示す図。
【図１５】秘匿積和計算システム７００、８００の処理フロー例を示す図。
【図１６】秘匿積和計算システム９００、９１０、９２０の構成例を示す図。
【図１７】秘匿積和計算システム９００、９１０、９２０の処理フロー例を示す図。
【発明を実施するための形態】
【００２２】
以下、本発明の実施形態について、詳細に説明する。
【実施例１】
【００２３】
図１に秘匿積和計算システム１００の構成例を、図２にその処理フロー例をそれぞれ示す。秘匿積和計算システム１００は、それぞれ対称な計算処理を行う計算装置であるパーティＸ、パーティＹ、パーティＺを備える。【００２４】
本発明の秘匿積和計算は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａ0＝（a00，…，a0na0-1）、Ａ1＝（a10，…，a1na1-1）、及びＡ2＝（a20，…，a2na2-1）と、データ列Ｂ0＝（b00，…，b0nb0-1）、Ｂ1＝（b10，…，b1nb1-1）、及びＢ2＝（b20，…，b2nb2-1）との積和計算を行う。na0、na1、na2、nb0、nb1、nb2はそれぞれ自然数である。【００２５】
各パーティは、図３に示すように乱数生成手段１０１と第１計算手段１０２と第２計算手段１０３とを備える。図３においては、自パーティをＰ、他パーティをＰ−、Ｐ＋と表示する。具体的には自パーティがＸのとき、Ｐ−はパーティＺ、Ｐ＋はパーティＹであり、自パーティがＹのとき、Ｐ−はパーティＸ、Ｐ＋はパーティＺであり、自パーティがＺのとき、Ｐ−はパーティＹ、Ｐ＋はパーティＸである。なお、本明細書では、このように、どのパーティから見ても、自パーティＰと他パーティＰ−、Ｐ＋との関係が同じになることを「対称」と呼ぶ。また、そのときの処理に対して、「対称な処理」または「処理が対称」のように表現する。【００２６】
以下、各パーティの協調計算処理の内容について具体的に説明する。まず、パーティＸにデータ列Ａ0、Ａ1、Ｂ0、Ｂ1が入力され、パーティＹにデータ列Ａ1、Ａ2、Ｂ1、Ｂ2が入力され、パーティＺにデータ列Ａ2、Ａ0、Ｂ2、Ｂ0が入力される（Ｓ１）。【００２７】
続いて、パーティＸは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒXを生成し、パーティＹに送信する（Ｓ２−１）。続いて、第１計算手段１０２が、ｃXを【００２８】
【数８】
2012102203.tif 000010
により計算し、パーティＺに送信する（Ｓ２−２）。ここで、i0＝０，…，na0−１、i1＝０，…，na1−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１であり、e01i0,j1とe10i1,j0は任意の数である。そして、第２計算手段１０３が、パーティＺから乱数ｒzを、パーティＹからｃYを、それぞれ受信し、ｃ0とｃ1をそれぞれ、【００２９】
【数９】
2012102203.tif 000011
により計算して出力する（Ｓ３）。ここで、e00i0,j0とe11i1,j1は任意の数である。【００３０】
また、パーティＹは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒYを生成し、パーティＺに送信する（Ｓ４−１）。続いて、第１計算手段１０２が、ｃYを【００３１】
【数１０】
2012102203.tif 000012
により計算し、パーティＸに送信する（Ｓ４−２）。ここで、i2＝０，…，na2−１、j2＝０，…，nb2−１であり、e12i1,j2とe21i2,j1は任意の数である。そして、第２計算手段１０３が、パーティＸから乱数ｒXを、パーティＺからｃZを、それぞれ受信し、ｃ1とｃ2をそれぞれ、【００３２】
【数１１】
2012102203.tif 000013
により計算して出力する（Ｓ５）。ここで、e22i2,j2は任意の数である。【００３３】
また、パーティＺは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒZを生成し、パーティＸに送信する（Ｓ６−１）。続いて、第１計算手段１０２が、ｃZを【００３４】
【数１２】
2012102203.tif 000014
により計算し、パーティＹに送信する（Ｓ６−２）。ここで、e20i2,j0とe02i0,j2は任意の数である。そして、第２計算手段１０３が、パーティＹから乱数ｒYを、パーティＸからｃXを、それぞれ受信し、ｃ0とｃ2をそれぞれ、【００３５】
【数１３】
2012102203.tif 000015
により計算して出力する（Ｓ７）。なお、Ｓ２−１、２とＳ４−１、２とＳ６−１、２とは並行処理が可能であり、Ｓ３とＳ５とＳ７とについても並行処理が可能である。【００３６】
そして、パーティＸ、Ｙ、Ｚから出力されたｃ0、ｃ1、ｃ2の総和をとることで、
【数１４】
2012102203.tif 000016
というような積和計算結果を得ることができる。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。【００３７】
本発明の方法と非特許文献１による方法の効果を比較する。非特許文献１における計算量のほとんどが、乱数生成のための計算量と、物理的セキュアチャネルを用意できない場合の通信の暗号化・復号でのための計算量である。暗号化・復号のための計算量は通信量と一致するため、生成する乱数の数と通信量を観察すれば効率を評価できる。【００３８】
非特許文献１の乗算を繰り返してから加算を行う方法の場合、生成する乱数の数、通信量は入力データ列の要素の個数に比例する。一方、本発明の方法の場合、パーティＸ、Ｙ、Ｚとも、生成する乱数が１個、他のパーティへ送信するデータが２個で済む。また、パーティＸ、Ｙ、Ｚの処理が対称なため、すべてのパーティに共通なプログラムを実装できるので実装コストを抑えることができる。
【実施例２】
【００３９】
実施例２は、実施例１の具体例であり、na0＝na1＝na2＝nb0＝nb1＝nb2＝ｎ（ｎは１以上の整数）、e00＝e01＝e10＝e11＝e12＝e21＝e22＝e20＝e02＝１の場合である。図４に本実施例の秘匿積和計算システム２００の構成例を、図５にその処理フロー例をそれぞれ示す。秘匿積和計算システム２００は、パーティＸ、パーティＹ、パーティＺ、データ列分解供給部２１０、及び出力部２２０を備える。各パーティは、実施例１と同様、図３に示すように乱数生成手段１０１、第１計算手段１０２、及び第２計算手段１０３を備える。【００４０】
秘匿積和計算システム２００は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、素数ｐ未満の自然数である要素ａi、ｂi（ｉ＝０，…，ｎ−１）からなる２つのデータ列Ａ＝（ａ0，…，ａn-1）、Ｂ＝（ｂ0，…，ｂn-1）について、データ列の内容を秘匿したまま、積和計算【００４１】
【数１５】
2012102203.tif 000017
を行う（ｎ＝１の場合はａとｂとの乗算）。【００４２】
具体的には、まず、データ列分解供給部２１０は、入力されたデータ列Ａ、Ｂの各要素ａi、ｂiを、ａi＝a0i＋a1i＋a2i modｐ、ｂi＝b0i＋b1i＋b2i modｐ（a0i、a1i、b0i、b1iは乱数、ｐは素数）の条件式を満たすように分解し、パーティＸにデータ列Ａ0＝（a00，…，a0n-1）とデータ列Ａ1＝（a10，…，a1n-1）とデータ列Ｂ0＝（b00，…，b0n-1）とデータ列Ｂ1＝（b10，…，b1n-1）とを与え、パーティＹにデータ列Ａ1とデータ列Ａ2＝（a20，…，a2n-1）とデータ列Ｂ1とデータ列Ｂ2＝（b20，…，b2n-1）とを与え、パーティＺにデータ列Ａ2とデータ列Ａ0とデータ列Ｂ2とデータ列Ｂ0とを与える（Ｓ１１）。【００４３】
続いて、パーティＸは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒXを生成し、パーティＹに送信する（Ｓ１２−１）。続いて、第１計算手段１０２が、ｃXを【００４４】
【数１６】
2012102203.tif 000018
により計算し、パーティＺに送信する（Ｓ１２−２）。続いて、第２計算手段１０３が、パーティＺから乱数ｒzを、パーティＹからｃYを、それぞれ受信し、ｃ0とｃ1をそれぞれ、【００４５】
【数１７】
2012102203.tif 000019
により計算して出力する（Ｓ１３）。【００４６】
また、パーティＹは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒYを生成し、パーティＺに送信する（Ｓ１４−１）。続いて、第１計算手段１０２が、ｃYを【００４７】
【数１８】
2012102203.tif 000020
により計算し、パーティＸに送信する（Ｓ１４−２）。続いて、第２計算手段１０３が、パーティＸから乱数ｒXを、パーティＺからｃZを、それぞれ受信し、ｃ1とｃ2をそれぞれ、【００４８】
【数１９】
2012102203.tif 000021
により計算して出力する（Ｓ１５）。【００４９】
また、パーティＺは以下の処理を行う。まず、乱数生成手段１０１が、乱数ｒZを生成し、パーティＸに送信する（Ｓ１６−１）。続いて、第１計算手段１０２が、ｃZを【００５０】
【数２０】
2012102203.tif 000022
により計算し、パーティＹに送信する（Ｓ１６−２）。続いて、第２計算手段１０３が、パーティＹから乱数ｒYを、パーティＸからｃXを、それぞれ受信し、ｃ0とｃ2をそれぞれ、【００５１】
【数２１】
2012102203.tif 000023
により計算して出力する（Ｓ１７）。なお、Ｓ１２−１、２とＳ１４−１、２とＳ１６−１、２とは並行処理が可能であり、Ｓ１３とＳ１５とＳ１７とについても並行処理が可能である。【００５２】
そして、出力部２２０がパーティＸ、Ｙ、Ｚから出力されたｃ0、ｃ1、ｃ2の総和（ｃ0＋ｃ1＋ｃ2）を計算して出力する。【００５３】
【数２２】
2012102203.tif 000024
なので、正しく積和計算（ｉ＝１の場合はａとｂとの乗算）ができていることがわかる。【００５４】
なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。また、データ列分解供給部２１０、出力部２２０については、各パーティとは異なる別の装置が備えることとしても、各パーティに該当する装置のいずれか１以上が備えることとしてもよい。【００５５】
本発明と非特許文献１の方法の効果を比較する。乗算については、非特許文献１の方法では、通信回数が２ラウンド（ラウンドとは、パーティＸ、Ｙ、Ｚの並行処理において他のパーティの処理を待つ回数）であり、パーティＸが生成する乱数が１個、送信するデータが４個であり、パーティＹ、Ｚが生成する乱数が０個、送信するデータが１個である。一方、本発明では、通信回数が１ラウンドであり、パーティＸ、Ｙ、Ｚとも生成する乱数が１個、送信するデータが２個である。つまり、ラウンド数は半分となっている。また、生成する乱数と送信するデータの個数は同じであるが、パーティＸ、Ｙ、Ｚの処理が対称になっているため、ボトルネックが小さくなっていると言える。【００５６】
積和計算については、非特許文献１の乗算を繰り返してから加算を行う方法の場合、生成する乱数の数、通信量は入力データ列の要素の個数に比例するが、本発明の方法の場合、パーティＸ、Ｙ、Ｚとも、生成する乱数が１個、他のパーティへ送信するデータが２個で済む。そして、いずれの計算の場合においても、パーティＸ、Ｙ、Ｚの処理が対称なため、実装コストを抑えることができる。
【実施例３】
【００５７】
実施例３は、積和計算を行う実施例１、２に不正検知機能を加えた構成である。図６に秘匿積和計算システム３００の構成例を、図７にその処理フロー例をそれぞれ示す。秘匿積和計算システム３００は、それぞれ対称な計算処理を行う計算装置であるパーティＸ、パーティＹ、パーティＺを備える。【００５８】
本発明の秘匿積和計算は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）、Ａq_1＝（a1q_0，…，a1q_na1-1）、及びＡq_2＝（a2q_0，…，a2q_na2-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）、Ｂq_1＝（b1q_0，…，b1q_nb1-1）、及びＢq_2＝（b2q_0，…，b2q_nb2-1）との積和計算を、ｑ＝０，…，ｍ−１の計ｍ組（ｍは１以上の整数）について（ｍが２以上の場合は並列に）行う。na0、na1、na2、nb0、nb1、nb2はそれぞれ自然数である。【００５９】
各パーティは、図８に示すように第１乱数生成手段３０１、第１計算手段３０２、第２計算手段３０３、第２乱数生成手段３０４、第３計算手段３０５、第４計算手段３０６、及び不正検知手段３０７を備える。図８においては、いずれかの前記計算装置がパーティＰであるとしたとき、パーティＰがパーティＸである場合には、パーティＰ−がパーティＺ、パーティＰ＋がパーティＹ、符号0p、1p、2pがそれぞれ0、1、2に対応し、パーティＰがパーティＹである場合には、パーティＰ−がパーティＸ、パーティＰ＋がパーティＺ、符号0p、1p、2pがそれぞれ1、2、0に対応し、パーティＰがパーティＺである場合には、パーティＰ−がパーティＹ、パーティＰ＋がパーティＸ、符号0p、1p、2pがそれぞれ2、0、1に対応する。【００６０】
以下、各パーティの協調計算処理の内容について具体的に説明する。Ｓ２１〜Ｓ２７が実施例１に相当する積和計算処理であり、Ｓ２８〜Ｓ３９が不正検知処理である。なお、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有しているものとする。まず、パーティＸにデータ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が入力され、パーティＹにデータ列Ａq_1、Ａq_2、Ｂq_1、Ｂq_2が入力され、パーティＺにデータ列Ａq_2、Ａq_0、Ｂq_2、Ｂq_0が入力される（Ｓ２１）。【００６１】
続いて、パーティＸは以下の処理を行う。まず、第１乱数生成手段３０１が、乱数ｒq_Xを生成し、パーティＹに送信する（Ｓ２２−１）。続いて、第１計算手段３０２が、ｃq_Xを【００６２】
【数２３】
2012102203.tif 000025
により計算し、パーティＺに送信する（Ｓ２２−２）。ここで、i0＝０，…，na0−１、i1＝０，…，na1−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１であり、e01q_i0,q_j1とe10q_i1,q_j0は任意の数である。続いて、第２計算手段３０３が、パーティＺから乱数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信し、ｃq_0とｃq_1をそれぞれ、【００６３】
【数２４】
2012102203.tif 000026
により計算する（Ｓ２３）。ここで、e00q_i0,q_j0、e11q_i1, q_j1は任意の数である。【００６４】
また、パーティＹは以下の処理を行う。まず、乱数生成手段３０１が、乱数ｒq_Yを生成し、パーティＺに送信する（Ｓ２４−１）。続いて、第１計算手段３０２が、ｃq_Yを【００６５】
【数２５】
2012102203.tif 000027
により計算し、パーティＸに送信する（Ｓ２４−２）。ここで、i2＝０，…，na2−１、j2＝０，…，nb2−１であり、e12q_i1,q_j2とe21q_i2,q_j1は任意の数である。続いて、第２計算手段３０３が、パーティＸから乱数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、【００６６】
【数２６】
2012102203.tif 000028
により計算する（Ｓ２５）。ここで、e22q_i2,q_j2は任意の数である。【００６７】
また、パーティＺは以下の処理を行う。まず、乱数生成手段３０１が、乱数ｒq_Zを生成し、パーティＸに送信する（Ｓ２６−１）。続いて第１計算手段３０２が、ｃq_Zを【００６８】
【数２７】
2012102203.tif 000029
により計算し、パーティＹに送信する（Ｓ２６−２）。ここで、e20q_i2,q_j0とe02q_i0,q_j2は任意の乗数である。続いて、第２計算手段３０３が、パーティＹから乱数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、【００６９】
【数２８】
2012102203.tif 000030
により計算する（Ｓ２７）。なお、Ｓ２２−１、２とＳ２４−１、２とＳ２６−１、２とは並行処理が可能であり、Ｓ２３とＳ２５とＳ２７とについても並行処理が可能である。【００７０】
Ｓ２１〜Ｓ２７の処理に続き、各パーティは以下のように不正検知処理を行う。【００７１】
パーティＸの処理について説明する。まず、第２乱数生成手段３０４が、乱数列（αY1q_0，…，αY1q_na1-1）及び乱数ρxを生成してパーティＹに送信し、乱数列（αZ0q_0，…，αZ0q_na0-1）を生成してパーティＺに送信する（Ｓ２８）。続いて、第３計算手段３０５が、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を計算してパーティＹに送信し、パーティＹから乱数列（αX1q_0，…，αX1q_na1-1）を、パーティＺから乱数列（αX0q_0，…，αX0q_na0-1）を、それぞれ受信し、（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）及び【００７２】
【数２９】
2012102203.tif 000031
を計算してパーティＺに送信する（Ｓ２９）。続いて、第４計算手段３０６が、パーティＹから（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）を、パーティＺからρZを、それぞれ受信し、【００７３】
【数３０】
2012102203.tif 000032
を計算してパーティＹに送信する（Ｓ３０）。そして、不正検知手段３０７が、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を、それぞれ受信し、【００７４】
【数３１】
2012102203.tif 000033
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ３１）。【００７５】
次に、パーティＹの処理について説明する。まず、第２乱数生成手段３０４が、乱数列（αZ2q_0，…，αZ2q_na2-1）及び乱数ρYを生成してパーティＺに送信し、乱数列（αX1q_0，…，αX1q_na1-1）を生成してパーティＸに送信する（Ｓ３２）。続いて、第３計算手段３０５が、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を計算してパーティＺに送信し、パーティＸから乱数列（αY1q_0，…，αY1q_na1-1）を、パーティＺから乱数列（αY2q_0，…，αY2q_na2-1）を、それぞれ受信し、（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_na2-1−ｓq_Z・a2q_na2-1）及び【００７６】
【数３２】
2012102203.tif 000034
を計算してパーティＸに送信する（Ｓ３３）。続いて、第４計算手段３０６が、パーティＸから乱数ρXを、パーティＺから（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）を、それぞれ受信し、【００７７】
【数３３】
2012102203.tif 000035
を計算してパーティＺに送信する（Ｓ３４）。そして、不正検知手段３０７が、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）を、パーティＺからγZを、それぞれ受信し、【００７８】
【数３４】
2012102203.tif 000036
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ３５）。【００７９】
次に、パーティＺの処理について説明する。まず、第２乱数生成手段３０４が、乱数列（αX0q_0，…，αX0q_na0-1）及び乱数ρZを生成してパーティＸに送信し、乱数列（αY2q_0，…，αY2q_na2-1）を生成してパーティＹに送信する（Ｓ３６）。続いて、第３計算手段３０５が、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）を計算してパーティＸに送信し、パーティＸから乱数列（αZ0q_0，…，αZ0q_na0-1）を、パーティＹから乱数列（αZ2q_0，…，αZ2q_na2-1）を、それぞれ受信し、（αX0q_0−ｓq_X・a0q_0，…，αX0q_na0-1−ｓq_X・a0q_na0-1）及び【００８０】
【数３５】
2012102203.tif 000037
を計算してパーティＹに送信する（Ｓ３７）。続いて、第４計算手段３０６が、パーティＸから（αY1q_0−ｓq_Y・a1q_0，…，αY1q_na1-1−ｓq_Y・a1q_na1-1）を、パーティＹから乱数ρYを、それぞれ受信し、【００８１】
【数３６】
2012102203.tif 000038
を計算してパーティＸに送信する（Ｓ３８）。そして、不正検知手段３０７が、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）を、それぞれ受信し、【００８２】
【数３７】
2012102203.tif 000039
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ３９）。【００８３】
そして、不正検知が無かった場合には、パーティＸ、Ｙ、Ｚから出力されたｃq_0、ｃq_1、ｃq_2の総和をとることで、
【数３８】
2012102203.tif 000040
というような積和計算結果を得ることができる。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。【００８４】
本発明の不正検知は、１回の乗算、積和演算または並列に実行された乗算、積和演算に対して1回行われる。また、不正検知機能における各Ｐ＋が送信するγP+に含まれるαP+0q_i0、αP+1q_i1、αP+2q_i2（ただし、ｑ＝０，…，ｍ−１）は、各aq_iに異なる乱数を掛けた数の断片である。したがって、ひとつでも不正な値があれば、Ｐ＋に予知できない乱数となる。よって、法が素数ｐであれば、不正があった場合に積和計算処理での不正と辻褄を合わせられる確率は１／（ｐ−１）しかない。
【実施例４】
【００８５】
実施例４は、実施例３の具体例であり、na0＝na1＝na2＝nb0＝nb1＝nb2＝ｎ（ｎは１以上の整数）、e00＝e01＝e10＝e11＝e12＝e21＝e22＝e20＝e02＝１の場合である。図９に本実施例の秘匿積和計算システム４００の構成例を、図１０にその処理フロー例をそれぞれ示す。秘匿積和計算システム４００は、パーティＸ、パーティＹ、パーティＺ、データ列分解供給部４１０、及び出力部４２０を備える。各パーティは、実施例３と同様、第１乱数生成手段３０１、第１計算手段３０２、第２計算手段３０３、第２乱数生成手段３０４、第３計算手段３０５、第４計算手段３０６、及び不正検知手段３０７を備える。【００８６】
秘匿積和計算システム４００は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、素数ｐ未満の自然数である要素ａq_i、ｂq_i（ｉ＝０，…，ｎ−１（ｎは１以上の整数））からなるｍ組のデータ列Ａq＝（ａq_0，…，ａq_n-1）、Ｂq＝（ｂq_0，…，ｂq_n-1）（ｍは１以上の整数、ｑ＝０，…，ｍ−１）につき、各組の積和計算【００８７】
【数３９】
2012102203.tif 000041
を行う（ｎ＝１の場合はａｑとｂｑとの乗算）。なお、実施例３と同様、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有しているものとする。【００８８】
具体的な処理としては、まず、データ列分解供給部４１０が、入力されたｍ組のデータ列Ａq、Ｂqの各要素ａq_i、ｂq_iを、ａq_i＝a0q_i＋a1q_i＋a2q_i modｐ、ｂq_i＝b0q_i＋b1q_i＋b2q_i modｐ（a0q_i、a1q_i、b0q_i、b1q_iは乱数、ｐは素数）の条件式を満たすように分解し、パーティＸにデータ列Ａq_0＝（a0q_0，…，a0q_n-1）とデータ列Ａq_1＝（a1q_0，…，a1q_n-1）とデータ列Ｂq_0＝（b0q_0，…，b0q_n-1）とデータ列Ｂq_1＝（b1q_0，…，b1q_n-1）とを与え、パーティＹにデータ列Ａq_1とデータ列Ａq_2＝（a2q_0，…，a2q_n-1）とデータ列Ｂq_1とデータ列Ｂq_2＝（b2q_0，…，b2q_n-1）とを与え、パーティＺにデータ列Ａq_2とデータ列Ａq_0とデータ列Ｂq_2とデータ列Ｂq_0とを与える（Ｓ４１）。【００８９】
続いて、パーティＸは以下の処理を行う。まず、第１乱数生成手段３０１が、乱数ｒq_Xを生成し、パーティＹに送信するＳ４２−１）。続いて、第１計算手段３０２が、ｃq_Xを【００９０】
【数４０】
2012102203.tif 000042
により計算し、パーティＺに送信する（Ｓ４２−２）。続いて、第２計算手段３０３が、パーティＺから乱数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信し、ｃq_0とｃq_1をそれぞれ、【００９１】
【数４１】
2012102203.tif 000043
により計算する（Ｓ４３）。【００９２】
また、パーティＹは以下の処理を行う。まず、乱数生成手段３０４が、乱数ｒq_Yを生成し、パーティＺに送信する（４４−１）。続いて、第１計算手段３０５が、ｃq_Yを【００９３】
【数４２】
2012102203.tif 000044
により計算し、パーティＸに送信する（Ｓ４４−２）。続いて、第２計算手段３０６が、パーティＸから乱数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、【００９４】
【数４３】
2012102203.tif 000045
により計算する（Ｓ４５）。【００９５】
また、パーティＺは以下の処理を行う。まず、第１乱数生成手段３０１が、乱数ｒq_Zを生成し、パーティＸに送信する（Ｓ４６−１）。続いて、第１計算手段３０２が、ｃq_Zを【００９６】
【数４４】
2012102203.tif 000046
により計算し、パーティＹに送信する（Ｓ４６−２）。続いて、第２計算手段３０３が、パーティＹから乱数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、【００９７】
【数４５】
2012102203.tif 000047
により計算する（Ｓ４７）。なお、Ｓ４２−１、２とＳ４４−１、２とＳ４６−１、２とは並行処理が可能であり、Ｓ４３とＳ４５とＳ４７とについても並行処理が可能である。【００９８】
Ｓ４１〜Ｓ４７の処理に続き、各パーティは以下のように不正検知処理を行う。パーティＸの処理について説明する。まず、第２乱数生成手段３０４が、乱数列（αY1q_0，…，αY1q_n-1）及び乱数ρxを生成してパーティＹに送信し、乱数列（αZ0q_0，…，αZ0q_n-1）を生成してパーティＺに送信する（Ｓ４８）。続いて、第３計算手段３０５が、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_n-1−ｓq_Z・a0q_n-1）を計算してパーティＹに送信し、パーティＹから乱数列（αX1q_0，…，αX1q_n-1）を、パーティＺから乱数列（αX0q_0，…，αX0q_n-1）を、それぞれ受信し、（αY1q_0−ｓq_Y・a1q_0，…，αY1q_n-1−ｓq_Y・a1q_n-1）及び【００９９】
【数４６】
2012102203.tif 000048
を計算してパーティＺに送信する（Ｓ４９）。続いて、第４計算手段３０６が、パーティＹから（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_n-1−ｓq_Z・a2q_n-1）を、パーティＺからρZを、それぞれ受信し、【０１００】
【数４７】
2012102203.tif 000049
を計算してパーティＹに送信する（Ｓ５０）。そして、不正検知手段３０７が、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_n-1−ｓq_Y・a2q_n-1）を、それぞれ受信し、【０１０１】
【数４８】
2012102203.tif 000050
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ５１）。【０１０２】
次にパーティＹの処理について説明する。【０１０３】
まず、第２乱数生成手段３０４が、乱数列（αZ2q_0，…，αZ2q_n-1）及び乱数ρYを生成してパーティＺに送信し、乱数列（αX1q_0，…，αX1q_n-1）を生成してパーティＸに送信する（Ｓ５２）。続いて、第３計算手段３０５が、（αX1q_0−ｓq_X・a1q_0，…，αX1q_n-1−ｓq_X・a1q_n-1）を計算してパーティＺに送信し、パーティＸから乱数列（αY1q_0，…，αY1q_n-1）を、パーティＺから乱数列（αY2q_0，…，αY2q_n-1）を、それぞれ受信し、（αZ2q_0−ｓq_Z・a2q_0，…，αZ2q_n-1−ｓq_Z・a2q_n-1）及び【０１０４】
【数４９】
2012102203.tif 000051
を計算してパーティＸに送信する（Ｓ５３）。続いて、第４計算手段３０６が、パーティＸから乱数ρXを、パーティＺから（αX0q_0−ｓq_X・a0q_0，…，αX0q_n-1−ｓq_X・a0q_n-1）を、それぞれ受信し、【０１０５】
【数５０】
2012102203.tif 000052
を計算してパーティＺに送信する（Ｓ５４）。そして、不正検知手段３０７が、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_n-1−ｓq_Z・a0q_n-1）を、パーティＺからγZを、それぞれ受信し、【０１０６】
【数５１】
2012102203.tif 000053
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ５５）。【０１０７】
次に、パーティＺの処理について説明する。まず、第２乱数生成手段３０４が、乱数列（αX0q_0，…，αX0q_n-1）及び乱数ρZを生成してパーティＸに送信し、乱数列（αY2q_0，…，αY2q_n-1）を生成してパーティＹに送信する（Ｓ５６）。続いて、第３計算手段３０５が、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_n-1−ｓq_Y・a2q_n-1）を計算してパーティＸに送信し、パーティＸから乱数列（αZ0q_0，…，αZ0q_n-1）を、パーティＹから乱数列（αZ2q_0，…，αZ2q_n-1）を、それぞれ受信し、（αX0q_0−ｓq_X・a0q_0，…，αX0q_n-1−ｓq_X・a0q_n-1）及び【０１０８】
【数５２】
2012102203.tif 000054
を計算してパーティＹに送信する（Ｓ５７）。続いて、第４計算手段３０６が、パーティＸから（αY1q_0−ｓq_Y・a1q_0，…，αY1q_n-1−ｓq_Y・a1q_n-1）を、パーティＹから乱数ρYを、それぞれ受信し、【０１０９】
【数５３】
2012102203.tif 000055
を計算してパーティＸに送信する（Ｓ５８）。そして、不正検知手段３０７が、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_n-1−ｓq_X・a1q_n-1）を、それぞれ受信し、【０１１０】
【数５４】
2012102203.tif 000056
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ５９）。【０１１１】
そして、出力部４２０がパーティＸ、Ｙ、Ｚから出力されたｃq_0、ｃq_1、ｃq_2の総和（ｃq_0＋ｃq_1＋ｃq_2）を計算して出力する（Ｓ６０）。【０１１２】
【数５５】
2012102203.tif 000057
なので、正しく積和計算（ｉ＝１のみの場合（ｎ＝１の場合）はａｑとｂｑとの乗算）ができていることがわかる。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。【０１１３】
また、データ列分解供給部４１０、出力部４２０については、各パーティとは異なる別の装置が備えることとしても、各パーティに該当する装置のいずれか１以上が備えることとしてもよい。【０１１４】
本発明と非特許文献１の方法の効果を比較する。ｍ＝１の場合、本発明ではラウンド数は２、各パーティが送信するデータは１０個、生成する乱数は５個である。しかも、ｓＰは一度共有すれば何度でも使うことができるため、実際にはラウンド数は２、送信するデータは９個、生成する乱数は４個でよい。これに対して、非特許文献１の方法では、ラウンド数は４、パーティＸが送信するデータは２０個、生成する乱数は１２個、パーティＹ、Ｚが送信するデータは１７個、生成する乱数は９個である。したがって、本発明の方が２倍程度効率的である。【０１１５】
ｍ≧２の場合は、より効率的である。本発明ではラウンド数は２、各パーティが送信するデータは６ｍ＋３個、生成する乱数は３ｍ＋１個である。これに対して、非特許文献１の方法では、ラウンド数は４、パーティＸが送信するデータは２０ｍ個、生成する乱数は１２ｍ個、パーティＹ、Ｚが送信するデータは１７ｍ個、生成する乱数は９ｍ個である。したがって、本発明の方が３倍程度効率的である。
【実施例５】
【０１１６】
実施例４の秘匿積和計算システム４００は、
【数５６】
2012102203.tif 000058
という積和計算を行う構成であったが、実施例５の秘匿積和計算システム５００は、この乗算の片方の値が共通である場合の構成例である。すなわち、秘匿積和計算システム５００は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、素数ｐ未満の自然数である要素ａq_i（ｑ＝０，…，ｍ−１（ｍは１以上の整数）、ｉ＝０，…，ｎ−１（ｎは１以上の整数））からなるデータ列Ａq＝（ａq_0，…，ａq_n-1）（ｍは１以上の整数、ｑ＝０，…，ｍ−１）と素数ｐ未満の自然数であるｂとの間で、ｍ個の積和計算
【数５７】
2012102203.tif 000059
を行う。なお、機能構成と処理フローは実施例４と同様であるため、以下、これらを引用して説明する（構成図：図９（及び８）、処理フロー図：図１０）。なお、実施例４と同様、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有しているものとする。【０１１７】
具体的な処理としては、まず、データ列分解供給部４１０が、入力されたデータ列Ａqの各要素ａq_iを、ａq_i＝a0q_i＋a1q_i＋a2q_i modｐ、ｂをｂ＝b0＋b1＋b2 modｐ（a0q_i、a1q_i、b0、b1は乱数、ｐは素数）の条件式を満たすように分解し、パーティＸにデータ列Ａq_0＝（a0q_0，…，a0q_n-1）、データ列Ａq_1＝（a1q_0，…，a1q_n-1）、b0、及びb1を与え、パーティＹにデータ列Ａq_1、データ列Ａq_2＝（a2q_0，…，a2q_n-1）、b1、及びb2を与え、パーティＺにデータ列Ａq_2、データ列Ａq_0、b2、及びb0を与える（Ｓ４１）。【０１１８】
続いて、パーティＸは以下の処理を行う。まず、第１乱数生成手段３０１が、乱数ｒq_Xを生成し、パーティＹに送信するＳ４２−１）。続いて、第１計算手段３０２が、ｃq_Xを【０１１９】
【数５８】
2012102203.tif 000060
により計算し、パーティＺに送信する（Ｓ４２−２）。続いて、第２計算手段３０３が、パーティＺから乱数ｒq_zを、パーティＹからｃq_Yを、それぞれ受信し、ｃq_0とｃq_1をそれぞれ、【０１２０】
【数５９】
2012102203.tif 000061
により計算する（Ｓ４３）。【０１２１】
また、パーティＹは以下の処理を行う。まず、乱数生成手段３０４が、乱数ｒq_Yを生成し、パーティＺに送信する（４４−１）。続いて、第１計算手段３０５が、ｃq_Yを【０１２２】
【数６０】
2012102203.tif 000062
により計算し、パーティＸに送信する（Ｓ４４−２）。続いて、第２計算手段３０６が、パーティＸから乱数ｒq_Xを、パーティＺからｃq_Zを、それぞれ受信し、ｃq_1とｃq_2をそれぞれ、【０１２３】
【数６１】
2012102203.tif 000063
により計算する（Ｓ４５）。【０１２４】
また、パーティＺは以下の処理を行う。まず、第１乱数生成手段３０１が、乱数ｒq_Zを生成し、パーティＸに送信する（Ｓ４６−１）。続いて、第１計算手段３０２が、ｃq_Zを
【数６２】
2012102203.tif 000064
により計算し、パーティＹに送信する（Ｓ４６−２）。続いて、第２計算手段３０３が、パーティＹから乱数ｒq_Yを、パーティＸからｃq_Xを、それぞれ受信し、ｃq_0とｃq_2をそれぞれ、【０１２５】
【数６３】
2012102203.tif 000065
により計算する（Ｓ４７）。なお、Ｓ４２−１、２とＳ４４−１、２とＳ４６−１、２とは並行処理が可能であり、Ｓ４３とＳ４５とＳ４７とについても並行処理が可能である。【０１２６】
Ｓ４１〜Ｓ４７の処理に続き、各パーティは以下のように不正検知処理を行う。パーティＸの処理について説明する。まず、第２乱数生成手段３０４が、乱数αY1及び乱数ρxを生成してパーティＹに送信し、乱数αZ0を生成してパーティＺに送信する（Ｓ４８）。続いて、第３計算手段３０５が、【０１２７】
【数６４】
2012102203.tif 000066
を計算してパーティＹに送信し、パーティＹから乱数αX1を、パーティＺから乱数αX0を、それぞれ受信し、【０１２８】
【数６５】
2012102203.tif 000067
及び
【数６６】
2012102203.tif 000068
を計算してパーティＺに送信する（Ｓ４９）。続いて、第４計算手段３０６が、パーティＹから【０１２９】
【数６７】
2012102203.tif 000069
を、パーティＺからρZを、それぞれ受信し、【０１３０】
【数６８】
2012102203.tif 000070
【０１３１】
を計算してパーティＹに送信する（Ｓ５０）。そして、不正検知手段３０７が、パーティＹからγYを、パーティＺからγY´と
【数６９】
2012102203.tif 000071
を、それぞれ受信し、【０１３２】
【数７０】
2012102203.tif 000072
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ５１）。【０１３３】
次にパーティＹの処理について説明する。まず、第２乱数生成手段３０４が、乱数αZ2及び乱数ρYを生成してパーティＺに送信し、乱数αX1を生成してパーティＸに送信する（Ｓ５２）。続いて、第３計算手段３０５が、【０１３４】
【数７１】
2012102203.tif 000073
を計算してパーティＺに送信し、パーティＸから乱数αY1を、パーティＺから乱数αY2を、それぞれ受信し、【０１３５】
【数７２】
2012102203.tif 000074
及び
【数７３】
2012102203.tif 000075
を計算してパーティＸに送信する（Ｓ５３）。続いて、第４計算手段３０６が、パーティＸから乱数ρXを、パーティＺから
【数７４】
2012102203.tif 000076
を、それぞれ受信し、【０１３６】
【数７５】
2012102203.tif 000077
を計算してパーティＺに送信する（Ｓ５４）。そして、不正検知手段３０７が、パーティＸからγZ´と
【数７６】
2012102203.tif 000078
を、パーティＺからγZを、それぞれ受信し、【０１３７】
【数７７】
2012102203.tif 000079
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ５５）。【０１３８】
次に、パーティＺの処理について説明する。まず、第２乱数生成手段３０４が、乱数αX0及び乱数ρZを生成してパーティＸに送信し、乱数αY2を生成してパーティＹに送信する（Ｓ５６）。続いて、第３計算手段３０５が、【０１３９】
【数７８】
2012102203.tif 000080
を計算してパーティＸに送信し、パーティＸから乱数αZ0を、パーティＹから乱数αZ2を、それぞれ受信し、【０１４０】
【数７９】
2012102203.tif 000081
及び
【数８０】
2012102203.tif 000082
を計算してパーティＹに送信する（Ｓ５７）。続いて、第４計算手段３０６が、パーティＸから【０１４１】
【数８１】
2012102203.tif 000083
を、パーティＹから乱数ρYを、それぞれ受信し、【０１４２】
【数８２】
2012102203.tif 000084
を計算してパーティＸに送信する（Ｓ５８）。そして、不正検知手段３０７が、パーティＸからγXを、パーティＹからγX´と
【数８３】
2012102203.tif 000085
を、それぞれ受信し、【０１４３】
【数８４】
2012102203.tif 000086
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ５９）。【０１４４】
そして、出力部４２０がパーティＸ、Ｙ、Ｚから出力されたｃq_0、ｃq_1、ｃq_2の総和（ｃq_0＋ｃq_1＋ｃq_2）を計算して出力する（Ｓ６０）。
【数８５】
2012102203.tif 000087
なので、正しく積和計算ができていることがわかる。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。また、データ列分解供給部４１０、出力部４２０については、各パーティとは異なる別の装置が備えることとしても、各パーティに該当する装置のいずれか１以上が備えることとしてもよい。【０１４５】
本発明と非特許文献１の方法の効果を比較する。本発明の場合、ラウンド数は２、各パーティが送信するデータは２ｍ個、生成する乱数は３個である。従って、非特許文献１の方法と比べ、９倍程度効率的である。また、ｍが増加すると生成する乱数の数も増加したのが、ｍに依存しない定数に改善されていることがわかる。
【実施例６】
【０１４６】
実施例３で示した不正検知機能付きの秘匿積和計算システム３００では、ａとｂとの乗算プロトコルにおいて、ａ0p・ｂ1p＋ａ1p・ｂ0pの正当性の確認のために、ｓP・ａ0pの分散値を表すαP0p、αPP-を用いて、(αP0p−αPP-)・ｂ1pとｓP・ａ0p・ｂ1pとを比較するとともに、ｓP・ａ1pの分散値を表すαP1p、αPP+を用いて、(αP1p−αPP+)・ｂ0pとｓP・ａ1p・ｂ0pとを比較する。しかし、秘匿積和計算システム３００の乗算プロトコルは前者の比較に際し、パーティ間で計算値を往復させる手順を含む。具体的には、αZ2q_i2−ｓq_Z・a2q_i2をパーティＹ→パーティＸ→パーティＹ、αX0q_i0−ｓq_X・a0q_i0をパーティＺ→パーティＹ→パーティＺ、αY1q_i1−ｓq_Y・a1q_i1をパーティＸ→パーティＺ→パーティＸというように、それぞれ往復させる必要がある。そのため、このように往復する間に計算値が漏洩し、計算結果を変化させない範囲でサーバが不正（秘匿すべきデータの情報を得る）を行う余地があった。つまり、実施例３はサーバに不正がない場合に限り完全秘匿が可能な構成と言える。【０１４７】
実施例６は、サーバに不正があっても完全秘匿が可能な構成である。具体的には、不正の原因となっている計算値の往復がプロトコル内に含まれない構成である。図１１に実施例６の秘匿積和計算システム６００の構成例を、図１２にその処理フロー例をそれぞれ示す。秘匿積和計算システム６００は、パーティＸ、パーティＹ、パーティＺを備える。各パーティは図１３に示すように、秘匿積和計算システム３００のものと同じ第１乱数生成手段３０１、第１計算手段３０２、及び第２計算手段３０３のほか、第２乱数生成手段６０４、第３計算手段６０５、第４計算手段６０６、及び不正検知手段６０７を備える。【０１４８】
以下、具体的に説明するが、第１乱数生成手段３０１、第１計算手段３０２、及び第２計算手段３０３の各機能と、それらの機能として実現される秘匿積和計算処理（Ｓ２１〜Ｓ２７）については、秘匿積和計算システム３００と共通であるため説明を省略し、相違点である不正検知処理に絞って説明する。【０１４９】
Ｓ２１〜Ｓ２７の処理に続き、各パーティは以下のように不正検知処理を行う。なお、実施例３と同様、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有していることとする。【０１５０】
パーティＸの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρxを生成してパーティＹに送信し、乱数列（αZ0q_0，…，αZ0q_na0-1）と乱数列（βZ0q_0，…，βZ0q_nb0-1）を生成してパーティＺに送信する（Ｓ６８）。続いて、第３計算手段６０５が、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を計算してパーティＹに送信し、パーティＹから乱数列（αX1q_0，…，αX1q_na1-1）と乱数列（βX1q_0，…，βX1q_nb1-1）を受信し、【０１５１】
【数８６】
2012102203.tif 000088
を計算してパーティＺに送信する（Ｓ６９）。続いて、第４計算手段６０６がパーティＺからρZを受信し、【０１５２】
【数８７】
2012102203.tif 000089
を計算してパーティＹに送信する（Ｓ７０）。そして、不正検知手段６０７が、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を、それぞれ受信し、【０１５３】
【数８８】
2012102203.tif 000090
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ７１）。【０１５４】
次に、パーティＹの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρYを生成してパーティＺに送信し、乱数列（αX1q_0，…，αX1q_na1-1）と乱数列（βX1q_0，…，βX1q_nb1-1）を生成してパーティＸに送信する（Ｓ７２）。続いて、第３計算手段６０５が、（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を計算してパーティＺに送信し、パーティＺから乱数列（αY2q_0，…，αY2q_na2-1）と乱数列（βY2q_0，…，βY2q_nb2-1）を受信し、【０１５５】
【数８９】
2012102203.tif 000091
を計算してパーティＸに送信する（Ｓ７３）。続いて、第４計算手段６０６が、パーティＸから乱数ρXを受信し、【０１５６】
【数９０】
2012102203.tif 000092
を計算してパーティＺに送信する（Ｓ７４）。そして、不正検知手段６０７が、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_na0-1−ｓq_Z・a0q_na0-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_nb0-1−ｓq_Z・b0q_nb0-1）を、パーティＺからγZを、それぞれ受信し、【０１５７】
【数９１】
2012102203.tif 000093
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ７５）。【０１５８】
次に、パーティＺの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρZを生成してパーティＸに送信し、乱数列（αY2q_0，…，αY2q_na2-1）と乱数列（βY2q_0，…，βY2q_nb2-1）を生成してパーティＹに送信する（Ｓ７６）。続いて、第３計算手段６０５が、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_na2-1−ｓq_Y・a2q_na2-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_nb2-1−ｓq_Y・b2q_nb2-1）を計算してパーティＸに送信し、パーティＸから乱数列（αZ0q_0，…，αZ0q_na0-1）と乱数列（βZ0q_0，…，βZ0q_nb0-1）を受信し、【０１５９】
【数９２】
2012102203.tif 000094
を計算してパーティＹに送信する（Ｓ７７）。続いて、第４計算手段６０６がパーティＹから乱数ρYを受信し、【０１６０】
【数９３】
2012102203.tif 000095
を計算してパーティＸに送信する（Ｓ７８）。そして、不正検知手段６０７が、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_na1-1−ｓq_X・a1q_na1-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_nb1-1−ｓq_X・b1q_nb1-1）を、それぞれ受信し、【０１６１】
【数９４】
2012102203.tif 000096
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ７９）。なお、以上の処理においても、乱数を用いている部分についてはハッシュ値等で代用しても構わない。【０１６２】
以上説明した秘匿積和計算システム６００においては、ａとｂとの乗算プロトコルにおいて、ａ0p・ｂ1p＋ａ1p・ｂ0pの正当性の確認のために、ｓP・ｂ1pの分散値を表すβP1p、βPP+を用いて、(βP1p＋ａ0p・βPP+)とｓP・ａ1p・ｂ0pとを比較するとともに、ｓP・ａ1pの分散値を表すαP1p、αPP+を用いて、(αP1p−αPP+)・ｂ0pとｓP・ａ1p・ｂ0pとを比較する。このように構成することで、プロトコル上、パーティ間で計算値を往復させる必要がないため、計算値の漏洩を防ぐことができ、そのためサーバは不正を働くことができない。また、処理のステップ数は秘匿積和計算システム３００と同じであるため、同程度の効率を維持することができる。
【実施例７】
【０１６３】
実施例７は、実施例６の具体例であり、na0＝na1＝na2＝nb0＝nb1＝nb2＝ｎ、e00＝e01＝e10＝e11＝e12＝e21＝e22＝e20＝e02＝１の場合である。図１４に本実施例の秘匿積和計算システム７００の構成例を、図１５にその処理フロー例をそれぞれ示す。秘匿積和計算システム７００は、パーティＸ、パーティＹ、パーティＺ、データ列分解供給部４１０、及び出力部４２０を備える。データ列分解供給部４１０と出力部４２０は、実施例４の秘匿積和計算システム４００のものと同じである。各パーティは図１３に示すように、秘匿積和計算システム４００のものと同じ第１乱数生成手段３０１、第１計算手段３０２、及び第２計算手段３０３のほか、第２乱数生成手段６０４、第３計算手段６０５、第４計算手段６０６、及び不正検知手段６０７を備える。【０１６４】
秘匿積和計算システム７００は、実施例４の秘匿積和計算システム４００と同様に、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、素数ｐ未満の自然数である要素ａq_i、ｂq_iからなるｍ組のデータ列Ａq＝（ａq_0，…，ａq_n-1）、Ｂq＝（ｂq_0，…，ｂq_n-1）につき、各組の積和計算
【数９５】
2012102203.tif 000097
を行う（ｎ＝１の場合はａｑとｂｑとの乗算）。【０１６５】
以下、具体的に説明するが、データ列分解供給部４１０、第１乱数生成手段３０１、第１計算手段３０２、第２計算手段３０３、及び出力部４２０の各機能と、それらの機能として実現される秘匿積和計算処理（Ｓ４１〜Ｓ４７、Ｓ６０）については、実施例４の秘匿積和計算システム４００と共通であるため説明を省略し、相違点である不正検知処理に絞って説明する。【０１６６】
Ｓ４１〜Ｓ４７の処理に続き、各パーティは以下のように不正検知処理を行う。なお、実施例６と同様、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有していることとする。【０１６７】
パーティＸの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρxを生成してパーティＹに送信し、乱数列（αZ0q_0，…，αZ0q_n-1）と乱数列（βZ0q_0，…，βZ0q_n-1）を生成してパーティＺに送信する（Ｓ８８）。続いて、第３計算手段６０５が、（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_n-1−ｓq_Z・a0q_n-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_n-1−ｓq_Z・b0q_n-1）を計算してパーティＹに送信し、パーティＹから乱数列（αX1q_0，…，αX1q_n-1）と乱数列（βX1q_0，…，βX1q_n-1）を受信し、【０１６８】
【数９６】
2012102203.tif 000098
を計算してパーティＺに送信する（Ｓ８９）。続いて、第４計算手段６０６が、パーティＺからρZを受信し、【０１６９】
【数９７】
2012102203.tif 000099
を計算してパーティＹに送信する（Ｓ９０）。そして、不正検知手段６０７が、パーティＹからγYを、パーティＺからγY´と（αY2q_0−ｓq_Y・a2q_0，…，αY2q_n-1−ｓq_Y・a2q_n-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_n-1−ｓq_Y・b2q_n-1）を、それぞれ受信し、【０１７０】
【数９８】
2012102203.tif 000100
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ９１）。【０１７１】
次にパーティＹの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρYを生成してパーティＺに送信し、乱数列（αX1q_0，…，αX1q_n-1）と乱数列（βX1q_0，…，βX1q_n-1）を生成してパーティＸに送信する（Ｓ９２）。続いて、第３計算手段６０５が、（αX1q_0−ｓq_X・a1q_0，…，αX1q_n-1−ｓq_X・a1q_n-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_n-1−ｓq_X・b1q_n-1）を計算してパーティＺに送信し、パーティＺから乱数列（αY2q_0，…，αY2q_n-1）と乱数列（βY2q_0，…，βY2q_n-1）を、それぞれ受信し、【０１７２】
【数９９】
2012102203.tif 000101
を計算してパーティＸに送信する（Ｓ９３）。続いて、第４計算手段６０６が、パーティＸから乱数ρXを受信し、【０１７３】
【数１００】
2012102203.tif 000102
を計算してパーティＺに送信する（Ｓ９４）。そして、不正検知手段６０７が、パーティＸからγZ´と（αZ0q_0−ｓq_Z・a0q_0，…，αZ0q_n-1−ｓq_Z・a0q_n-1）と（βZ0q_0−ｓq_Z・b0q_0，…，βZ0q_n-1−ｓq_Z・b0q_n-1）を、パーティＺからγZを、それぞれ受信し、【０１７４】
【数１０１】
2012102203.tif 000103
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ９５）。【０１７５】
次に、パーティＺの処理について説明する。【０１７６】
まず、第２乱数生成手段６０４が、乱数ρZを生成してパーティＸに送信し、乱数列（αY2q_0，…，αY2q_n-1）と乱数列（βY2q_0，…，βY2q_n-1）を生成してパーティＹに送信する（Ｓ９６）。続いて、第３計算手段６０５が、（αY2q_0−ｓq_Y・a2q_0，…，αY2q_n-1−ｓq_Y・a2q_n-1）と（βY2q_0−ｓq_Y・b2q_0，…，βY2q_n-1−ｓq_Y・b2q_n-1）を計算してパーティＸに送信し、パーティＸから乱数列（αZ0q_0，…，αZ0q_n-1）と乱数列（βZ0q_0，…，βZ0q_n-1）を受信し、【０１７７】
【数１０２】
2012102203.tif 000104
を計算してパーティＹに送信する（Ｓ９７）。続いて、第４計算手段６０６がパーティＹから乱数ρYを受信し、【０１７８】
【数１０３】
2012102203.tif 000105
を計算してパーティＸに送信する（Ｓ９８）。そして、不正検知手段６０７が、パーティＸからγXを、パーティＹからγX´と（αX1q_0−ｓq_X・a1q_0，…，αX1q_n-1−ｓq_X・a1q_n-1）と（βX1q_0−ｓq_X・b1q_0，…，βX1q_n-1−ｓq_X・b1q_n-1）を、それぞれ受信し、【０１７９】
【数１０４】
2012102203.tif 000106
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ９９）。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。
【実施例８】
【０１８０】
実施例７の秘匿積和計算システム７００は、実施例４と同様に
【数１０５】
2012102203.tif 000107
という積和計算を行い、この積和計算に対する不正検知処理に実施例６の方法を適用する構成であったが、実施例８の秘匿積和計算システム８００は、この積和計算において乗算の片方の値が共通である場合の実施例である。すなわち、秘匿積和計算システム８００は、実施例５の秘匿積和計算システム５００と同様に、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、素数ｐ未満の自然数である要素ａq_iからなるデータ列Ａq＝（ａq_0，…，ａq_n-1）と素数ｐ未満の自然数であるｂとの間で、ｍ個の積和計算
【数１０６】
2012102203.tif 000108
を行い、この積和計算に対する不正検知処理に実施例６の不正検知方法を適用する構成である。【０１８１】
以下、具体的に説明するが、データ列分解供給部４１０、第１乱数生成手段３０１、第１計算手段３０２、第２計算手段３０３、及び出力部４２０の各機能と、それらの機能として実現される秘匿積和計算処理（Ｓ４１〜Ｓ４７、Ｓ６０）については、実施例５の秘匿積和計算システム５００と共通であるため説明を省略し、相違点である不正検知処理に絞って説明する。機能構成と処理フローは実施例７と同様であるため、説明はこれらを引用して行う（構成図：図１４（及び１３）、処理フロー図：図１５）。【０１８２】
Ｓ４１〜Ｓ４７の処理に続き、各パーティは以下のように不正検知処理を行う。なお、実施例７と同様、パーティＸとＹは乱数ｓq_Zを、パーティＹとＺは乱数ｓq_Xを、パーティＺとＸは乱数ｓq_Yを、それぞれ予め共有しているものとする。【０１８３】
パーティＸの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρxを生成してパーティＹに送信し、乱数αZ0と乱数βZ0qを生成してパーティＺに送信する（Ｓ８８）。続いて、第３計算手段６０５が、【０１８４】
【数１０７】
2012102203.tif 000109
を計算してパーティＹに送信し、パーティＹから乱数αX1とβX1qを受信し、【０１８５】
【数１０８】
2012102203.tif 000110
を計算してパーティＺに送信する（Ｓ８９）。続いて、第４計算手段６０６が、パーティＺからρZを受信し、【０１８６】
【数１０９】
2012102203.tif 000111
を計算してパーティＹに送信する（Ｓ９０）。そして、不正検知手段６０７が、パーティＹからγYを、パーティＺからγY´と【０１８７】
【数１１０】
2012102203.tif 000112
と
【数１１１】
2012102203.tif 000113
を、それぞれ受信し、【０１８８】
【数１１２】
2012102203.tif 000114
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_0とｃq_1を出力する（Ｓ９１）。【０１８９】
次にパーティＹの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρYを生成してパーティＺに送信し、乱数αX1と乱数βX1qを生成してパーティＸに送信する（Ｓ９２）。続いて、第３計算手段６０５が、【０１９０】
【数１１３】
2012102203.tif 000115
を計算してパーティＺに送信し、パーティＺから乱数αY2とβY2qを受信し、【０１９１】
【数１１４】
2012102203.tif 000116
を計算してパーティＸに送信する（Ｓ９３）。続いて、第４計算手段６０６が、パーティＸから乱数ρXを受信し、【０１９２】
【数１１５】
2012102203.tif 000117
を計算してパーティＺに送信する（Ｓ９４）。そして、不正検知手段６０７が、パーティＺからγZを、パーティＸからγZ´と【０１９３】
【数１１６】
2012102203.tif 000118
と
【数１１７】
2012102203.tif 000119
を、それぞれ受信し、【０１９４】
【数１１８】
2012102203.tif 000120
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_1とｃq_2を出力する（Ｓ９５）。【０１９５】
次に、パーティＺの処理について説明する。まず、第２乱数生成手段６０４が、乱数ρZを生成してパーティＸに送信し、乱数αY2と乱数βY2qを生成してパーティＹに送信する（Ｓ９６）。続いて、第３計算手段６０５が、   【０１９６】
【数１１９】
2012102203.tif 000121
を計算してパーティＸに送信し、パーティＸから乱数αZ0とβZ0qを受信し、【０１９７】
【数１２０】
2012102203.tif 000122
を計算してパーティＹに送信する（Ｓ９７）。続いて、第４計算手段６０６が、パーティＹから乱数ρYを受信し、【０１９８】
【数１２１】
2012102203.tif 000123
を計算してパーティＸに送信する（Ｓ９８）。そして、不正検知手段６０７が、パーティＸからγXを、パーティＹからγX´と【０１９９】
【数１２２】
2012102203.tif 000124
と
【数１２３】
2012102203.tif 000125
を、それぞれ受信し、【０２００】
【数１２４】
2012102203.tif 000126
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了し、０であればｃq_2とｃq_0を出力する（Ｓ９９）。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。
【実施例９】
【０２０１】
実施例６、７は、２つのデータ列Ａ＝(aq_0，…，aq_n-1)、Ｂ＝(bq_0，…，bq_n-1)について、それぞれＡ＝Ａ0＋Ａ1＋Ａ2 mod p、Ｂ＝Ｂ0＋Ｂ1＋Ｂ2 mod pの条件を満たすように３つに分散して、パーティＸにデータ列Ａ0＝（a0q_0，…，a0q_na0-1）、Ａ1＝（a1q_0，…，a1q_na1-1）、Ｂ0＝（b0q_0，…，b0q_nb0-1）、及びＢ1＝（b1q_0，…，b1q_nb1-1）を、パーティＹにデータ列Ａ1、Ａ2＝（a2q_0，…，a2q_na2-1）、Ｂ1、及びＢ2＝（b2q_0，…，b2q_nb2-1）を、パーティＺにデータ列Ａ2、Ａ0、Ｂ2、Ｂ0を、それぞれ秘匿値として与え、これらの秘匿積和である【０２０２】
【数１２５】
2012102203.tif 000127
【０２０３】
を、パーティＸでの計算結果であるｃq_0とｃq_1、パーティＹでの計算結果であるｃq_1とｃq_2、及びパーティＺでの計算結果であるｃq_2とｃq_0からｃq_0＋ｃq_1＋ｃq_2を求めることにより、安全に秘匿積和計算することを可能とするものである。この秘匿積和計算において、上式のΣa0q_i0・b1q_j1、Σa1q_i1・b0q_j0、Σa1q_i1・b2q_j2、Σa2q_i2・b1q_j1、Σa2q_i2・b0q_j0、及びΣa0q_i0・b2q_j2の６つの項に着目すると、これらの項を構成する２つの分散値について、ある１パーティは両方を持っており、残りのパーティはそれぞれ異なる一方のみを持っているという関係にある。例えば、Σa0q_i0・b1q_j1のa0q_i0とb1q_j1については、パーティＸはa0q_i0とb1q_j1の両方を持っているが、パーティＹはb1q_j1のみを、パーティＺはa0q_i0のみをそれぞれ持っている。Σa1q_i1・b0q_j0についても同様である。実施例９の秘匿積和計算システム９００は、このように３つのパーティのうちいずれか１つのパーティが両方の分散値を、他の２つのパーティがそれぞれ異なる一方の分散値を持っている場合に、これら２つの分散値の積和を求める方法であり、いわば実施例６、７の秘匿積和計算の基礎となっている積和計算方法である。【０２０４】
以下、パーティＸが両方の分散値を、パーティＹ、Ｚがそれぞれ異なる一方の分散値を持っている場合を例にとって説明するが、パーティＹが両方の分散値を、パーティＸ、Ｚがそれぞれ異なる一方の分散値を持っている場合、及び、パーティＺが両方の分散値を、パーティＸ、Ｙがそれぞれ異なる一方の分散値を持っている場合についても同様な方法で計算することが可能である。【０２０５】
図１６に秘匿積和計算システム９００の構成例を、図１７にその処理フロー例をそれぞれ示す。秘匿積和計算システム９００は、計算装置であるパーティＸ、パーティＹ、パーティＺを備える。パーティＸは、パーティＸ乱数生成手段９０１とパーティＸ計算手段９０３とを備え、パーティＹは、パーティＹ乱数生成手段９０２とパーティＹ計算手段９０４とを備え、パーティＺは、不正検知手段９０５を備える。【０２０６】
秘匿積和計算システム９００は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_na0-1）及びＡq_1＝（a1q_0，…，a1q_na1-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_nb0-1）及びＢq_1＝（b1q_0，…，b1q_nb1-1）との積和計算
【数１２６】
2012102203.tif 000128
（i0＝０，…，na0−１、i1＝０，…，na1−１、j0＝０，…，nb0−１、j1＝０，…，nb1−１、na0とna１とnb0とnb1は自然数、e01q_i0,q_j1とe10q_i1,q_j0は任意の数）を、ｑ＝０，…，ｍ−１の計ｍ組（ｍは１以上の整数）について（ｍが２以上の場合には並列に）行う。【０２０７】
パーティＸには、データ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹには、データ列Ａq_1、Ｂq_1が、パーティＺには、データ列Ａq_0、Ｂq_0が、それぞれ入力される（Ｓ１０１）。【０２０８】
まず、パーティＸのパーティＸ乱数生成手段９０１が、乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_nb0-1）と乱数列（β1q_0，…，β1q_na0-1）を生成してパーティＹに送信する（Ｓ１０２）。また、パーティＹのパーティＹ乱数生成手段９０２が、乱数ｓqを生成してパーティＺに送信する（Ｓ１０３）。【０２０９】
続いて、パーティＸのパーティＸ計算手段９０３が、cq_0とγ0を、
【数１２７】
2012102203.tif 000129
により計算し、パーティＺに送信する（Ｓ１０４）。【０２１０】
また、パーティＹのパーティＹ計算手段９０４が、パーティＸから乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_nb0-1）と乱数列（β1q_0，…，β1q_na0-1）を受信し、数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´をそれぞれ、
【数１２８】
2012102203.tif 000130
により計算し、パーティＺに送信する（Ｓ１０５）。【０２１１】
続いて、パーティＺの不正検知手段９０５が、パーティＸからcq_0とγ0を、パーティＹから乱数ｓqと数列（α0q_0，…，α0q_nb0-1）と数列（β0q_0，…，β0q_na0-1）とγ´を、それぞれ受信し、
【数１２９】
2012102203.tif 000131
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了する（Ｓ１０６）。【０２１２】
そして、不正検知手段９０５での計算結果が０であれば、パーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する（Ｓ１０７）。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。
【実施例１０】
【０２１３】
実施例１０は、実施例９の具体例であり、na0＝na1＝na2＝nb0＝nb1＝nb2＝ｎ、e00＝e01＝e10＝e11＝e12＝e21＝e22＝e20＝e02＝１の場合である。構成及び処理フローは実施例９と同様である（構成例：図１６、処理フロー例：図１７）。実施例１０の秘匿積和計算システム９１０は、パーティＸ、パーティＹ、パーティＺの３つの計算装置の協調計算により、データ列Ａq_0＝（a0q_0，…，a0q_n-1）及びＡq_1＝（a1q_0，…，a1q_n-1）と、データ列Ｂq_0＝（b0q_0，…，b0q_n-1）及びＢq_1＝（b1q_0，…，b1q_n-1）との積和計算
【数１３０】
2012102203.tif 000132
（ｉ＝０，…，ｎ−１、ｎは自然数）を、ｑ＝０，…，ｍ−１の計ｍ組（ｍは１以上の整数）について（ｍが２以上の場合には並列に）行う。【０２１４】
パーティＸには、データ列Ａq_0、Ａq_1、Ｂq_0、Ｂq_1が、パーティＹには、データ列Ａq_1、Ｂq_1が、パーティＺには、データ列Ａq_0、Ｂq_0が、それぞれ入力される（Ｓ１０１）。【０２１５】
まず、パーティＸのパーティＸ乱数生成手段９０１が、乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_n-1）と乱数列（β1q_0，…，β1q_n-1）を生成してパーティＹに送信する（Ｓ１０２）。また、パーティＹのパーティＹ乱数生成手段９０２が、乱数ｓqを生成してパーティＺに送信する（Ｓ１０３）。【０２１６】
続いて、パーティＸのパーティＸ計算手段９０３が、cq_0とγ0を、
【数１３１】
2012102203.tif 000133
により計算し、パーティＺに送信する（Ｓ１０４）。【０２１７】
また、パーティＹのパーティＹ計算手段９０４が、パーティＸから乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_n-1）と乱数列（β1q_0，…，β1q_n-1）を受信し、数列（α0q_0，…，α0q_n-1）と数列（β0q_0，…，β0q_n-1）とγ´をそれぞれ、
【数１３２】
2012102203.tif 000134
により計算し、パーティＺに送信する（Ｓ１０５）。【０２１８】
続いて、パーティＺの不正検知手段９０５が、パーティＸからcq_0とγ0を、パーティＹから乱数ｓqと数列（α0q_0，…，α0q_n-1）と数列（β0q_0，…，β0q_n-1）とγ´を、それぞれ受信し、
【数１３３】
2012102203.tif 000135
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了する（Ｓ１０６）。【０２１９】
そして、不正検知手段９０５での計算結果が０であれば、パーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する（Ｓ１０７）。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。
【実施例１１】
【０２２０】
実施例１１の秘匿積和計算システム９２０は、実施例１０の秘匿積和計算システム９１０における積和計算
【数１３４】
2012102203.tif 000136
について、各項の乗算の一方がｉ、ｑの値によらず共通である場合、すなわち
【数１３５】
2012102203.tif 000137
である場合に、より効率的にかつ安全に積和計算を行うことを可能とするものである。【０２２１】
秘匿積和計算システム９０２の構成及び処理フローは実施例９、１０と同様である（構成例：図１６、処理フロー例：図１７）。ただし、パーティＸには、データa0及びa1と、データ列Ｂq_0＝（b0q_0，…，b0q_n-1）及びＢq_1＝（b1q_0，…，b1q_n-1）とが、パーティＹには、データa1とデータ列Ｂq_1が、パーティＺには、データa0とデータ列Ｂq_0が、それぞれ入力される（Ｓ１０１）。【０２２２】
まず、パーティＸのパーティＸ乱数生成手段９０１が、乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_n-1）と乱数β1を生成してパーティＹに送信する（Ｓ１０２）。【０２２３】
また、パーティＹのパーティＹ乱数生成手段９０２が、乱数ｓqを生成してパーティＺに送信する（Ｓ１０３）。【０２２４】
続いて、パーティＸのパーティＸ計算手段９０３が、cq_0とγ0を、
【数１３６】
2012102203.tif 000138
により計算し、パーティＺに送信する（Ｓ１０４）。【０２２５】
また、パーティＹのパーティＹ計算手段９０４が、パーティＸから乱数cq_１と乱数γ1と乱数列（α1q_0，…，α1q_n-1）と乱数β1を受信し、数列（α0q_0，…，α0q_n-1）とβ0とγ´をそれぞれ、
【数１３７】
2012102203.tif 000139
により計算し、パーティＺに送信する（Ｓ１０５）。【０２２６】
続いて、パーティＺの不正検知手段９０５が、パーティＸからcq_0とγ0を、パーティＹから乱数ｓqと数列（α0q_0，…，α0q_n-1）とβ0とγ´を、それぞれ受信し、
【数１３８】
2012102203.tif 000140
を計算して、計算結果が０でなければ不正検知を表すデータを出力して処理を終了する（Ｓ１０６）。【０２２７】
そして、不正検知手段９０５での計算結果が０であれば、パーティＸからｃq_0とｃq_1を、パーティＹからｃq_1と０を、パーティＺから０とｃq_0を、それぞれ出力する（Ｓ１０７）。なお、以上の処理において、乱数を用いている部分についてはハッシュ値等で代用しても構わない。【０２２８】
以上説明した本発明の秘匿積和計算方法、秘匿積和計算システムにおける各処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本発明の秘匿積和計算システムの各構成要素の機能は必要に応じ、併合・分割しても構わない。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。本発明の各実施例の秘匿積和計算システムをコンピュータによって実現する場合、装置及びその各部が有す機能の処理内容はプログラムによって記述される。そのプログラムは、例えば、ハードディスク装置に格納されており、実行時には必要なプログラムやデータがＲＡＭ(Random Access Memory)に読み込まれる。その読み込まれたプログラムがＣＰＵにより実行されることにより、コンピュータ上で各処理内容が実現される。
【図１】
2012102203.tif 000247
【図２】
2012102203.tif 000248
【図３】
2012102203.tif 000249
【図４】
2012102203.tif 000250
【図５】
2012102203.tif 000251
【図６】
2012102203.tif 000252
【図７】
2012102203.tif 000253
【図８】
2012102203.tif 000254
【図９】
2012102203.tif 000255
【図１０】
2012102203.tif 000256
【図１１】
2012102203.tif 000257
【図１２】
2012102203.tif 000258
【図１３】
2012102203.tif 000259
【図１４】
2012102203.tif 000260
【図１５】
2012102203.tif 000261
【図１６】
2012102203.tif 000262
【図１７】
2012102203.tif 000263
【国際調査報告】
2012102203.tif 000264
2012102203.tif 000265
2012102203.tif 000266
2012102203.tif 000267