(57)【特許請求の範囲】
【請求項１】
複数の第一ユーザ装置ｕ１，ｕ２，…，ｕｎと、これらと区別が可能な１つの第二ユーザ装置ｖと、２つのマッチングサーバ装置Ａ，Ｂと、公開掲示板装置なる誰もが参照可能な領域とを備え、
各第一ユーザ装置ｕｉ（ｉ＝１，２，…，ｎ）はその装置ｕｉの答えがＹＥＳならば相異なり、ＮＯならば同じ値である乱数ＡＮＳi,A とＡＮＳi,B を生成し、これらＡＮＳi,A ，ＡＮＳi,B をマッチングサーバ装置Ａの各公開鍵ＰＫA ，ＰＫB でそれぞれ暗号化してＵi,A ，Ｕi,B を作成し、そのＵi,A をマッチングサーバ装置Ａへ、Ｕi,B をマッチングサーバ装置Ｂへ送り、
さらに相異なる乱数Ｒi,A ，Ｒi,B を生成し、（ＡＮＳi,A，Ｒi,A），（ＡＮＳi,B，Ｒi,B）に、それぞれ一方向性関数を施してｈi,A ＝ｈ（ＡＮＳi,A ，Ｒi,A ）とｈi,B ＝ｈ（ＡＮＳi,B ，Ｒi,B ）を生成し、これらｈi,A ，ｈi,B を答えの否認防止のためのコミットメントとして公開掲示板装置にて公開し、
マッチングサーバ装置Ａは各第一ユーザ装置ｕｉから受信した各Ｕi,Aを秘密鍵ＳＫAで復号してＡＮＳi,Aを求め、これら（ＡＮＳ1,A，…，ＡＮＳn,A）に一方向性関数を施してｈA ＝ｈ（ＡＮＳ1,A ，ＡＮＳ2,A ，…，ＡＮＳn,A ）を計算し、これをマッチングサーバ装置Ａの公開鍵を用いて確率的準同型公開鍵暗号にて暗号化してＴA を求め、これを第二ユーザ装置ｖに送り、
マッチングサーバ装置Ｂは各ユーザ装置ｕｉから受信した各Ｕi,Bを秘密鍵ＳＫBで復号してＡＮＳi,Bを求め、これら（ＡＮＳ1,B，…，ＡＮＳn,B）に一方向性関数を施してｈB ＝ｈ（ＡＮＳ1,B ，ＡＮＳ2,B ，…，ＡＮＳn,B ）を計算し、これをマッチングサーバ装置Ｂの公開鍵を用いて確率的準同型公開鍵暗号にて暗号化してＴB を作り、これを第二ユーザ装置ｖに送り、
第二ユーザ装置ｖは乱数Ｒv を生成し、Ｒv をマッチングサーバ装置Ａの公開鍵、マッチングサーバ装置Ｂの公開鍵をそれぞれ用いて確率的準同型公開鍵暗号にて各々暗号化してＳA ，ＳB を作り、その装置ｖの答えがＹＥＳならばＶA ＝ＴA ×ＳA ，ＶB ＝ＴB ×ＳB を演算し、ＮＯならばＶA ＝ＳA ，ＶB ＝ＳB とし、ＶA をマッチングサーバ装置Ａに、ＶB をマッチングサーバ装置Ｂに送り、さらにＲvに一方向性関数を施してｈv＝ｈ（Ｒv）を計算し、このｈvを答えの否認防止のためのコミットメントとして公開掲示板装置にて公開し、
マッチングサーバ装置ＡはＶA をマッチングサーバ装置ＢはＶB を各々その秘密鍵で復号して、各々ＦA ，ＦB を作り、これらを公開掲示板装置にて公開し、
これらＦAとＦB が相異なれば第一ユーザ装置ｕ１，…，ｕｎの答えに少くなくとも１つＹＥＳがあり、かつ第二ユーザ装置ｖの答えがＹＥＳであり、これらが一致すればそれ以外であると判断することを特徴とする電子マッチング方法。
【請求項２】
複数の第一ユーザ装置ｕ１，ｕ２，…，ｕｎと、これらと区別が可能な１つの第二ユーザ装置ｖと、２つのマッチングサーバ装置Ａ，Ｂと、公開掲示板装置なる誰もが参照可能な領域とを備え、
第一ユーザ装置ｕｉ（ｉ＝１，…，ｎ）はその答えがＹＥＳならば相異なる値の、ＮＯならば同じ値の乱数ＡＮＳi,A とＡＮＳi,B を生成し、
マッチングサーバ装置Ａ，Ｂの各公開鍵ＰＫA ，ＰＫB を用いて確率的準同型公開鍵暗号により乱数ＡＮＳi,A ，ＡＮＳi,B をそれぞれ暗号化してＵi,A ，Ｕi,B を生成し、
これらＵi,A ，Ｕi,B を公開掲示板装置へ送信して公開し、
相異なる乱数Ｒi,A ，Ｒi,B を生成し、
（ＡＮＳi,A ，Ｒi,A ）と（ＡＮＳi,B ，Ｒi,B ）にそれぞれ一方向性関数を施してｈi,A ＝ｈ（ＡＮＳi,A ，Ｒi,A ）とｈi,B ＝ｈ（ＡＮＳi,B ，Ｒi,B ）を生成し、
これらｈi,A ，ｈi,B を答えの否認防止のためのコミットメントとして公開掲示板装置へ送信して公開し、
第二ユーザ装置ｖは公開掲示板装置からＵ1,A ，…，Ｕn,A ，Ｕ1,B ，…，Ｕn,B を取得し、
ＴA ＝Ｕ1,A ×Ｕ2,A ×…×Ｕn,A ，ＴB ＝Ｕ1,B ×Ｕ2,B ×…×Ｕn,B を演算し、
乱数Ｒv を生成し、
公開鍵ＰＫA ，ＰＫB を用いてＲv を確率的準同型公開鍵暗号により暗号化してＳA ，ＳB を生成し、
第二ユーザ装置ｖの答えがＹＥＳであればＶA ＝ＴA ×ＳA ，ＶB ＝ＴB ×ＳB を演算し、答えがＮＯであればＶA ＝ＳA ，ＶB ＝ＳB とし、
ＶA をマッチングサーバ装置Ａへ、ＶB をマッチングサーバ装置Ｂへそれぞれ送信し、
Ｒv に一方向性関数を施してｈv ＝ｈ（ Ｒv ）を生成し、
ｈv を答えの否認防止のためのコミットメントとして公開掲示板装置へ送信して公開し、
マッチングサーバ装置Ａは受信したＶA を秘密鍵ＳＫA で復号してＦA を生成し、このＦA を公開掲示板装置へ送信し、
マッチングサーバ装置Ｂは受信したＶB を秘密鍵ＳＫB で復号してＦB を生成し、このＦB を公開掲示板装置へ送信し、
ＦA とＦB が異なれば第一ユーザ装置ｕ１，…，ｕｎの答えの少くなくとも１つはＹＥＳであり、かつ第二ユーザ装置ｖの答えがＹＥＳであり、ＦA とＦB が一致すれば、それ以外であると判断することを特徴とする電子マッチング方法。
【請求項３】
自装置の答えがＹＥＳならば相異なる値の、ＮＯならば同じ値の乱数ＡＮＳi,A とＡＮＳi,B を生成し、
これら乱数ＡＮＳi,A ，ＡＮＳi,B を、それぞれマッチングサーバ装置Ａ，Ｂへ、ＡＮＳi,A ，ＡＮＳi,B を第三者に漏らすことなく秘密送信し、
相異なる乱数Ｒi,A ，Ｒi,B を生成し、
（ＡＮＳi,A ，Ｒi,A ）と（ＡＮＳi,B ，Ｒi,B ）にそれぞれ一方向性関数を施してｈi,A ＝ｈ（ＡＮＳi,A ，Ｒi,A ）とｈi,B ＝ｈ（ＡＮＳi,B ，Ｒi,B ）を生成し、これらｈi,A ，ｈi,B を答えの否認防止のためのコミットメントとして公開掲示板装置へ送信して公開することを特徴とする電子マッチングユーザ装置の処理方法。
【請求項４】
第一ユーザ装置ｕ１，…，ｕｎから暗号文Ｕ1,A，…，Ｕn,Aをそれぞれ受信し、
これら暗号文Ｕ1,A，…，Ｕn,Aをそれぞれ復号してＡＮＳ1,A ，…，ＡＮＳn,A を求め、
これらに対し一括して一方向性関数を施してｈA ＝ｈ（ＡＮＳ1,A ，…，ＡＮＳn,A ）を生成し、
ｈA を自装置の公開鍵を用いて確率的準同型公開鍵暗号により暗号化してＴA を生成し、
ＴA を第二ユーザ装置へ送信し、
第二ユーザ装置から暗号文ＶA を受信し、
そのＶA を、自装置の秘密鍵を用いて確率的準同型公開鍵暗号により復号し、その復号結果ＦA を公開掲示板装置へ送信して公開することを特徴とする電子マッチングのマッチングサーバ装置の処理方法。
【請求項５】
マッチングサーバ装置Ａ，Ｂから確率的準同型公開鍵暗号により暗号化された暗号文ＴA ，ＴB をそれぞれ受信し、
乱数Ｒv を生成し、
マッチングサーバ装置Ａ，Ｂの公開鍵ＰＫA ，ＰＫB をそれぞれ用いて確率的準同型公開鍵暗号にて暗号化してＳA ，ＳB を生成し、
Ｒv に対し一方向性関数を施してｈv ＝ｈ（Ｒv ）を生成し、
そのｈv を公開掲示板装置へ送信して公開し、
自装置の答えがＹＥＳであればＶA ＝ＴA ×ＳA ，ＶB ＝ＴB ×ＳB を演算し、答えがＮＯであればＶA ＝ＳA ，ＶB ＝ＳB とし、
ＶA とＶB をそれぞれマッチングサーバ装置Ａ，Ｂへ送信することを特徴とする電子マッチングユーザ装置の処理方法。
【請求項６】
自装置の答えがＹＥＳならば相異なる値の、ＮＯならば同じ値の乱数ＡＮＳi,A とＡＮＳi,B を生成し、
マッチングサーバ装置Ａ，Ｂの各公開鍵ＰＫA ，ＰＫB を用いて確率的準同型公開鍵暗号によりＡＮＳi,A ，ＡＮＳi,B をそれぞれ暗号化してＵi,A ，Ｕi,B を生成し、
これらＵi,A ，Ｕi,B を公開掲示板装置へ送信して公開し、
相異なる乱数Ｒi,A ，Ｒi,B を生成し、
（ＡＮＳi,A ，Ｒi,A ）と（ＡＮＳi,B ，Ｒi,B ）にそれぞれ一方向性関数を施してｈi,A ＝ｈ（ＡＮＳi,A ，Ｒi,A ）とｈi,B ＝ｈ（ＡＮＳi,B ，Ｒi,B ）を生成し、
これらｈi,A ，ｈi,B を答えの否認防止のためのコミットメントとして公開掲示板装置へ送信して公開することを特徴とする電子マッチングユーザ装置の処理方法。
【請求項７】
公開掲示板装置から、確率的準同型公開鍵暗号により暗号化された暗号文Ｕ1,A，…，Ｕn,A，Ｕ1,B，…，Ｕn,Bを取得し、
ＴA ＝Ｕ1,A×Ｕ2,A ×…×Ｕn,A ，ＴB ＝Ｕ1,B×Ｕ2,B×…×Ｕn,Bを演算し、
乱数Ｒv を生成し、
公開鍵ＰＫA ，ＰＫB を用いてＲv を確率的準同型公開鍵暗号により暗号化してＳA ，ＳB を生成し、
自装置ｖの答えがＹＥＳであればＶA ＝ＴA ×ＳA ，ＶB ＝ＴB ×ＳB を、ＮＯであればＶA ＝ＳA ，ＶB ＝ＳB を生成し、
ＶA をマッチングサーバ装置Ａへ、ＶB をマッチングサーバ装置Ｂへそれぞれ送信し、
Ｒv に一方向性関数を施してｈv ＝ｈ（Ｒv ）を生成し、
ｈv を答えの否認防止のためのコミットメントとして公開掲示板装置へ送信して公開することを特徴とする電子マッチングユーザ装置の処理方法。
【請求項８】
請求項３、５〜７の何れかに記載の方法をコンピュータに実行させるための電子マッチングユーザ装置プログラム。
【請求項９】
請求項４記載の方法をコンピュータに実行させるための電子マッチングのマッチングサーバ装置プログラム。
【請求項１０】
請求項８又は９に記載のプログラムを記録したコンピュータ読み出し可能な記録媒体。
【請求項１１】
複数の第一ユーザ装置ｕ１，ｕ２，…，ｕｎの各装置ｕｉ（ｉ＝１，…，ｎ）は、価格リスト中のｍ個の価格のそれぞれと対応した乱数列ＡＮＳi,A＝｛ＡＮＳi,1,A，…，ＡＮＳi,m,A｝ＡＮＳi,B ＝｛ＡＮＳi,1,B ，…，ＡＮＳi,m,B ｝を、希望売値ｓ（１＜ｓ＜ｍ）以上の価格に対してＡＮＳi,j,A ≠ＡＮＳi,j,B（ｓ＜ｊ＜ｍ）とし、ｓより小さい価格に対してＡＮＳi,j,A ＝ＡＮＳi,j,B（１＜ｊ＜ｓ）として生成し、
ＡＮＳi,A をマッチングサーバ装置Ａへ、ＡＮＳi,Bをマッチングサーバ装置Ｂへそれぞれ、これら乱数列を第三者に漏らすことなく安全に送信し、
マッチングサーバ装置Ａは受信したｎ個の乱数列ＡＮＳi,Aを各同一価格のもののｍ個の乱数列ＡＮＳj,A ＝｛ＡＮＳ1,j,A，ＡＮＳ2,j,A，…，ＡＮＳn,j,A｝に並びかえ、
これらｍ個の乱数列のそれぞれに対し一方向性関数を施してｈj,A ＝ｈ（ＡＮＳj,A）を生成し、
各ｈj,A を自装置の公開鍵ＰＫAで確率的準同型暗号により暗号化してＴj,Aを生成し、
そのＴj,Aをひとつの第二ユーザ装置へ送信し、
マッチングサーバ装置Ｂは受信したｎ個の乱数列ＡＮＳi,Bを各同一価格のもののｍ個の乱数列ＡＮＳj,B＝｛ＡＮＳ1,j,B，ＡＮＳ2,j,B，…，ＡＮＳn,j,B｝に並びかえ、
これらｍ個の乱数列のそれぞれに対し、一方向性関数を施してｈj,B＝ｈ（ＡＮＳj,B）を生成し、
各ｈj,Bを自装置の公開鍵ＰＫBで確率的準同型暗号により暗号化してＴj,Bを生成し、
そのＴj,Bを第二ユーザ装置へ送信し、
第二ユーザ装置はｍ個の乱数Ｒj,vを生成し、
マッチングサーバ装置Ａ、Ｂの各公開鍵ＰＫA、ＰＫBでＲj,vをそれぞれ暗号化してＳj,A，Ｓj,Bを生成し、
希望買値ｂ（１＜ｂ＜ｍ）以下の価格ｊ（ｊ＜ｂ）に対し、Ｖj,A＝Ｔj,A×Ｓj,A，Ｖj,B＝Ｔj,B×Ｓj,Bを生成し、ｂより大きい価格ｊ（ｊ＞ｂ）に対してＶj,A＝Ｓj,A、Ｖj,B＝Ｓj,Bを生成し、
Ｖj,Aをマッチングサーバ装置Ａへ、Ｖj,Bをマッチングサーバ装置Ｂへそれぞれ送信し、
マッチングサーバ装置Ａは受信したｍ個のＶj,Aを自装置の秘密鍵で復号してｍ個のＦj,Aを得、
マッチングサーバ装置Ｂは受信したｍ個のＶj,Bを自装置の秘密鍵で復号してｍ個のＦj,Bを得、
マッチングサーバ装置Ａ及びＢはｊ＝１から順にＦj,A、Ｆj,Bをそれぞれ順次公開し、Ｆj,A≠Ｆj,Bとなると、マッチングサーバ装置Ａ及びＢはそのｊに対するＡＮＳi,j,A、ＡＮＳi,j,Bをそれぞれｉについて予め決めた順に公開し、ＡＮＳi,j,A≠ＡＮＳi,j,Bとなったらそのｉの第一ユーザ装置を勝者とする
ことを特徴とする電子マッチング方法。
【請求項１２】
複数の第一ユーザ装置ｕ１，ｕ２，…，ｕｎの各装置ｕｉ（ｉ＝１，…，ｎ）は、価格リスト中のｍ個の価格のそれぞれと対応した乱数列ＡＮＳi,A＝｛ＡＮＳi,1,A，…，ＡＮＳi,m,A｝ＡＮＳi,B ＝｛ＡＮＳi,1,B ，…，ＡＮＳi,m,B ｝を、希望買値ｂ（１＜ｂ＜ｍ）以下の価格に対してＡＮＳi,j,A ≠ＡＮＳi,j,B（ｂ＞ｊ＞１）とし、ｂより大きい価格に対してＡＮＳi,j,A ＝ＡＮＳi,j,B（ｂ＜ｊ＜ｍ）として生成し、
ＡＮＳi,A をマッチングサーバ装置Ａへ、ＡＮＳi,Bをマッチングサーバ装置Ｂへそれぞれ、これら乱数列を第三者に漏らすことなく安全に送信し、
マッチングサーバ装置Ａは受信したｎ個の乱数列ＡＮＳi,Aを各同一価格のもののｍ個の乱数列ＡＮＳj,A ＝｛ＡＮＳ1,j,A，ＡＮＳ2,j,A，…，ＡＮＳn,j,A｝に並びかえ、
これらｍ個の乱数列のそれぞれに対し一方向性関数を施してｈj,A ＝ｈ（ＡＮＳj,A）を生成し、
各ｈj,A を自装置の公開鍵ＰＫAで確率的準同型暗号により暗号化してＴj,Aを生成し、
そのＴj,Aをひとつの第二ユーザ装置へ送信し、
マッチングサーバ装置Ｂは受信したｎ個の乱数列ＡＮＳi,Bを各同一価格のもののｍ個の乱数列ＡＮＳj,B＝｛ＡＮＳ1,j,B，ＡＮＳ2,j,B，…，ＡＮＳn,j,B｝に並びかえ、
これらｍ個の乱数列のそれぞれに対し、一方向性関数を施してｈj,B＝ｈ（ＡＮＳj,B）を生成し、
各ｈj,Bを自装置の公開鍵ＰＫBで確率的準同型暗号により暗号化してＴj,Bを生成し、
そのＴj,Bを第二ユーザ装置へ送信し、
第二ユーザ装置はｍ個の乱数Ｒj,vを生成し、
マッチングサーバ装置Ａ、Ｂの各公開鍵ＰＫA、ＰＫBでＲj,vをそれぞれ暗号化してＳj,A，Ｓj,Bを生成し、
希望買値ｓ（１＜ｓ＜ｍ）以上の価格ｊ（ｊ＞ｓ）に対し、Ｖj,A＝Ｔj,A×Ｓj,A，Ｖj,B＝Ｔj,B×Ｓj,Bを生成し、ｓより小さい価格ｊ（ｊ＜ｓ）に対してＶj,A＝Ｓj,A、Ｖj,B＝Ｓj,Bを生成し、
Ｖj,Aをマッチングサーバ装置Ａへ、Ｖj,Bをマッチングサーバ装置Ｂへそれぞれ送信し、
マッチングサーバ装置Ａは受信したｍ個のＶj,Aを自装置の秘密鍵で復号してｍ個のＦj,Aを得、
マッチングサーバ装置Ｂは受信したｍ個のＶj,Bを自装置の秘密鍵で復号してｍ個のＦj,Bを得、
マッチングサーバ装置Ａ及びＢはｊ＝ｍから順にＦj,A、Ｆj,Bをそれぞれ順次公開し、Ｆj,A≠Ｆj,Bとなると、マッチングサーバ装置Ａ及びＢはそのｊに対するＡＮＳi,j,A、ＡＮＳi,j,Bをそれぞれｉについて予め決めた順に公開し、ＡＮＳi,j,A≠ＡＮＳi,j,Bとなったらそのｉの第一ユーザ装置を勝者とする
ことを特徴とする電子マッチング方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は複数のユーザ（ｕ１，ｕ２，…，ｕｎ）とこれと区別が可能な１人のユーザ（ｖ）と彼らへの質問（例えばｕ１，ｕ２，…，ｕｎに対して「１万円で売るか？」、ｖに対して「１万円で買うか？」など）が存在し、ｕ１，ｕ２，…，ｕｎ中の１人でも、かつｖの質問への答えがＹＥＳであるときにのみその旨判定できる方法であり、前述の例のように両者が売買人の関係にあるときは「取引成立」とすることが可能な電子マッチングの方法およびそのプログラムを記録した記録媒体に関する。
【０００２】
【従来の技術】
従来の電子マッチングの方法がＭｏｎｉ  Ｎａｏｒ，Ｂｅｎｎｙ  Ｐｉｎｋａｓ：「Ｏｂｌｉｖｉｏｕｓ  Ｔｒａｎｓｆｅｒ  ａｎｄ  Ｐｏｌｙｎｏｍｉａｌ  Ｅｖａｌｕａｔｉｏｎ」，ＳＴＯＣ９９，ＡＣＭに挙げられている。この方法は１人対１人の電子マッチングシステムであり、この方法はＯｂｌｉｖｉｏｕｓ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｐｏｌｙｎｏｍｉａｌという技術を用いている。この技術はＡｌｉｃｅ（アリス）とＢｏｂ（ボブ）がおり、Ａｌｉｃｅしか知らない値ｘとＢｏｂしか知らない多項式Ｐがあり、ＡｌｉｃｅはＢｏｂにｘを知られることなく、ＢｏｂはＡｌｉｃｅにＰを知られることなく、Ａｌｉｃｅが値Ｐ（ｘ）を得るものである。ＭｏｎｉとＮａｏｒはこの手法の応用として以下のような１対１のマッチングを提案している。ユーザｕとユーザｖがおり、ｕしか知らない関数Ｐｕ  と値ｘｕ  ，ｖしか知らない関数Ｐｖ  と値ｘｖ  がある。先のＯｂｌｉｖｉｏｕｓ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｐｏｌｙｎｏｍｉａｌ  を用いて、各々相手にｘｕ  ，ｘｖ  を知られることなく、ｕはＰｖ  （ｘｕ  ）を、ｖはＰｕ  （ｘｖ  ）を得、ｕはＰｕ  （ｘｕ  ）＋Ｐｖ  （ｘｕ  ）を公開し、ｖはＰｖ  （ｘｖ  ）＋Ｐｕ  （ｘｕ  ）を公開する。両者の秘密の値ｘｕ  ，ｘｖ  が等しいならば公開されたこれらも一致する。
【０００３】
【発明が解決しようとする課題】
従来技術の問題点は、１対１でのマッチングしかできないということである。その理由は、各種電子商取引の分野では１対多ないしは多対多であることが多く、これに対応できないためである。
この発明の目的は、１対多者間においてユーザのプライバシー（答え）を守りつつ比較できる電子マッチング方法を提供することにある。
【０００４】
【課題を解決するための手段】
この発明によれば複数の第一ユーザ装置ｕ１，ｕ２，…，ｕｎと、これらと区別が可能な１つの第二ユーザ装置ｖと、２つのマッチングサーバ装置Ａ，Ｂとを備え、第一ユーザ装置及び第二ユーザ装置への質問に対するＹＥＳまたはＮＯの答えをこれら装置はそれぞれ秘密に持ち、２つのマッチングサーバ装置Ａ，Ｂを仲介させることにより第一ユーザ装置ｕ１，ｕ２，…，ｕｎの回答が少くとも１つＹＥＳがあり、かつ第二ユーザ装置の回答がＹＥＳの時のみ、そのことを判定可能とする。
【０００５】
例えば第一ユーザ装置ｕ１，ｕ２，…，ｕｎではその回答がＹＥＳであれば、互いに異なる乱数ＡＮＳｉ，Ａ  ，ＡＮＳｉ，Ｂ  （ｉ＝１，２，…，ｎ）を、回答がＮＯであれば互いに等しい乱数ＡＮＳｉ，Ａ  ，ＡＮＳｉ，Ｂ  を生成し、第二ユーザ装置ｖはその答えがＹＥＳであればＡＮＳｉ，Ａ  の全てと関連した成分を含む確率的準同型暗号文ＶＡ  とＡＮＳｉ，Ｂ  の全てと関連した成分を含む確率的準同型暗号文ＶＢ  を、答えがＮＯであれば同一乱数に対する各確率的準同型暗号文ＶＡ  ，ＶＢ  を生成し、マッチングサーバ装置Ａ，ＢはＶＡ  ，ＶＢ  を復号する。
【０００６】
従来技術とは、１対多者間でのマッチングを可能とした点が異なる。
【０００７】
【発明の実施の形態】
次に、この発明の実施の形態について図面を参照して詳細に説明する。
第１の実施の形態
この発明が適用されるシステムの構成例は図１に示すように、複数の第一ユーザ装置１００と、ひとつの第二ユーザ装置２００と、２つのマッチングサーバ装置３００と、公開掲示板装置４００がネットワーク５００で接続されている。
第一ユーザ装置１００の機能構成例を図２に、第二ユーザ装置２００の機能構成例を図３に、マッチングサーバ装置３００の機能構成例を図４に、公開掲示板装置４００の機能構成例を図５にそれぞれ示す。
【０００８】
次に、図６〜図１０のフローチャートを参照してこの実施の形態の全体の動作について詳細に説明する。
まず図６に示すように、第一ユーザｕｉ（ｉ＝１，２，…，ｎ）の第一ユーザ装置１００（図２参照）は乱数生成部１０１にて異なる乱数ＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂ，Ｒｉ，Ａ，Ｒｉ，Ｂを生成し（Ｓ１）、回答記憶部１０２からの回答としてＹＥＳまたはＮＯを読み出す（Ｓ２）。回答生成部１０３はこの回答がＮＯならば（Ｓ３）、ＡＮＳｉ，ＢをＡＮＳｉ，Ａで上書きしてＡＮＳｉ，Ａと等しくする（Ｓ４）。公開鍵記憶部１０４からＰＫＡ，ＰＫＢを読み出し（Ｓ５）、確率暗号演算部１０５はＰＫＡ，ＰＫＢでＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂをそれぞれ暗号化してＵｉ，Ａ，Ｕｉ，Ｂを作成する（Ｓ６）。また一方向性関数演算部１０６にて（ＡＮＳｉ，Ａ，Ｒｉ，Ａ），（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ）に対しそれぞれ一方向性関数を施してｈｉ，Ａ，ｈｉ，Ｂを作成する（Ｓ７）。送信部１０７はｈｉ，Ａ，ｈｉ，Ｂを公開掲示板装置４００へ、Ｕｉ，Ａをマッチングサーバ装置３００へ、Ｕｉ，Ｂをもうひとつのマッチングサーバ装置３００へそれぞれ送信する（Ｓ８）。
【０００９】
図１０に示すように公開掲示板装置４００（図５参照）は受信部４０１にてｈｉ，Ａ，ｈｉ，Ｂを受信し（Ｓ１）、他の装置からも参照可能な公開記憶部４０２へ蓄積する（Ｓ２）。
次に図８に示すように、マッチングサーバ装置３００は動作する。なお図８及び以下の説明ではマッチングサーバ装置３００はマッチングサーバＡであるものとして記述するが、もうひとつのマッチングサーバ装置３００はマッチングサーバＢとなり、その動作は図８および以下の説明内容中のＡを全てＢに置き換えたものとして動作する。マッチングサーバ装置３００（図４参照）はまず受信部３０１にて複数の第一ユーザ装置１００から送信されたＵ１，Ａ，Ｕ２，Ａ…，Ｕｎ，Ａを受信する（Ｓ１）。次に公開鍵秘密鍵記憶部３０２からマッチングサーバの秘密鍵ＳＫＡを読み出し（Ｓ２）、確率的準同型公開鍵暗号復号部３０３にてＵ１，Ａ，Ｕ２，  Ａ…，Ｕｎ，Ａを復号してＡＮＳ１，Ａ，ＡＮＳ２，Ｂ，…ＡＮＳｎ，Ａを得る（Ｓ３）。一方向性関数演算部３０４にて（ＡＮＳ１，Ａ，ＡＮＳ２，Ａ，…ＡＮＳｎ，Ａ）に一方向性関数を施してｈＡを得る（Ｓ４）。公開鍵秘密鍵記憶部３０２から公開鍵ＰＫＡを読み出し（Ｓ５）、確率的準同型公開鍵暗号暗号部３０５にてｈＡをＰＫＡで暗号化してＴＡを得る（Ｓ６）。送信部３０６にてＴＡを第二ユーザ装置２００へ送信する（Ｓ７）。
【００１０】
次に図７に示すように、第二ユーザ装置２００（図３参照）は、受信部２０１にてマッチングサーバ装置３００からＴＡを、もうひとつのマッチングサーバ装置３００からＴＢをそれぞれ受信する（Ｓ１）。乱数生成部２０３にて乱数ＲＶを生成し（Ｓ２）、公開鍵記憶部２０２からＰＫＡ，ＰＫＢを読み出す（Ｓ３）。確率的準同型公開鍵暗号暗号部２０４にてＲＶをＰＫＡ，ＰＫＢでそれぞれ暗号化してＳＡ，ＳＢを得る（Ｓ４）。回答記憶部２０５より回答としてＹＥＳまたはＮＯを読み出す（Ｓ５）。回答生成部２０６は、読み出した回答がＹＥＳならば（Ｓ６）、ＶＡ＝ＳＡ×ＴＡ，ＶＢ＝ＳＢ×ＴＢとしてそれぞれ生成し（Ｓ７）、回答がＮＯならばＶＡ＝ＳＡ，ＶＢ＝ＳＢとし（Ｓ８）、一方向性関数演算部２０７はＲＶに一方向性関数を施してｈＶを作成する（Ｓ９）。送信部２０８はｈＶを公開掲示板装置４００へ、ＶＡをマッチングサーバ装置３００へ、ＶＢをもうひとつのマッチングサーバ装置３００にそれぞれ送信する（Ｓ９）。
【００１１】
図１０に示すように、公開掲示板装置４００は受信部４０１にてｈＶを受信し（Ｓ１）、公開記憶部４０２へ蓄積する（Ｓ２）。
次に図９に示すように、マッチングサーバ装置３００は動作する。なお図９及び以下の説明ではマッチングサーバ装置３００はマッチングサーバＡであるものとして記述するが、もうひとつのマッチングサーバ装置３００はマッチングサーバＢとなり、その動作は図９および以下の説明内容中のＡを全てＢに置き換えたものとして動作する。まず受信部３０１にてＶＡを受信する（Ｓ１）。公開鍵秘密鍵記憶部３０２からマッチングサーバＡの秘密鍵ＳＫＡを読み出し（Ｓ２）、確率的準同型公開鍵暗号復号部３０３にてＶＡをＳＫＡで復号してＦＡを得る（Ｓ３）。送信部３０６にてＦＡを公開掲示板装置４００へ送信する（Ｓ４）。
【００１２】
次に図１０に示すように、公開掲示板装置４００は動作し、まず２つのマッチングサーバ装置３００よりＦＡ，ＦＢをそれぞれ受信部４０１にて受信し、次に他の装置からも参照可能な公開記憶部４０２へＦＡ，ＦＢを蓄積する。
確率的準同型暗号はＥ（ａ・ｂ）＝Ｅ（ａ）・Ｅ（ｂ）となる性質がある。従って、第二ユーザ装置ｖの回答がＹＥＳの場合は、ＶＡ＝ＳＡ×ＴＡ＝ＥＰＫＡ（Ｒｖ・ｈＡ），ＶＢ＝ＳＢ×ＴＢ＝ＥＰＫＢ（Ｒｖ・ｈＢ）となる。第一ユーザ装置ｕ１，…，ｕｎ中の１つでもその回答にＹＥＳがあれば、ｈＡ≠ｈＢとなる。つまり第一ユーザ装置ｕ１，…，ｕｎ中の１つでもその回答がＹＥＳであり、かつ第二ユーザ装置ｖの回答もＹＥＳであれば、必ずＦＡ（＝ＲＶ・ｈＡ）≠ＦＢ（＝ＲＶ・ｈＢ）となる。これ以外の場合には、第一ユーザ装置ｕ１，…，ｕｎの回答中にＹＥＳがあっても、第二ユーザ装置ｖの回答がＮＯであれば、ＦＡ（＝ＲＶ）＝ＦＢ（＝ＲＶ）となり、また第二ユーザ装置ｖの回答がＹＥＳであっても第一ユーザ装置ｕ１，…，ｕｎの全ての回答がＮＯであればｈＡ＝ｈＢであるため、ＦＡ（＝ＲＶ・ｈＡ）＝ＦＢ（＝ＲＶ・ｈＢ）となり、何れの場合もＦＡ＝ＦＢとなる。よってＦＡ≠ＦＢの時のみマッチングが成立したことになる。
【００１３】
しかも確率暗号により暗号化されているため第三者はＴＡ＝ＴＢなのかＴＡ≠ＴＢなのか区別することができず、またＶＡ，ＶＢもＴＡ，ＴＢを含むかどうか分からない。つまり第一ユーザ装置の回答が全てＮＯだったのか、第二ユーザ装置の回答がＮＯだったのか判別が不可能である。
第一ユーザ装置１００がｈｉ，Ａ，ｈｉ，Ｂを公開掲示板装置４００へ送信するのは、その答えの否認防止のためのコミットメントとして公開し、第二ユーザ装置２００がｈＶを公開掲示板装置４００へ送信するのも、その答えの否認防止のためのコミットメントとして公開するためである。第一ユーザ装置１００からサーバ装置３００へのＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂの送信は、要はこれらを第三者に漏らすことなく秘密に送ればよい。
第２の実施の形態
第１の実施の形態は公開掲示板装置４００を除くと、情報の流れが第一ユーザ装置１００→マッチングサーバ装置３００→第二ユーザ装置２００→マッチングサーバ装置３００となっていた。第２の実施の形態では、情報の流れを第一ユーザ装置１００→第二ユーザ装置２００→マッチングサーバ装置３００としてマッチングサーバ装置３００の負担を軽減したものである。
【００１４】
適用されるシステム構成例は図１に示したものと同様である。第一ユーザ装置１００の機能構成例は図１１に示すように、図２に示した構成中の確率暗号演算部１０５が確率的準同型公開鍵暗号暗号部１１５となっている。第二ユーザ装置２００の機能構成例は図１２に示すように、図３に示した構成に、ＴＡ，ＴＢ生成部２０９が加わっている。マッチングサーバ装置３００の機能構成例は図１３に示すものとなり、公開掲示板装置４００の機能構成例は図５に示したものと同様である。第一ユーザ装置１００、第二ユーザ装置２００、マッチングサーバ装置３００の各処理手順の例を図１４〜図１６にそれぞれ示す。公開掲示板装置４００の処理手順は図１０と同様である。
【００１５】
以下第２の実施の形態の全体の動作について詳細に説明する。
まず第一ユーザｉ（ｉ＝１，２，…，ｎ）の第一ユーザ装置１００（図１１参照）は図１４に示すように、乱数生成部１０１にて異なる乱数ＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂ，Ｒｉ，Ａ，Ｒｉ，Ｂを生成し（Ｓ１）、回答記憶部１０２から回答としてＹＥＳまたはＮＯを読み出す（Ｓ２）。回答生成部１０３はこの回答がＮＯならば（Ｓ３）、ＡＮＳｉ，ＢをＡＮＳｉ，Ａで上書きしてＡＮＳｉ，ＢとＡＮＳｉ，Ａを等しくする（Ｓ４）。公開鍵記憶部１０４からマッチングサーバＡ，Ｂの各公開鍵ＰＫＡ，ＰＫＢを読み出し（Ｓ５）、確率的準同型公開鍵暗号暗号部１１５によりＰＫＡ，ＰＫＢをそれぞれ用いてＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂを暗号化してＵｉ，Ａ，Ｕｉ，Ｂを生成する（Ｓ６）。
【００１６】
一方向性関数演算部１０６により（ＡＮＳｉ，Ａ，Ｒｉ，Ａ）と（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ）にそれぞれ一方向性関数を施してｈｉ，Ａ＝ｈ（ＡＮＳｉ，Ａ，Ｒｉ，Ａ）とｈｉ，Ｂ＝ｈ（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ）を生成する（Ｓ７）。送信部１０７によりＵｉ，Ａ，Ｕｉ，Ｂ、ｈｉ，Ａ，ｈｉ，Ｂを公開掲示板装置４００へ送信する（Ｓ８）。なおｈｉ，Ａ，ｈｉ，Ｂは答えの否認防止のためのコミットメントとして用いられる。
第二ユーザ装置２００（図１２参照）は図１５に示すように、受信部２０１にて公開掲示板装置４００からＵ１，Ａ，Ｕ２，Ａ，…，Ｕｎ，Ａ，Ｕ１，Ｂ，Ｕ２，Ｂ，…，Ｕｎ，Ｂを受信する（Ｓ１）。ＴＡ，ＴＢ生成部２０９にてＴＡ＝Ｕ１，Ａ×Ｕ２，Ａ×…×Ｕｎ，Ａ，ＴＢ＝Ｕ１，Ｂ×Ｕ２，Ｂ×…×Ｕｎ，Ｂを演算生成する（Ｓ２）。
【００１７】
乱数生成部２０３にて乱数ＲＶを生成し（Ｓ３）、公開鍵記憶部２０２からマッチングサーバＡ，Ｂの公開鍵ＰＫＡ，ＰＫＢを読み出す（Ｓ４）。
確率的準同型公開鍵暗号暗号部２０４により公開鍵ＰＫＡ，ＰＫＢを用いてＲＶを暗号化してＳＡ，ＳＢを生成する（Ｓ５）。回答記憶部２０５より回答としてＹＥＳまたはＮＯを読み出す（Ｓ６）。回答生成部２０６は読み出した回答がＹＥＳであれば（Ｓ７）、ＶＡ＝ＳＡ×ＴＡ、ＶＢ＝ＳＢ×ＴＢを生成し（Ｓ８）、回答がＮＯであればＶＡ＝ＳＡ、ＶＢ＝ＳＢとし（Ｓ９）、一方向性関数部２０７はＲＶに一方向性関数を施してｈＶ＝ｈ（ＲＶ）を生成する（Ｓ１０）。送信部２０８はｈＶを答えの否認防止のためのコミットメントとして公開掲示板装置４００へ、ＶＡをマッチングサーバＡの装置３００へ、ＶＢをマッチングサーバＢの装置３００へそれぞれ送信する（Ｓ１１）。
【００１８】
図１０に示すように公開掲示板装置４００は受信部４０１にてｈＶを受信し（Ｓ１）、公開記憶部４０２へ蓄積する（Ｓ２）。
図１６に示すようにマッチングサーバ装置３００（図１３参照）は次のように動作する。なお図１６及び以下の説明ではマッチングサーバ装置３００はマッチングサーバＡの装置であるものとして記述するが、もうひとつのマッチングサーバ装置３００はマッチングサーバＢのものとなり、その動作は図１０および以下の説明内容中のＡを全てＢに置き換えたものとして動作する。まず受信部３０１にてＶＡを受信する（Ｓ１）。秘密鍵記憶部３０２から自装置の秘密鍵ＳＫＡを読み出し（Ｓ２）、確率的準同型公開鍵暗号復号部３０３にてＶＡを復号しＦＡを得る（Ｓ３）。送信部３０４にてＦＡを公開掲示板装置４００へ送信する（Ｓ４）。
【００１９】
図１０に示すように公開掲示板装置４００は、２つのマッチングサーバ装置３００よりＦＡ，ＦＢをそれぞれ受信部４０１にて受信する。次に他の装置からも参照可能な公開記憶部４０２へＦＡ，ＦＢを蓄積する。
この場合も、第１の実施の形態と同様に、ＦＡとＦＢが異なれば、ユーザｕ１，…ｕｎの各装置１００からの回答の少くとも１つがＹＥＳであり、かつ第二ユーザ装置２００の回答がＹＥＳであると判断し、ＦＡとＦＢが一致すれば、他の場合であると判断する。ＶＡ，ＶＢは第二ユーザ装置２００の回答がＹＥＳの場合、準同型暗号の性質から次式となる。
【００２０】
0003619486.tif 000002
これらの両式から、第二ユーザ装置２００の回答がＹＥＳであれば、第一ユーザｕ１，ｕ２…ｕｎの各装置１００の回答の少くとも１つがＹＥＳであればＦＡ≠ＦＢとなり、第一ユーザ装置１００からの回答の全てがＮＯであればＦＡ＝ＦＢとなる。
【００２１】
一方、第一ユーザ装置１００からの回答にＹＥＳが含まれていても、第二ユーザ装置２００の回答がＮＯであれば、ＶＡ＝ＳＡ、ＶＢ＝ＳＢとなりＦＡ＝ＦＢとなる。従って、上記判断が正しいことになる。
第１の実施の形態、第２の実施の形態の何れにおいても、ＦＡ，ＦＢを公開することなく、マッチングサーバＡ，Ｂの各装置３００が復号したＦＡ，ＦＢを、従来の技術の項で説明した１対１のマッチングを利用し、これらを公開することなく比較してもよい。例えばマッチングサーバ装置３００が復号したＦＡを、Ｏｂｌｉｖｉｏｕｓ  Ｅｖａｌｕａｔｉｏｎ  ｏｆ  Ｐｏｌｙｎｏｍｉａｌ技術を用いて、マッチングサーバＡの装置３００はマッチングサーバＢしか知らない多項式ＰＢについてＰＢ（ＦＡ）をマッチングサーバＢに知られることなく得、同様に、マッチングサーバＢの装置３００がＰＡ（ＦＢ）を得、両マッチングサーバ装置３００において、それぞれＰＡ（ＦＡ）＋ＰＢ（ＦＡ），ＰＢ（ＦＢ）＋ＰＡ（ＦＢ）をそれぞれ公開して両者を比較し、これらが互いに相違すればＦＡ≠ＦＢであると判定できる。
第３の実施の形態
次に、この発明の電子マッチング方法を電子商取引に適用した例を述べる。ｎ人の売り手（ｕ１，…，ｕｎ）と１人の買い手（ｖ）が存在し、１円〜５円のいずれかを売値・買値として回答してくるものとする。また準同型確率暗号としてＥｌＧａｍａｌ暗号を用いることとし、素数ｐとＺ＊ｐの原始元ｇをシステムに共通なシステムパラメータとする。
【００２２】
マッチングサーバ装置Ａの秘密鍵をｘＡ（∈Ｚｐ−１）、公開鍵をｙＡ（＝ｇｘＡ  ｍｏｄ  ｐ）とし、同様にマッチングサーバ装置Ｂの秘密鍵をｘＢ（∈Ｚｐ−１）、公開鍵をｙＢ（＝ｇｘＢ  ｍｏｄ  ｐ）とする。成立した際の買い手の優先順位はｕ１，ｕ２，…ｕｎの順とする。また複数価格で成立する可能性がある場合は買値が優先されるものとする。
（１）希望売値登録
各売り手装置ｕｉは以下のようにＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂを準備する。
【００２３】
0003619486.tif 000003
但し、ＡＮＳｉ，ｘ，ｘ∈Ｚｐである。
例えば売り手装置ｕｉの希望売値が「３円以上」であるとすると、ＡＮＳｉ，ＡとＡＮＳｉ，Ｂは図１６のようにセットされる。つまりＡＮＳｉ，ｊ，Ａ，ＡＮＳｉ，ｊ，Ｂ（ｊ＝１，２，…，５）を各価格に対応して用意し、希望売値以上のＡＮＳｉ，ｊ，ＡとＡＮＳｉ，ｊ，Ｂとを互いに異ならせ、つまり回答ＹＥＳとし、希望売値より小さいＡＮＳｉ，ｊ，ＡとＡＮＳｉ，ｊ，Ｂとを互いに等しく、つまり回答ＮＯとする。
【００２４】
ｕｉは次のような乱数群Ｒｉ，Ａ，Ｒｉ，Ｂを生成する。
0003619486.tif 000004
をコミットメントとして公開する。さらにＡＮＳｉ，ＡとＲｉ，Ａをマッチングサーバ装置Ａに、ＡＮＳｉ，ＢＡとＲｉ，Ｂをマッチングサーバ装置Ｂに他人に知られないように送信する。
（２）売値バンドル
マッチングサーバ装置ＡはＡＮＳ１，Ａ，ＡＮＳ２，Ａ，…，ＡＮＳｎ，Ａを受け取る。
【００２５】
0003619486.tif 000005
ｈ１，Ａ，ｈ２，Ａ，…，ｈ５，Ａを自装置の公開鍵と乱数ｒａで各々暗号化してＴｊ，Ａ（ｊ＝１，…，５）を得る。
【００２６】
Ｔｊ，Ａ＝（ｙｒａＡｈｊ，Ａ  ｍｏｄ  ｐ，ｇｒａ  ｍｏｄ  ｐ）
ｊ＝１，…，５に対して
Ｔｊ，Ａをユーザ装置ｖに送る。
同様にマッチングサーバ装置ＢはＡＮＳ１，Ｂ，ＡＮＳ２，Ｂ，…，ＡＮＳｎ，Ｂを受け取り、ｈ１，Ｂ，ｈ２，Ｂ，…，ｈ５，Ｂを計算し、自装置の公開鍵と乱数ｒｂにて各々暗号化して、Ｔｊ，Ｂ（ｊ＝１，…，５）を得る。
Ｔｊ，Ｂ＝（ｙｒｂＢ  ｈｊ，Ｂ  ｍｏｄ  ｐ，ｇｒｂ  ｍｏｄ  ｐ）
ｊ＝１，…，５に対して、
Ｔｊ，Ｂをユーザ装置ｖに送る。
（３）希望買値登録
ユーザ装置ｖはＴ１，Ａ，Ｔ２，Ａ，…，Ｔ５，Ａ，Ｔ１，Ｂ，Ｔ２，Ｂ，…，Ｔ５，Ｂを受け取り、乱数Ｒ１，ｖ，Ｒ２，ｖ，…，Ｒ５，ｖ（∈Ｚｐ）を生成する。Ｒｊ，ｖを装置Ａの公開鍵と乱数ｒＡ，ｖにて各々暗号化してＳｊ，Ａを得る。同様に、Ｒｊ，ｖを装置Ｂの公開鍵と乱数ｒＢ，ｖにて各々暗号化してＳｊ，Ｂを得る。
【００２７】
0003619486.tif 000006
装置ｖは乱数Ｒｊ，Ｖ（ｊ＝１，…，５）を生成し、ｈ（Ｒｊ，ｖ，Ｒｊ，ｖ）をコミットメントとして公開する。各ｊと希望買値の大小関係に応じて以下のようにＶｊ，Ａ，Ｖｊ，Ｂを計算する。
【００２８】
0003619486.tif 000007
ｊ＝１，…，５に対してＶｊ，Ａを装置Ａに、Ｖｊ，Ｂを装置Ｂに送る。
（４）売買値比較
装置Ａは（Ｖｊ，Ａ）を復号し、Ｗ１，Ａ，Ｗ２，Ａ，…，Ｗ５，Ａを得る。同様に装置Ｂは（Ｖｊ，Ｂ）を復号し、Ｗ１，Ｂ，Ｗ２，Ｂ，…，Ｗ５，Ｂを得る。ｊ＝１とする。Ａ，ＢはＷｊ，Ａ，Ｗｊ，Ｂを公開する。もしＷｊ，Ａ≠Ｗｊ，Ｂならば（５）へ、それ以外ではｊ←ｊ＋１とし、同じプロセスを繰り返す。もし全てのｊに対してＷｊ，Ａ＝Ｗｊ，Ｂとなれば、この取引は「不成立」を結果として返して終了する。
（５）ｕｉ特定
（４）の処理からのｊの値を引き継ぎ以下を実行する。ｉ＝１とする。装置Ａ，ＢはＡＮＳｉ，ｊ，ＡとＡＮＳｉ，ｊ，Ｂを各々公開する。もしＡＮＳｉ，ｊ，Ａ≠ＡＮＳｉ，ｊ，Ｂならば装置ｕｉが勝者であり、この取引は「成立」を結果として返して終了する。それ以外ではｉ←ｉ＋１とし、同じプロセスを繰り返す。
【００２９】
この方法によれば以下のように安全性が保証される。
（Ａ）ユーザの登録情報の秘匿性
もしマッチングが「不成立」（ＦＡ＝ＦＢ）ならば、第三者が得たいのは、どの状況で「不成立」となったかである。第三者が得られる情報は、ｈ（ＡＮＳｉ，Ａ，Ｒｉ，Ａ），ｈ（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ），ＴＡ，ＴＢ，ｈ（ＲＶ，ＲＶ′），ＶＡ，ＶＢ，ＷＡ，ＷＢである。
ｈ（ＡＮＳｉ，Ａ，Ｒｉ，Ａ），ｈ（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ）からＡＮＳｉ，Ａ，ＡＮＳｉ，Ｂを求める困難性は関数ｈの一方向性に基づいている。
【００３０】
ＴＡ，ＴＢは確率暗号にて暗号化された結果であるので、第三者はＴＡ＝ＴＢなのかＴＡ≠ＴＢなのか区別がつかない。
またＶＡ，ＶＢも確率暗号による暗号文であるため、これらがＴＡ，ＴＢを含むかどうかは分からない。
（Ｂ）公平性
各ユーザは他ユーザの登録した回答を得られるか。
（Ａ）と同様に、公開されている情報から他ユーザの回答は得られない。ただし、両マッチングサーバＡ，Ｂは互いに結託しないものとし、またマッチングサーバＡ，Ｂが同一のユーザと結託することがないものとする。
【００３１】
以上よりユーザは自分の回答登録前に他ユーザの回答を得ることはできない。
（Ｃ）否認不可性
第一ユーザがｕはｈ（ＡＮＳｉ，Ａ，Ｒｉ，Ａ），ｈ（ＡＮＳｉ，Ｂ，Ｒｉ，Ｂ）を、第二ユーザｖはｈ（ＲＶ，ＲＶ′）をコミットメントとして公開しており、これを否認するためには関数ｈのコリジョンを見つけることが必要となる。
上述においては最も安い価格で買うことができるが、第一ユーザ装置ｕ１，…ｕｎが希望買値登録し、第二ユーザ装置ｖが希望売値登録して、最も高い価格で売るようにすることもできる。この場合は第一ユーザ装置ｕｉはその希望買値ｂ（１＜ｂ＜ｍ：ｍは価格リストの最高値、前記例では５円）に対し、ｊ＜ｂではＡＮＳｉ，ｊ，Ａ≠ＡＮＳｉ，ｊ，Ｂ，ｊ＞ｂではＡＮＳｉ，ｊ，Ａ＝ＡＮＳｉ，ｊ，Ｂとし（ｊ＝１，…，ｍ、ｉ＝１，…，ｎ）、第二ユーザ装置ｖはその希望売値ｓ（１＜ｓ＜ｍ）に対し、ｊ＜ｓではＶｊ，Ａ＝Ｓｊ，Ａ、Ｖｊ，Ｂ＝Ｓｊ，Ｂとし、ｊ＞ｓではＶｊ，Ａ＝Ｔｊ，Ａ×Ｓｊ，Ａ、Ｖｊ，Ｂ＝Ｔｊ，Ｂ×Ｓｊ，Ｂとし、売買値比較の際にｊ＝ｍから順次ｊの値を小さくして最初にＦｊ，Ａ≠Ｆｊ，Ｂとなるｊを探せばよい。
【００３２】
図２、図３、図１１、図１２にそれぞれ示したユーザ装置はコンピュータにより、それぞれ図６、図７、図１４、図１５に示した処理方法を実行する電子マッチングユーザ装置プログラムを実行させて機能させてもよい。この場合はそのコンピュータに、ＣＤ−ＲＯＭ、可撓性磁気ディスクなどの記録媒体から電子マッチングユーザ装置プログラムをインストールさせ、又は通信回線を介してダウンロードさせて実行させればよい。同様に図４に示したマッチングサーバ装置はコンピュータにより、図８及び図９に示した方法を実行するマッチングサーバ装置プログラムを実行させて機能させてもよい。
【００３３】
【発明の効果】
以上述べたようにこの発明によれば、２つのマッチングサーバ装置を仲介させることにより、次の効果が得られる。
この発明による第１の効果は、現実に近い商取引の場にて、より効率的にかつ安全に取引相手を決定することが可能であることにある。
その理由は、一般的な商取引では１対多ないし多対多での価格交渉が一般的である。これまでの１対１のマッチングではこれを人数回数分繰り返すなど膨大な処理を繰り返すことになっていた。これに対し、この発明では１対多者間にて、マッチングを実現し、かつもし答えが一致するものが一組もなければ各ユーザの答えを守りつつマッチングができるという従来の安全性に関する性質を落とすことなく実現していることにある。
【図面の簡単な説明】
【図１】この発明方法が適用されるシステム構成例を示す図。
【図２】第１の実施の形態における第一ユーザ装置１００の機能構成例を示す図。
【図３】第１の実施の形態における第二ユーザ装置２００の機能構成例を示す図。
【図４】第１の実施の形態におけるマッチングサーバ装置３００の機能構成例を示す図。
【図５】第１の実施の形態における公開掲示板装置４００の機能構成例を示す図。
【図６】第１の実施の形態における第一ユーザ装置１００の処理手順の例を示す流れ図。
【図７】第１の実施の形態における第二ユーザ装置２００の処理手順の例を示す流れ図。
【図８】第１の実施の形態におけるマッチングサーバ装置３００の処理手順の例の一部を示す流れ図。
【図９】図８に示した処理手順の残りの部分を示す流れ図。
【図１０】第１の実施の形態における公開掲示板装置４００の処理手順の例を示す流れ図。
【図１１】第２の実施の形態における第一ユーザ装置１００の機能構成例を示す図。
【図１２】第２の実施の形態における第二ユーザ装置２００の機能構成例を示す図。
【図１３】第２の実施の形態におけるマッチングサーバ装置３００の機能構成例を示す図。
【図１４】第２の実施の形態における第一ユーザ装置１００の処理手順の例を示す流れ図。
【図１５】第２の実施の形態における第二ユーザ装置２００の処理手順の例を示す流れ図。
【図１６】第２の実施の形態におけるマッチングサーバ装置３００の処理手順の例の一部を示す流れ図。
【図１７】第１ユーザ装置ｕｉの希望売値登録の例を示す図。
【図１】
0003619486.tif 000008
【図２】
0003619486.tif 000009
【図３】
0003619486.tif 000010
【図４】
0003619486.tif 000011
【図５】
0003619486.tif 000012
【図６】
0003619486.tif 000013
【図７】
0003619486.tif 000014
【図８】
0003619486.tif 000015
【図９】
0003619486.tif 000016
【図１０】
0003619486.tif 000017
【図１１】
0003619486.tif 000018
【図１２】
0003619486.tif 000019
【図１３】
0003619486.tif 000020
【図１４】
0003619486.tif 000021
【図１５】
0003619486.tif 000022
【図１６】
0003619486.tif 000023
【図１７】
0003619486.tif 000024