JP3619486B2 - Electronic matching method, apparatus program thereof and recording medium thereof - Google Patents

Description

これらの両式から、第二ユーザ装置２００の回答がＹＥＳであれば、第一ユーザｕ１，ｕ２…ｕｎの各装置１００の回答の少くとも１つがＹＥＳであればＦ_Ａ≠Ｆ_Ｂとなり、第一ユーザ装置１００からの回答の全てがＮＯであればＦ_Ａ＝Ｆ_Ｂとなる。
【００２１】
一方、第一ユーザ装置１００からの回答にＹＥＳが含まれていても、第二ユーザ装置２００の回答がＮＯであれば、Ｖ_Ａ＝Ｓ_Ａ、Ｖ_Ｂ＝Ｓ_ＢとなりＦ_Ａ＝Ｆ_Ｂとなる。従って、上記判断が正しいことになる。
第１の実施の形態、第２の実施の形態の何れにおいても、Ｆ_Ａ，Ｆ_Ｂを公開することなく、マッチングサーバＡ，Ｂの各装置３００が復号したＦ_Ａ，Ｆ_Ｂを、従来の技術の項で説明した１対１のマッチングを利用し、これらを公開することなく比較してもよい。例えばマッチングサーバ装置３００が復号したＦ_Ａを、Ｏｂｌｉｖｉｏｕｓ Ｅｖａｌｕａｔｉｏｎ ｏｆ Ｐｏｌｙｎｏｍｉａｌ技術を用いて、マッチングサーバＡの装置３００はマッチングサーバＢしか知らない多項式Ｐ_ＢについてＰ_Ｂ（Ｆ_Ａ）をマッチングサーバＢに知られることなく得、同様に、マッチングサーバＢの装置３００がＰ_Ａ（Ｆ_Ｂ）を得、両マッチングサーバ装置３００において、それぞれＰ_Ａ（Ｆ_Ａ）＋Ｐ_Ｂ（Ｆ_Ａ），Ｐ_Ｂ（Ｆ_Ｂ）＋Ｐ_Ａ（Ｆ_Ｂ）をそれぞれ公開して両者を比較し、これらが互いに相違すればＦ_Ａ≠Ｆ_Ｂであると判定できる。
第３の実施の形態
次に、この発明の電子マッチング方法を電子商取引に適用した例を述べる。ｎ人の売り手（ｕ１，…，ｕｎ）と１人の買い手（ｖ）が存在し、１円〜５円のいずれかを売値・買値として回答してくるものとする。また準同型確率暗号としてＥｌＧａｍａｌ暗号を用いることとし、素数ｐとＺ^＊ _ｐの原始元ｇをシステムに共通なシステムパラメータとする。
【００２２】
マッチングサーバ装置Ａの秘密鍵をｘ_Ａ（∈Ｚ_ｐ−１）、公開鍵をｙ_Ａ（＝ｇ^ｘＡ ｍｏｄ ｐ）とし、同様にマッチングサーバ装置Ｂの秘密鍵をｘ_Ｂ（∈Ｚ_ｐ−１）、公開鍵をｙ_Ｂ（＝ｇ^ｘＢ ｍｏｄ ｐ）とする。成立した際の買い手の優先順位はｕ１，ｕ２，…ｕｎの順とする。また複数価格で成立する可能性がある場合は買値が優先されるものとする。
（１）希望売値登録
各売り手装置ｕｉは以下のようにＡＮＳ_ｉ，Ａ，ＡＮＳ_ｉ，Ｂを準備する。
【００２３】

但し、ＡＮＳ_{ｉ，ｘ，ｘ}∈Ｚ_ｐである。
例えば売り手装置ｕｉの希望売値が「３円以上」であるとすると、ＡＮＳ_ｉ，ＡとＡＮＳ_ｉ，Ｂは図１６のようにセットされる。つまりＡＮＳ_{ｉ，ｊ，Ａ}，ＡＮＳ_{ｉ，ｊ，Ｂ}（ｊ＝１，２，…，５）を各価格に対応して用意し、希望売値以上のＡＮＳ_{ｉ，ｊ，Ａ}とＡＮＳ_{ｉ，ｊ，Ｂ}とを互いに異ならせ、つまり回答ＹＥＳとし、希望売値より小さいＡＮＳ_{ｉ，ｊ，Ａ}とＡＮＳ_{ｉ，ｊ，Ｂ}とを互いに等しく、つまり回答ＮＯとする。
【００２４】
ｕｉは次のような乱数群Ｒ_ｉ，Ａ，Ｒ_ｉ，Ｂを生成する。

をコミットメントとして公開する。さらにＡＮＳ_ｉ，ＡとＲ_ｉ，Ａをマッチングサーバ装置Ａに、ＡＮＳ_ｉ，ＢＡとＲ_ｉ，Ｂをマッチングサーバ装置Ｂに他人に知られないように送信する。
（２）売値バンドル
マッチングサーバ装置ＡはＡＮＳ_１，Ａ，ＡＮＳ_２，Ａ，…，ＡＮＳ_ｎ，Ａを受け取る。
【００２５】

ｈ_１，Ａ，ｈ_２，Ａ，…，ｈ_５，Ａを自装置の公開鍵と乱数ｒａで各々暗号化してＴ_ｊ，Ａ（ｊ＝１，…，５）を得る。
【００２６】
Ｔ_ｊ，Ａ＝（ｙ^ｒａ _Ａｈ_ｊ，Ａ ｍｏｄ ｐ，ｇ^ｒａ ｍｏｄ ｐ）
ｊ＝１，…，５に対して
Ｔ_ｊ，Ａをユーザ装置ｖに送る。
同様にマッチングサーバ装置ＢはＡＮＳ_１，Ｂ，ＡＮＳ_２，Ｂ，…，ＡＮＳ_ｎ，Ｂを受け取り、ｈ_１，Ｂ，ｈ_２，Ｂ，…，ｈ_５，Ｂを計算し、自装置の公開鍵と乱数ｒｂにて各々暗号化して、Ｔ_ｊ，Ｂ（ｊ＝１，…，５）を得る。
Ｔ_ｊ，Ｂ＝（ｙ^ｒｂ _Ｂ ｈ_ｊ，Ｂ ｍｏｄ ｐ，ｇ^ｒｂ ｍｏｄ ｐ）
ｊ＝１，…，５に対して、
Ｔ_ｊ，Ｂをユーザ装置ｖに送る。
（３）希望買値登録
ユーザ装置ｖはＴ_１，Ａ，Ｔ_２，Ａ，…，Ｔ_５，Ａ，Ｔ_１，Ｂ，Ｔ_２，Ｂ，…，Ｔ_５，Ｂを受け取り、乱数Ｒ_１，ｖ，Ｒ_２，ｖ，…，Ｒ_５，ｖ（∈Ｚ_ｐ）を生成する。Ｒ_ｊ，ｖを装置Ａの公開鍵と乱数ｒ_Ａ，ｖにて各々暗号化してＳ_ｊ，Ａを得る。同様に、Ｒ_ｊ，ｖを装置Ｂの公開鍵と乱数ｒ_Ｂ，ｖにて各々暗号化してＳ_ｊ，Ｂを得る。
【００２７】

