(57)【特許請求の範囲】
【請求項１】
複数のユーザ装置ｉ,i=1,…,Nと、Nは２以上の整数であり、第１及び第２大小比較装置と、上記ユーザ装置及び上記第１及び第２大小比較装置から受信した情報を公開する掲示板装置とにより、予め決めた下限値V1と上限値VMの範囲の単調増加するＭ個の値Vw、ただし、w=1,2,…,M、で、全ユーザがそれぞれ決めた意中の値Vviからそれらの最小値VMIN及びその最小値を意中値としたユーザｊだけを特定する大小比較方法であり、
(a) 各上記ユーザ装置ｉで、ユーザにより入力された意中値Vviに対し、上記下限値V1以上、上記意中値Vvi未満で互いに対応した要素が等しく、上記意中値Vvi以上、上記上限値VM以下で互いに対応した要素が互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成し、それらに対応する情報を秘密にそれぞれ上記第１及び第２大小比較装置に送信するステップと、Ｍは上記下限値V1以上で上記上限値VM以下の上記意中値として選択可能な値の数を表し、
(b) 上記第１大小比較装置で、上記下限値V1以上、上記上限値VM以下の与えられた値Vwについて、全ユーザ装置からの上記情報系列si中のそれぞれｗに対応した要素si,w を取り出し、それらを決められた順序により並べた要素連結Seqs,w＝s1,w‖s2,w‖…‖sN,wを作成するステップと、‖はデータの連結を表し、
(c) 上記第２大小比較装置で、上記与えられた値Vwについて、全ユーザ装置からの上記情報系列ti中のそれぞれｗに対応した要素ti,wを取り出し、それらを決められた順序により並べた要素連結Seqt,w＝t1,w‖t2,w‖…‖tN,wを作成するステップと、
(d) 上記掲示板装置で、上記要素連結Seqs,wとSeqt,w を、それら自身の値を明かすことなく比較し、それらが互いに異なっていればVw以下を意中の値としたユーザがいると判定し、等しければVw以下を意中の値としたユーザがいないと判定し、その判定に基づき、ｗの値を変更していくことで最小意中値VMINを決定し，要素番号MINを公表するステップと、
(e) 上記第１及び第２大小比較装置で，公表された上記要素番号MINに対し，対応する要素連結Seqs,MIN及びSeqt,MINを上記掲示板装置に送信して公開することにより，各上記ユーザ装置に対し，上記要素連結中の互いに対応する要素si,MIN及びti,MINについてsj,MIN≠tj,MINとなる番号ｊが、上記最小意中値をコミットしたユーザ番号ｊであることを検出可能にするステップ，
とを含むことを特徴とする大小比較方法。
【請求項２】
請求項１記載の大小比較方法において、
上記ステップ(a) は、各ユーザｉのユーザ装置で、乱数R1i，R2iを生成し、(R1i, si)の組を上記第１大小比較装置に、(R2i, ti)の組を上記第２大小比較装置にそれぞれ秘密に送信するステップと、
また、各上記組の連結R1i‖si及びR2i‖ti についてハッシュ関数ｈによってハッシュ値H1i＝h(R1i‖si)及びH2i＝h(R2i‖ti)を計算し、それらを掲示板装置に送信するステップとを含み、
上記ステップ(d) は、上記掲示板装置で上記ハッシュ値H1i, H2i,i=1,2,…,N,を全ユーザのコミットとして公開するステップを含むことを特徴とする大小比較方法。
【請求項３】
請求項２記載の大小比較方法において、
上記ステップ(b) は、上記第１大小比較装置で上記要素連結Seqs,wについてハッシュ関数ｈによってハッシュ値HSw＝h(Seqs,w)を計算し、それを上記掲示板装置に送信するステップを含み、
上記ステップ(c) は、上記第２大小比較装置で上記要素連結Seqt,wについてハッシュ関数ｈによってハッシュ値HTw＝h(Seqt,w)を計算し、それを上記掲示板装置に送信するステップを含み、
上記ステップ(d) は、上記掲示板装置で上記第１及び第２大小比較装置より受信した上記ハッシュ値HSw, HTwを公開して比較し、それらが異なっていればVw以下を意中の値としたユーザがいると判断し、等しければVw以下を意中の値としたユーザがいないと判断し、ｗを変更していくことで最小意中値VMINを決定するステップを含むことを特徴とする大小比較方法。
【請求項４】
請求項２記載の大小比較方法において、
上記第１及び第２大小比較装置は、上記掲示板装置より予め公開された素数Ｐを記憶し、上記素数Ｐは、P-1が大きな素数を約数に持つ素数であり、上記第１及び第２大小比較装置は、共通の整数値ｗを選択し、
上記ステップ(b) は、上記第１大小比較装置で上記要素連結Seqs,wについて任意の整数を有限体Fp上に一意に、かつランダムに写すハッシュ関数h'によりハッシュ値HSw=h'(Seqs,w)を計算し、乱数RAwを生成し、連結RAw‖HSwについてハッシュ関数ｈによってハッシュ値HAw＝h(RAw‖HSw)を計算し、HSwRAw(mod P)を計算し、それらの組(HAw, HSwRAw(mod P))を掲示板装置に送信するステップを含み、
上記ステップ(c) は、上記第２大小比較装置で上記要素連結Seqt,wについてハッシュ関数h'によりハッシュ値HTw=h'(Seqt,w)を計算し、乱数RBwを生成し、連結RBw‖HTwについてハッシュ関数ｈによってハッシュ値HBw＝h(RBw‖HTw)を計算し、HTwRBw(mod P)を計算し、それらの組(HBw, HTwRBw(mod P))を掲示板装置に送信するステップを含み、
上記ステップ(d) は、上記第１大小比較装置が上記掲示板装置から上記HTwRBw(mod P)を読んで(HTwRBw)RAw(mod P)を計算し、上記掲示板装置に送信し、上記第２大小比較装置が上記掲示板装置から上記HSwRAw(mod P)を読んで(HSwRAw)RBw(mod P)を計算し、上記掲示板装置に送信するステップと、
上記掲示板装置は、上記第１及び第２大小比較装置より受信した(HTwRBw)RAw(mod P)及び(HSwRAw)RBw(mod P)を公開して比較し、それらが異なっていればVw以下を意中の値としたユーザがいると判定し、等しければVw以下を意中の値としたユーザがいないと判定し、上記第１及び第２大小比較装置がｗを変更していくことで最小意中値VMINを決定するステップとを含むことを特徴とする大小比較方法。
【請求項５】
請求項３又は４記載の大小比較方法において、上記第１及び第２大小比較装置は初期値としてwmin=1, wmax=Mとおいてｗを(wmin+wmax)/2=(1+M)/2以下の最大の整数として共有し、上記ステップ(d) は、Vw以下を意中の値としたユーザがいると判別されたときは変数wmaxにｗを代入し、そうでないときは変数wminにw+1を代入して上記ステップ(b)と(c)を実行することを、wmax＝wmin＝MINとなるまで繰り返してMINに対応する最小意中値VMINを求め、その過程を上記掲示板装置により逐次公開するステップを含むことを特徴とする大小比較方法。
【請求項６】
請求項４記載の大小比較方法において、上記情報系列si, tiの各要素は１ビットである。
【請求項７】
請求項４又は６記載の大小比較方法において、上記ステップ(e) は上記第１及び第２大小比較装置が乱数RAMIN及びRBMINをそれぞれ上記掲示板装置に送信して公開するステップを含むことを特徴とする大小比較方法。
【請求項８】
請求項１〜４の何れかに記載の大小比較方法において、３以上のＬ個の大小比較装置が備えられ、
上記ステップ(a) において、各上記ユーザ装置はVviが入力されるとV1以上Vvi未満に対応した情報は全て等しく、Vvi以上VM以下に対応した情報は全て異なるようなＬ個の情報系列sik, k=1,2,…,Lを作成し、上記Ｌ個の情報系列sikのうち少なくとも２系列sia, sib,ａ≠ｂ,がそろえばVviが分かるものとし、系列sikを第ｋ大小比較装置にそれぞれ秘密に送信するステップを含み、
２個の大小比較装置で大小比較を行い、大小比較装置にトラブルが発生すると、他の正常な大小比較装置を用いてその比較動作を継続して行うことを特徴とする大小比較方法。
【請求項９】
請求項１記載の大小比較方法において、
上記ステップ(a) は、各上記ユーザ装置で、上記情報系列si及びtiに対応する情報としてシード値s'i, t'iを秘密に上記第１及び第２大小比較装置にそれぞれ送信し、上記シード値s'i, t'iは、上記意中値Vviに対応する要素番号をviとすると、
一方向性関数Ｆに対してd=0,1,…,M-viでFd(s'i)＝Fd(t'i)となり、かつe=M-vi+1,…,M-1でFe(s'i)≠Fe(t'i)となるよう決められ、上記２つの情報系列si, tiはそれぞれ次式
si＝｛si,1=FM-1(s'i), si,2=FM-2(s'i), …, si,vi-1=FM-vi+1(s'i), si,vi=FM-vi(s'i), …, si,M-1=F(s'i), si,M＝s'i｝
ti＝｛ti,1=FM-1(t'i), ti,2=FM-2(t'i), …, ti,vi-1=FM-vi+1(t'i), ti,vi=FM-vi(t'i), …, ti,M-1=F(t'i), ti,M=t'i｝
で与えられることを特徴とする大小比較方法。
【請求項１０】
請求項１記載の大小比較方法において、
上記ステップ(a)は、各上記ユーザ装置で初期乱数R1i, R2i, cai, cbi, si,M+1, ti,M+1を生成するステップと、
ｍの初期値をＭと設定し、上記意中値Vviに対応する要素番号viに対して、m=M,M-1,…,viについて逐次
si,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
ti,m＝h(ti,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
を計算し、si,m≠ti,mである部分系列とし、
m=vi-1についての系列要素
si,m＝ti,m＝h(si,m-1‖ti,m-1‖hM+1-m(cai)‖hM+1-m(cbi))
と、
m=vi-2, vi-3, …, 0についての要素
si,m=ti,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
とを計算し、si,m=ti,mの部分系列とし、
これらm=M,M-1,…,1の要素si,m, ti,mの列を上記情報系列si, tiとして得るとともに、m=0の値si,0を得るステップ、とを含み、
上記ステップ(a) は更に、各上記ユーザ装置で、
R1i, si=[si,1,si,2,…,si,M]を暗号化関数EAで暗号化し、得られたEA(si‖R1i)を上記第１大小比較装置へ送信し、R2i, ti=[ti,1,ti,2,…,ti,M]を暗号化関数EBで暗号化し、得られたEB(ti‖R2i)を上記第２大小比較装置へ送信するステップと、
H1i=h(si‖R1i), H2i=h(ti‖R2i), si,0, hM+1(cai), hM+1(cbi)を掲示板装置２１に送り、公開するステップ、とを含むことを特徴とする大小比較方法。
【請求項１１】
複数のユーザ装置ｉ,i=1,…,Nと、Nは２以上の整数であり、第１及び第２大小比較装置と、上記ユーザ装置及び上記第１及び第２大小比較装置から受信した情報を公開する掲示板装置とにより、予め決めた下限値V1と上限値VMの範囲の単調増加するＭ個の値Vw、ただし、w=1,2,…,M,で全ユーザがそれぞれ決めた意中の値Vviからそれらの最大値VMAX及びその最大値を意中値としたユーザｊだけを特定する大小比較方法であり、
(a) 各上記ユーザ装置ｉで、ユーザにより入力された意中値Vviに対し、上記下限値Vmin以上、上記意中値Vvi以下で互いに対応した要素が異なり、上記意中値Vviを超え、上記上限値VM以下で互いに対応した要素が互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成し、それらに対応する情報を秘密にそれぞれ上記第１及び第２大小比較装置に送信するステップと、Ｍは上記下限値V1以上で上記上限値以下の、上記意中値として選択可能な値の数を表し、
(b) 上記第１大小比較装置で、上記下限値V1以上、上記上限値VM以下の与えられた値Vwについて、全ユーザ装置からの上記情報系列si中の要素番号ｗの要素si,wを取り出し、それらを決められた順序により並べた要素連結Seqs,w＝s1,w‖s2,w‖…‖sN,wを作成するステップと、‖はデータの連結を表し、
(c) 上記第２大小比較装置で、上記与えられた値ｗについて、全ユーザ装置からの上記情報系列ti中のそれぞれｗに対応した要素ti,wを取り出し、それらを決められた順序により並べた要素連結Seqt,w＝t1,w‖t2,w‖…‖tN,wを作成するステップと、
(d) 上記掲示板装置で、上記要素連結Seqs,wとSeqt,wを、それら自身の値を明かすことなく比較し、それらが互いに異なっていればVw以上を意中の値としたユーザがいると判定し、等しければVw以上を意中の値としたユーザがいないと判定し、その判定に基づき、ｗの値を変更していくことで最大値VMAXを決定し、要素番号MINを公開するステップと、
(e) 上記第１及び第２大小比較装置で、公表された上記要素番号MAXに対し、対応する要素連結Seqs,MAX及びSeqt,MAXを上記掲示板装置に送信して公開することにより，各上記ユーザ装置に対し，上記要素連結Seqs,MAX及びSeqt,MAX中の互いに対応する要素si,MAX及びti,MAXについてsj,MAX≠tj,MAXとなる番号ｊを上記最大意中値をコミットしたユーザの番号ｊであることを検出可能にするステップ，
とを含むことを特徴とする大小比較方法。
【請求項１２】
請求項１１記載の大小比較方法において、
上記ステップ(a) は、各ユーザｉのユーザ装置で、乱数R1i，R2iを生成し、(R1i, si)の組を上記第１大小比較装置に、(R2i, ti)の組を上記第２大小比較装置にそれぞれ秘密に送信するステップと、
また、各上記組の連結R1i‖si及びR2i‖ti についてハッシュ関数ｈによってハッシュ値H1i＝h(R1i‖si)及びH2i＝h(R2i‖ti)を計算し、それらを掲示板装置に送信するステップとを含み、
上記ステップ(d) は、上記掲示板装置で上記ハッシュ値H1i, H2i,i=1,2,…,N,を全ユーザのコミットとして公開するステップを含むことを特徴とする大小比較方法。
【請求項１３】
請求項１２記載の大小比較方法において、
上記ステップ(b) は、上記第１大小比較装置で上記要素連結Seqs,wについてハッシュ関数ｈによってハッシュ値HSw＝h(Seqs,w)を計算し、それを上記掲示板装置に送信するステップを含み、
上記ステップ(c) は、上記第２大小比較装置で上記要素連結Seqt,wについてハッシュ関数ｈによってハッシュ値HTw＝h(Seqt,w)を計算し、それを上記掲示板装置に送信するステップを含み、
上記ステップ(d) は、上記掲示板装置で上記第１及び第２大小比較装置より受信した上記ハッシュ値HSw, HTwを公開して比較し、それらが異なっていればVw以上を意中の値としたユーザがいると判断し、等しければVw以上を意中の値としたユーザがいないと判断し、ｗを変更していくことで最大意中値VMAXを決定するステップを含むことを特徴とする大小比較方法。
【請求項１４】
請求項１２記載の大小比較方法において、
上記第１及び第２大小比較装置は、上記掲示板装置より予め公開された素数Ｐを記憶し、上記素数Ｐは、P-1が大きな素数を約数に持つ素数であり、上記第１及び第２大小比較装置は、共通の整数値ｗを選択して共有し、
上記ステップ(b) は、上記第１大小比較装置で上記要素連結Seqs,wについて任意の整数を有限体Fp上に一意に、かつ、ランダムに写すハッシュ関数h'によりハッシュ値HSw=h'(Seqs,w)を計算し、乱数RAwを生成し、連結RAw‖HSwについてハッシュ関数ｈによってハッシュ値HAw＝h(RAw‖HSw)を計算し、HSwRAw(mod P)を計算し、それらの組(HAw, HSwRAw(mod P))を掲示板装置に送信するステップを含み、
上記ステップ(c) は、上記第２大小比較装置で上記要素連結Seqt,wについてハッシュ関数h'によりハッシュ値HTw=h'(Seqt,w)を計算し、乱数RBwを生成し、連結RBw‖HTwについてハッシュ関数ｈによってハッシュ値HBw＝h(RBw‖HTw)を計算し、HTwRBw(mod P)を計算し、それらの組(HBw, HTwRBw(mod P))を掲示板装置に送信するステップを含み、
上記ステップ(d) は、上記第１大小比較装置が上記掲示板装置から上記HTwRBw(mod P)を読んで(HTwRBw)RAw(mod P)を計算し、上記掲示板装置に送信し、上記第２大小比較装置が上記掲示板装置から上記HSwRAw(mod P)を読んで(HSwRAw)RBw(mod P)を計算し、上記掲示板装置に送信するステップと、
上記掲示板装置は、上記第１及び第２大小比較装置より受信した(HTwRBw)RAw(mod P)及び(HSwRAw)RBw(mod P)を公開して比較し、それらが異なっていればVw以上を意中の値としたユーザがいると判定し、等しければVw以上を意中の値としたユーザがいないと判定し、上記第１及び第２大小比較装置がｗを変更していくことで最大値を決定するステップとを含むことを特徴とする大小比較方法。
【請求項１５】
請求項１３又は１４記載の大小比較方法において、wmin, wmaxを1〜Ｍの整数の変数とすると、上記第１及び第２大小比較装置は初期値としてwmin=1, wmax=Mとおいてｗを(wmin+wmax)/2=(1+M)/2以下の最大の整数として共有し、上記ステップ(d) は、Vw以上を意中の値としたユーザがいると判別されたときは変数wmaxにｗを代入し、そうでないときは変数wminにw+1を代入して上記ステップ(b)と(c)を実行することを、wmax＝wmin＝MAXとなるまで繰り返してMAXに対応する最大値VMAXを求め、その過程を上記掲示板装置により逐次公開するステップを含むことを特徴とする大小比較方法。
【請求項１６】
請求項１４記載の大小比較方法において、上記情報系列si, tiの各要素は１ビットである。
【請求項１７】
請求項１４又は１６記載の大小比較方法において、上記ステップ(e) は、上記第１及び第２大小比較装置が、公表された上記要素番号MAXに対し、乱数RAMAX及びRBMAXをそれぞれ上記掲示板装置に送信して公開するステップを含むことを特徴とする大小比較方法。
【請求項１８】
請求項１１〜１４の何れかに記載の大小比較方法において、３以上のＬ個の大小比較装置が備えられ、
上記ステップ(a) において、各上記ユーザ装置はVviが入力されるとV1以上Vvi以下に対応した情報は全て等しく、Vviを越えVM以下に対応した情報は全て異なるようなＬ個の情報系列sik, k=1,2,…,Lを作成し、上記Ｌ個の情報系列sikのうち少なくとも２系列sia, sib,ａ≠ｂ,がそろえばVviが分かるものとし、系列sikを第ｋ大小比較装置にそれぞれ秘密に送信するステップを含み、
２個の大小比較装置で大小比較を行い、大小比較装置にトラブルが発生すると、他の正常な大小比較装置を用いてその比較動作を継続して行うことを特徴とする大小比較方法。
【請求項１９】
請求項１１記載の大小比較方法において、
上記ステップ(a) は、各上記ユーザ装置で、上記情報系列si及びtiに対応する情報としてシード値s'i, t'iを秘密に上記第１及び第２大小比較装置にそれぞれ送信し、上記シード値s'i, t'iは、上記意中値Vviに対応する要素番号をviとすると、
一方向性関数Ｆに対してd=0,1,…,vi-1でFd(s'i)＝Fd(t'i)となり、かつe=vi,…,M-1でFe(s'i)≠Fe(t'i)となるよう決められ、上記２つの情報系列si, tiはそれぞれ次式
si＝｛si,1=FM-1(s'i), si,2=FM-2(s'i), …, si,vi-1=FM-vi+1(s'i), si,vi=FM-vi(s'i), …, si,M-1=F(s'i), si,M＝s'i｝
ti＝｛ti,1=FM-1(t'i), ti,2=FM-2(t'i), …, ti,vi-1=FM-vi+1(t'i), ti,vi=FM-vi(t'i), …, ti,M-1=F(t'i), ti,M=t'i｝
で与えられることを特徴とする大小比較方法。
【請求項２０】
請求項１１記載の大小比較方法において、
上記ステップ(a)は、各上記ユーザ装置で初期乱数R1i, R2i, cai, cbi, si,M+1, ti,M+1を生成するステップと、
ｍの初期値をＭと設定し、上記意中値Vviに対応する要素番号viに対し、m=M,M-1,…,vi+1について逐次
si,m＝ti,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
を計算し、si,m＝ti,mである部分系列とし、
m=viについての系列要素
si,m＝ti,m＝h(si,m-1‖ti,m-1‖hM+1-m(cai)‖hM+1-m(cbi))
と、
m=vi-1, vi-2, …, 0についての要素
si,m=ti,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
ti,m＝h(ti,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
とを計算し、si,m≠ti,mの部分系列とし、
これらm=M,M-1,…,1の要素si,m, ti,mの列を上記情報系列si, tiとして得るとともに、m=0の値si,0を得るステップ、とを含み、
上記ステップ(a) は更に、各上記ユーザ装置で、
R1i, si=[si,1,si,2,…,si,M]を暗号化関数EAで暗号化し、得られたEA(si‖R1i)を上記第１大小比較装置へ送信し、R2i, ti=[ti,1,ti,2,…,ti,M]を暗号化関数EBで暗号化し、得られたEB(ti‖R2i)を上記第２大小比較装置へ送信するステップと、
H1i=h(si‖R1i), H2i=h(ti‖R2i), si,0, hM+1(cai), hM+1(cbi)を掲示板装置２１に送り、公開するステップ、とを含むことを特徴とする大小比較方法。
【請求項２１】
請求項１又は１１記載の大小比較方法において、上記ステップ(a) は、各上記ユーザ装置で乱数riを生成し、ri=ai*biなる乱数情報ai, biを決め、＊は予め決めた共通の演算子であり、上記乱数情報ai, tiをそれぞれ上記第１及び第２大小比較装置に送ると共に、それぞれハッシュしてh(ai), h(bi), h(Viv‖ri)を上記掲示板装置に送り、上記ステップ(d) は、最小値VMIN又は最大値VMAX決定後、上記大小比較装置は上記aj, bjを上記掲示板装置に送り上記ユーザ装置はaj, bjにより公開h(aj), h(bj)を検証し、h(Vj‖rj)=h(Vj‖aj*bj)を検証するステップを含むことを特徴とする大小比較方法。
【請求項２２】
請求項１記載の大小比較方法に用いられるユーザ装置が、比較の対象となる整数値についての上限VM及び下限V1のＭ個、Ｍは２以上の整数、の値から選択した意中値Vviを登録する方法であって、
(a) 入力された上記意中値Vviに対し、V1以上Vvi未満に対応した要素は互いに等しく、Vvi以上VM以下に対応した要素は互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成するステップと、
(b) 上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i，H2iを出力するステップと、
(c) 上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信するステップ、
とを含むことを特徴とする意中値登録方法。
【請求項２３】
請求項１１記載の大小比較方法に用いられるユーザ装置が、比較対象となる整数値についての上限VM及び下限V1のＭ個、Ｍは２以上の整数、の値から選択した意中値Vviを登録する方法であって、
(a) 入力された意中値Vviに対し、V1以上Vvi以下に対応した要素は互いに異なり、VVi+1以上VM以下に対応した要素は互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成して出力するステップと、
(b) 上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i，H2iを出力するステップと、
(c) 上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信するステップ、
とを含むことを特徴とする意中値登録方法。
【請求項２４】
請求項１記載の大小比較方法に用いられるユーザ装置であって、
比較の対象となる整数値についての上限VM及び下限V1のＭ個の値が記憶された記憶部と、
V1以上、VM以下の意中の値Vviを入力する入力手段と、
VviとV1，VMが入力され、V1以上Vvi未満に対応した要素は互いに等しく、Vvi以上VM以下に対応した要素は互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びti、又はV1以上Vvi以下に対応した要素は互いに異なり、VVi+1以上VM以下に対応した要素は互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiの一方を生成して出力する情報系列生成部と、ＭはV1以上VM以下の意中値Vviとして選択可能な値の数であり、
上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i， H2iを出力する一方向性関数演算部と、
上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信する送信部と
を含むことを特徴とするユーザ装置。
【請求項２５】
請求項１１記載の大小比較方法に用いられるユーザ装置であって、
比較の対象となる整数値についての上限VM及び下限V1のＭ個、Ｍは２以上の整数、の値が記憶された記憶部と、
V1以上、VM以下の意中の値Vviを入力する入力手段と、
VviとV1，VMが入力され、V1以上Vvi以下に対応した要素は互いに異なり、VVi+1以上VM以下に対応した要素は互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成して出力する情報系列生成部と、
上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i， H2iを出力する一方向性関数演算部と、
上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信する送信部と
を含むことを特徴とするユーザ装置。
【請求項２６】
請求項１又は１１記載の大小比較方法に用いられる大小比較装置であって、
各ユーザ装置から送られた、下限値V1以上、上限値VM以下の意中値Vviとして選択可能な値の数Ｍの要素よりなる情報系列を受信し、掲示板装置から送られた整数値ｗを受信する受信部と、
受信した上記情報系列を記憶する記憶部と、
各ユーザから受信した情報系列中のｗ番目の要素を入力して、これらの連結に対して一方向性関数を演算し、その演算結果を出力する一方向性関数演算部と、
上記一方向性関数演算結果を上記掲示板装置へ送信する送信部と
を含むことを特徴とする大小比較装置。
【請求項２７】
請求項１又は１１記載の大小比較方法に用いられる大小比較装置による大小比較方法であって、
(a) 各ユーザ装置i, i=1,2,…,Nから、下限値V1以上、上限値VM以下のＭ個の値中の意中値Vviを表す情報としてＭ個の要素よりなる情報系列si=[si,1,si,2,…,si,M]をそれぞれ受信するステップと、
(b) 掲示板装置から送られた整数値ｗを受信するステップと、
(c) 各ユーザ装置から受信した情報系列si中のｗ番目の要素si,wを入力して、これらの連結に対して一方向性関数を演算するステップと、
(d) 上記一方向性関数演算結果を上記掲示板装置へ送信するステップ、
とを含むことを特徴とする大小比較方法。
【請求項２８】
請求項１又は１１記載の大小比較方法に用いられる大小比較装置であって、
各ユーザ装置から送られた、下限値V1以上、上限値VM以下の意中値Vviとして選択可能な値の数Ｍの要素よりなる情報系列を受信し、掲示板装置から送られた整数値ｗを受信する受信部と、
受信した上記情報系列を記憶する記憶部と、
各ユーザから受信した情報系列中のｗ番目の要素を入力して、これらの連結に対して一方向性関数を演算し、その演算結果を出力する一方向性関数演算部と、
上記一方向性関数演算結果を上記掲示板装置へ送信する送信部と
を含むことを特徴とする大小比較装置。
【請求項２９】
請求項１又は１１記載の大小比較方法に用いられるユーザ装置の処理をコンピュータで実行するためのプログラムであり、上記プログラムの処理は、
(a) 比較の対象となる整数値についての上限値VM以下、下限値V1以上の入力された意中の値Vviに対し、V1以上、Vvi未満に対応した要素は互いに等しく、Vvi以上、VM以下に対応した要素は互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びti、又はV1以上、Vvi以下に対応した要素は互いに異なり、Vvi+1以上、VM以下に対応した要素は互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiのいずれかを生成する処理と、Ｍは上記下限値V1以上、上記上限値VM以下の意中値Vviとして選択可能な値の数であり、
(b) 上記情報系列si及びtiに対しそれぞれ一方向性関数を演算して演算結果H1i，H2iを出力する処理と、
(c) 上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信する処理、
とを含む。
【請求項３０】
請求項２９記載のプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、情報セキュリティ技術の応用技術であって、例えばインターネットなどによるオンライン上で、複数のユーザ（利用者）が意中の値を秘密に保持したまま比較し、最大値あるいは最小値と、それを意中の値としたユーザだけが特定される大小比較方法、その装置、ユーザの意中値登録方法、そのプログラム及びその記録媒体に関するものである。
【０００２】
【従来の技術】
大小比較がオンラインで実施される例として「電子入札方式」などがある。上記方式では、最大値あるいは最小値と、それを意中の値としたユーザは特定されるが、その他の情報は秘密に保持される技術が例えば
・小林，森田，「大小比較に一方向性関数を用いた効率的な入札方式」,ＩＳＥＣ９９，などに示されている。また、
・H.Kikuchi,M.Harkavy, J.D.Tygar,"Multi-round anonymous auction protocols"In IEEE Workshop on Dependable and Real-Time E-Commerce System,1998,では、ある数値に対してそれ以上あるいはそれ以下を意中の値としたユーザがいるかどうかだけが分かる方式を提案している。
【０００３】
【発明が解決しようとする課題】
後者は最大値あるいは最小値を意中の値としたユーザが複数いる場合にそのユーザを特定できないことと、最大値あるいは最小値を意中の値としたユーザが２番目の数値を知り得てしまうという問題点があった。
この発明の目的は複数のユーザが意中のものとした値の大小をオンラインで比較して、安全かつ効率的に、これらの最大値あるいは最小値、更に必要に応じてそれを意中の値としたユーザだけが特定され、他は秘密が保持されるための大小比較方法、その装置、ユーザの意中値登録方法、そのプログラム及びその記録媒体を提供することにある。
【０００４】
【課題を解決するための手段】
この発明によれば、複数のユーザ装置ｉ,i=1,…,Nと、Nは２以上の整数であり、第１及び第２大小比較装置と、上記ユーザ装置及び上記第１及び第２大小比較装置から受信した情報を公開する掲示板装置とにより、予め決めた下限値V1と上限値VMの範囲の単調増加するＭ個の値Vw、ただし、w=1,2,…,M、で、全ユーザがそれぞれ決めた意中の値Vviからそれらの最小値VMIN及びその最小値を意中値としたユーザｊだけを特定する大小比較方法は、
(a) 各上記ユーザ装置ｉで、ユーザにより入力された意中値Vviに対し、上記下限値V1以上、上記意中値Vvi未満で互いに対応した要素が等しく、上記意中値Vvi以上、上記上限値VM以下で互いに対応した要素が互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成し、それらに対応する情報を秘密にそれぞれ上記第１及び第２大小比較装置に送信するステップと、Ｍは上記下限値V1以上で上記上限値VM以下の上記意中値として選択可能な値の数を表し、
(b) 上記第１大小比較装置で、上記下限値V1以上、上記上限値VM以下の与えられた値Vwについて、全ユーザ装置からの上記情報系列si中のそれぞれｗに対応した要素si,w を取り出し、それらを決められた順序により並べた要素連結Seqs,w＝s1,w‖s2,w‖…‖sN,wを作成するステップと、‖はデータの連結を表し、
(c) 上記第２大小比較装置で、上記与えられた値Vwについて、全ユーザ装置からの上記情報系列ti中のそれぞれｗに対応した要素ti,wを取り出し、それらを決められた順序により並べた要素連結Seqt,w＝t1,w‖t2,w‖…‖tN,wを作成するステップと、
(d) 上記掲示板装置で、上記要素連結Seqs,wとSeqt,w を、それら自身の値を明かすことなく比較し、それらが互いに異なっていればVw以下を意中の値としたユーザがいると判定し、等しければVw以下を意中の値としたユーザがいないと判定し、その判定に基づき、ｗの値を変更していくことで最小意中値VMINを決定し、要素番号MINを公開するステップと、
(e) 上記第１及び第２大小比較装置で，公表された上記要素番号MINに対し，対応する要素連結Seqs,MIN及びSeqt,MINを上記掲示板装置に送信して公開することにより，各上記ユーザ装置に対し，上記要素連結中の互いに対応する要素si,MIN及びti,MINについてsj,MIN≠tj,MINとなる番号ｊが、上記最小意中値をコミットしたユーザ番号ｊであることを検出可能にするステップ，
とを含む。
【０００５】
この発明による上記大小比較方法に用いられるユーザ装置が、比較の対象となる整数値についての上限VM及び下限V1のＭ個、Ｍは２以上の整数、の値から選択した意中値Vviを登録する方法は、
(a) 入力された上記意中値Vviに対し、V1以上Vvi未満に対応した要素は互いに等しく、Vvi以上VM以下に対応した要素は互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びtiを生成するステップと、
(b) 上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i，H2iを出力するステップと、
(c) 上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信するステップ、
とを含む。
【０００６】
この発明による大小比較方法に用いられるユーザ装置は、
比較の対象となる整数値についての上限VM及び下限V1のＭ個の値が記憶された記憶部と、
V1以上、VM以下の意中の値Vviを入力する入力手段と、
VviとV1，VMが入力され、V1以上Vvi未満に対応した要素は互いに等しく、Vvi以上VM以下に対応した要素は互いに異なるそれぞれＭ個の要素からなる２つの情報系列si及びti、又はV1以上Vvi以下に対応した要素は互いに異なり、VVi+1以上VM以下に対応した要素は互いに等しいそれぞれＭ個の要素からなる２つの情報系列si及びtiの一方を生成して出力する情報系列生成部と、ＭはV1以上VM以下の意中値Vviとして選択可能な値の数であり、
上記情報系列si及びtiが入力され、これらに対する一方向性関数を演算して演算結果H1i，H2iを出力する一方向性関数演算部と、
上記情報系列siを第１大小比較装置へ、上記情報系列tiを第２大小比較装置へ、H1i及びH2iを掲示板装置へそれぞれ送信する送信部と
を含むように構成される。
【０００７】
この発明による大小比較方法に用いられる大小比較装置は、
各ユーザ装置から送られた、下限値V1以上、上限値VM以下の意中値Vviとして選択可能な値の数Ｍの要素よりなる情報系列を受信し、掲示板装置から送られた整数値ｗを受信する受信部と、
受信した上記情報系列を記憶する記憶部と、
各ユーザから受信した情報系列中のｗ番目の要素を入力して、これらの連結に対して一方向性関数を演算し、その演算結果を出力する一方向性関数演算部と、
上記一方向性関数演算結果を上記掲示板装置へ送信する送信部と
を含むように構成される。
【０００８】
上述において、最大意中値VMAXを決定するには、一連の値V1〜VMに対し、その大きい順に番号１〜Ｍを対応付け、意中値Vviに対応する番号をviとすると、２つの情報系列si, tiの生成は、番号１〜Ｍに対し、番号要素ｗが１以上、vi未満ではsi,w=ti,wとし、vi以上、Ｍ以下ではsi,w≠ti,wとなるように情報系列を生成すれば、上述したアルゴリズムをそのまま使って意中値Vviの最大値VMAXを決定することができる。
この発明による上記大小比較方法に用いられる大小比較装置による大小比較方法は、
(a) 各ユーザ装置i, i=1,2,…,Nから、下限値V1以上、上限値VM以下のＭ個の値中の意中値Vviを表す情報としてＭ個の要素よりなる情報系列si=[si,1,si,2,…,si,M]をそれぞれ受信するステップと、
(b) 掲示板装置から送られた整数値ｗを受信するステップと、
(c) 各ユーザ装置から受信した情報系列si中のｗ番目の要素si,wを入力して、これらの連結に対して一方向性関数を演算するステップと、
(d) 上記一方向性関数演算結果を上記掲示板装置へ送信するステップ、
とを含む。
【０００９】
この発明による上記大小比較方法に用いられる大小比較装置は、
各ユーザ装置から送られた、下限値V1以上、上限値VM以下の意中値Vviとして選択可能な値の数Ｍの要素よりなる情報系列を受信し、掲示板装置から送られた整数値ｗを受信する受信部と、
受信した上記情報系列を記憶する記憶部と、
各ユーザから受信した情報系列中のｗ番目の要素を入力して、これらの連結に対して一方向性関数を演算し、その演算結果を出力する一方向性関数演算部と、
上記一方向性関数演算結果を上記掲示板装置へ送信する送信部と
を含むことを含むように構成される。
【００１０】
このように、この発明では、各ユーザ11-i(i=1,2,…,N)は、V1以上VM以下の意中の値Vviを決定した後、ユーザ装置により、それぞれＭ個の値からなる２系列の数値をV1以上Vvi未満に対応した要素は等しく、Vvi以上VM以下に対応した要素は互いに異なるような２つの情報系列si及びtiを作成し、siを第１大小比較装置に、tiを第２大小比較装置にそれぞれ秘密に送信する。siあるいはtiだけでは、Vviに関する情報は全く分からないために、誰にもまた各大小比較装置にさえもVviが知られることはない。
【００１１】
全ユーザの意中の値に関する情報si, ti(i＝1,2,…,N)がそろったら次に最小値を決定する。この手順は自由であるが、効率的な手法としては、まず１〜Ｍの２つの変数wmin, wmaxの初期値をそれぞれ１及びＭとし、(wmin+wmax)/2=(1+M)/2以下の最大の整数をｗとし、Vw以下を意中の値としたユーザがいるかどうかの判定を、第１大小比較装置は全ユーザの情報系列siからｗ番目の要素si,wを取り出し、それらを決められた順序（例えばユーザに予め番号が割り振られていてその番号順など）により並べたものSeqs,w＝s1,w‖s2,w‖…‖sN,w（‖はデータの連結を表す）を作成し、第２大小比較装置は全ユーザの情報系列tiからｗ番目の要素ti,wを取り出し、それらを決められた順序により並べたものSeqt,w＝t1,w‖t2,w‖…‖tN,wを作成し、Seqs,wとSeqt,wを、一方向性関数や暗号関数などを用いてそれ自身の値を明かすことなく比較し、それらが異なっていればVw以下を意中の値としたユーザがいると判定し、変数wmaxにｗを代入し、同様にSeqs,w, Seqt,wを生成し、前記比較を行い等しければVw以下を意中の値としたユーザがいないと判定し、変数wminにw+1を代入して、上記操作をwmin＝wmax(=MIN)となるまで繰り返すことで最小値VMINを決定する。
最後にwmin=wmax=MINである場合、Seqs,MIN, Seqt,MINを公開して、誰もが最小値VMINを意中の値としたユーザを特定することができる。
【００１２】
【発明の実施の形態】
大小比較を行う際、上限の整数値VM、下限の整数値V1、大きな素数Ｐがすでに決められているものとする。素数ＰはP-1が大きな素因数を約数に持つ、つまり離散対数問題をより所とする暗号方式の条件を満すような素数である。
まず第１の実施例として、２つの大小比較装置を用いて全ユーザの意中の値から最小値及びそれを意中の値としたユーザのみが特定できる方法を示す。次に第２の実施例として、そのセキュリティを改善した例を、また、第３実施例として３つの大小比較装置を用いて、そのうちの一つが大小比較の途中でシステムがダウンした場合に、全ユーザの読み出した意中の値から最小値及びそれを意中の値としたユーザのみを特定できる方法を示す。
第１実施例
まずはじめに、第１の実施例におけるシステム全体の構成を図１に示す。ユーザ装置13-1〜13-N、大小比較装置１５Ａ及び１５Ｂ、掲示板装置２１及びデータベース２３が設けられ、各ユーザ装置13-1〜13-Nは通信網を通じて大小比較装置１５Ａ，１５Ｂ、及び掲示板装置２１と通信することができ、大小比較装置１５Ａ及び１５Ｂは掲示板装置２１と通信することができる。記号Ｙは掲示板装置２１から読み出された閲覧情報を示す。また掲示板装置２１にはデータベース２３が接続されている。なお、図１に破線で示す大小比較装置１５Ｃは、後述の第３実施例において使用されるものである。
【００１３】
各ユーザ装置13-iは、図２に示すように入力部３０と、乱数生成部３１と、記憶部３２と、情報系列生成部３３と、暗号化部３４と、ハッシュ関数演算部３５と、送信部３６と、制御部３７と、連結部３８と、分解部３９とから構成される。
各ユーザ11-ｉ(i=1,2,…,N)は、V1以上VM以下の意中の整数値Vviを定め、そのユーザ装置13-iにキーボードなどの入力部３０により入力する。ユーザ装置13-iの情報系列生成部３３は入力されたVviと乱数生成部３１により生成した乱数に基づき同じ要素数Ｍの２系列の情報si＝｛si,1, si,2,…,si,M｝と ti＝｛ti,1, ti,2,…, ti,M｝を生成する。ＭはV1からVMまでのユーザが意中の値として選択することができる値の数であり、従って、単調増加の一連の値V1〜VMはそれぞれ番号１〜Ｍに１対１で対応する。
【００１４】
ここでユーザ11-iは意中値をVviと決めると、2系列si, tiをsi,1＝ti,1，si,2＝ti,2，…，si,vi-1＝ti,vi-1，si,vi≠ti,vi，si,vi+1≠ti,vi+1，…，si,M≠ti,Mとなるように生成する。つまりsiとtiは、V1以上Vvi未満の対応した要素（情報）は互いに等しく、Vvi以上VM以下の対応した要素は互いに異なるように生成する。
図３は、このような２系列の情報siとtiの生成手順の例を示す。
ステップＳ１：予め決めたビット数からなるvi-1個の乱数r1, r2, …, r(vi-1)を生成し、これらをsi,m=ti,m, m=1,2,…,vi-1である２つの部分系列si,1, si,2, …, si,vi-1及びti,1, ti,2, …, ti,vi-1とする。
ステップＳ２：ｍをviとする。
ステップＳ３：２個の乱数rs, rtを生成する。
ステップＳ４：この２個の乱数rsとrtを比較し、等しければステップＳ３に戻る。
ステップＳ５：これら２個の乱数が互いに異なればrsをsi,mに、rtをti,mにそれぞれ設定し、ｍを＋１する。
ステップＳ６：ｍがＭより小であればステップＳ３に戻る。
ステップＳ７：ステップＳ６でｍがＭより小でなければ、ステップＳ１で生成した２つの部分系列si,1, si,2, …, si,vi-1及びti,1, ti,2, …, ti,vi-1にステップＳ３〜Ｓ５の繰り返しで設定したsi,vi, si,vi+1,  …, si,Mとti,vi, ti,vi+1, …, ti,Mをそれぞれ連結して２系列情報si=｛si,1, si,2, …, si,M｝とti=｛ti,1, ti,2, …, ti,M｝を得て、図２の記憶部３２に保存する。
【００１５】
乱数生成部３１で乱数R1i，R2iを生成し、(si，R1i)の組を大小比較装置１５Ａに、(ti，R2i)の組を大小比較装置１５Ｂにそれぞれ秘密に、例えば暗号化部３４で暗号化関数EA, EBにより暗号化して暗号化系列情報EA(si‖R1i), EB(ti‖R2i)として送信する。暗号化関数EA及びEBはそれぞれ大小比較装置15A及び15Bのみが復号できる公開鍵暗号関数である。また、後述する最小の意中値VMINの正当性を検証するためのデータとして、乱数生成部３１で乱数riを生成し、連結部３８で意中値Vviと乱数riを連結したVvi‖riを生成し、更に、分解部３９でri=ai*bi（＊は予め公表されている演算子）となる乱数情報ai, biを決める。演算子＊はai, biが与えられればriが一義に定まるものである必要があればどのようなものでもよく、例えば排他的論理和、減算、加算、その他を使用することができる。
【００１６】
ハッシュ関数演算部３５で各系列と乱数の連結si‖R1i及びti‖R2iに対しハッシュ関数ｈによってハッシュ値H1i＝h(si‖R1i)，H2i＝h(ti‖R2i)を計算する。ハッシュ関数演算部３５は更に、ai, bi, Vvi‖riのハッシュ値h(ai), h(bi), h(Vvi‖ri)を計算し、これら全てを掲示板装置２１に送信する。なお、最小値及び最大値V1、VM、２系列si，ti、乱数R1i，R2i，意中値Vvi、乱数ri、乱数情報ai, biは記憶部３２に記憶され、各情報の大小比較装置１５Ａ，１５Ｂや掲示板装置２１への送信は送信部３６が行う。記憶部３２に対する読み書き、各部に対する動作指示は制御部３７により行う。このユーザ装置13-iはコンピュータによりプログラムを実行させて機能させるように構成してもよい。
【００１７】
各ユーザ装置13-iはこのようにハッシュ値h(Vvi‖ri), H1i及びH2iを掲示板装置２１に送信し、その値が公開されることで意中値Vviをコミットしたことになる。つまり意中値Vviを公に明かすことなく、Vviを意中の値としたことを登録したことになる。これにより、以降、意中値Vviを変更不可能とするとともに、もしなんらかの理由で自分の意中の値Vviより大きい値が最小値VMINととして掲示板装置２１に公表された場合は、si，R1i，ti，R2iの組又は(Vvi‖ri)を公開することで自分の意中値Vviが公表された最小値VMINより小さいことを示し、不正を立証することができる。また、掲示板装置2１に情報系列si, tiを送る際に、それらをそれぞれ単独でハッシュするのではなく、情報系列si, tiと乱数R1i, R2iをそれぞれ連結してハッシュする理由は、以下の理由による。即ち、H1i＝h(si)，H2i＝h(ti)とすると、もし通信容量削減のため情報系列si, tiの各要素のビット数を小さくし、かつ系列siあるいはtiの一方を他ユーザが何らかの方法で知ったとすると、そのユーザは他方の値も推定しやすくなる（従って、si, tiを知ればVviが分かる可能性がある）ので、そのようなことを防ぎ、大小比較装置１５Ａ，１５Ｂに対して秘密を高めるためである。しかしながら、秘密性をある程度緩めてよい、又は各要素のビット数が大きいのであれば、乱数R1i，R2iを省略してもよい。
【００１８】
大小比較装置１５Ａ（及び１５Ｂ）の構成は図４（及び図５）に示すように、受信部40A（40B)と、復号部47A(47B)と、記憶部47A(47B)と、乱数生成部42A,(42B)と、ハッシュ関数演算部43A(43B)と、べき乗剰余演算部44A(44B)と、送信部45A(45B)と、制御部46A(46B)とから構成されている。
大小比較装置１５Ａの受信部40Aに受信された各ユーザ装置13-iからの暗号化系列情報EA(si‖R1i)は復号部47Aにより復号されてsi‖R1i(i=1,…,N)が得られ、必要に応じてsi‖R1iをハッシュ関数演算部43Aでハッシュすることによりh(si‖R1i)を得て、これが掲示板装置２１に公開されたH1iと一致することを検証することができる。得られたsi‖R1iから情報系列s1〜sN及び乱数R11〜R1N分離され、それぞれ記憶部41Aに格納される。記憶部41Aには前述した大きな素数Ｐも予め格納されてある。同様に、大小比較装置１５Ｂの受信部40Bに受信された各ユーザ装置13-iからの暗号化系列情報EB(ti‖R2i)は復号部47Bにより復号され、得られたti‖R2iを同様に検証してから情報系列t1〜tN及び乱数R21〜R2Nを分離し、それぞれ記憶部41Bに格納する。記憶部41Bには前記大きな素数Ｐが格納されている。
【００１９】
掲示板装置２１はユーザ装置13-1〜13-N及び大小比較装置15A, 15Bから受信した情報をデータベース２３に格納し、どの装置からでもアクセス可能に公開し、後述の大小比較処理においては、大小比較装置15Aと15Bからの情報が一致するか判定し、判定結果に基づいて大小比較装置15A, 15Bに与えるｗの値を更新するだけであり、それらの構成は図示してない。
全てのユーザ装置13-i, i=1,…,N,から暗号化情報EA(si‖R1i)，EB(ti‖R2i)、ハッシュ値H1i，H2i, h(Vvi‖ri), h(ai), h(bi)の送信が完了すると、例えば掲示板装置２１から、１〜Ｍの２つの整数変数wmin, wmaxの初期値をそれぞれ１及びＭとし、(wmin+wmax)/2=(1+M)/2以下の最大の整数をｗとして初期値Vwが大小比較装置１５Ａ，１５Ｂに送信し、受信部40A, 40Bで受信される。大小比較装置１５Ａは、図４に示すように乱数生成部42Aから乱数RAwを生成し、系列生成器48Aで各ユーザ装置13-iから受信した系列si中のｗに対応した要素si,wを記憶部41Aから取り出し、それらをユーザ11-1，ユーザ11-2，…，ユーザ11-Nの順に並べた要素の連結Seqs,w＝s1,w‖s2,w‖…‖sN,wを作成する。ハッシュ関数演算部43Aはハッシュ関数h'によって要素連結Seqs,wに対するハッシュ値HSw＝h'(Seqs,w)と連結器49Aで生成した乱数RAwとハッシュ値HSwの連結RAw‖HSwに対するハッシュ関数ｈによるハッシュ値HAw＝h(RAw‖HSw)を計算し、そのHSwと乱数RAwをべき乗剰余演算部44Aに入力してCAw=HSwRAw(mod P)を計算し、それら(HAw，CAw)の組を送信部45Aから掲示板装置２１に送信し、公開する。ただし、ハッシュ関数h'は任意の値を有限体Fp上に一意に、かつランダムに写すような一方向性関数である。また、ハッシュ関数ｈはSHA-1のような汎用性関数である。
【００２０】
大小比較装置１５Ｂは図５に示すように乱数生成部42Bで乱数RBwを生成し、全ユーザ装置から受信した各情報系列ti中のｗに対応した要素ti,wを記憶部41Bから取り出し、それらをユーザ11-1，ユーザ11-2，…，ユーザ11-Nの順に並べた要素連結Seqt,w＝t1,w‖t2,w‖…‖tN,wを作成する。ハッシュ関数演算部43Bは、ハッシュ関数h'によって要素連結Seqt,wに対するハッシュ値HTw＝h'(Seqt,w)と、連結器49Bで生成した乱数RBwとハッシュ関数ｈによるハッシュ値HTwの連結RBw‖HTwに対するハッシュ値HBw＝h(RBw‖HTw)を計算する。これらHTwとRBwをべき乗剰余演算部44Bに入力してCBw=HTwRBw(mod P)を計算し、それら(HBw，CBw)の組を送信部45Bから掲示板装置２１に送信し、公開する。
【００２１】
次に大小比較装置１５Ａは、掲示板装置２１により公開されたCBwを読み、べき乗剰余演算部44Aに入力し、先に生成した乱数RAwを使ってCBwRAwを計算し、その計算結果を掲示板装置２１に送信する。大小比較装置１５Ｂも同様に、掲示板装置２１により公開されたCAw=HSwRAw(mod P)を読み、べき乗剰余演算部44Bに入力してCAwRBw=(HSwRAw)RBw(mod P)を計算し、その結果を掲示板装置２１に送信する。
図６は各ユーザ装置13-iが情報系列生成部３３で生成する情報系列si, ti, i=1,…,Nを模式的にそれぞれ縦に並べて示す。各対の系列si=｛si,1,si,2,…,si,m,…,si,M｝, ti=｛ti,1,ti,2,…,ti,m,…,ti,M｝中の対応する要素の任意の組(si,m, ti,m), m=1,2,…,Mにおいて、直線部はsi,m=ti,mの部分系列を表し、ジグザグ部はsi,m≠ti,mの部分系列を表している。例えば、図に示すように、m=wの値が全ての系列si, tiの組に対し、それらの直線部を通る場合は、(s1,w‖s2,w‖…‖sN,w)＝(t1,w‖t2,w‖…‖tN,w), 即ち、Seqs,w＝Seqt,wであり、従って、h'(Seqs,w)=h'(Seqt,w),即ちHSw=HTwであることがわかる。しかしながら、ｗの高さが少なくとも１組のsi, tiのジグザグ部を通る高さであれば、(s1,w‖s2,w‖…‖sN,w)≠(t1,w‖t2,w‖…‖tN,w)なので、HSw=HTwとなる可能性は無視できる程度に小さい。従って、HSw≠HTwとなる。
【００２２】
HSwとHTwが等しければ、掲示板装置２１に送信された(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)は等しい。またＰが大きな素数であり、かつP-1は大きな素因数を約数にもつから、HSwとHTwが異なれば、(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が等しくなる可能性は無視できるほど小さい。従って、(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が等しければs1,w＝t1,w，s2,w＝t2,w，…，sN,w＝tN,wであるから、各ｉに対し、si,m=ti,m, m=1,…,wであり、V1からVMのＭ個の値のうち、１番目からｗ番目までの値V1〜Vwに意中値Vviはなく、従っての最小意中値VMINはない。即ち、w+1番目からＭ番目までに最小意中値があることになる。(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が異なればｗ番目以下に最小意中値があるということが圧倒的確率で分かる。
【００２３】
掲示板装置２１はこの比較判定を行い、もし(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が等しければ変数wminにw+1を代入し、異なれば変数wmaxにｗを代入して上記操作を繰り返す。以上のことを繰り返すことにより、およそlogＭ回でwmax＝wmin(＝MINとおく)となる。このとき、V1〜VM中のMIN番目の値VMINが最小意中値である。
上述の最小値探索手順を図７に示す。
ステップＳ１：掲示板装置２１は、まず1〜Ｍの整数変数wminとwmaxの初期値をそれぞれ１及びＭとし、(wmin+wmax)/2以下の最大の整数ｗを求め、そのｗを大小比較装置１５Ａ、１５Ｂに送信する。
ステップＳ２Ａ：大小比較装置１５Ａでは要素連結Seqs,w及び乱数RAwを生成し、ハッシュ値HSw=h'(Seqs,w), HAw=h(RAw‖HSw)及びべき乗剰余CAw=HSwRAw(mod P)をそれぞれ計算し、(HAw, CAw)を掲示板装置２１に送信する。
ステップＳ２Ｂ：大小比較装置１５Ｂにおいても同様に要素連結Seqt,w及び乱数RBwを生成し、HTw=h'(Seqt,w), HBw=h(RBw‖HTw)，CBw=HTwRBw(mod P)をそれぞれ計算し、(HBw, CBw)を掲示板装置２１に送信する。
ステップＳ３Ａ：大小比較装置１５Ａは、掲示板装置２１からCBwを読み取り、CBwRAwmod P=(HTwRBw)RAwmod Pを計算して掲示板装置２１に送信する。
ステップＳ３Ｂ：大小比較装置１５Ｂは、掲示板装置２１からCAwを読み取り、CAwRBwmod P=(HSwRAw)RBwmod Pを計算し、掲示板装置２１に送信する。
ステップＳ４：掲示板装置2１は(HTwRBw)RAwmod Pと(HSwRAw)RBwmod Pが一致しているかを調べる。
ステップＳ５：一致していればw+1をwminとする。
ステップＳ６：一致していなければｗをwmaxとする。
ステップＳ７：wmax＝wminになったかを調べ、なっていなければステップＳ１に戻り、ステップＳ２Ａ，Ｓ２Ｂ，Ｓ３Ａ，Ｓ３Ｂ，Ｓ４，Ｓ５，Ｓ６による同様の処理が繰り返される。
ステップＳ８：ステップＳ７でwmaxとwminとが等しければ、そのwmin=MINと、その番号MINに対応する値を最小意中値VMINとして共に公表する。大小比較装置15A, 15BはMINに対応する要素連結Seqs,MIN, Seqt,MINを掲示板装置２１に送信することにより、これら２つの要素連結中の対応する要素sj,MINとtj,MINが互いに異なるユーザ11-jを特定可能にする。
【００２４】
つまりユーザ11-1〜11-Nがそれぞれ意中値Vv1〜VvNとしてコミットしたもののうちの最小意中値VMINが求まったことになる。この最小意中値VMINが分かった後、大小比較装置１５Ａ，１５Ｂはそのwmin=wmax= MINとなったときのSeqs,MIN，RAMIN，Seqt,MIN，RBMINを掲示板装置２１に送信することにより、全ユーザ11-1〜11-Nは、それら２要素連結Seqs,MIN, Seqt,MINの対応する要素si,MINとti,MIN, を各i=1,…,Nについて比較し、対応する部分がsj,MIN≠tj,MINとなる情報が入ったｊ番目の部分に該当するユーザ11-jが最小意中値VMINを意中値Vvjとしたことを確認できる。Seqs,MIN，Seqt,MINの配列順が知られていれば、前記異なるｊ番目に該当するユーザｊが特定できる。
【００２５】
上述の第１実施例において、大小比較装置１５Ａはユーザ11-i, i=1,…,Nからri=ai*biなる乱数情報aiを受信しており、大小比較装置１５Ｂはユーザ11-iから乱数情報biを受信している。又、掲示板装置２１は各ユーザ11-iからh(ai), h(bi), h(Vvi‖ri)を受信している。従って、最小意中値VMINの探索前において、もし大小比較装置１５Ａが全てのユーザについての乱数riを知ってしまったら、各ｉについてV1からVMまで各値Vwに対し順次h(Vw‖ri)を計算することにより、公開されているh(Vvi‖ri)と一致するVw=Vviを見つけることができ、従って、掲示板装置２１がVMINの探索を開始する前にVMINが大小比較装置１５Ｂに知られてしまい、セキュリティの点から好ましくない。しかしながら、上述の第１実施例では、ri=ai*biの乱数情報aiとbiは大小比較装置１５Ａと１５Ｂに別々に与えるので、大小比較装置１５Ａ，１５Ｂは何れも単独でVMINを探索することはできない。
【００２６】
最小意中値VMINの探索後、掲示板装置２１に公開された最小意中値VMINの正当性は以下のようにして検証することができる。
ユーザ11-jのh(aj), h(bj), h(Vvj‖rj)はすでに公開されている。大小比較装置１５Ａ、１５Ｂはそれぞれ乱数情報aj, bjを掲示板装置２１に送信し、公表する。各ユーザ装置13-iは、公開されたVvj=VMIN, rj=aj*bjを使ってh(VMIN‖aj*bj)を計算し、h(VMIN‖aj*bj)=h(Vvj‖rj)が成立するかを検証する。一致しない場合は、ユーザ11-jが不正をしたか、大小比較装置１５Ａ又は１５Ｂが不正をしたことになる。そこで、aj, bjからh(aj), h(bj)を計算し、それらが公開されているものと一致するか検証する。不一致であれば、aj, bjのうち不一致のものを送信した大小比較装置が不正をしたと判定することができる。もし、両方とも一致すれば、公開されたh(Vvj‖rj)を送信したユーザｊが不正をしたと判定できる。
【００２７】
このように、各ユーザはri=ai*biなるai, biを決め、h(ai), h(bi), h(Vvi‖ri)を掲示板装置２１に公開しておくことにより、大小比較装置１５Ａ，１５Ｂが掲示板装置２１に送信したaj, bjの正当性を確認することができるが、これは掲示板装置２１により公開された検証用情報h(ai), h(bi)がユーザ11-iのものであることさえ証明されていれば、ai, biにユーザ11-iが署名をつけて正当性を保証する場合と同等の効果が得られ、しかも署名を使用する場合より演算処理量が少なく、かつ、ユーザは署名手段を必要としない利点がある。なお、乱数riはセキュリティの観点から十分な大きさであることが望ましい。
【００２８】
なお上述の第１実施例において、仮にHTwを知ったものがHSwを推定でき、それが正しければ他のユーザの意中の値を知ることができるが、Ｐが大きな素数であり、かつP-1は大きな素因数を約数にもつようにされているためHSwRAwmod PのRAwを求めることが困難であるため、そのHSwが真に正しいものか知ることができない。従って他のユーザが意中の値を知ることはできない。
最後に、RAMIN，RBMINを公開することにより、これらとSeqs,MIN，Seqt,MINを用いることにより、大小比較処理が正しく行われたかを確認することができる。
【００２９】
大小比較装置１５Ａ，１５Ｂにおいては、その記憶部41A, 41Bに対する読み書き、受信情報の処理、各送信情報を対応する装置へ送信部45A, 45Bにより送信させ、その他の各部の動作をさせることなどを制御部46A, 46Bで行う。この大小比較装置１５Ａ，１５Ｂもコンピュータによりプログラムを実行させて機能させることもできる。
掲示板装置２１はその機能構成を特に図に示さなかったが、各ユーザ装置、大小比較装置１５Ａ，１５Ｂとの送受信部を備え、受信された情報をデータベース２３（図１）に格納し、閲覧要求があれば、対応する情報をデータベース２３が読み出して、要求元へ送信し、また図７に示した処理とその実行に必要な送受信を行う。この掲示板装置２１もコンピュータによりプログラムを実行させて機能させるようにすることもできる。
【００３０】
上述では一連の値V1〜VMに対し、その小さい順に番号１〜Ｍを対応付け、全ユーザの意中値Vvi中の最小値VMINを決定する場合を説明したが、最大意中値VMAXを決定するには、一連の値V1〜VMに対し、その大きい順に番号１〜Ｍを対応付けすれば、意中値Vviに対応する番号をviとすると、２つの情報系列si, tiの生成は、番号１〜Ｍに対し、番号要素ｗが１以上、vi未満ではsi,w=ti,wとし、vi以上、Ｍ以下ではsi,w≠ti,wとなるように情報系列を生成すれば、上述したアルゴリズムをそのまま使って意中値Vviの最大値VMAXを決定することができる。つまり、図６において値V1〜VMの上下を逆転して並べるだけで、前述した最小意中値VMINを与える番号MINを決定することは最大意中値VMANを与える番号MAXを決定することと同じであることが分かる。即ち、上述の第１実施例において、V1〜VMに対する1〜Ｍの番号付けを逆にＭ〜１とし、MINをMAXに置き換えれば図７の処理は最大意中値VMAXを探索する大小比較処理手順を示すことになる。このことは以下の実施例についても同様である。
第２実施例
ところで、上述の第１実施例において、もしあるユーザ11-iがいずれか一方の大小比較装置と結託すれば、そのユーザ11-iはすでに意中値Vviをコミットしているにもかかわらず、他ユーザ及び他大小比較装置に知られることなく、試合放棄（入札の取り下げ）ができてしまう。ここで、試合放棄とは、コミットした意中値Vviとは無関係に、即ち、全ユーザの意中値Vv1,Vv2,…,VvN中、Vviが最小であるか否かに係わらず、そのユーザ11-iが最小意中値VMINに決まることがない（落札しない）ことを意味する。
【００３１】
例えば、ユーザ11-iが大小比較装置１５Ｂと結託し、図７の大小比較処理において、掲示板装置２１からｗが与えられるごとに、ステップＳ２Ｂでそのユーザ11-iの系列要素ti,wを要素連結Seqt,wに埋め込む代わりに、ユーザ11-iから知らされた系列要素si,wの値を埋め込むことにより、即ち本来si,w≠ti,wであるべきところを系列si,w=ti,wとしてしまうことにより、たとえユーザ11-iの意中値Vviが最小値VMINであったとしても、掲示板装置２１による最小値探索でユーザ11-iが最小値VMINとして決定されることはなくなり、残りのユーザのいずれかがVMINと決定されてしまう。このような決定は正当であるといえない。この最小値VMINの決定の正当性については、前述の正当性の検証方法は、最小値VMINと決定され、公表された意中値Vvjとユーザ11-jに対してのみh(Vvj‖rj)とh(aj‖bj)を検証するだけなので、ユーザ11-iと大小比較装置１５Ｂの結託による不正を検出することはできない。
【００３２】
以下に、このようなユーザと大小比較装置の結託による不正ができないように改善した実施例の大小比較方法を説明する。
この第２実施例の特徴は、第１実施例における各ユーザ11-iの対の情報系列si, tiの生成方法にあり、その特徴は、Ｍ個の要素からなる系列si=｛si,1,…,si,M｝及びti=｛ti,1,…,ti,M｝の生成において、第ｍ番目の要素の生成は、それを遡る全ての要素の情報に基づいて生成することである。従って、系列si,1, si,2, …, si,Mを生成した場合、もし、ｍ番目の要素si,mをti,mあるいは他の任意の値s'i,mで置き換えると、系列si,1, si,2, …, s'i,m, …, si,Mにおける要素s'i,mはそれより遡った要素si,1, si,2, …, si,m-1の情報に基づいておらず、また、それ以降の要素si,m+1, …,si,Mも要素si,m以前の要素に基づいていないので、その不正な置き換えを検出することができる。以下、第２実施例を具体的に説明する。
【００３３】
図８は第２実施例による大小比較方法を実施するためのユーザ装置13-iの構成を示す。この構成は、図２のユーザ装置において連結部３８及び分解部３９を除去し、情報系列生成部３３を図９に示す構成としたものである。乱数生成部３１は図２の実施例と同様に乱数R1i, R2iを生成し、更に初期乱数としてsi,M+1, ti,M+1, cai, cbiを生成する。情報系列生成部３３はこれら初期乱数を元に、順次si,M, si,M-1,…,si,1,及びsi,0と、ti,M, ti,M-1,…,ti,1を生成する。
図９は情報系列生成部３３の構成例を示す。図９において、情報系列生成部３３はハッシュ演算器33-1A, 33-1Bと、連結器33-2A, 33-2Bと、ハッシュ演算器33-3A, 33-3Bと、連結器33-4とから構成される。ハッシュ演算器33-1A, 33-1Bは初期乱数cai, cbiがそれぞれ与えられ、それらのハッシュ値h(cai), h(cbi)を演算し、次回以降はそれら演算結果を繰り返しハッシュ演算する。連結器33-2Aは前回までのsi系列情報と、その回のハッシュ演算器33-1A, 33-1Bの出力を連結する。連結器33-2Bは前回までのti系列情報と、その回のハッシュ演算器33-1A, 33-1Bの出力を連結する。ハッシュ演算器33-3A, 33-3Bはそれぞれ連結器33-2A, 33-2Bの出力をハッシュ値を計算し、その回の系列要素si,m, ti,mとして出力する。ハッシュ演算器33-3A, 33-3Bによるｍ回目のハッシュ演算のために連結器33-2A, 33-2Bに入力するハッシュ演算器33-1A, 33-1Bの出力は、m+1回目のハッシュ演算出力である。
【００３４】
si,m≠ti,mの部分系列si,m, ti,mを生成する処理においては、si系列情報及びti系列情報の初期値としてそれぞれsi,M+1, ti,M+1を連結器33-2A, 33-2Bに入力し、ハッシュ器33-1A, 33-1Bの１回目のハッシュ出力を両連結器33-2A, 33-2Bに入力し、それらの連結器の出力のハッシュ値が２回目以降のsi系列情報及びti系列情報として連結器33-2A, 33-2Bの入力として与えられる。
m=Mからm=vまでの部分系列の生成が終了すると、意中値Vviに対応するm=vi-1において連結器33-4の出力si,vi‖ti,viを両連結器33-2A, 33-2Bにそれぞれsi系列情報及びti系列情報として入力し、連結結果をそれぞれハッシュ演算器33-3A, 33-3Bでハッシュ値を計算する。この処理では、同じハッシュ演算器33-1A, 33-1Bの出力と同じ系列情報si,vi‖ti,viが両連結器33-2A, 33-2Bに与えられるので、m=vi-1でのハッシュ演算器33-3A, 33-3Bの出力si,mとti,mは等しくなる。
【００３５】
以降は、再びハッシュ演算器33-3A, 33-3Bの出力si,m, ti,mがそれぞれ系列情報として連結器33-2A, 33-2Bに入力され、m=vi-2, vi-3, …, 0について逐次演算を繰り返すことによりsi,m=ti,mの部分系列が生成される。
図１０は第２実施例におけるユーザ装置13-iの処理手順を示す。
ステップＳ１：ユーザ11-iは初期乱数R1i, R2i, cai, cbi, si,M+1, ti,M+1を生成する。
ステップＳ２：ｍの初期値をＭと設定し、意中値Viに対応する要素番号viに対し、m=M,M-1,…,viについて逐次
si,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
ti,m＝h(ti,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
を計算し、si,m≠ti,mである部分系列として保存する。
ステップＳ３：m=vi-1についての系列要素
si,m＝ti,m＝h(si,m+1‖ti,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
を計算し、保存する。
ステップＳ４：m=vi-2, vi-3, …, 0について逐次
si,m=ti,m＝h(si,m+1‖hM+1-m(cai)‖hM+1-m(cbi))
を計算し、si,m=ti,mの部分系列として保存する。
ステップＳ５：R1i, si=[si,1,si,2,…,si,M]を暗号化し、得られたEA(si‖R1i)を大小比較装置１５Ａへ送信し、R2i, ti=[ti,1,ti,2,…,ti,M]を暗号化し、得られたEB(ti‖R2i)を大小比較装置１５Ｂへ送信する。
ステップＳ６：H1i=h(si‖R1i), H2i=h(ti‖R2i), si,0, hM+1(cai), hM+1(cbi)を掲示板装置２１に送り、公開する。
【００３６】
掲示板装置２１と大小比較装置１５Ａ，１５Ｂによる大小比較処理、即ち最小意中値VMIN探索処理は、図７と同じである。
最小意中値VMINの特定以降、掲示板装置２１は各ユーザ装置13-iから受信したh(cai), h(cbi)をM+1-MIN回ハッシュ演算することによりhM+1-MIN(cai), hM+1-MIN (cbi), i=1,2,…,Nを得て、これらを公開する。これらの値の正当性は、これらの値を更にMIN回ハッシュ演算して得られた値が公開情報hM+1(cai), hM+1(cbi)と一致することを検証することにより保障される。更に、勝者（落札者）特定のフェーズによって、各ユーザのsi,MIN, ti,MIN, hM+1-MIN(cai), hM+1-MIN(cbi)が公開されているため、これらを使ってステップＳ４を実行することによりこれらからどのユーザもsi,0を計算できる。
【００３７】
ここで、もし前述のようにユーザ11-iと大小比較装置１５Ａまたは１５Ｂが結託してsi,wとti,wの置き換えをこれらsi,MIN及びti,MINに対して行っていれば、一般にsi,0とは異なる値が計算される。即ち、この置き換えは検出されることになる。ただし、この検証は意中値の選択可能数Ｍとユーザ数Ｎの積MNのオーダで効率が悪い。しかしながら、本来の目的は勝者とその意中値を導出することなので、この敗者の"正当性検証フェーズ"は本質的でなく、実際にはプロトコル終了後に行えば十分である。
第３実施例
前述の第１及び第２実施例においては、２つの大小比較装置を使用し、各ユーザ装置は２系列の情報si, tiを生成する場合を示したが、第３実施例は、図１に破線で示す第３の大小比較装置１５Ｃを加えて３つの大小比較装置を使用する。各ユーザは３系列の情報si,ti,uiを前述の実施例と同様にm=1,2,…,vi-1に対してsi,m=ti,m=ui,mとし、m=vi,vi+1,…,Mに対してsi,m≠ti,m≠ui,mとなるように生成し、それぞれ秘密に３つの大小比較装置に送り、第１実施例と同様に２つの大小比較装置と掲示板装置による大小比較処理を行う。この場合、２つのうちのいずれか一方が故障した場合、第３の大小比較装置が故障したものに代わって処理を実行可能である。基本的な動作は第１実施例と同様であるので、それらの図を参照して以下に説明する。
【００３８】
ユーザ11-i(i=1,2,…,N)は、V1以上VM以下の意中の整数値Vviを定め、図２のユーザ装置13-iにおける情報系列生成部３３によりV1以上Vvi未満に対応した情報は全て等しく、Vvi以上VM以下に対応した情報は全て異なるような３系列の情報si，ti，uiを作成する。また、乱数生成部３１により乱数R1i，R2i，R3i及びriを生成し、ri=ai*bi*ciなる乱数情報ai, bi, ciを決める。(si，R1i)の組と情報aiを大小比較装置１５Ａに、(ti，R2i)の組と情報biを大小比較装置１５Ｂに、(ui，R3i)の組と情報ciを大小比較装置１５Ｃに、それぞれ秘密に（即ち、暗号化して）送信する。また、各組の連結si‖R1i，ti‖R2i，ui‖R3iについてハッシュ関数ｈによってハッシュ値H1i＝h(si‖R1i)，H2i＝h(ti‖R2i)，H3i＝h(ui‖R3i)を計算し、更に、乱数情報のハッシュ値h(ai), h(bi), h(ci)と意中値Vviと乱数riのハッシュ値h(Vvi‖ri)を計算し、更に乱数情報のハッシュ値h(ai), h(bi), h(ci)と意中値Vviと乱数riのハッシュ値h(Vvi‖ri)を計算し、それらを掲示板装置２１に送信し、公開する。
【００３９】
各ユーザ11-iはH1i, H2i, H3i及びh(Vvi‖ri)を掲示板装置２１に送信し、その値が公開されることでVviをコミットしたことになる。これにより、以降、意中の値を変更不可能とするとともに、もしなんらかの理由で自分の意中の値より大きい値が最小値となったときは、(si，R1i)，(ti，R2i)，(ui，R3i)の少なくとも２組を公開することで自分の意中の値が最小値であることを示すことができる。ただし、少なくとも２組が揃えばriが計算できるものとする。
以降の大小比較処理は、第１実施例で示したように掲示板装置２１と２つの大小比較装置があればできるので、２つの大小比較装置，例えば１５Ａ及び１５Ｂを使って図７の処理手順に従って実行する。
【００４０】
即ち、掲示板装置２１は、まず(wmin+wmax)/2=(1+M)/2以下の最大の整数ｗを初期値として大小比較装置１５Ａ，１５Ｂに送る。大小比較装置１５Ａは、乱数RAw を生成し、全ユーザ装置から受信した系列si の要素si,wを取り出し、それらをユーザ11-1, 11-2, …,11-Nの順に並べた要素の連結Seqs,w＝s1,w‖s2,w‖…‖sN,wを作成する。更に、ハッシュ関数h'によるハッシュ値HSw＝h'(Seqs,w),ハッシュ関数ｈによるハッシュ値HAw＝h(RAw‖HSw)及びべき乗剰余CAw=HSwRAw(mod P)を計算し、それら(HAw,CAw)の組を掲示板装置に送信する。大小比較装置１５Ｂは、乱数RBwを生成し、全ユーザ装置から受信した系列ti の要素ti,wを取り出し、それらをユーザ11-1，11-2,…, 11-Nの順に並べた要素連結Seqt,w＝t1,w‖t2,w‖…‖tN,wを作成し、ハッシュ関数h'によるハッシュ値HTw＝h'(Seqt,w)、ハッシュ関数ｈによるハッシュ値HBw＝h(RBw‖HTw)及びCBw=HTwRBw(mod P)を計算し、それら(HBw,CBw)の組を掲示板装置に送信する。
【００４１】
次に大小比較装置１５Ａは、掲示板装置２１より公開されたCBw=HTwRBw(mod P)を読み込み、CBwRAwmod P=(HTwRBw)RAw(mod P)を計算し、それを掲示板装置２１に送信し、大小比較装置１５Ｂは、掲示板装置２１より公開されたCAw=HSwRAw(mod P)を読み込み、CAwRBwmod P=(HSwRAw)RBw(mod P)を計算し、それを掲示板装置２１に送信する。
HSw とHTw が等しければ(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)は等しく、またＰが大きな素数であり、かつP-1は大きな素因子を約数にもつから、HSw とHTw が異なり(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が等しくなる可能性は無視できるほど小さい。従って、(HTwRBw)RAw(mod P)と(HSwRAw)RBw(mod P)が等しければ最小意中値VMINはVw+1以上であり、異なればVw以下であることが圧倒的確率で分かる。もし等しければ変数wminにw+1を代入し、異なれば変数wmaxにｗを代入して上記操作を繰り返すことにより、およそlogＭ回でwmax＝wmin(＝MIN)となる。このときの値VMINが最小意中値となる。以下、図６で示したと同様に、MINを系列si, ti中のVMINに対応する要素番号とする。
【００４２】
最小意中値VMINが分かった後、大小比較装置１５Ａは、aj, Seqs,MIN, RAMINを、大小比較装置１５Ｂはbj, Seqt,MIN, RBMINを、大小比較装置１５Ｃはcjのみをそれぞれ掲示板装置２１に送信して公開することで、全ユーザは、それら２系列に対して異なる情報が入った部分に該当するユーザが最小値VMINを意中の値としたユーザ11-jであるということを特定できる。
上記過程で、トラブルにより一方の大小比較装置、例えば１５Ｂのシステムがダウンしたとする。しかし、大小比較装置１５Ｂのもつ情報と大小比較装置１５Ｃのもつ情報は本質的に同じであるから、そのまま大小比較装置１５Ｂの操作を大小比較装置１５Ｃが引き継ぐことができる。
【００４３】
最小意中値VMINの探索後、掲示板装置２１に公開された最小意中値VMINの正当性についてはコミットしたH(Aj), H(Bj), H(Cj)について、例えばShamir, Aによる"How to Share a Secret," Comm. Assoc. Comput. March., vol.22, no.11, pp.612-613(Nov. 1979)に示されているようなシークレットシェアリング技術を応用することにより、３つの大小比較装置の任意の少なくとも２つが協力することで、ユーザのコミットした値Aj, Bj, Cjを開示するようにできる。即ち、H(Vmin‖Aj*Bj*Cj)を検証することができる。
【００４４】
大小比較装置１５Ａ，１５Ｂは連結要素Seqs,MIN, Seqt,MINを掲示板装置２１に送信して公開した後、必要に応じてSeqs,z, Seqt,z(z＝1,2,…,MIN)のうち大小比較処理に用いられたものを掲示板装置２１へ送信し、VMINが正しいものであることを明らかにしてもよい。
以上説明したように、この発明では、要は、大小比較装置１５Ａ，１５Ｂにおいて、掲示板装置２１により指定された値ｗに対応した要素si,w, ti,wをそれぞれの系列si, ti(i=1,…,N)から取出し、それらを決められた順序に並べた要素連結Seqs,wとSeqt,wを作り、これらを明すことなく比較して、異なるか等しいかにより、Vw以下（最大値を求める場合はVw以上）に意中の値としたユーザがいるかを判定し、その判定結果にもとづき、ｗを変更すればよい。大小比較装置１５Ａ，１５Ｂはべき乗剰余演算CAw=HSwRAw(mod P), CBw=HTwRBw(mod P)を使用せず、図７のステップＳ２Ａ，Ｓ２ＢにおいてHSw=h(Seqs,w)とHTw=h(Seqt,w)とのみを生成して掲示板装置２１に送信し、ステップＳ４でこれらを比較して、一致するか否か判定をしてもよい。ただし、この場合、系列si, tiの各要素が例えば１ビットと単純な構成にすると、要素連結Seqs,wが例えば(0‖1‖1‖0‖1‖0‖0)のように簡単なものになってしまい、任意のビット列のSeqs,wを作り、そのハッシュ値を計算して公開されているHSw=h(Seqs,w)と一致するようなビット列を試行錯誤で見つけることは容易になってしまうため、安全上好ましくない。一方、図７の実施例のように、HSw及びHTwをそれぞれ乱数RAw, RBwと連結してハッシュすることによりHSw, HTwを秘匿した場合、系列si, tiの要素を１ビットとしても安全である。系列si, tiの各要素を１ビットにした場合、ユーザ装置から大小比較装置１５Ａ，１５Ｂへ送信する暗号化情報EA(si‖R1i), EB(ti‖R2i)のデータ量を削減でき、通信容量を削減できる利点がある。
【００４５】
検証用ハッシュ値H1i=h(si‖R1i), H2i=h(ti‖R2i)を掲示板装置２１に送信する場合も同様に、乱数R1i，R2iは安全性を高めたのであり、必ずしも用いなくてもよい。従ってH1i＝h(si)，H2i＝h(ti)として掲示板装置へ送信してもよい。
また、上述においては大小比較装置１５Ａ，１５Ｂで作成したSeqs,w, Seqt,wをそれ自身の値を明かすことなく、比較するために一方向性関数を用いたが、例えば同一の暗号鍵で、同一の暗号演算をSeqs,w, Seqt,wに対して行い、その結果を掲示板装置２１へ送信して比較を行ってもよい。
【００４６】
上述した第１及び第３実施例において、情報系列生成部３３で生成する２系列情報si，tiとしては、例えば最小値を求める場合は、予め決めた共通の一方向性関数Ｆを使い、意中値Vviに対して、Fd(s'i)≠Fd(t'i)、(d=0, 1, …, M-vi)かつFe(s'i)＝Fe(t'i)、(e＝M-vi+1, …, M-1)となるようなシード値s'i, t'iを決めてもよい。ここで例えばF3(s'i)はF(F(F(s'i)))を表わす多重関数である。従って、情報系列si, tiはそれぞれ
si＝｛si,1=FM-1(s'i), si,2=FM-2(s'i), …, si,vi-1=FM-vi+1(s'i), si,vi=FM-vi(s'i), …, si,M-1=F(s'i), si,M＝s'i｝
ti＝｛ti,1=FM-1(t'i), ti,2=FM-2(t'i), …, ti,vi-1=FM-vi+1(t'i), ti,vi=FM-vi(t'i), …, ti,M-1=F(t'i), ti,M=t'i｝
となる。この系列生成法では、シード値s'i, t'iが与えられれば、共通の一方向性関数Ｆを使って全ての要素si,1,…,si,M及びti,1,…,ti,Mを計算により求めることができる。従って、ユーザ装置から大小比較装置１５Ａ，１５Ｂに送る暗号化系列情報EA(si‖R1i)及びEB(ti‖R2i)中に系列si, tiの全体を組み込まなくても、シート値s'i, t'iのみ、即ち、EA(s'i‖R1i), EB(t'i‖R2i)を組み込んで送れば、大小比較装置１５Ａ，１５Ｂは、共通の一方向性関数Ｆを使ってシード値s'i, t'iから系列si, tiを生成することができる。
【００４７】
このようなシード値s'i, t'iに基づいて情報系列si, tiを生成する多重関数F(x)、及びシード値の決め方について以下に説明する。
ユーザ装置11-iは、適当な大きさの素数ｐ、ｑを選んで合成数n=p*qを計算する。合成数ｎは素因数分解問題を拠り所とする、ＲＳＡ暗号などで用いられる方である。セキュリティの観点から、ｐ、ｑは512ビット又は1024ビット程度の大きさ、かつp-1, q-1はそれぞれ大きな素因数を持つことが好ましい。
続いて、k=0からｍについて、値が０からn-1の間の乱数akを生成し、多項式
F(x)＝ am*xm ＋ am-1*xm-1 ＋ … ＋ a1*x ＋ a0
を作成する。次に、値が０からn-1の間の乱数s'i, t'iを生成し、これらをシード値とする。次に、手法は自由であるが、例えば以下によりF(x)mod nに対するコリジョンを見つける。
ステップ１：u=1,2,…,cについてFu(s'i)mod nを計算し、逐次その計算結果F(s'i), F2(s'i),…, Fc(s'i)を記憶する。ここで、ｃはユーザが決定するパラメータであり、また、Fu(x)はｕ重の多重関数である。
ステップ２：flag=0, v=0, mx=c'とする。ここで、c'はユーザが決定するパラメータである。
ステップ３：Fv(t'i)mod nを計算し、その計算結果を記憶すると共に、その値がステップ１で記憶したF(s'i), F2(s'i),… ,Fc(s'i)のいずれかと一致するかを検査し、一致するものがあればflag=1とする。
ステップ４：flag=1又はv=c'であれば処理を終了し、そうでなければｖに+1してステップ３に戻る。
【００４８】
この場合、最終的にflag=1であることは、コリジョンが見つかったことに等しい。しかし一般にはF(x)mod nのとる範囲が広いため（1024ビット又は2048ビット程度）、コリジョンは簡単に見つからないことが予想される。そこで、ｎより小さい自然数n'を選び、本来の出力F(x)mod nを(F(x)mod n)mod n'と置き換えるなど、小さい範囲に還元する方法をとることによりコリジョンを見つけやすくできる。ここで、例えば(35mod15)mod3は5mod3=2である。いずれにしろ、以降、コリジョンが見つかったとして説明する。
【００４９】
Fu'-1(s'i)≠Fv'-1(t'i), Fu'(s'i)＝Fv'(t'i), 意中の値Vviが最小値V1から数えてｗ番目であるとすると、M-w+1≦u'かつM-w+1≦v'であればsi, tiが構成できる。即ち、
si＝｛si,1=Fu'+w-2 (s'i),…,si,w=Fu'-1(s'i),…,si,M=Fu'+w-M-1(s'i)｝
ti＝｛ti,1=Fv'+w-2 (t'i),…,ti,w=Fv'-1(t'i),…,ti,M=Fv'+w-M-1(t'i)｝
とすればよい。
なお，法(mod)として素因数分解問題を拠り所とするような合成数ｎを使用するのは，ある定数x'が存在したとき，F(x)-x'=0 mod nについて多項式F'(x)=F(x)/(x-x')の因数分解を容易にできなくするためである。例えば，siの要素の１つであるsi,kをみたとき、F(z)=si,kmod nを満たすｚがただ１つ，即ちsi,k+1しか存在しない場合，明らかにユーザ11-iはVkを意中値としていないことがわかる。
【００５０】
上述のコリジョン探索方法では意中値に関する情報が漏れてしまう危険があるため，n'のとり方に注意する必要がある。逆に，上記si, tiの構成条件を満たさない場合は，コリジョン探索ステップ１〜４を再度行えばよい。
また，関数F(x)としては，ハッシュ関数を用いてもよい。その場合もやはり一般にコリジョンは簡単に見つからないことが予想されるが，上記と同様の手法で出力を小さい範囲に還元することでコリジョンを見つけやすくすることができる。ただし，還元するサイズに関連して，場合によっては入力に対してパディングする必要が生じる。
【００５１】
上述したようなシード値のみを送る方法によれば、大小比較装置へ系列情報を送信するための通信容量及び通信時間を削減することができる。また、意中値Vviとして選択可能な値の数Ｍが増加しても、送るのはシード値だけであり、通信容量は変わらない。一方、第１実施例のように、乱数により系列を生成する場合は、意中値として選択可能な値の数Ｍが増加すればそれと比例して系列の要素数が増加し、通信容量が増加する。
最大値を求める場合も同様に一方向性関数を使ってシード値から系列の全要素を生成してもよい。
【００５２】
上述の実施例においては全ユーザの意中の値Vvi中の最小値VMINを決定したが、最大意中値VMAXの決定も同様に行うことができる。この場合は２系列情報siとtiとしては、V1以上Vvi以下に対応した情報はsiとtiとで異なり、Vvi+1以上VM以下に対応した情報はsiとtiとで等しいようにする。また各選択されたｗに対応するSeqs,wとSeqt,wの比較、HSw＝h'(Seqs,w)とHTw＝h'(Seqt,w)の比較、(HTwRBw)RAwmod Pと(HSwRAw)RBwmod Pの比較において異なっていればVw以上を意中の値としたユーザがいると判断し、等しければVw以上を意中の値としたユーザがいないと判断し、等しい場合はw-1をwmaxとし、異なっていれば、ｗをwminとして、同様の処理を繰り返せばよい。
【００５３】
ｗの決定は先に述べたようにすると効率的に最小値又は最大値を求めることができるが、ｗを例えばV1又はVMから順次変化させて大小比較を行ってもよい。更に１つの大小比較装置が最初のｗを決定し、ｗを掲示板装置２１を介して他の大小比較装置へ送り、掲示板装置２１から必要な情報を受け取って、図７に示した処理を行ってもよい。
【００５４】
【発明の効果】
以上述べたようにこの発明によれば、ユーザは意中の値に関する情報を１回だけ各大小比較装置及び掲示板装置に送信するだけで、効率的に最大値あるいは最小値とを特定でき、必要に応じてそれを意中の値としたユーザのみが特定できる、秘匿性の高い大小比較が実現できる。
【図面の簡単な説明】
【図１】第１の実施形態の全体のシステム構成例を示す図。
【図２】ユーザ装置のおもな機能構成例を示す図。
【図３】２系列情報の生成手順を示す流れ図。
【図４】大小比較装置１５Ａのおもな機能構成例を示す図。
【図５】大小比較装置１５Ｂのおもな機能構成例を示す図。
【図６】それぞれの組の２系列情報を模式的に示す図。
【図７】最小値を特定するための流れ図。
【図８】第２実施例におけるユーザ装置の機能構成を示すブロック図。
【図９】図８における情報系列生成部３３の機能構成を示すブロック図。
【図１０】第２実施例におけるユーザ装置の処理手順を示す流れ図。
【図１】
0004024542.tif 000002
【図２】
0004024542.tif 000003
【図３】
0004024542.tif 000004
【図４】
0004024542.tif 000005
【図５】
0004024542.tif 000006
【図６】
0004024542.tif 000007
【図７】
0004024542.tif 000008
【図８】
0004024542.tif 000009
【図９】
0004024542.tif 000010
【図１０】
0004024542.tif 000011