装置ｖは乱数Ｒ_ｊ，Ｖ（ｊ＝１，…，５）を生成し、ｈ（Ｒ_ｊ，ｖ，Ｒ_ｊ，ｖ）をコミットメントとして公開する。各ｊと希望買値の大小関係に応じて以下のようにＶ_ｊ，Ａ，Ｖ_ｊ，Ｂを計算する。
【００２８】

ｊ＝１，…，５に対してＶ_ｊ，Ａを装置Ａに、Ｖ_ｊ，Ｂを装置Ｂに送る。
（４）売買値比較
装置Ａは（Ｖ_ｊ，Ａ）を復号し、Ｗ_１，Ａ，Ｗ_２，Ａ，…，Ｗ_５，Ａを得る。同様に装置Ｂは（Ｖ_ｊ，Ｂ）を復号し、Ｗ_１，Ｂ，Ｗ_２，Ｂ，…，Ｗ_５，Ｂを得る。ｊ＝１とする。Ａ，ＢはＷ_ｊ，Ａ，Ｗ_ｊ，Ｂを公開する。もしＷ_ｊ，Ａ≠Ｗ_ｊ，Ｂならば（５）へ、それ以外ではｊ←ｊ＋１とし、同じプロセスを繰り返す。もし全てのｊに対してＷ_ｊ，Ａ＝Ｗ_ｊ，Ｂとなれば、この取引は「不成立」を結果として返して終了する。
（５）ｕｉ特定
（４）の処理からのｊの値を引き継ぎ以下を実行する。ｉ＝１とする。装置Ａ，ＢはＡＮＳ_{ｉ，ｊ，Ａ}とＡＮＳ_{ｉ，ｊ，Ｂ}を各々公開する。もしＡＮＳ_{ｉ，ｊ，Ａ}≠ＡＮＳ_{ｉ，ｊ，Ｂ}ならば装置ｕｉが勝者であり、この取引は「成立」を結果として返して終了する。それ以外ではｉ←ｉ＋１とし、同じプロセスを繰り返す。
【００２９】
この方法によれば以下のように安全性が保証される。
（Ａ）ユーザの登録情報の秘匿性
もしマッチングが「不成立」（Ｆ_Ａ＝Ｆ_Ｂ）ならば、第三者が得たいのは、どの状況で「不成立」となったかである。第三者が得られる情報は、ｈ（ＡＮＳ_ｉ，Ａ，Ｒ_ｉ，Ａ），ｈ（ＡＮＳ_ｉ，Ｂ，Ｒ_ｉ，Ｂ），Ｔ_Ａ，Ｔ_Ｂ，ｈ（Ｒ_Ｖ，Ｒ_Ｖ′），Ｖ_Ａ，Ｖ_Ｂ，Ｗ_Ａ，Ｗ_Ｂである。
ｈ（ＡＮＳ_ｉ，Ａ，Ｒ_ｉ，Ａ），ｈ（ＡＮＳ_ｉ，Ｂ，Ｒ_ｉ，Ｂ）からＡＮＳ_ｉ，Ａ，ＡＮＳ_ｉ，Ｂを求める困難性は関数ｈの一方向性に基づいている。
【００３０】
Ｔ_Ａ，Ｔ_Ｂは確率暗号にて暗号化された結果であるので、第三者はＴ_Ａ＝Ｔ_ＢなのかＴ_Ａ≠Ｔ_Ｂなのか区別がつかない。
またＶ_Ａ，Ｖ_Ｂも確率暗号による暗号文であるため、これらがＴ_Ａ，Ｔ_Ｂを含むかどうかは分からない。
（Ｂ）公平性
各ユーザは他ユーザの登録した回答を得られるか。
（Ａ）と同様に、公開されている情報から他ユーザの回答は得られない。ただし、両マッチングサーバＡ，Ｂは互いに結託しないものとし、またマッチングサーバＡ，Ｂが同一のユーザと結託することがないものとする。
【００３１】
以上よりユーザは自分の回答登録前に他ユーザの回答を得ることはできない。
（Ｃ）否認不可性
第一ユーザがｕはｈ（ＡＮＳ_ｉ，Ａ，Ｒ_ｉ，Ａ），ｈ（ＡＮＳ_ｉ，Ｂ，Ｒ_ｉ，Ｂ）を、第二ユーザｖはｈ（Ｒ_Ｖ，Ｒ_Ｖ′）をコミットメントとして公開しており、これを否認するためには関数ｈのコリジョンを見つけることが必要となる。
上述においては最も安い価格で買うことができるが、第一ユーザ装置ｕ１，…ｕｎが希望買値登録し、第二ユーザ装置ｖが希望売値登録して、最も高い価格で売るようにすることもできる。この場合は第一ユーザ装置ｕｉはその希望買値ｂ（１＜ｂ＜ｍ：ｍは価格リストの最高値、前記例では５円）に対し、ｊ＜ｂではＡＮＳ_{ｉ，ｊ，Ａ}≠ＡＮＳ_{ｉ，ｊ，Ｂ}，ｊ＞ｂではＡＮＳ_{ｉ，ｊ，Ａ}＝ＡＮＳ_{ｉ，ｊ，Ｂ}とし（ｊ＝１，…，ｍ、ｉ＝１，…，ｎ）、第二ユーザ装置ｖはその希望売値ｓ（１＜ｓ＜ｍ）に対し、ｊ＜ｓではＶ_ｊ，Ａ＝Ｓ_ｊ，Ａ、Ｖ_ｊ，Ｂ＝Ｓ_ｊ，Ｂとし、ｊ＞ｓではＶ_ｊ，Ａ＝Ｔ_ｊ，Ａ×Ｓ_ｊ，Ａ、Ｖ_ｊ，Ｂ＝Ｔ_ｊ，Ｂ×Ｓ_ｊ，Ｂとし、売買値比較の際にｊ＝ｍから順次ｊの値を小さくして最初にＦ_ｊ，Ａ≠Ｆ_ｊ，Ｂとなるｊを探せばよい。
【００３２】
図２、図３、図１１、図１２にそれぞれ示したユーザ装置はコンピュータにより、それぞれ図６、図７、図１４、図１５に示した処理方法を実行する電子マッチングユーザ装置プログラムを実行させて機能させてもよい。この場合はそのコンピュータに、ＣＤ−ＲＯＭ、可撓性磁気ディスクなどの記録媒体から電子マッチングユーザ装置プログラムをインストールさせ、又は通信回線を介してダウンロードさせて実行させればよい。同様に図４に示したマッチングサーバ装置はコンピュータにより、図８及び図９に示した方法を実行するマッチングサーバ装置プログラムを実行させて機能させてもよい。
【００３３】
【発明の効果】
以上述べたようにこの発明によれば、２つのマッチングサーバ装置を仲介させることにより、次の効果が得られる。
この発明による第１の効果は、現実に近い商取引の場にて、より効率的にかつ安全に取引相手を決定することが可能であることにある。
その理由は、一般的な商取引では１対多ないし多対多での価格交渉が一般的である。これまでの１対１のマッチングではこれを人数回数分繰り返すなど膨大な処理を繰り返すことになっていた。これに対し、この発明では１対多者間にて、マッチングを実現し、かつもし答えが一致するものが一組もなければ各ユーザの答えを守りつつマッチングができるという従来の安全性に関する性質を落とすことなく実現していることにある。
【図面の簡単な説明】
【図１】この発明方法が適用されるシステム構成例を示す図。
【図２】第１の実施の形態における第一ユーザ装置１００の機能構成例を示す図。
【図３】第１の実施の形態における第二ユーザ装置２００の機能構成例を示す図。
【図４】第１の実施の形態におけるマッチングサーバ装置３００の機能構成例を示す図。
【図５】第１の実施の形態における公開掲示板装置４００の機能構成例を示す図。
【図６】第１の実施の形態における第一ユーザ装置１００の処理手順の例を示す流れ図。
【図７】第１の実施の形態における第二ユーザ装置２００の処理手順の例を示す流れ図。
【図８】第１の実施の形態におけるマッチングサーバ装置３００の処理手順の例の一部を示す流れ図。
【図９】図８に示した処理手順の残りの部分を示す流れ図。
【図１０】第１の実施の形態における公開掲示板装置４００の処理手順の例を示す流れ図。
【図１１】第２の実施の形態における第一ユーザ装置１００の機能構成例を示す図。
【図１２】第２の実施の形態における第二ユーザ装置２００の機能構成例を示す図。
【図１３】第２の実施の形態におけるマッチングサーバ装置３００の機能構成例を示す図。
【図１４】第２の実施の形態における第一ユーザ装置１００の処理手順の例を示す流れ図。
【図１５】第２の実施の形態における第二ユーザ装置２００の処理手順の例を示す流れ図。
【図１６】第２の実施の形態におけるマッチングサーバ装置３００の処理手順の例の一部を示す流れ図。
【図１７】第１ユーザ装置ｕｉの希望売値登録の例を示す図。[0001]
BACKGROUND OF THE INVENTION
In the present invention, a plurality of users (u1, u2,..., Un), one user (v) that can be distinguished from this, and their questions (for example, u1, u2,. , "Do you want to buy for 10,000 yen?") And v is one of u1, u2, ..., un, and the answer to v's question is YES The present invention relates to an electronic matching method capable of determining “transaction establishment” when both are in the relationship of a seller as in the above example, and a recording medium on which the program is recorded.
[0002]
[Prior art]
Conventional electronic matching methods are listed in Moni Naor, Benny Pinkas: “Obligious Transfer and Polynomial Evaluation”, STOC99, ACM. This method is a one-to-one electronic matching system, and this method uses a technique called Obvious Evaluation of Polynomial. This technique has Alice (Alice) and Bob (Bob), there is a value x that only Alice knows and a polynomial P that only Bob knows, Alice knows Bob does not know x, Bob knows P to Alice Without Alice, the value P (x) is obtained. Moni and Naor have proposed the following one-to-one matching as an application of this method. Function P that user u and user v know only u_uAnd value x_u, V only knows function P_vAnd value x_vThere is. Using the previous Oblivious Evaluation of Polynomial,_u, X_vWithout knowing u_v(X_u), V is P_u(X_v), U is P_u(X_u) + P_v(X_u) And v is P_v(X_v) + P_u(X_u). Secret value x of both_u, X_vIf they are equal, the published ones will match.
[0003]
[Problems to be solved by the invention]
The problem with the prior art is that only one-to-one matching is possible. The reason is that in the field of various electronic commerce, there are many one-to-many or many-to-many, and this is not possible.
An object of the present invention is to provide an electronic matching method capable of making a comparison between a one-to-many person while protecting a user's privacy (answer).
[0004]
[Means for Solving the Problems]
According to the present invention, a plurality of first user devices u1, u2,..., Un, one second user device v distinguishable from these, and two matching server devices A and B are provided. These devices each have a secret answer of YES or NO to the questions to the device and the second user device, and the answers of the first user devices u1, u2,..., Un by interposing the two matching server devices A and B. Can be determined only when there is at least one YES and the answer of the second user device is YES.
[0005]
For example, if the answer is YES in the first user devices u1, u2,._{i, A}  , ANS_{i, B}  (I = 1, 2,..., N) are equal to each other if the answer is NO._{i, A}  , ANS_{i, B}  If the answer is YES, the second user device v_{i, A}  Probabilistic homomorphic ciphertext V containing components related to all_AAnd ANS_{i, B}  Probabilistic homomorphic ciphertext V containing components related to all_BIf the answer is NO, each stochastic homomorphic ciphertext V for the same random number_A, V_BAnd the matching server devices A and B are V_A, V_BIs decrypted.
[0006]
It differs from the prior art in that one-to-many matching is possible.
[0007]
DETAILED DESCRIPTION OF THE INVENTION
Next, embodiments of the present invention will be described in detail with reference to the drawings.
First embodiment
A configuration example of a system to which the present invention is applied includes a plurality of first user devices 100, one second user device 200, two matching server devices 300, and a public bulletin board device 400 as shown in FIG. 500 is connected.
FIG. 2 shows a functional configuration example of the first user device 100, FIG. 3 shows a functional configuration example of the second user device 200, FIG. 4 shows a functional configuration example of the matching server device 300, and FIG. Each is shown in FIG.
[0008]
Next, the overall operation of this embodiment will be described in detail with reference to the flowcharts of FIGS.
First, as shown in FIG. 6, the first user device 100 (see FIG. 2) of the first user ui (i = 1, 2,..., N) has different random numbers ANS in the random number generation unit 101._{i, A}, ANS_{i, B}, R_{i, A}, R_{i, B}Is generated (S1), and YES or NO is read as an answer from the answer storage unit 102 (S2). If this answer is NO (S3), the answer generation unit 103 determines that the answer is ANS._{i, B}ANS_{i, A}Overwrite with ANS_{i, A}(S4). Public key storage unit 104 to PK_A, PK_BIs read (S5), and the probability cryptographic operation unit 105 performs PK_A, PK_BANS_{i, A}, ANS_{i, B}Encrypt U_{i, A}, U_{i, B}Is created (S6). In the one-way function calculation unit 106 (ANS_{i, A}, R_{i, A}), (ANS_{i, B}, R_{i, B}) For each one-way function_{i, A}, H_{i, B}Is created (S7). The transmitter 107 is h_{i, A}, H_{i, B}To the public bulletin board apparatus 400, U_{i, A}To the matching server device 300, U_{i, B}Are transmitted to another matching server device 300 (S8).
[0009]
As shown in FIG. 10, the public bulletin board apparatus 400 (see FIG. 5)_{i, A}, H_{i, B}Are stored in the public storage unit 402 that can be referred to by other devices (S2).
Next, as shown in FIG. 8, the matching server device 300 operates. In FIG. 8 and the following description, the matching server device 300 is described as being the matching server A, but the other matching server device 300 is the matching server B, and the operation thereof is shown in FIG. It is assumed that all are replaced with B. The matching server device 300 (see FIG. 4) first receives Us transmitted from the plurality of first user devices 100 by the receiving unit 301._{1, A}, U_{2, A}..., U_{n, A}Is received (S1). Next, the private key SK of the matching server from the public key private key storage unit 302_A(S2), and the probabilistic homomorphic public key encryption / decryption unit 303 executes U_{1, A}, U_{2, A}..., U_{n, A}ANS_{1, A}, ANS_{2, B}, ANS_{n, A}Is obtained (S3). In the one-way function calculation unit 304 (ANS_{1, A}, ANS_{2, A}, ANS_{n, A}) With a one-way function_AIs obtained (S4). Public key PK from public key private key storage unit 302_A(S5), and the probabilistic homomorphic public key encryption unit 305_APK_AEncrypt with T_AIs obtained (S6). T at transmission unit 306_AIs transmitted to the second user apparatus 200 (S7).
[0010]
Next, as shown in FIG. 7, the second user device 200 (see FIG. 3) receives the matching server device 300 from the matching server device 300 in the receiving unit 201._AFrom another matching server device 300 to T_BAre respectively received (S1). Random number R in random number generator 203_V(S2) and PK from the public key storage unit 202_A, PK_BIs read (S3). R in the probabilistic homomorphic public key encryption unit 204_VPK_A, PK_BEncrypt each with S_A, S_BIs obtained (S4). YES or NO is read from the answer storage unit 205 as an answer (S5). If the read answer is YES (S6), the answer generator 206_A= S_A× T_A, V_B= S_B× T_B(S7), and if the answer is NO, V_A= S_A, V_B= S_B(S8), the one-way function calculation unit 207 is R_VApply a one-way function to h_VIs created (S9). The transmitter 208 is h_VTo the public bulletin board device 400, V_ATo the matching server device 300, V_BAre transmitted to another matching server device 300 (S9).
[0011]
As shown in FIG. 10, the public bulletin board apparatus 400 receives h at the receiving unit 401._VIs received (S1) and stored in the public storage unit 402 (S2).
Next, as shown in FIG. 9, the matching server device 300 operates. In FIG. 9 and the following description, the matching server device 300 is described as being the matching server A, but the other matching server device 300 is the matching server B, and the operation thereof is shown in FIG. It is assumed that all are replaced with B. First, the receiving unit 301 uses V_AIs received (S1). The private key SK of the matching server A from the public key private key storage unit 302_A(S2), and the probabilistic homomorphic public key encryption / decryption unit 303 performs V_ASK_ADecrypted with F_AIs obtained (S3). F at the transmission unit 306_AIs transmitted to the public bulletin board apparatus 400 (S4).
[0012]
Next, as shown in FIG. 10, the public bulletin board device 400 operates, and first F_A, F_BAre received by the receiving unit 401 and then transferred to the public storage unit 402 that can be referred to by other devices._A, F_BAccumulate.
Probabilistic homomorphic encryption has the property that E (a · b) = E (a) · E (b). Therefore, if the answer of the second user device v is YES, V_A= S_A× T_A= E_PKA(R_v・ H_A), V_B= S_B× T_B= E_PKB(R_v・ H_B) If at least one of the first user devices u1,._A≠ h_BIt becomes. That is, if at least one of the first user devices u1,..., Un is answered and the answer of the second user device v is also YES, F_A(= R_V・ H_A) ≠ F_B(= R_V・ H_B) In other cases, even if there is YES in the responses of the first user devices u1,..., Un, if the answer of the second user device v is NO, F_A(= R_V) = F_B(= R_VIn addition, even if the answer of the second user device v is YES, if all the answers of the first user devices u1,._A= H_BTherefore, F_A(= R_V・ H_A) = F_B(= R_V・ H_B) And in either case F_A= F_BIt becomes. So F_A≠ F_BMatching is established only when
[0013]
Moreover, since it is encrypted with probability encryption,_A= T_BNana T_A≠ T_BCannot be distinguished, and V_A, V_BAlso T_A, T_BI don't know if it contains. That is, it is impossible to determine whether the answer of the first user device is NO or the answer of the second user device is NO.
The first user device 100 is h_{i, A}, H_{i, B}Is transmitted to the public bulletin board apparatus 400 as a commitment to prevent denial of the answer, and the second user apparatus 200 sends h_VIs sent to the public bulletin board apparatus 400 in order to make it public as a commitment to prevent denial of the answer. ANS from the first user device 100 to the server device 300_{i, A}, ANS_{i, B}In short, it is only necessary to send them secretly without leaking them to a third party.
Second embodiment
In the first embodiment, except for the public bulletin board device 400, the information flow is the first user device 100 → the matching server device 300 → the second user device 200 → the matching server device 300. In the second embodiment, the burden of the matching server device 300 is reduced by changing the information flow from the first user device 100 to the second user device 200 to the matching server device 300.
[0014]
The applied system configuration example is the same as that shown in FIG. As shown in FIG. 11, the functional configuration example of the first user device 100 is a probabilistic homomorphic public key encryption unit 115 in the configuration of the stochastic encryption unit 105 illustrated in FIG. 2. An example of the functional configuration of the second user apparatus 200 is shown in FIG._A, T_BA generation unit 209 is added. The functional configuration example of the matching server device 300 is as shown in FIG. 13, and the functional configuration example of the public bulletin board device 400 is the same as that shown in FIG. Examples of the processing procedures of the first user device 100, the second user device 200, and the matching server device 300 are shown in FIGS. The processing procedure of the public bulletin board apparatus 400 is the same as that in FIG.
[0015]
The overall operation of the second embodiment will be described in detail below.
First, the first user device 100 (see FIG. 11) of the first user i (i = 1, 2,..., N) has different random numbers ANS in the random number generation unit 101 as shown in FIG._{i, A}, ANS_{i, B}, R_{i, A}, R_{i, B}Is generated (S1), and YES or NO is read from the answer storage unit 102 as an answer (S2). If this answer is NO (S3), the answer generation unit 103 determines that the answer is ANS._{i, B}ANS_{i, A}Overwrite with ANS_{i, B}And ANS_{i, A}Are made equal (S4). Each public key PK of the matching servers A and B from the public key storage unit 104_A, PK_BIs read out (S5), and the probabilistic homomorphic public key encryption unit 115 performs PK_A, PK_BANS using each_{i, A}, ANS_{i, B}Encrypt U_{i, A}, U_{i, B}Is generated (S6).
[0016]
The one-way function calculation unit 106 (ANS_{i, A}, R_{i, A}) And (ANS_{i, B}, R_{i, B}) With a one-way function_{i, A}= H (ANS_{i, A}, R_{i, A}) And h_{i, B}= H (ANS_{i, B}, R_{i, B}) Is generated (S7). U by the transmitter 107_{i, A}, U_{i, B}, H_{i, A}, H_{i, B}Is transmitted to the public bulletin board apparatus 400 (S8). H_{i, A}, H_{i, B}Is used as a commitment to prevent nonrepudiation of answers.
As shown in FIG. 15, the second user device 200 (see FIG. 12) receives the U from the public bulletin board device 400 in the receiving unit 201._{1, A}, U_{2, A}, ..., U_{n, A}, U_{1, B}, U_{2, B}, ..., U_{n, B}Is received (S1). T_A, T_BT in the generation unit 209_A= U_{1, A}× U_{2, A}× ... × U_{n, A}, T_B= U_{1, B}× U_{2, B}× ... × U_{n, B}Is generated (S2).
[0017]
Random number R in random number generator 203_V(S3) and the public keys PK of the matching servers A and B from the public key storage unit 202_A, PK_BIs read (S4).
The public key PK is obtained by the probabilistic homomorphic public key cryptography unit 204._A, PK_BUsing R_VEncrypt S_A, S_BIs generated (S5). YES or NO is read from the answer storage unit 205 as an answer (S6). If the read answer is YES (S7), the answer generator 206_A= S_A× T_A, V_B= S_B× T_BIs generated (S8), and if the answer is NO, V_A= S_A, V_B= S_B(S9), the one-way function unit 207 is R_VApply a one-way function to h_V= H (R_V) Is generated (S10). The transmitter 208 is h_VTo the public bulletin board apparatus 400 as a commitment to prevent non-repudiation of the answer,_ATo the device 300 of the matching server A, V_BAre transmitted to the device 300 of the matching server B (S11).
[0018]
As shown in FIG. 10, the public bulletin board apparatus 400 is h_VIs received (S1) and stored in the public storage unit 402 (S2).
As shown in FIG. 16, the matching server device 300 (see FIG. 13) operates as follows. In FIG. 16 and the following description, the matching server device 300 is described as being the device of the matching server A, but the other matching server device 300 is that of the matching server B, and the operation thereof is illustrated in FIG. 10 and the following description. It operates as if A in the content is all replaced with B. First, the receiving unit 301 uses V_AIs received (S1). Private key SK of own device from secret key storage unit 302_A(S2), and the probabilistic homomorphic public key encryption / decryption unit 303 performs V_ADecrypts F_AIs obtained (S3). F at the transmission unit 304_AIs transmitted to the public bulletin board apparatus 400 (S4).
[0019]
As shown in FIG. 10, the public bulletin board device 400 has two Fs from the matching server device 300._A, F_BAre received by the receiving unit 401. Next, to the public storage unit 402 that can be referred to from other devices._A, F_BAccumulate.
Also in this case, as in the first embodiment, F_AAnd F_BAre different, it is determined that at least one of the responses from the devices 100 of the users u1,... Un is YES and the response of the second user device 200 is YES._AAnd F_BIf they match, it is determined that the other case has occurred. V_A, V_BIf the answer of the second user device 200 is YES, the following equation is obtained from the property of the homomorphic encryption.
[0020]

From both of these formulas, if the answer of the second user device 200 is YES, if at least one of the responses of each device 100 of the first user u1, u2,._A≠ F_BIf all of the responses from the first user device 100 are NO, F_A= F_BIt becomes.
[0021]
On the other hand, even if YES is included in the answer from the first user device 100, if the answer of the second user device 200 is NO, V_A= S_A, V_B= S_BNext F_A= F_BIt becomes. Therefore, the above judgment is correct.
In both the first embodiment and the second embodiment, F_A, F_BF that decrypted by each device 300 of matching servers A and B without publishing_A, F_BMay be compared without using the one-to-one matching described in the section of the prior art. For example, the F decrypted by the matching server device 300_AUsing the Obvious Evaluation of Polynomial technique, the device 300 of the matching server A knows only the polynomial P_BAbout P_B(F_A) Without being known to the matching server B, and similarly, the device 300 of the matching server B_A(F_B) And both matching server devices 300 each have P_A(F_A) + P_B(F_A), P_B(F_B) + P_A(F_B) And comparing them, and if they are different from each other,_A≠ F_BCan be determined.
Third embodiment
Next, an example in which the electronic matching method of the present invention is applied to electronic commerce will be described. It is assumed that there are n sellers (u1,..., un) and one buyer (v), and any one of 1 to 5 yen is answered as the selling price / buying price. ElGamal encryption is used as the homomorphic probability encryption, and the prime numbers p and Z^* _pIs a system parameter common to the system.
[0022]
The secret key of matching server device A is x_A(∈Z_p-1) Y_A(= G^xA  mod p), and similarly, the matching server device B's private key is x_B(∈Z_p-1) Y_B(= G^xB  mod p). The priority order of buyers when established is u1, u2,. If there is a possibility that it will be established at multiple prices, the purchase price will be given priority.
(1) Register desired price
Each seller device ui is ANS as follows_{i, A}, ANS_{i, B}Prepare.
[0023]

However, ANS_{i, x, x}∈Z_pIt is.
For example, if the desired selling price of the seller device ui is “3 yen or more”, the ANS_{i, A}And ANS_{i, B}Are set as shown in FIG. In other words, ANS_{i, j, A}, ANS_{i, j, B}(J = 1, 2,..., 5) corresponding to each price, ANS more than the desired selling price_{i, j, A}And ANS_{i, j, B}Are different from each other, that is, the answer is YES, and the ANS is smaller than the desired selling price._{i, j, A}And ANS_{i, j, B}Are equal to each other, that is, the answer is NO.
[0024]
ui is a random number group R such as_{i, A}, R_{i, B}Is generated.

Is published as a commitment. ANS_{i, A}And R_{i, A}To the matching server device A, ANS_{i, BA}And R_{i, B}Is transmitted to the matching server device B so as not to be known to others.
(2) Sell price bundle
Matching server device A is ANS_{1, A}, ANS_{2, A}, ..., ANS_{n, A}Receive.
[0025]

h_{1, A}, H_{2, A}, ..., h_{5, A}Is encrypted with its own public key and random number ra._{j, A}(J = 1,..., 5) is obtained.
[0026]
T_{j, A}= (Y^ra _Ah_{j, A}  mod p, g^ramod p)
For j = 1, ..., 5
T_{j, A}To the user device v.
Similarly, the matching server device B is an ANS._{1, B}, ANS_{2, B}, ..., ANS_{n, B}H_{1, B}, H_{2, B}, ..., h_{5, B}Are calculated using the public key of the device and the random number rb, and T_{j, B}(J = 1,..., 5) is obtained.
T_{j, B}= (Y^rb _B  h_{j, B}  mod p, g^rb  mod p)
For j = 1, ..., 5,
T_{j, B}To the user device v.
(3) Desired bid price registration
User device v is T_{1, A}, T_{2, A}, ..., T_{5, A}, T_{1, B}, T_{2, B}, ..., T_{5, B}Random number R_{1, v}, R_{2, v}, ..., R_{5, v}(∈Z_p) Is generated. R_{j, v}Device A's public key and random number r_{A, v}Encrypt each with S_{j, A}Get. Similarly, R_{j, v}Device B's public key and random number r_{B, v}Encrypt each with S_{j, B}Get.
[0027]

Device v is a random number R_{j, V}(J = 1,..., 5) and h (R_{j, v}, R_{j, v}) As a commitment. Depending on the magnitude relationship between each j and the desired bid price, V_{j, A}, V_{j, B}Calculate
[0028]

V for j = 1, ..., 5_{j, A}To device A, V_{j, B}To device B.
(4) Comparison of trading value
Device A is (V_{j, A}) And W_{1, A}, W_{2, A}, ..., W_{5, A}Get. Similarly, device B is (V_{j, B}) And W_{1, B}, W_{2, B}, ..., W_{5, B}Get. Let j = 1. A and B are W_{j, A}, W_{j, B}Publish. If W_{j, A}≠ W_{j, B}If so, go to (5), otherwise set j ← j + 1 and repeat the same process. W for all j_{j, A}= W_{j, B}If this is the case, this transaction is terminated with a “not established” result.
(5) Specify ui
Takes over the value of j from the process of (4) and executes the following. i = 1. Devices A and B are ANS_{i, j, A}And ANS_{i, j, B}Publish each. If ANS_{i, j, A}≠ ANS_{i, j, B}If so, the device ui is the winner, and the transaction ends with “successful” as a result. Otherwise, i ← i + 1, and the same process is repeated.
[0029]
According to this method, safety is ensured as follows.
(A) Confidentiality of user registration information
If the match is “not established” (F_A= F_B) If so, what the third party wants to get is in what situation it was “not established”. Information obtained by a third party is h (ANS_{i, A}, R_{i, A}), H (ANS_{i, B}, R_{i, B}), T_A, T_B, H (R_V, R_V′), V_A, V_B, W_A, W_BIt is.
h (ANS_{i, A}, R_{i, A}), H (ANS_{i, B}, R_{i, B}) To ANS_{i, A}, ANS_{i, B}Is based on the unidirectionality of the function h.
[0030]
T_A, T_BIs the result of encryption using probability encryption,_A= T_BNana T_A≠ T_BI can't tell if it is.
V_A, V_BSince these are ciphertexts using probabilistic encryption, these are T_A, T_BI don't know if it contains.
(B) Fairness
Can each user get answers registered by other users?
Similar to (A), other users' answers cannot be obtained from the published information. However, it is assumed that the matching servers A and B do not collide with each other, and the matching servers A and B do not collide with the same user.
[0031]
From the above, the user cannot obtain another user's answer before registering his answer.
(C) Non-repudiation
The first user is u (ANS_{i, A}, R_{i, A}), H (ANS_{i, B}, R_{i, B}), The second user v is h (R_V, R_V′) Is published as a commitment, and in order to deny it, it is necessary to find the collision of the function h.
In the above, it is possible to buy at the lowest price, but the first user device u1,. . In this case, the first user device ui has its desired bid price b (1<b<m: m is the highest price in the price list (5 yen in the above example)<In b, ANS_{i, j, A}≠ ANS_{i, j, B}, J> b, ANS_{i, j, A}= ANS_{i, j, B}(J = 1,..., M, i = 1,..., N), and the second user device v receives the desired selling price s (1<s<m) for j <s_{j, A}= S_{j, A}, V_{j, B}= S_{j, B}And j>s for V_{j, A}= T_{j, A}× S_{j, A}, V_{j, B}= T_{j, B}× S_{j, B}And the value of j is sequentially decreased from j = m in the sale price comparison, and F_{j, A}≠ F_{j, B}Find j that becomes
[0032]
2, 3, 11, and 12 cause a computer to execute an electronic matching user device program that executes the processing methods illustrated in FIGS. 6, 7, 14, and 15, respectively, by a computer. May function. In this case, the electronic matching user device program may be installed in the computer from a recording medium such as a CD-ROM or a flexible magnetic disk, or downloaded through a communication line and executed. Similarly, the matching server apparatus shown in FIG. 4 may be caused to function by executing a matching server apparatus program that executes the method shown in FIGS. 8 and 9 by a computer.
[0033]
【The invention's effect】
As described above, according to the present invention, the following effects can be obtained by mediating two matching server devices.
The first effect of the present invention is that it is possible to determine a trading partner more efficiently and safely in a commercial transaction place.
The reason is that in general commercial transactions, one-to-many or many-to-many price negotiations are common. In the one-to-one matching so far, enormous processing such as repeating this for the number of people has been repeated. On the other hand, in the present invention, matching is realized between one-to-many people, and if there is no one that matches the answer, it is possible to perform matching while protecting each user's answer. It is to have realized without dropping.
[Brief description of the drawings]
FIG. 1 is a diagram showing a system configuration example to which the method of the present invention is applied.
FIG. 2 is a diagram illustrating a functional configuration example of a first user device 100 according to the first embodiment.
FIG. 3 is a diagram illustrating a functional configuration example of a second user apparatus 200 according to the first embodiment.
FIG. 4 is a diagram illustrating a functional configuration example of a matching server device 300 according to the first embodiment.
FIG. 5 is a diagram illustrating a functional configuration example of a public bulletin board apparatus 400 according to the first embodiment.
FIG. 6 is a flowchart showing an example of a processing procedure of the first user apparatus 100 in the first embodiment.
FIG. 7 is a flowchart showing an example of a processing procedure of the second user apparatus 200 according to the first embodiment.
FIG. 8 is a flowchart showing a part of an example of a processing procedure of the matching server device 300 according to the first embodiment.
FIG. 9 is a flowchart showing the remaining part of the processing procedure shown in FIG. 8;
FIG. 10 is a flowchart showing an example of a processing procedure of the public bulletin board apparatus 400 in the first embodiment.
FIG. 11 is a diagram illustrating a functional configuration example of a first user device 100 according to the second embodiment.
FIG. 12 is a diagram illustrating a functional configuration example of a second user apparatus 200 according to the second embodiment.
FIG. 13 is a diagram illustrating a functional configuration example of a matching server device 300 according to the second embodiment.
FIG. 14 is a flowchart showing an example of a processing procedure of the first user apparatus 100 according to the second embodiment.
FIG. 15 is a flowchart illustrating an example of a processing procedure of the second user apparatus 200 according to the second embodiment.
FIG. 16 is a flowchart showing a part of an example of a processing procedure of the matching server device 300 according to the second embodiment.
FIG. 17 is a diagram showing an example of desired selling price registration of the first user device ui.

Claims (12)

A plurality of first user devices u1, u2,..., One second user device v that can be distinguished from these, two matching server devices A and B, and any public bulletin board device can be referred to. With areas,
Each first user device ui (i = 1, 2,..., N) generates random numbers ANS _{i, A} and ANS _{i, B} that are different if the answer of the device ui is YES, and if NO, is the same value. these ANS _i, a, ANS _i, each public key _B to matching server device a PK _a, and encrypts each with _{PK B U i, a, U} i, to create a _B, matching the U _{i, a} Send U _{i, B} to matching server device B to server device A,
Furthermore, different random numbers R _{i, A} , R _{i, B} are generated, and a one-way function is applied to (ANS _{i, A} , R _{i, A} ), (ANS _{i, B} , R _{i, B} ), respectively. h _{i, A} = h (ANS _{i, A} , R _{i, A} ) and h _{i, B} = h (ANS _{i, B} , R _{i, B} ) are generated, and these h _{i, A} , h _{i, B} are generated. Published on the bulletin board device as a commitment to prevent denial of answers,
The matching server device A decrypts each U _{i, A} received from each first user device ui with the secret key SK _A to obtain ANS _{i, A} and determines them (ANS _{1, A} ,..., ANS _{n, A} ). A one-way function is applied to calculate h _A = h (ANS _{1, A} , ANS _{2, A} ,..., ANS _{n, A} ), and this is used for probabilistic homomorphic disclosure using the public key of the matching server device A seeking T _a and encrypted by key encryption and sends it to the second user device v,
The matching server device B decrypts each U _{i, B} received from each user device ui with the secret key SK _B to obtain ANS _{i, B and} makes one direction to these (ANS _{1, B} ,..., ANS _{n, B} ). H _B = h (ANS _{1, B} , ANS _{2, B} ,..., ANS _{n, B} ) is calculated by applying a sex function, and this is used for the probabilistic homomorphic public key cryptography using the public key of the matching server device B make T _B by encrypting at sends it to the second user device v,
Second user device v generates a random number R _v, the public key of R _v a matching server device A, and each encrypted by the matching server device, respectively used in stochastic homomorphic public key encryption public key of B S _A , S _B, and if the answer of the device v is YES, V _A = T _A × S _A , V _B = T _B × S _B is calculated, and if NO, V _A = S _A , V _B = S _B and then, the V _a matching server device a, sends V _B to matching server device B, to calculate the h _v = h (R _v) further subjected to one-way function to the R _v, answer the h _v Published on the bulletin board device as a commitment to prevent non-repudiation,
The matching server device A decrypts V _A and the matching server device B decrypts V _B with the secret key, respectively, creates F _A and F _B , and publishes them on the public bulletin board device,
These F _A and F _B is first user equipment Different phases u1, ..., even without less to answer un has one YES, and is the answer of the second user device v is YES, it if they match An electronic matching method characterized in that it is determined to be other than the above. A plurality of first user devices u1, u2,..., One second user device v that can be distinguished from these, two matching server devices A and B, and any public bulletin board device can be referred to. With areas,
The first user device ui (i = 1,..., N) generates random numbers ANS _{i, A} and ANS _{i, B} having different values if the answer is YES, and the same value if NO.
The random numbers ANS _{i, A} and ANS _{i, B} are encrypted by probabilistic homomorphic public key encryption using the public keys PK _A and PK _B of the matching server devices A and B, respectively, and U _{i, A} , U _{i, B} Produces
Send these U _{i, A} , U _{i, B} to the public bulletin board device and publish them,
Generate different random numbers R _{i, A} , R _{i, B} ,
(ANS _{i, A} , R _{i, A} ) and (ANS _{i, B} , R _{i, B} ) are respectively subjected to a one-way function to obtain h _{i, A} = h (ANS _{i, A} , R _{i, A} ) and h _{i, B} = h (ANS _{i, B} , R _{i, B} )
These h _{i, A} , h _{i, B} are sent to the public bulletin board device as a commitment to prevent the repudiation of answers, and are released.
Second user device v is U ₁ from the public bulletin board _{system, A, ..., U n,} A, U 1, B, ..., acquires U _{n, B,}
T _A = U _{1, A} × U _{2, A} × ... × U _{n, A} , T _B = U _{1, B} × U _{2, B} × ... × U _{n, B}
Generate a random number R _v
Public key PK _A, and encrypted by stochastic homomorphic public key encryption and R _v using PK _B S _A, generates a S _B,
If the answer of the second user device v is _{YES V A = T A × S} A, calculates the _{V B = T B × S B} , If the answer is _{NO V A = S A, V} B = S B age,
V _A is sent to matching server device A and V _B is sent to matching server device B.
Applying a one-way function to R _v , h _v = h ( R _v )
h _v is sent to the public bulletin board device as a commitment to prevent non-repudiation of the answer,
The matching server device A decrypts the V _A received a secret key SK _A to generate F _A, sends this F _A to public bulletin board system,
Matching server device B decrypts the V _B received the secret key SK _B to generate F _B, sends this F _B to public bulletin board system,
F _A and F _B are different if the first user device u1, ..., one even without least answer un is YES, and and the answer of the second user device v is YES, the match F _A and F _B If so, an electronic matching method characterized in that it is determined to be other than that. Generate random numbers ANS _{i, A} and ANS _{i, B} of different values if the answer of the device is YES, or the same value if NO,
These random numbers ANS _{i, A} and ANS _{i, B} are sent to the matching server devices A and B in secret without leaking the ANS _{i, A} and ANS _{i, B} to a third party,
Generate different random numbers R _{i, A} , R _{i, B} ,
(ANS _{i, A} , R _{i, A} ) and (ANS _{i, B} , R _{i, B} ) are respectively subjected to a one-way function to obtain h _{i, A} = h (ANS _{i, A} , R _{i, A} ) and h _{i, B} = h (ANS _{i, B} , R _{i, B} ) is generated, and these h _{i, A} , h _{i, B} are transmitted to the public bulletin board apparatus as a commitment for preventing the denial of the answer and published. The processing method of the electronic matching user apparatus characterized by the above-mentioned. The first user device u1, ..., ciphertext from un U _{1, A,} ..., received U _{n, A,} respectively,
These ciphertext _{U 1, A, ..., U} n, decodes each _A ANS _{1, A,} ..., determine the ANS _{n, A,}
These are collectively subjected to a one-way function to generate h _A = h (ANS _{1, A} ,..., ANS _{n, A} ),
h _A is encrypted by probabilistic homomorphic public key cryptography using its own public key to generate T _A ,
T _A is sent to the second user device,
Receiving the ciphertext V _A from the second user device,
The matching server device for electronic matching, characterized in that the V _A is decrypted by probabilistic homomorphic public key encryption using the private key of the device itself, and the decrypted result F _A is transmitted to the public bulletin board device for publication. Processing method. Ciphertexts T _A and T _B encrypted by probabilistic homomorphic public key cryptography are received from matching server devices A and _B , respectively.
Generate a random number R _v
S _A and S _B are generated by encrypting with the probabilistic homomorphic public key encryption using the public keys PK _A and PK _B of the matching server devices A and B, respectively.
By performing a one-way function to the R _v generate a _{h v = h (R v)} ,
Send the h _v to the public bulletin board device and publish it,
If the answer of the device itself is YES calculates the _{V A = T A × S A} , V B = T B × S B, and _{V A = S A, V B} = S B If the answer is NO,
_A processing method for an electronic matching user device, wherein V _A and V _B are transmitted to matching server devices A and B, respectively. Generate random numbers ANS _{i, A} and ANS _{i, B} of different values if the answer of the device is YES, or the same value if NO,
Using the public keys PK _A and PK _B of the matching server devices A and B, ANS _{i, A} and ANS _{i, B} are respectively encrypted by probabilistic homomorphic public key cryptography to obtain U _{i, A} , U _{i, B.} Generate
Send these U _{i, A} , U _{i, B} to the public bulletin board device and publish them,
Generate different random numbers R _{i, A} , R _{i, B} ,
(ANS _{i, A} , R _{i, A} ) and (ANS _{i, B} , R _{i, B} ) are respectively subjected to a one-way function to obtain h _{i, A} = h (ANS _{i, A} , R _{i, A} ) and h _{i, B} = h (ANS _{i, B} , R _{i, B} )
_A processing method of an electronic matching user device, wherein h _{i, A} , h _{i, B} are transmitted to a public bulletin board device as a commitment for preventing rejection of an answer and are made public. Obtain ciphertexts U _{1, A} ,..., U _{n, A} , U _{1, B} ,..., U _{n, B} encrypted by probabilistic homomorphic public key cryptography from the public bulletin board apparatus,
T _A = U _{1, A} × U _{2, A} × ... × U _{n, A} , T _B = U _{1, B} × U _{2, B} × ... × U _{n, B}
Generate a random number R _v
Public key PK _A, and encrypted by stochastic homomorphic public key encryption and R _v using PK _B S _A, generates a S _B,
If the answer of the device itself v is a _{YES V A = T A × S} A, the _{V B = T B × S B} , to generate the _{V A = S A, V B} = S B if NO, the
V _A is sent to matching server device A and V _B is sent to matching server device B.
By applying a one-way function in R _v generate a _{h v = h (R v)} ,
A processing method for an electronic matching user device, wherein h _v is transmitted to a public bulletin board device as a commitment for preventing nonrepudiation of an answer and made public. The electronic matching user apparatus program for making a computer perform the method in any one of Claim 3, 5-7 . An electronic matching server program for causing a computer to execute the method according to claim 4 . A computer-readable recording medium in which the program according to claim 8 or 9 is recorded. Each device ui (i = 1,..., N) of the plurality of first user devices u1, u2,..., Un is a random number sequence ANS _{i, A} = {ANS corresponding to each of the m prices in the price list. _{i, 1, A} ,..., ANS _{i, m, A} } ANS _{i, B} = {ANS _{i, 1, B} ,..., ANS _{i, m, B} } is greater than or equal to the desired selling price s (1 < s < m). ANS _{i, j, A} ≠ ANS _{i, j, B} (s < j < m) and ANS _{i, j, A} = ANS _{i, j, B} (1 < j <s),
ANS _{i, A} is sent to matching server device A, and ANS _{i, B} is sent to matching server device B.
The matching server device A converts the received n random number sequences ANS _{i, A} into m random number sequences ANS _{j, A} = {ANS _{1, j, A} , ANS _{2, j, A} ,. _{n, j, A} }
_A one-way function is applied to each of these m random number sequences to generate h _{j, A} = h (ANS _{j, A} ),
Each h _j, encrypted by stochastic homomorphic encryption with the public key PK _A of the apparatus the _A T _j, generates _A,
Send that T _{j, A} to one second user device,
The matching server apparatus B converts the received n random number sequences ANS _{i, B} into m random number sequences ANS _{j, B} = {ANS _{1, j, B} , ANS _{2, j, B} ,. _{n, j, B} }
Each of these m random number sequences is subjected to a one-way function to generate h _{j, B} = h (ANS _{j, B} ),
T _{j, B} is generated by encrypting each h _{j, B} with the public key PK _B of its own device by probabilistic homomorphic encryption,
Send the T _{j, B} to the second user device,
The second user device generates m random numbers R _{j, v} ,
S _{j , A} , S _{j, B} are generated by encrypting R _{j, v} with the public keys PK _A , PK _B of the matching server devices A, B,
V _{j, A} = T _{j, A} × S _{j, A} , V _{j, B} = T _{j, B} × S _j, for price j (j < b) less than desired bid price b (1 < b < m) _B , V _{j, A} = S _{j, A} , V _{j, B} = S _{j, B} for a price j (j> b) greater than b,
V _{j, A} is sent to matching server device A, V _{j, B} is sent to matching server device B,
The matching server device A decrypts the received m V _{j, A} with its own secret key to obtain m F _{j, A} ,
The matching server device B decrypts the received m V _{j, B} with its own secret key to obtain m F _{j, B} ,
The matching server devices A and B sequentially release F _{j, A} and F _{j, B} in order from j = 1 _, and when F _{j, A} ≠ F _{j, B} , the matching server devices A and B are ANS for that j. _{i, j, A} and ANS _{i, j, B} are released in the order determined in advance for _i, and if ANS _{i, j, A} ≠ ANS _{i, j, B} , the first user device of i is the winner An electronic matching method characterized by that. Each device ui (i = 1,..., N) of the plurality of first user devices u1, u2,..., Un is a random number sequence ANS _{i, A} = {ANS corresponding to each of the m prices in the price list. _{i, 1, A} ,..., ANS _{i, m, A} } ANS _{i, B} = {ANS _{i, 1, B} ,..., ANS _{i, m, B} } is less than or equal to the desired bid price b (1 < b < m). ANS _{i, j, A} ≠ ANS _{i, j, B} (b > j > 1) and ANS _{i, j, A} = ANS _{i, j, B} (b < j < m),
ANS _{i, A} is sent to matching server device A, and ANS _{i, B} is sent to matching server device B.
The matching server device A converts the received n random number sequences ANS _{i, A} into m random number sequences ANS _{j, A} = {ANS _{1, j, A} , ANS _{2, j, A} ,. _{n, j, A} }
_A one-way function is applied to each of these m random number sequences to generate h _{j, A} = h (ANS _{j, A} ),
Each h _j, encrypted by stochastic homomorphic encryption with the public key PK _A of the apparatus the _A T _j, generates _A,
Send that T _{j, A} to one second user device,
The matching server apparatus B converts the received n random number sequences ANS _{i, B} into m random number sequences ANS _{j, B} = {ANS _{1, j, B} , ANS _{2, j, B} ,. _{n, j, B} }
Each of these m random number sequences is subjected to a one-way function to generate h _{j, B} = h (ANS _{j, B} ),
T _{j, B} is generated by encrypting each h _{j, B} with the public key PK _B of its own device by probabilistic homomorphic encryption,
Send the T _{j, B} to the second user device,
The second user device generates m random numbers R _{j, v} ,
S _{j, A} , S _{j, B} are generated by encrypting R _{j, v} with the public keys PK _A , PK _B of the matching server devices A, B,
V _{j, A} = T _{j, A} × S _{j, A} , V _{j, B} = T _{j, B} × S _j, for price j (j > s) greater than or equal to the desired bid price s (1 < s < m) _B is generated, and V _{j, A} = S _{j, A} and V _{j, B} = S _{j, B} are generated for a price j (j <s) smaller than s,
V _{j, A} is sent to matching server device A, V _{j, B} is sent to matching server device B,
The matching server device A decrypts the received m V _{j, A} with its own secret key to obtain m F _{j, A} ,
The matching server device B decrypts the received m V _{j, B} with its own secret key to obtain m F _{j, B} ,
The matching server devices A and B sequentially release F _{j, A} and F _{j, B} in order from j = m _, and when F _{j, A} ≠ F _{j, B} , the matching server devices A and B are ANS for that j. _{i, j, A} and ANS _{i, j, B} are released in the order determined in advance for _i, and if ANS _{i, j, A} ≠ ANS _{i, j, B} , the first user device of i is the winner An electronic matching method characterized by that.

Images