JP2004220248A - Multi-to-multi matching system, market server, terminal device, and computer program - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To match orders of a seller and a buyer while keeping information related to order price confidential and efficiently deliver valuable digital information between the matched seller and buyer while keeping the information confidential except the matched persons. <P>SOLUTION: A share generation server 5 generates a price information share corresponding to each market server 1-1 to 1-n. A terminal device 3b of the seller receives encrypted price information shares of all prices from the market servers 1-1 to 1-n, first and second divided seller information encryption keys, and a first divided buyer information decoding key, and transmits the price information share of a desired price and variable digital information encrypted with the seller information encryption key of the desired price to the market servers 1-1 to 1-n. The terminal device 3b of the seller further receives a second divided buyer information decoding key to decode the buyer information decoding key, and decodes the information broadcasted from the market server 1-1 to receive the matched valuable digital information. <P>COPYRIGHT: (C)2004,JPO&NCIPI

Description

をＸ^ｙ _ｚのように記述する。
１． 構成
図１は、この発明の一実施の形態による多対多マッチングシステムの構成を示すブロック図である。多対多マッチングシステムで交換される有価ディジタル情報としては電子株券、電子チケット、電子会員権、音楽あるいは動画などのディジタルコンテンツなどが考えられるが、以下では簡単のため，電子株券の売買の取引に眼定する。そしてここでは、ある１種類の電子株券を扱う市場Ｍが開かれているとする。
【００１９】
市場サーバ１は、市場Ｍのサーバであり、インターネットなどの公衆ネットワークであるネットワークＮあるいはＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）などのローカルネットワークを介してデータベース２−１及びデータベース２−２と接続される。また、ネットワークＮを介して、売り手Ｕ_Ｓの端末装置３ａ及び買い手Ｕ_Ｂの端末装置４ａと接続される。そして、売り手Ｕ_Ｓの端末装置３ａから希望価格を示す価格情報Ｘ及び電子株券ｄからなる売り注文情報Ｏ_Ｓを受信し、マッチした希望価格を示す価格情報Ｘを送信した買い手Ｕ_Ｂの電子マネーｍを復号するための買い手情報復号鍵を生成して売り手Ｕ_Ｓの端末装置３ａへ返送する機能と、売り手情報暗号鍵により暗号化された電子株券ｄをデータベース２−１に格納する機能を有する。また、買い手Ｕ_Ｂの端末装置４ａから希望価格を示す価格情報Ｘ及び電子マネーｍからなる買い注文情報Ｏ_Ｂを受信し、マッチした希望価格を示す価格情報Ｘを送信した売り手Ｕ_Ｓの電子株券ｄを復号するための売り手情報復号鍵を生成して買い手Ｕ_Ｂの端末装置４ａへ返送する機能と、買い手情報暗号鍵により暗号化された電子マネーｍをデータベース２−２に格納する機能を有する。さらに、データベース２−１及び２−２に格納されている暗号化された電子マネーｍ及び電子株券ｄを買い手Ｕ_Ｂの端末装置３ａ及び売り手Ｕ_Ｓの端末装置４ａへブロードキャストする機能を有する。
なお、本市場Ｍにおいて「マッチした」、すなわち、買い注文と売り注文がマッチングしていると判断するためのマッチングルールについては後述する。
【００２０】
データベース２−１及び２−２は、市場Ｍのデータベースであり、ネットワークＮあるいはプライベートネットワークを介して市場サーバ１と接続される。そして、データベース２−１は、暗号化された電子株券ｄを、データベース２−２は暗号化された電子マネーｍを記憶する。なお、データベース２−１及び２−２は、市場サーバ１に直接接続されるか、あるいは、市場サーバ１の内部に備えてもよい。
【００２１】
端末装置３ａは、売り手Ｕ_Ｓの保有するパーソナルコンピュータであり、ネットワークＮを介して市場サーバ１と接続される。そして、市場サーバ１に対して希望価格を示す価格情報Ｘ及び電子株券ｄからなる売り注文情報Ｏ_Ｓを送信する機能と、送信した売り注文情報Ｏ_Ｓに対応して市場サーバ１から受信した買い手情報復号鍵により、ブロードキャストされる暗号化された電子マネーｍを復号して、マッチした電子マネーｍを受け取る機能を有する。
【００２２】
端末装置４ａは、買い手Ｕ_Ｂの保有するパーソナルコンピュータであり、ネットワークＮを介して市場サーバ１と接続される。そして、市場サーバ１に対して希望価格を示す価格情報Ｘ及び電子マネーｍからなる買い注文情報Ｏ_Ｂを送信する機能と、送信した買い注文情報Ｏ_Ｂに対応して市場サーバ１から受信した売り手情報復号鍵により、ブロードキャストされる暗号化された電子株券ｄを復号して、マッチした電子株券ｄを受け取る機能を有する。
【００２３】
２． 市場モデル
ここでは、本実施の形態による多対多マッチングシステムの市場モデルを説明する。
市場には、ある同じ銘柄の電子株券をそれぞれの売買希望価格で売りたい複数の売り手Ｕ_Ｓと、ある同じ銘柄の電子株券をそれぞれの売買希望価格で購入したい複数の買い手Ｕ_Ｂが存在する。売り手Ｕ_Ｓと買い手Ｕ_Ｂをあわせて注文者と呼ぶ。そして、売り注文情報Ｏ_Ｓと買い注文情報Ｏ_Ｂのマッチングを行うセンタである市場Ｍが存在する。市場Ｍは、以下に示す一般的な市場で用いられているマッチングルールに基づいて売り注文情報Ｏ_Ｓと買い注文情報Ｏ_Ｂのマッチングを行う。（１）同じ希望価格の売り注文情報Ｏ_Ｓと買い注文情報Ｏ_Ｂをマッチングする。
（２）２つ以上の同じ希望価格の売り注文情報Ｏ_Ｓ、あるいは、同じ希望価格の買い注文情報Ｏ_Ｂが存在する場合、先に市場に届いた注文を優先する。
【００２４】
本発明のマッチングに必要な性質を以下に挙げる。
データ交換の正当性：
売り手Ｕ_Ｓの売り注文情報Ｏ_Ｓと，買い手Ｕ_Ｂの買い注文情報Ｏ_Ｂがマッチした場合、売り手Ｕ_Ｓは買い注文情報Ｏ_Ｂに含まれる電子マネーｍを受け取り、買い手Ｕ_Ｂは売り注文情報Ｏ_Ｓに含まれる電子株券ｄを受け取る。
データの秘匿性：
市場Ｍは、全ての電子マネーｍと電子株券ｄを所有することはできない。また、全ての売り手Ｕ_Ｓは、マッチした買い注文情報Ｏ_Ｂに含まれる電子マネーｍ以外の電子マネーｍを得ることは出来ない。そして、全ての買い手Ｕ_Ｂは、マッチした売り注文情報Ｏ_Ｓに含まれる電子株券ｄ以外の電子株券ｄを得ることができない。
希望価格の秘匿性：
全ての注文者及び市場Ｍは、全ての買い注文情報Ｏ_Ｂ及び売り注文情報Ｏ_Ｓ（以下、単に注文と記述）の希望価格と、希望価格毎の注文数を知ることができない。
匿名性：
全ての注文者及び市場Ｍは、マッチした電子マネーｍ、電子株券ｄを誰が受け取ったかを知ることができない。
堅牢性：
市場Ｍは、注文者から不正な注文が送信された場合に対する堅牢性を持っている。すなわち、市場Ｍは、不正な動作をした注文者や、不正な注文を拒絶することができる。
【００２５】
３． 基本的な暗号ツール
ここでは本実施の形態において利用する基本的な暗号ツールについて説明する。
３．１ 紛失通信
紛失通信（Ｍａｔｃｈｉｎｇ Ｏｂｌｉｖｉｏｕｓ Ｔｒａｎｓｆｅｒ：ＯＴ）は，送信者が受信者へ複数のメッセージを送った場合、受信者は送信者が送信したメッセージのうちの１つのみを受信し、送信者は受信者がどのメッセージを受信したかを知ることができないという２者間のプロトコルである。特に、（１，Ｎ）−ＯＴは、送信者がＮ個のメッセージ｛Ｄ_１， Ｄ_２，…， Ｄ_Ｎ｝を受信者へ送信した場合、受信者は受信するメッセージのインデックスｉ∈｛１， ２，．．．．， Ｎ｝から任意のｉを選ぶと、結果としてＤ_ｉのみを受け取るが、その他のメッセージについては何も得ず、また、送信者は受信者が受け取ったｉについて知り得ないという通信である。
【００２６】
３．２ 検証可能な秘密分散
秘密分散（Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ：ＳＳ）とは、ディーラが持つ秘密情報ｓをｎ個のシェアに分割して各シェアをｎ人のプレーヤーに配布し、各プレーヤーは、ある定められた数以上のプレーヤーのシェアを合わせることによって元の秘密情報ｓを復元することができるが、自分に配られたシェアからは秘密を知ることができないように分散符号化する暗号方式である。特に、（ｔ，ｎ）しきい値ＳＳにおいては、ｔ−１人以下のプレーヤーのシェアを合わせることでは秘密情報ｓを復元することができないが、ｔ人以上のプレーヤーのシェアを合わせることにより秘密情報ｓを復元することができる。
一方、検証可能な秘密分散（Ｖｅｒｉｆｉａｂｌｅ Ｓｅｃｒｅｔ Ｓｈａｒｉｎｇ：ＶＳＳ）とは、各プレーヤーが、自分に配付されたシェアが秘密情報ｓから正しく計算されていることを検証できるＳＳである。
また、多くのＳＳは準同型性を持っている。すなわち、秘密情報ｓ_１をｎ個のシェア｛Ｓ_１，１，Ｓ_１，２，．．．，Ｓ_１，ｎ｝に、秘密情報ｓ_２をｎ個のシェア｛Ｓ_２，１，Ｓ_２，２，．．．，Ｓ_２，ｎ｝に分散し、ｉ番目のプレーヤーがＳ_１，ｉ及びＳ_２，ｉを受け取る場合、秘密情報ｓ_１とｓ_２の和であるｓ_１＋ｓ_２は、各プレーヤーの持つＳ_１，ｉ＋Ｓ_２，ｉを合わせた｛Ｓ_１，１＋Ｓ_２，１，Ｓ_１，２＋Ｓ_２，２，．．．．，Ｓ_１，ｎ＋Ｓ_２，ｎ｝から復元することができる。
【００２７】
４． 多対多マッチングシステムの動作
４．１ システムプロトコル
ここでは、図１に示す多対多マッチングシステムに適用される多対多マッチングシステムのシステムプロトコルを説明する。
市場Ｍにおける電子株券の価格ｉは１≦ｉ≦ｌの範囲内にあるとする。そして、市場サーバ１は、価格ｉ（１≦ｉ≦ｌ）に対応する売りカウンタＣ^（Ｓ） _ｉ、買いカウンタＣ^（Ｂ） _ｉを保有する。なお、売りカウンタＣ^（Ｓ） _ｉ及び買いカウンタＣ^（Ｂ） _ｉの初期値は乱数であるが、同じ価格ｉに対しては同じ初期値をとる。
そして、市場サーバ１は、価格ｉの売りカウンタＣ^（Ｓ） _ｉの現在の値ｃから公開鍵及び秘密鍵を算出する。そして、算出された公開鍵は、電子株券ｄを暗号化するための売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃとして使用される。また、秘密鍵は、この売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃにより暗号化された電子株券ｄを復号するための売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃとして使用される。
同様に、市場サーバ１は、価格ｉの買いカウンタＣ^（Ｂ） _ｉの現在の値ｃから公開鍵及び秘密鍵を算出する。そして、算出された公開鍵は、電子マネーｍを暗号化するための買い手情報暗号鍵ＰＫ^（Ｂ） _ｉ，ｃとして使用される。また、秘密鍵は、この買い手情報暗号鍵ＰＫ^（Ｂ） _ｉ，ｃにより暗号化された電子マネーｍを復号するための買い手情報復号鍵ＳＫ^（Ｂ） _ｉ，ｃとして使用される。
すなわち、売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃ及び売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃ、ならびに、買い手情報暗号鍵ＰＫ^（Ｂ） _ｉ，ｃ及び買い手情報復号鍵ＳＫ^（Ｂ） _ｉ，ｃは、売り注文または買い注文別に売りカウンタＣ^（Ｓ） _ｉあるいは買いカウンタＣ^（Ｂ） _ｉの現在の値ｃにより一意に算出される。そして、ある売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃまたは買い手情報復号鍵ＳＫ^（Ｂ） _ｉ，ｃから、他の売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃや買い手情報復号鍵ＳＫ^（Ｂ） _ｉ，ｃが類推できてはいけない。このような鍵は公開鍵暗号方式の一種であるＥｌＧａｍａｌ（エルガマル）暗号方式に利用できる形式として、以下のように生成することができる。
【数２】

上記において、ｇ、ｒ及びαは、公開値であり、ｐ及びｑは、ｐ−１｜ｑＬ（Ｌ≧２ｌ）を満たす大きな素数である。なお、「｜」は、整除関係を示し、（ｐ−１）がｑＬを割り切ることを示す。また、αはｍｏｄ ｐ（ｐの剰余）上のＬ乗根、ｒはｍｏｄ ｐ上の位数がｑとなる群上の乱数、ｇは位数ｐとなる群の生成元である。なお、位数ｑとは、群においてｑ乗すると１になるような元の個数である。また、生成元とは、群のすべての元がその値のべき乗で表現されるような数である。
【００２８】
また、売りカウンタＣ^（Ｓ） _ｉ及び買いカウンタＣ^（Ｂ） _ｉは、価格ｉに対応した乱数ｒ_ｉを用いて、以下のように算出される。
【数３】

売り手Ｕ_Ｓの端末装置３ａは、希望価格Ｐ_Ｓの売り注文情報Ｏ_Ｓを出したとき、後述する売り注文サブプロトコルの結果、希望価格Ｐ_Ｓの
【数４】

（以下、「売りカウンタＣ^（Ｓ） _ＰＳ」と記述）の現在の値ｃに対応した
【数５】

（以下、「買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃ」と記述）を受け取る。そして、売り手Ｕ_Ｓの端末装置３ａは、希望価格Ｐ_Ｓの
【数６】

により暗号化された電子マネーｍが後述するブロードキャストサブプロトコルで市場サーバ１からブロードキャストされると、買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃを用いて復号し、マッチした電子マネーｍを受け取ることができる。同様に、買い手Ｕ_Ｂの端末装置４ａが希望価格Ｐ_Ｂの買い注文情報Ｏ_Ｂを出したときは、後述する買い注文サブプロトコルの結果、希望価格Ｐ_Ｂの
【数７】

（以下、「買いカウンタＣ^（Ｂ） _ＰＢ」と記述）の現在の値ｃに対応した
【数８】

（以下、「売り手情報復号鍵ＳＫ^（Ｓ） _ＰＢ，ｃ」と記述）を受け取る。そして、買い手Ｕ_Ｂの端末装置４ａは、希望価格Ｐ_Ｂの
【数９】

により暗号化された電子株券ｄが後述するブロードキャストサブプロトコルで市場サーバ１からブロードキャストされると、売り手情報復号鍵ＳＫ^（Ｓ） _ＰＢ，ｃを用いて復号し、マッチした電子株券ｄを受け取ることができる。
【００２９】
４．２ 基本プロトコル
ここでは、市場Ｍが信頼できる機関である、すなわち市場サーバ１に信頼性があり、全てのプライベートな情報が公開されず、改ざん等がないと仮定したプロトコルを考える。
（１）セットアップ
まず、市場Ｍのセットアップの手順について説明する。図２は、市場Ｍのセットアップの手順を示す図である。
市場サーバ１は、市場Ｍが開かれる前に、自身の保有する全ての買いカウンタＣ^（Ｂ） _ｉ及び売りカウンタＣ^（Ｓ） _ｉを同じ価格ｉに対して同値になるように初期化する。すなわち、市場サーバ１は全価格ｉ（１≦ｉ≦ｌ）に対する乱数ｒ_ｉを生成し、以下の式によりカウンタをセットする。
【数１０】

図２においては、価格１に対する売りカウンタＣ^（Ｓ） _１及び買いカウンタＣ^（Ｂ） _１は乱数ｒ_１の値「０２６３」に、価格２に対する売りカウンタＣ^（Ｓ） _２及び買いカウンタＣ^（Ｂ） _２は乱数ｒ_２の値「０４２８」に、価格ｉに対する売りカウンタＣ^（Ｓ） _ｉ及び買いカウンタＣ^（Ｂ） _ｉは乱数ｒ_ｉの値「８７４２」に、価格ｌ−１に対する売りカウンタＣ^（Ｓ） _ｌ−１及び買いカウンタＣ^（Ｂ） _ｌ−１は、乱数ｒ_ｌ−１の値「１３２７」に、そして、価格ｌに対する売りカウンタＣ^（Ｓ） _ｌ及び買いカウンタＣ^（Ｂ） _ｌは、乱数ｒ_ｌの値「２５８２」に初期化されることを示している。さらに、市場サーバ１は、データベース２−１及びデータベース２−２の内容を初期化する。
【００３０】
（２）売り注文サプブロトコル
ここでは、売り手Ｕ_Ｓの端末装置３ａから売り注文情報Ｏ_Ｓを受信する売り注文サブプロトコルの手順について説明する。図３は、売り注文サブプロトコルの手順を示す図である。
ステップＳ１１０：
売り手Ｕ_Ｓの端末装置３ａは、希望価格がＰ_Ｓである電子株券ｄの売り注文情報Ｏ_Ｓを市場Ｍに送信する。すなわち、売り手Ｕ_Ｓの端末装置３ａは、希望価格Ｐ_Ｓを示す
【数１１】

（以下、「価格情報Ｘ^（ＰＳ）」と記述）を生成する。価格ｉを示す価格情報Ｘ^（ｉ）は、各価格を示す要素Ｘ^（ｉ） _ｋ（１≦ｋ≦ｌ）の集合｛Ｘ^（ｉ） _１，Ｘ^（ｉ） _２，．．．，Ｘ^（ｉ） _ｌ｝からなり、ｋ＝ｉである要素Ｘ^（ｉ） _ｋにのみ「１」が設定され、ｋ＝ｉ以外の要素Ｘ^（ｉ） _ｋには「０」は設定される。従って、希望価格Ｐ_Ｓを示す価格情報Ｘ^（ＰＳ）は、以下のように生成される。
【数１２】

そして、端末装置３ａは価格情報Ｘ^（ＰＳ）と電子株券ｄからなる売り注文情報Ｏ_Ｓを市場サーバ１に送信する。
【００３１】
ステップＳ１２０：
市場サーバ１は売り手Ｕ_Ｓの端末装置３ａから受信した売り注文情報Ｏ_Ｓの正当性を検証する。すなわち、市場サーバ１は、価格情報Ｘ^（ＰＳ）内の
【数１３】

の中で、１つだけに「１」が設定されており、その他は全て「０」が設定されていることを検証する。そして、「１」が設定されている
【数１４】

により、売り手Ｕ_Ｓの希望価格Ｐ_Ｓを得る。
【００３２】
ステップＳ１３０、ステップＳ１３５：
市場サーバ１は、売り手Ｕ_Ｓの希望価格Ｐ_Ｓに対応した売りカウンタＣ^（Ｓ） _ＰＳの現在の値ｃから、電子株券ｄを暗号化するための
【数１５】

（以下、「売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃ」と記述）と（ステップＳ１３０）、マッチする電子マネーｍを復号するための買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃと（ステップＳ１３５）を（数２）により作成する。
【００３３】
ステップＳ１４０：
市場サーバ１は、電子株券ｄを売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃにより暗号化する。
【数１６】

なお、左辺ＥＥは、電子株券ｄを売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃを用いて暗号化した結果を示す。市場サーバ１は、暗号化された電子株券ＥＥをデータベース２−１に格納する。
【００３４】
ステップＳ１５０：
市場サーバ１は、ステップＳ１３５において作成した買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃを売り手Ｕ_Ｓの端末装置３ａに送信する。
【００３５】
ステップＳ１６０：
市場サーバ１は、希望価格Ｐ_Ｓに対応する売りカウンタＣ^（Ｓ） _ＰＳの値を更新する。すなわち、下記の式を実行することで、希望価格Ｐ_Ｓに対応する価格ｉの売りカウンタＣ^（Ｓ） _ｉのみが更新され、希望価格Ｐ_Ｓとは異なる価格ｉの売りカウンタＣ^（Ｓ） _ｉはそのままの値を維持する。なお、乱数ｒ_ｉは、セットアップ時の売りカウンタＣ^（Ｓ） _ｉの初期化に使用した乱数ｒ_ｉと同一である。
【数１７】

【００３６】
（３）買い注文サブプロトコル
次に、買い手Ｕ_Ｂの端末装置４ａから買い注文情報Ｏ_Ｂを受信する買い注文サブプロトコルの手順について説明する。
ステップＳ２１０：
買い手Ｕ_Ｂはの端末装置４ａ、希望価格がＰ_Ｂである電子株券ｄの買い注文情報Ｏ_Ｂを市場Ｍに送信する。すなわち、買い手Ｕ_Ｂの端末装置４ａは、希望価格Ｐ_Ｂを示す
【数１８】

（以下、「価格情報Ｘ^（ＰＢ）」と記述）を以下のように設定する。
【数１９】

そして、端末装置４ａは価格情報Ｘ^（ＰＢ）と電子マネーｍからなる買い注文情報Ｏ_Ｂを市場サーバ１に送信する。
【００３７】
ステップＳ２２０：
市場サーバ１は受信した買い注文情報Ｏ_Ｂの正当性を検証する。すなわち、まず、市場サーバ１は、電子マネーｍの額面と価格情報Ｘ^（ＰＢ）の希望価格Ｐ_Ｂの整合性を検証する。さらに、価格情報Ｘ^（ＰＢ）の正当性を売り注文サブプロトコルと同様の方法（ステップＳ１２０）により検証する。
【００３８】
ステップＳ２３０、ステップＳ２３５：
市場サーバ１は、買い手Ｕ_Ｂの希望価格Ｐ_Ｂに対応した買いカウンタＣ^（Ｂ） _ＰＢの現在の値ｃから、電子マネーｍを暗号化するための
【数２０】

（以下、「買い手情報暗号鍵ＰＫ^（Ｂ） _ＰＢ，ｃ」と記述）と（ステップＳ２３０）、マッチする電子株券ｄを復号するための売り手情報復号鍵ＳＫ^（Ｓ） _ＰＢ，ｃと（ステップＳ２３５）を（数２）により作成する。
【００３９】
ステップＳ２４０：
市場サーバ１は、電子マネーｍを買い手情報暗号鍵ＰＫ^（Ｂ） _ＰＢ，ｃにより暗号化する。
【数２１】

ここで、左辺ＥＰは、電子マネーｍを買い手情報暗号鍵ＰＫ^（Ｂ） _ＰＢ，ｃを用いて暗号化した結果を示す。市場サーバ１は、暗号化された電子マネーＥＰをデータベース２−２に格納する。
【００４０】
ステップＳ２５０：
市場サーバ１は、ステップＳ２３５において作成した売り手情報復号鍵ＳＫ^（Ｓ） _ＰＢ，ｃを買い手Ｕ_Ｂの端末装置４ａに送信する。
【００４１】
ステップＳ２６０：
市場サーバ１は、希望価格Ｐ_Ｂに対応する買いカウンタＣ^（Ｂ） _ＰＢの値を更新する。すなわち、下記の式を実行することで、希望価格Ｐ_Ｂに対応する価格ｉの買いカウンタＣ^（Ｂ） _ｉのみが更新され、希望価格Ｐ_Ｂとは異なる価格ｉの買いカウンタＣ^（Ｂ） _ｉはそのままの値を維持する。なお、乱数ｒ_ｉは、セットアップ時の買いカウンタＣ^（Ｂ） _ｉの初期化に使用した乱数ｒ_ｉと同一である。
【数２２】

【００４２】
（４）ブロードキャストサブプロトコル
次に、市場サーバ１が売り手Ｕ_Ｓの端末装置３ａ及び買い手Ｕ_Ｂの端末装置４ａへ暗号化された電子株券ＥＥと暗号化された電子マネーＥＰをブロードキャストするブロードキャストサブプロトコルの手順について説明する。図４は、ブロードキャストサブプロトコルの手順を示す図である。なお、ブロードキャストはある一定時間毎に実行される。
ステップＳ３１０：
市場サーバ１はデータベース２−１に記憶されている暗号化された電子株券ＥＥと、データベース２−２に記憶されている暗号化された電子マネーＥＰを読み出し、全売り手Ｕ_Ｓの端末装置３ａ及び買い手Ｕ_Ｂの端末装置４ａにブロードキャストする。
【００４３】
ステップＳ３２０：
売り手Ｕ_Ｓの端末装置３ａは、市場サーバ１から受信した全ての暗号化された電子マネーＥＰを図３のステップＳ１５０において配布された買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃを用いて復号し、得られた電子マネーｍの正当性を検証する。すなわち、正しく復号されるマッチした電子マネーｍがあれば、売り手Ｕ_Ｓはその電子マネーｍを受け取る。
【００４４】
ステップＳ３２５：
同様に、買い手Ｕ_Ｂの端末装置４ａは、市場サーバ１から受信した全ての暗号化された電子株券ＥＥを（２）のステップＳ２５０において配布された売り手情報復号鍵ＳＫ^（Ｓ） _ＰＢ，ｃを用いて復号し、得られた電子株券ｄの正当性を検証する。すなわち、正しく復号されるマッチした電子株券ｄがあれば、買い手Ｕ_Ｂはその電子株券ｄを受け取る。
【００４５】
ここで、それぞれの買い手Ｕ_Ｂの端末装置４ａへ配布された売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃはすべて異なるので、全ての暗号化された電子株券ＥＥについて以下が成り立つ。
【数２３】

なお、左辺は暗号化された電子株券ＥＥを売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃにより復号した情報を示す。すなわち、売り手情報復号鍵ＳＫ^（Ｓ） _ｉ，ｃを持つ買い手Ｕ_Ｂはマッチした電子株券ｄのみを受け取ることができる。
もし、買い手Ｕ_Ｂの買い注文情報Ｏ_Ｂにマッチする暗号化された電子株券ＥＥがブロードキャスト時点において存在しないとしても、将来マッチする暗号化された電子株券ＥＥがデータベース２−１に格納された場合、今後のブロードキャストにおいてマッチした電子株券ｄを得ることができる。
また、売り手Ｕ_Ｓの端末装置３ａにおいて、売り注文情報Ｏ_Ｓにマッチする電子マネーｍを受け取る場合についても同様である。
【００４６】
５． 市場サーバを分散させた多対多マッチングシステム
価格の秘匿性は、市場サーバ１の機能をｎ台のサーバ、すなわち市場サーバ１−１〜１−ｎに分散させることによって実現できる。ここではｎ台の市場サーバ１−１〜１−ｎのうち、ｔ−１（ｎ＝２ｔ）台までの不正に耐えるプロトコルについて、基本プロトコルからの変更点を示す。
図５は、市場サーバを分散させた多対多マッチングシステムの構成を示すブロック図である。なお、この図において、図１と同一部分には同一の符号が付してある。
市場サーバ１を分散させた形態の場合、売り手Ｕ_Ｓの端末装置３ｂ及び買い手Ｕ_Ｂの端末装置４ｂは、ＶＳＳを用いて希望価格Ｐ_Ｓ及び希望価格Ｐ_Ｂを市場サーバ１−１〜１−ｎに分散する。さらに、市場サーバ１−１〜１−ｎは、売りカウンタＣ^（Ｓ） _ｉ及び買いカウンタＣ^（Ｂ） _ｉ（以下、単にカウンタと記述）の値を単独では知りえないようにＶＳＳを用いて秘密分散し、カウンタに対する全ての操作は、準同型性を持った（ｔ，ｎ）しきい値ＶＳＳを用いて行う。また、（１，ｌ）−ＯＴプロトコルを使用し、売り手と買い手のプライバシを守りながら、適切な鍵のみを配信する。
そして、本実施の形態においては、売り手Ｕ_Ｓの端末装置３ｂ及び買い手Ｕ_Ｂの端末装置４ｂが不正な注文を送信すること、ならびに、市場サーバ１−１〜１−ｎが希望価格Ｐ_Ｓ及び希望価格Ｐ_Ｂを知ることを防ぐために、秘密分散された価格情報を生成するシェア生成サーバ５を想定する。ただし、シェア生成サーバ５は、売り手Ｕ_Ｓ及び買い手Ｕ_Ｂの情報を一切操作しない。
【００４７】
５．１ 構成
シェア生成サーバ５は、ネットワークＮあるいはローカルネットワークを介して市場サーバ１−１〜１−ｎと接続される。そして、各市場サーバ１−１〜１−ｎに対応する秘密分散された価格情報Ｘのシェアを価格毎に生成し、それぞれに自身の電子署名を付与した上、売り手Ｕ_Ｓまたは買い手Ｕ_Ｂの公開鍵を用いて暗号化して各市場サーバ１−１〜１−ｎへ送信する機能を有する。また、各市場サーバ１−１〜１−ｎが売り手Ｕ_Ｓの端末装置３ｂ又は買い手Ｕ_Ｂの端末装置４ｂから受信する価格情報Ｘのシェアが正当であることを、価格を秘匿したまま確認するための正当性確認データを価格情報Ｘのシェアから生成し、各市場サーバ１−１〜１−ｎへ送信する機能を有する。
【００４８】
市場サーバ１−１〜１−ｎは、市場Ｍのサーバであり、ネットワークＮあるいはローカルネットワークを介して他の市場サーバ１−１〜１−ｎ、データベース２−１及びデータベース２−２、シェア生成サーバ５と接続される。また、ネットワークＮを介して、売り手Ｕ_Ｓの端末装置３ｂ及び買い手Ｕ_Ｂの端末装置４ｂと接続される。
市場サーバ１−１〜１−ｎは、売り手Ｕ_Ｓの端末装置３ｂまたは売り手Ｕ_Ｂの端末装置４ｂから、注文を行うための情報の要求を受け、他の市場サーバ１−１〜１−ｎ及びシェア生成サーバ５へ通知する機能を有する。また、売り手Ｕ_Ｓまたは買い手Ｕ_Ｂの公開鍵により暗号化された価格情報Ｘのシェアと、正当性確認データとをシェア生成サーバ５から受信し、内部に記憶する機能を有する。
さらに、ｎ台の市場サーバ１−１〜１−ｎのうち、２台の市場サーバとｔ−２台の市場サーバとにより、それぞれ、売り手情報暗号鍵を分割した第１の分割売り手情報暗号鍵及び第２の分割売り手情報暗号鍵を生成し、売り手Ｕ_Ｓの公開鍵で暗号化する機能と、ｎ台の市場サーバ１−１〜１−ｎにより買い手情報復号鍵を分割した第１の分割買い手情報復号鍵及び第２の分割買い手情報復号鍵を生成し、売り手Ｕ_Ｓの公開鍵で暗号化する機能とを有する。また、（１，ｌ）−ＯＴにより、全価格に対応する売り手Ｕ_Ｓの公開鍵により暗号化された価格情報Ｘのシェアと、第１及び第２の分割売り手情報暗号鍵と、第１の分割買い手情報復号鍵とを送信する機能を有する。そして、希望価格を示す価格情報Ｘのシェア及び暗号化された電子株券ｄを買い手Ｕ_Ｓの端末装置３ｂから受信し、シェア生成サーバ５の電子署名及びシェア生成サーバ５から受信した正当性確認データにより価格情報Ｘのシェアの正当性を確認する機能と、正当性が確認された場合に、暗号化された電子株券ｄをデータベース２−１へ書き込むとともに、売り手Ｕ_Ｓの公開鍵で暗号化された第２の分割買い手情報復号鍵を（１，ｌ）−ＯＴにより送信する機能を有する。
同様に、ｎ台の市場サーバ１−１〜１−ｎのうち、２台の市場サーバとｔ−２台の市場サーバとにより、それぞれ、買い手情報暗号鍵を分割した第１の分割買い手情報暗号鍵及び第２の分割買い手情報暗号鍵を生成し、買い手Ｕ_Ｂの公開鍵で暗号化する機能と、ｎ台の市場サーバ１−１〜１−ｎにより売り手情報復号鍵を分割した第１の分割売り手情報復号鍵及び第２の分割売り手情報復号鍵を生成し、買い手Ｕ_Ｂの公開鍵で暗号化する機能とを有する。また、（１，ｌ）−ＯＴにより、全価格に対応する買い手Ｕ_Ｂの公開鍵により暗号化された価格情報Ｘのシェアと、第１及び第２の分割買い手情報暗号鍵と、第１の分割売り手情報復号鍵とを送信する機能を有する。そして、希望価格を示す価格情報Ｘのシェア及び暗号化された電子マネーｍを売り手Ｕ_Ｂの端末装置４ｂから受信し、シェア生成サーバ５の電子署名及びシェア生成サーバ５から受信した正当性確認データにより価格情報Ｘのシェアの正当性を確認する機能と、正当性が確認された場合に、暗号化された電子マネーｍをデータベース２−２へ書き込むとともに、買い手Ｕ_Ｂの公開鍵で暗号化された第２の分割売り手情報復号鍵を（１，ｌ）−ＯＴにより送信する機能を有する。
加えて、データベース２−１及び２−２に格納されている暗号化された電子マネーｍ及び電子株券ｄを買い手Ｕ_Ｂの端末装置３ｂ及び売り手Ｕ_Ｓの端末装置４ｂへブロードキャストする機能とを有する。
【００４９】
データベース２−１及び２−２は、市場サーバ１−１〜１−ｎと接続され、図１におけるデータベース２−１及び２−２と同様の機能を有する。
【００５０】
端末装置３ｂは、売り手Ｕ_Ｓの保有するパーソナルコンピュータであり、ネットワークＮを介して市場サーバ１−１〜１−ｎと接続される。端末装置３ｂは、市場サーバ１−１〜１−ｎから、（１，ｌ）−ＯＴにより自身の公開鍵で暗号化された全価格に対応する価格情報Ｘのシェアと、第１及び第２の分割売り手情報暗号鍵と、第１の分割買い手情報復号鍵とを受信し、希望価格に対応した情報を選択して復号する機能を有する。また、希望価格に対応する第１の分割売り手情報暗号鍵及び第２の分割売り手情報暗号鍵から売り手情報暗号鍵を復元し、この売り手情報暗号鍵により暗号化した電子株券ｄと、希望価格に対応する価格情報Ｘのシェアとを市場サーバ１−１〜１−ｎへ送信する機能を有する。さらに、市場サーバ１−１〜１−ｎから、（１，ｌ）−ＯＴにより自身の公開鍵で暗号化された全価格に対応する第２の分割買い手情報復号鍵を受信し、希望価格に対応した第２の分割買い手情報復号鍵を選択して復号し、第１及び第２の分割買い手情報復号鍵から希望価格に対応する買い手情報復号鍵を復元する機能を有する。そして、市場サーバ１−１〜１−ｎからブロードキャストされる暗号化された買い手Ｕ_Ｂの電子マネーｍを復元した買い手情報復号鍵により復号し、マッチする電子マネーｍを受け取る機能を有する。
【００５１】
端末装置４ｂは、買い手Ｕ_Ｂの保有するパーソナルコンピュータであり、ネットワークＮを介して市場サーバ１−１〜１−ｎと接続される。端末装置４ｂは、市場サーバ１−１〜１−ｎから、（１，ｌ）−ＯＴにより自身の公開鍵で暗号化された全価格に対応する価格情報Ｘのシェアと、第１及び第２の分割買い手情報暗号鍵と、第１の分割売り手情報復号鍵とを受信し、希望価格に対応した情報を選択して復号する機能を有する。また、希望価格に対応する第１の分割買い手情報暗号鍵及び第２の分割買い手情報暗号鍵から買い手情報暗号鍵を復元し、この買い手情報暗号鍵により暗号化した電子マネーｍと、希望価格に対応する価格情報Ｘのシェアとを市場サーバ１−１〜１−ｎへ送信する機能を有する。さらに、市場サーバ１−１〜１−ｎから、（１，ｌ）−ＯＴにより自身の公開鍵で暗号化された全価格に対応する第２の分割売り手情報復号鍵を受信し、希望価格に対応した第２の分割売り手情報復号鍵を選択して復号し、第１及び第２の分割売り手情報復号鍵から希望価格に対応する売り手情報復号鍵を復元する機能を有する。そして、市場サーバ１−１〜１−ｎからブロードキャストされる暗号化された売り手Ｕ_Ｓの電子株券ｄを復元した売り手情報復号鍵により復号し、マッチする電子株券ｄを受け取る機能を有する。
【００５２】
５．２ 市場サーバを分散させた多対多マッチングシステムの動作
（１）セットアップ
各々の市場サーバ１−１〜１−ｎは、ＶＳＳにより秘密分散された売りカウンタＣ^（Ｓ） _ｉ及び買いカウンタＣ^（Ｂ） _ｉ（１≦ｉ≦ｌ）を記憶している。そして、カウンタの初期化において、各市場サーバ１−１〜１−ｎは、共同で全価格ｉ（１≦ｉ≦ｌ）に対する乱数ｒ_ｉを生成し、（数１０）に示す初期化を行う。
なお、全ての買いカウンタＣ^（Ｂ） _ｉ及び売りカウンタＣ^（Ｓ） _ｉは、市場サーバ１−１〜１−ｎ間で常に分散され、市場サーバ１−１〜１−ｎのうちｔ台以下の結託では元のカウンタ値を知ることはできない。乱数ｒ_ｉもまた、全ての市場サーバ１−１〜１−ｎ間で分散される。
【００５３】
（２）売り注文サブプロトコル
図６は、市場サーバを分散させた多対多マッチングシステムにおける売り注文サブプロトコルの手順を示す。
ステップＳ５１０：
売り手Ｕ_Ｓの端末装置３ｂは、売り注文を行うための情報を市場サーバ１−１〜１−ｎの何れかに要求し、要求を受信した何れかの市場サーバ１−１〜１−ｎは、残りの市場サーバ１−１〜１−ｎ及びシェア生成サーバ５へこの要求を転送する。あるいは、売り手Ｕ_Ｓの端末装置３ｂは、売り注文を行うための情報をシェア生成サーバ５に要求し、シェア生成サーバ５が、市場サーバ１−１〜１−ｎへ要求を転送してもよい。
【００５４】
ステップＳ５１５：
全ての市場サーバ１−１〜１−ｎが売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃを知りえないように生成するため、市場サーバ１−１〜１−ｎは、２台の市場サーバと（ｔ−２）台の市場サーバにより、売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃを第１の分割売り手情報暗号鍵と、第２の分割売り手情報暗号鍵とに分割して生成する。
市場サーバ１−１〜１−ｎが秘密分散して保有する価格ｉの売りカウンタＣ^（Ｓ） _ｉの現在の値をｃ_ｉ（以下、「売りカウンタの現在値ｃ_ｉ」と記述）、ｊ番目の市場サーバ１−ｊが保有する売りカウンタの現在値ｃ_ｉのシェアをｃ_ｉ，ｊ（以下、「売りカウンタの現在値のシェアｃ_ｉ，ｊ」と記述）とする。４．１節の（数２）に示すように、売り手情報暗号鍵ＰＫ^（Ｓ） _ｉ，ｃは、
【数２４】

に等しい。一方、
【数２５】

が成り立つ。なお、λｊは秘密分散の復元に使用されるラグランジェの補間係数である。従って、
【数２６】

が成り立つ。
そこで、市場サーバ１−１〜１−ｎのうち、ｔ台の市場サーバ（ここでは、市場サーバ１−ｊ（１≦ｊ≦ｔ）とする）の各々は、全価格ｉ（１≦ｉ≦ｌ）についてセットアップにおいて生成した乱数ｒ_ｉから、各売りカウンタの現在値のシェアｃ_ｉ，ｊに対する
【数２７】

をローカルに算出する。そして、このうち、２台の市場サーバ（ここでは、市場サーバ１−１及び１−２とする）は共同で、
【数２８】

を算出する。そして、算出された第１の分割売り手情報暗号鍵ＰＫ^{（Ｓ），（１）} _ｉ，ｃを売り手Ｕ_Ｓの公開鍵ＰｋＵ_Ｓで暗号化し、全価格ｉ（１≦ｉ≦ｌ）について
【数２９】

を算出する。なお、Ｅｎｃ＜ｋｅｙ＞（ｍｅｓ）とは、メッセージｍｅｓを公開鍵ｋｅｙにより暗号化することを示している。一方、残りのｔ−２台の市場サーバ、市場サーバ１−３〜１−ｔは、各々、
【数３０】

を暗号化する。そして、市場サーバ１−３〜１−ｔは、共同で
【数３１】

を全価格ｉ（１≦ｉ≦ｌ）について算出する。
【００５５】
ステップＳ５２０：
シェア生成サーバ５は、売り手Ｕ_Ｓの端末装置３ｂが価格情報Ｘ^（ＰＳ）を秘匿しながら売り注文情報Ｏ_Ｓを市場サーバ１−１〜１−ｎへ送信するために使用する価格情報Ｘ^（ｉ）のシェアを全価格（１≦ｉ≦ｌ）について生成するとともに、市場サーバ１−１〜１−ｎが売り手Ｕ_Ｓの端末装置３ｂから正しい価格情報Ｘ^（ＰＳ）を受信したことを確認するための正当性確認データを生成する。
まず、シェア生成サーバ５は、全価格ｉ（１≦ｉ≦ｌ）に対する
【数３２】

を算出する。そして、生成した全価格ｉの価格情報Ｘ^（ｉ）の要素Ｘ^（ｉ） _ｋ（ｉ，ｋ∈｛１，２，．．．，ｌ｝）を、全市場サーバ１−ｊ（１≦ｊ≦ｎ）に対して秘密分散するためのシェアｘ^（ｉ） _ｋ，ｊ（以下、「価格情報の要素のシェアｘ^（ｉ） _ｋ，ｊ」と記述）を生成し、それぞれに自身のディジタル署名を付与する。次に、売り手Ｕ_Ｓの公開鍵ＰｋＵ_Ｓを用いて全ｉ，ｊ，ｋ（１≦ｉ≦ｌ，１≦ｊ≦ｎ，１≦ｋ≦ｌ）について、このディジタル証明を付した価格情報の要素のシェアｘ^（ｉ） _ｋ，ｊを暗号化し、
【数３３】

を得る。
続いて、シェア生成サーバ５は、価格情報の要素のシェアｘ^（ｉ） _ｋ，ｊを用いて、各価格ｉ（１≦ｉ≦ｌ）について各市場サーバ１−ｊ（１≦ｊ≦ｎ）の
【数３４】

を算出する。なお、「Ｈ」は衝突困難な一方向性ハッシュ関数であり、「‖」は、結合を示す。
さらに、シェア生成サーバ５は、ランダム置換πを選ぶ。そして、価格を秘匿するために、各価格ｉ（１≦ｉ≦ｌ）の価格情報の要素のシェアのハッシュ値Ｈ^（ｉ） _ｊを、選択したπを用いてシャッフルし、各市場サーバ１−ｊ（１≦ｊ≦ｎ）の正当性確認データである
【数３５】

を得る。
最後にシェア生成サーバ５は、全価格ｉ（１≦ｉ≦ｌ）の
【数３６】

を各市場サーバ１−ｊ（１≦ｊ≦ｎ）へ送信する。
【００５６】
ステップＳ５２５：
各市場サーバ１−ｊ（１≦ｊ≦ｎ）は、現在の売りカウンタＣ^（Ｓ） _ｉの売りカウンタの現在値のシェアｃ_ｉ，ｊを用いて、全価格ｉ（１≦ｉ≦ｌ）の買い手情報復号鍵のシェアＳＫ^（Ｂ） _{ｉ，ｊ，ｃ}を以下のように生成する。
【数３７】

そして、各市場サーバ１−ｊ（１≦ｊ≦ｎ）は、算出した買い手情報復号鍵のシェアＳＫ^（Ｂ） _{ｉ，ｊ，ｃ}について、
【数３８】

を満たすように、ランダムに第１の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（１）} _{ｉ，ｊ，ｃ}及び第２の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（２）} _{ｉ，ｊ，ｃ}に分割する。最後に、各市場サーバ１−ｊ（１≦ｊ≦ｎ）は、第１の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（１）} _{ｉ，ｊ，ｃ}及び第２の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（２）} _{ｉ，ｊ，ｃ}を、売り手Ｕ_Ｓの公開鍵ＰｋＵ_Ｓを用いて暗号化し、全価格ｉ（１≦ｉ≦ｌ）の
【数３９】

【数４０】

を得る。
【００５７】
ステップＳ５３０：
各市場サーバ１−ｊ（１≦ｊ≦ｎ）は共同で、売り手Ｕ_Ｓの端末装置３ｂに対して全価格ｉ（１≦ｉ≦ｌ）の
【数４１】

の（１，ｌ）−ＯＴを実行する。このＯＴで、売り手Ｕ_Ｓの端末装置３ｂは、価格ｉが希望価格Ｐ_Ｓと一致する
【数４２】

（以下、「注文生成情報ＤＫ_ＰＳ」と記述）のみを選択する。
【００５８】
ステップＳ５３５：
図７は、図６に示す市場サーバを分散させた多対多マッチングシステムにおける売り注文サブプロトコルの手順の続きを示す。
売り手Ｕ_Ｓの端末装置３ｂは、価格ｉが希望価格Ｐ_Ｓと一致する注文生成情報ＤＫ_ＰＳを選択すると、希望価格Ｐ_Ｓの暗号化された第１の分割売り手情報暗号鍵ＥＰＫ^{（Ｓ），（１）} _ｉ，ｃ（ｉ＝Ｐ_Ｓ）及び暗号化された第２の分割売り手情報暗号鍵ＥＰＫ^{（Ｓ），（２）} _ｉ，ｃ（ｉ＝Ｐ_Ｓ）を公開鍵ＰｋＵ_Ｓに対応する秘密鍵により復号する。ここで、
【数４３】

とおくと、売り手Ｕ_Ｓの端末装置３ｂは、復号された第１の分割売り手情報暗号鍵ＰＫ^{（Ｓ），（１）} _ｉ，ｃ（ｉ＝Ｐ_Ｓ）及び第２の分割売り手情報暗号鍵ＰＫ^{（Ｓ），（２）} _ｉ，ｃ＝（ａ_３，・・・，ａ_ｔ）（ｉ＝Ｐ_Ｓ）から以下のように、希望価格Ｐ_Ｓの売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃを再構成する。
【数４４】

【００５９】
ステップＳ５４０：
売り手Ｕ_Ｓの端末装置３ｂは、ステップＳ５３５において算出した希望価格Ｐ_Ｓに対応する売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃにより電子株券ｄを暗号化し、
【数４５】

を算出する。
【００６０】
ステップＳ５４５：
売り手Ｕ_Ｓの端末装置３ｂは、希望価格Ｐ_Ｓの
【数４６】

の全ての項を公開鍵ＰｋＵ_Ｓに対応する秘密鍵により復号する。そして、希望価格Ｐ_Ｓに対応する全てのｊ，ｋ（１≦ｊ≦ｎ，１≦ｋ≦ｌ）の
【数４７】

（以下、「価格情報の要素のシェアｘ^（ＰＳ） _ｋ，ｊ」と記述）を得る。
【００６１】
ステップＳ５５０：
売り手Ｕ_Ｓの端末装置３ｂは、希望価格Ｐ_Ｓの売り手情報暗号鍵ＰＫ^（Ｓ） _ＰＳ，ｃにより暗号化された電子株券ＥＥと、希望価格Ｐ_Ｓの価格情報の要素のシェアｘ^（ＰＳ） _ｋ，ｊ（１≦ｋ≦ｌ）を、対応する全ての市場サーバ１−ｊ（１≦ｊ≦ｎ）へ送信する。
【００６２】
ステップＳ５５５：
各市場サーバ１−ｊ（１≦ｊ≦ｎ）は、価格情報の要素のシェアｘ^（ＰＳ） _ｋ，ｊ（１≦ｋ≦ｌ）に付されたシェア生成サーバ５のディジタル署名の正当性を確認する。続いて、各市場サーバ１−ｊ（１≦ｊ≦ｎ）は、全ての希望価格Ｐ_Ｓの価格情報の要素のシェアｘ^（ＰＳ） _ｋ，ｊの連結値からハッシュ値を生成し、ステップＳ５２０においてシェア生成サーバ５から受信した
【数４８】

の一つと等しいことを確認する。
【００６３】
ステップＳ５６０：
市場サーバ１−１〜１−ｎは、売り手Ｕ_Ｓの端末装置３ｂから受信した暗号化された電子株券ＥＥをデータベース２−１へ格納する。そして、市場サーバ１−１〜１−ｎは、（１，ｌ）−ＯＴを使用して、売り手Ｕ_Ｓの端末装置３ｂへ、
【数４９】

を送信する。
【００６４】
ステップＳ５６５：
全市場サーバ１−１〜１−ｎは、共同で下記のように売りカウンタＣ^（Ｓ） _ｉを更新する。
【数５０】

【００６５】
ステップＳ５７０：
売り手Ｕ_Ｓの端末装置３ｂは、価格ｉが希望価格Ｐ_Ｓと一致する
【数５１】

（以下、「暗号化された第２の分割買い手情報復号鍵ＥＳＫ^{（Ｂ），（２）} _ＰＳ，ｃ」と記述）を選択する。そして、この暗号化された第２の分割買い手情報復号鍵ＥＳＫ^{（Ｂ），（２）} _ＰＳ，ｃを、公開鍵ＰｋＵ_Ｓに対応する秘密鍵を使用して復号し、希望価格Ｐ_Ｓの
【数５２】

（以下、「第２の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（２）} _{ＰＳ，ｊ，ｃ}」と記述）を得る。さらに、ステップＳ５３０において選択した希望価格Ｐ_Ｓに対応する注文生成情報ＤＫ_ｉ内の暗号化された第１の分割買い手情報復号鍵ＥＳＫ^{（Ｂ），（１）} _ｉ，ｃから、公開鍵ＰｋＵ_Ｓに対応する秘密鍵を使用して希望価格Ｐ_Ｓの
【数５３】

（以下、「第１の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（１）} _{ＰＳ，ｊ，ｃ}」と記述）を復号する。売り手Ｕ_Ｓの端末装置３ｂは、復号された第１の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（１）} _{ＰＳ，ｊ，ｃ}と第２の分割買い手情報復号鍵のシェアＳＫ^{（Ｂ），（２）} _{ＰＳ，ｊ，ｃ}から買い手情報復号鍵ＳＫ^（Ｂ） _ＰＳ，ｃを復元する。
【００６６】
（３）買い注文サブプロトコル及びブロードキャストサブプロトコル
買い注文サブプロトコルは、この節の（２）に示す売り注文サブプロトコルと同様に行う。また、ブロードキャストサブプロトコルは、４．２節の基本プロトコルの（４）に記載したブロードキャストサブプロトコルと同様である。なお、ブロードキャストは、市場サーバ１−１〜１−ｎのいずれが行ってもよい。
【００６７】
６．その他
上記実施の形態によれば、通信コスト・計算コストを抑えて、データ交換の正当性、データの秘匿性、希望価格の秘匿性、匿名性、及び、堅牢性を満たした多対多マッチングシステムを提供することができる。
なお、上述の市場サーバ１、市場サーバ１−１〜１−ｎ、データベース２−１、データベース２−２、端末装置３ａ、端末装置３ｂ、端末装置４ａ、端末装置４ｂ及びシェア生成サーバ５は、内部にコンピュータシステムを有している。そして、上述した動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウェアを含むものである。
【００６８】
また、「コンピュータ読み取り可能な記録媒体」とは、ＲＯＭの他に、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００６９】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００７０】
【発明の効果】
この発明によれば、通信コスト・計算コストを抑えて、個々サーバの信頼性が高くなくとも、不正に強く、悪意を持った特定の市場運営者が売り手及び買い手の希望価格などのプライバシや金銭的価値のあるディジタル情報を取得することを防ぎながら、売り手と買い手の注文の多対多のマッチングを行うとともに、マッチした売り手と買い手との間の金銭的価値のあるディジタル情報を安全に配送・交換し、その換金を行う多対多マッチングシステム及びサービスを構築することができる。
【図面の簡単な説明】
【図１】この発明の一実施の形態による多対多マッチングシステムの構成を示すブロック図である。
【図２】同実施の形態による市場Ｍのセットアップの手順を示す図である。
【図３】同実施の形態による売り注文サブプロトコルの手順を示す図である。
【図４】同実施の形態によるブロードキャストサブプロトコルの手順を示す図である。
【図５】市場サーバを分散させた多対多マッチングシステムの構成を示すブロック図である。
【図６】図５の構成による売り注文サブプロトコルの手順を示す図である。
【図７】図６の売り注文サブプロトコルの手順の続きを示す図である。
【符号の説明】
１，１−１，１−２，１−３，１−ｔ，１−ｎ…市場サーバ
２−１，２−２…データベース
３ａ，３ｂ，４ａ，４ｂ…端末装置
５…シェア生成サーバ[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a many-to-many matching system that delivers electronically valuable information of a seller to a buyer and electronically valuable information of a buyer to a seller.
[0002]
[Prior art]
In recent years, with the spread of the Internet, e-commerce such as Internet banking, online auctions, and online stock trading has been realized on the Internet, and in particular, the scale of online stock trading has been rapidly expanding. At present, these service systems support only a part where a contract between two parties is concluded, and the distribution and settlement of goods are realized by another means. However, in the future, if valuable electronic information such as electronic money and electronic stock certificates becomes widespread, not only making a contract on the Internet, but also exchanging the valuable electronic information itself on the Internet. It is thought to be done in. In a trading system (hereinafter referred to as market) for exchanging valuable electronic information, a plurality of sellers, buyers and buyers exist simultaneously, and the seller exchanges electronic valuable information in exchange for the valuable information. Wanting to get money, buyers want to get valuable electronic information instead of electronic money. In such markets, it is envisaged that electronic money and electronic stock certificates, electronic money of another currency, electronic tickets, electronic memberships, and digital content such as music and movies may be exchanged.
On the other hand, Non-Patent Document 1 discloses that in a market in which a large number of sellers and buyers exchange valuable electronic information, matching of seller and buyer orders is possible while keeping information about the order price of the seller and buyer concealed. The other than the matched sellers and buyers, the electronically valuable information of the matched seller is provided to the buyer while the electronically valuable information is kept secret to the buyer. It describes the protocol for correctly sending information with the information to the seller.
[0003]
[Non-patent document 1]
Shinichiro Matsuo and Waka Ogata, "Data Exchangeable Many-to-Many Matching Protocol," Proceedings of the 2002 Symposium on Cryptography and Information Security, IEICE Information Security Research Special Committee, January-February 2002, Volume
I of II, p. 435-440
[0004]
[Problems to be solved by the invention]
In the method described in Non-Patent Document 1, a common key for encrypting or decrypting valuable digital information, which is valuable digital information of a seller and a buyer, is generated using a multi-party protocol. Performs encryption processing using a common key. Further, the validity of the order information sent by the seller and the buyer is confirmed using the zero knowledge proof. However, there is a problem that these processes are not practical because the efficiency is low and both the calculation cost and the communication cost are very large. A multi-party protocol is a cryptographic protocol in which a plurality of parties hold secret values, exchange information with each other while keeping the values secret, and obtain the result of a function using those secret values. is there. In general, a zero-knowledge proof is a process in which a verifier exchanges information several times between a prover and a verifier to verify that the prover knows the knowledge of secret information held by the prover. Is a method of probabilistically proving against.
The present invention has been made in view of the above-described circumstances, and its purpose is to match seller and buyer orders while keeping information on the seller and buyer order prices concealed, and to match other sellers and buyers. To properly deliver the digitized valuable information of the matched seller to the buyer and the digitized valuable information of the matched buyer to the seller while keeping the digitized value information confidential to the person Another object of the present invention is to provide an efficient many-to-many matching system.
[0005]
[Means for Solving the Problems]
SUMMARY OF THE INVENTION The present invention has been made to solve the above-mentioned problem, and the invention according to claim 1 is a method for generating a share for generating a share of a terminal device of an orderer and price information indicating a desired price of the orderer. A many-to-many matching system comprising a server and a market server for mediating valuable digital information, which is valuable digital information between orderers who have indicated matching desired prices, via a network, The generation server includes a share generation unit configured to generate and transmit a share of secretly distributed price information corresponding to each market server for each price, and to transmit the market server. The market server is configured to encrypt valuable digital information of the orderer. Key generating means for generating an encryption key and a decryption key for decrypting the orderer's valuable digital information indicating the matching desired price; and an encryption key generated by the key generating means. And order generation information transmitting means for transmitting a decryption key to the orderer's terminal device, a share of price information indicating a desired price, and the orderer's valuable digital information encrypted by an encryption key corresponding to the desired price. Order receiving means for receiving from the terminal apparatus of the orderer, and broadcast means for periodically broadcasting the valuable digital information of the orderer received by the order receiving means to the terminal apparatuses of all the orderers, The orderer's terminal device receives the encryption key, decryption key and price information share corresponding to all prices, and selects the encryption key, decryption key and price information share corresponding to the desired price from among them. Order information for transmitting to the market server, receiving means for transmitting, valuable digital information encrypted with the selected encryption key, and a share of price information corresponding to the desired price. And a decryption means for decrypting the encrypted valuable digital information broadcast from the market server using the decryption key and receiving matching valuable digital information. .
[0006]
According to a second aspect of the present invention, a terminal device of an orderer is connected via a network to a market server which mediates valuable digital information, which is valuable digital information, between the orderer who has indicated a matching desired price. The market server comprises: an encryption key for encrypting the orderer's valuable digital information; and an order key for decrypting the orderer's valuable digital information indicating the matching desired price. Key generating means for generating a decryption key and encrypting it with the orderer's key, an encryption key and a decryption key encrypted by the orderer's key, and encrypted by the orderer's key. Order generation information transmitting means for transmitting the share of the price information to the terminal device of the orderer for all prices, and a share of the price information indicating the desired price and an encryption key corresponding to the desired price Order receiving means for receiving the valued digital information of the orderer from the terminal device of the orderer; and periodically transmitting the encrypted digital value information of the orderer received by the order receiving means to the terminals of all the orderers. Broadcasting means for broadcasting to the device, wherein the orderer's terminal device receives an encrypted encryption key, a decryption key, and a share of price information corresponding to all prices from the market server, and receives its own key. Receiving means for selecting and decrypting an encryption key, a decryption key, and a share of price information corresponding to the desired price, valuable digital information encrypted with the decrypted encryption key, and a share of price information corresponding to the desired price Order information transmitting means for transmitting to the market server, the encrypted valuable digital information broadcast from the market server as the decryption key Ri decoded, and a decoding means for receiving a matching valuable digital information, which is many-to-many matching system, characterized in that.
[0007]
According to a third aspect of the present invention, there is provided a terminal device of an orderer, a share generation server for generating a share of price information indicating a desired price of the orderer, and a value between the orderer indicating a matching desired price. A many-to-many matching system in which a market server that mediates valuable digital information, which is digital information, is connected via a network, wherein the share generation server includes secret-shared price information corresponding to each market server. Is generated for each price, encrypted by the orderer's key, and transmitted to each market server. The market server, from the share generation server, Share receiving means for receiving a share of price information corresponding to a price; a first divided encryption key obtained by dividing an encryption key for encrypting valuable digital information of an orderer; An encryption key generating means for generating the second divided encryption key in a distributed manner and encrypting it with the orderer's key, and a decryption key for decrypting the orderer's valuable digital information indicating the matching desired price are divided. Decryption key generating means for generating a first divided decryption key and a second divided decryption key, and encrypting the first divided decryption key with an orderer's key; and an encrypted first divided encryption key corresponding to all prices, Order generation information transmitting means for transmitting the second divided encryption key, the first divided decryption key, and the share of the price information to the terminal device of the orderer, and the share of the price information indicating the desired price and corresponding to the desired price Order receiving means for receiving, from the orderer's terminal device, valuable digital information of the orderer encrypted with the encryption key to be transmitted, and returning the encrypted second divided decryption key corresponding to all prices; The order receiving means receives the Broadcasting means for broadcasting the encrypted valuable digital information of the orderer to the terminal devices of all the orderers, wherein the terminal device of the orderer has an encrypted first divided encryption key corresponding to all prices. , A second divided encryption key, a first divided decryption key, and a share of price information from the market server, and a first divided encryption key, a second divided encryption key corresponding to a desired price by its own key. Receiving means for selecting and decrypting a key, a first divided decryption key and a share of price information, and a seller information encryption key corresponding to a desired price from the first divided encryption key and the second divided encryption key. Order information transmitting means for restoring and transmitting valuable digital information encrypted with the encryption key and a share of price information corresponding to a desired price to the market server; and an encrypted order information corresponding to all prices from the market server. Receiving the second divided decryption key, selecting the second divided decryption key corresponding to the desired price, decrypting it with its own key, and combining the first divided decryption key with the decryption key corresponding to the desired price. Key decryption means for decrypting the valuable digital information of the buyer broadcast from the market server using the decryption key, and receiving matching valuable digital information. It is a many-to-many matching system.
[0008]
According to a fourth aspect of the present invention, a terminal device of a seller and a buyer and a market server that mediates valuable digital information, which is valuable digital information, between the seller and the buyer who have indicated a matching desired price, via a network. A market server, wherein the market server decrypts the seller's valuable digital information for encrypting the seller's valuable digital information and the buyer's valuable digital information indicating the matching desired price. Key generation means for generating a buyer information decryption key and encrypting the same with a seller key, a seller information encryption key encrypted by the first key generation means with a seller key, and a buyer information decryption key First order generation information transmission for transmitting a key and a share of price information encrypted by the seller's key to the terminal device of the seller for all prices. Generating a step, a buyer information encryption key for encrypting the buyer's valuable digital information, and a seller information decryption key for decrypting the seller's valuable digital information indicating the matching desired price, and using the buyer's key. Second key generation means for encrypting, a buyer information encryption key and a seller information decryption key encrypted by the second key generation means with a buyer key, and a share of price information encrypted with the buyer key Second order generation information transmitting means for transmitting the total price to the buyer's terminal device, a share of price information indicating the desired price, and the seller's valuable encrypted by the seller information encryption key corresponding to the desired price. Selling order receiving means for receiving digital information from the seller's terminal device, a share of price information indicating a desired price, and a buyer information encryption key corresponding to the desired price. A purchase order receiving means for receiving the encrypted valuable digital information of the buyer from the terminal device of the buyer; and periodically broadcasting the encrypted valuable digital information of the buyer and the seller to the terminal devices of the buyer and the seller. Broadcast means, the seller's terminal device receives the encrypted seller information encryption key, buyer information decryption key, and price information share corresponding to all prices from the market server, and receives its own key. Receiving means for selecting and decrypting the seller information encryption key, buyer information decryption key and price information share corresponding to the desired price, valuable digital information encrypted with the decrypted seller information encryption key, Selling order information transmitting means for transmitting the corresponding price information share to the market server; Decoding means for decrypting the encrypted valuable digital information of the buyer by the buyer information decryption key and receiving matching valuable digital information, wherein the buyer's terminal device has an encryption corresponding to all prices. The received buyer information encryption key, seller information decryption key, and share of price information are received from the market server, and the buyer information encryption key, seller information decryption key, and Receiving means for selecting and decrypting the share, valuable digital information encrypted with the decrypted buyer information encryption key, and a buy order information transmitting means for transmitting the share of price information corresponding to the desired price to the market server; Decrypting the encrypted valuable digital information of the seller broadcasted from the market server by the seller information decryption key, And a decoding means for receiving valuable digital information pitch, a many-to-many matching system, characterized in that.
[0009]
The invention according to claim 5 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A many-to-many matching system in which a market server that mediates valuable digital information, which is valuable digital information, is connected via a network, wherein the share generation server includes a secret sharing corresponding to each market server. A share generating means for generating a share of the price information for each price, encrypting the market information with a seller or buyer key, and transmitting the encrypted market information to each market server, wherein the market server has a database storing encrypted valuable digital information; Sell and buy counters corresponding to the price and taking the same initial value for the matching price; (A) share receiving means for receiving a share of price information corresponding to all prices encrypted with a seller or buyer key from a generation server, and for encrypting seller's valuable digital information based on the sell counter. First encryption key generation means for distributingly generating a first divided seller information encryption key and a second divided seller information encryption key obtained by dividing a seller information encryption key, and encrypting the generated information with a seller key; The first divided buyer information encryption key and the second divided buyer information encryption key obtained by dividing the buyer information encryption key for encrypting the buyer's valuable digital information are distributed and generated based on the buyer key. A second encryption key generating means for encrypting, and a buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price based on the selling counter. First decryption key generating means for generating the divided first partial buyer information decryption key and the second partial buyer information decryption key, and encrypting them with the seller's key; and a matching desired price based on the buy counter. A first divided seller information decryption key and a second divided seller information decryption key, which are obtained by dividing the seller information decryption key for decrypting the seller's valuable digital information, and encrypting with the buyer's key. Decryption key generating means, the first partial seller information encryption key, the second partial seller information encryption key, the first partial buyer information decryption key, and the encrypted price information corresponding to all prices. First order generation information transmitting means for transmitting the share of the price to the seller's terminal device, the share of the price information indicating the desired price, and the valuable digital information encrypted by the seller information encryption key corresponding to the desired price Selling order receiving means for receiving from the terminal device of the seller, writing the encrypted valuable digital information into the database, and returning the encrypted second partial buyer information decryption key corresponding to all prices. And the first partial buyer information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the share of the price information, which are encrypted, corresponding to all prices. A second order generation information transmitting means for transmitting to the terminal device, a share of price information indicating a desired price, and valuable digital information encrypted by a buyer information encryption key corresponding to the desired price from the terminal device of the buyer. Receiving and writing the encrypted valuable digital information to the database, and decrypting the encrypted second divided seller information corresponding to all prices And a counter updating means for updating the selling counter or the buying counter using random numbers, and periodically, the encrypted digital information of the buyer and seller stored in the database. Broadcast means for broadcasting to a buyer and a seller terminal device, wherein the seller terminal device has an encrypted first divided seller information encryption key, a second divided seller information encryption key corresponding to all prices, A first split buyer information decryption key, and a share of price information received from the market server, and a first split seller information encryption key, a second split seller information encryption key corresponding to a desired price by its own key, Receiving means for selecting and decrypting a first partial buyer information decryption key and a share of price information; The market server restores the seller information encryption key corresponding to the desired price from the second divided seller information encryption key and stores the valuable digital information encrypted by the seller information encryption key and the share of the price information corresponding to the desired price. Receiving the encrypted second partial buyer information decryption key corresponding to all prices from the market server and selecting the second partial buyer information decryption key corresponding to the desired price Key decryption means for decrypting the data with its own key and recovering the buyer information decryption key corresponding to the desired price together with the first split buyer information decryption key; and an encrypted buyer broadcasted from the market server. Decrypting the valuable digital information with the buyer information decryption key and receiving matching valuable digital information, and the buyer's terminal device comprises: Receiving, from the market server, a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to all prices; Receiving means for selecting and decrypting a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to a desired price with its own key. Recovering a buyer information encryption key corresponding to a desired price from the first partial buyer information encryption key and the second partial buyer information encryption key, and encrypting valuable digital information encrypted with the buyer information encryption key; Means for transmitting a share of price information corresponding to the above to the market server; receiving an encrypted second partial seller information decryption key corresponding to all prices from the market server; Key restoring means for selecting a second partial seller information decryption key corresponding to the case, decrypting the key with its own key, and restoring the seller information decryption key corresponding to the desired price together with the first partial seller information decryption key And decryption means for decrypting the encrypted valuable digital information of the seller broadcasted from the market server with the seller information decryption key, and receiving matching valuable digital information. System.
[0010]
The invention according to claim 6 is the many-to-many matching system according to claim 5, wherein the share generation means determines that the share of the price information that each market server receives from the terminal device of the seller or the buyer is valid. The validity confirmation data for confirming the existence is generated from the share of the price information, the price is concealed and transmitted to the market server, and the selling order receiving means receives the validity confirmation received from the share generation server Based on the data, if it is determined that the share of the price information received from the terminal device of the seller is valid, the encrypted second partial buyer information decryption key is returned, the buy order receiving means, If the share of the price information received from the terminal device of the buyer is determined to be valid based on the validity confirmation data received from the share generation server, the encrypted second It returns the division Seller information decryption key, characterized in that.
[0011]
The invention according to claim 7 is the many-to-many matching system according to claim 5 or 6, wherein the seller information encryption key, the buyer information encryption key, the seller information decryption key, and the buyer The information decryption key is generated by a public key cryptosystem.
[0012]
The invention according to claim 8 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A market server of a many-to-many matching system in which a market server that mediates valuable digital information, which is valuable digital information, is connected via a network, and a database that stores encrypted valuable digital information. Selling and buying counters corresponding to the price and taking the same initial value for the matching price, and secret sharing corresponding to each market server encrypted by the seller or buyer key from the share generation server. Share receiving means for receiving the share of the price information obtained, and the seller's valuable digital First encryption, in which a first divided seller information encryption key and a second divided seller information encryption key, which are obtained by dividing a seller information encryption key for encrypting file information, are generated in a distributed manner, and encrypted with the seller key. Key generating means and, based on the buy counter, distributing a first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing a buyer information encryption key for encrypting valuable digital information of a buyer; A second encryption key generating means for generating and encrypting with a buyer key, and a buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price based on the selling counter. First decryption key generating means for generating the first partial buyer information decryption key and the second partial buyer information decryption key and encrypting them with the seller's key; A first divided seller information decryption key and a second divided seller information decryption key, which are obtained by dividing a seller information decryption key for decrypting valuable digital information of a seller indicating a rating, are generated, and encrypted by a buyer key. 2 decryption key generating means, the first partial seller information encryption key, the second partial seller information encryption key, the first partial buyer information decryption key, and the encrypted price corresponding to all prices. First order generation information transmitting means for transmitting the share of the information to the terminal device of the seller, and the share of the price information indicating the desired price and the valuable digital information encrypted by the seller information encryption key corresponding to the desired price. Receiving the encrypted valuable digital information from the terminal device of the seller and writing the encrypted valuable digital information into the database, and encrypting the encrypted second partial buyer information decryption key corresponding to the total price Selling order receiving means for returning the first partial buyer information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the encrypted corresponding to all prices. Second order generation information transmitting means for transmitting the share of the price information to the terminal device of the buyer; share of the price information indicating the desired price; and valuable digital information encrypted by the buyer information encryption key corresponding to the desired price. Purchase order receiving means for receiving from the terminal device of the buyer, writing the encrypted valuable digital information into the database, and returning the encrypted second partial seller information decryption key corresponding to all prices. Counter updating means for updating the selling counter or the buying counter using a random number; and periodically, the encrypted data stored in the database. And broadcast means for broadcasting a valuable digital information buyer and seller terminal device of the buyer and seller, a marketplace server, characterized in that it comprises a.
[0013]
The invention according to claim 9 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A terminal device of a seller of a many-to-many matching system in which a market server which mediates valuable digital information as valuable digital information is connected via a network, and encrypts the valuable digital information of the seller. A first divided seller information encryption key and a second divided seller information encryption key obtained by dividing the seller information encryption key, and a buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price. Full-value cipher text of the divided first split buyer information decryption key and the share of price information secretly shared corresponding to each market server From the market server and share the first divided seller information encryption key, the second divided seller information encryption key, the first divided buyer information decryption key, and the price information corresponding to the desired price with its own key. Receiving means for selecting and decrypting, and restoring a seller information encryption key corresponding to a desired price from the first divided seller information encryption key and the second divided seller information encryption key, and encrypting the same with the seller information encryption key Selling order information transmitting means for transmitting the obtained valuable digital information and the share of price information corresponding to the desired price to the market server; and decrypting the encrypted second partial buyer information corresponding to all prices from the market server. Receiving the key, selecting the second partial buyer information decryption key corresponding to the desired price, decrypting it with its own key, and corresponding to the desired price together with the first partial buyer information decryption key Key restoring means for restoring a buyer information decryption key, decrypting the encrypted buyer's valuable digital information broadcasted from the market server with the buyer information decryption key, and receiving matching valuable digital information; And a seller's terminal device.
[0014]
The invention according to claim 10 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A buyer terminal of a many-to-many matching system in which a market server that mediates valuable digital information that is valuable digital information is connected via a network, and encrypts the buyer's valuable digital information. A first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing the buyer information encryption key for use with the buyer information encryption key, and a seller information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price. The ciphertext of the divided first split seller information decryption key and the share of the price information secretly shared in correspondence with each market server is completely stored. Of the first split buyer information encryption key, the second split buyer information encryption key, the first split seller information decryption key, and the price information of the Receiving means for selecting and decrypting a share; and restoring a buyer information encryption key corresponding to a desired price from the first partial buyer information encryption key and the second partial buyer information encryption key, and encrypting with the buyer information encryption key. Buy order information transmitting means for transmitting the converted valuable digital information and the share of price information corresponding to the desired price to the market server; and encrypted second partial seller information corresponding to all prices from the market server. Upon receiving the decryption key, a second partial seller information decryption key corresponding to the desired price is selected, decrypted by its own key, and combined with the first partial seller information decryption key to match the desired price. Key restoring means for restoring the seller information decryption key to be decrypted, decrypting the encrypted seller's valuable digital information broadcasted from the market server by the seller information decryption key, and receiving matching valuable digital information; And a buyer terminal device.
[0015]
The invention according to claim 11 includes a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A computer program used for a market server of a many-to-many matching system in which a market server that mediates valuable digital information as valuable digital information is connected via a network, and a selling counter corresponding to a price. And initializing the buy counter with the same value for the matching price; and, from the share generation server, the share of the price information secretly shared corresponding to each market server encrypted with the seller or buyer key. And encrypting the seller's valuable digital information based on the selling counter. Generating a first divided seller information encryption key and a second divided seller information encryption key by dividing the seller information encryption key for encryption and encrypting the divided information with the seller key; and A first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing a buyer information encryption key for encrypting buyer's valuable digital information are generated in a distributed manner, and encrypted with the buyer key. And a first partial buyer information decryption key and a second partial buyer information decryption obtained by dividing the buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price based on the selling counter. Generating a key and encrypting it with the seller's key; and decrypting the seller's valuable digital information indicating the matching desired price based on the buy counter. Generating a first divided seller information decryption key and a second divided seller information decryption key obtained by dividing the seller information decryption key, and encrypting the first divided seller information decryption key with the buyer's key; Transmitting the first split seller information encryption key, the second split seller information encryption key, the first split buyer information decryption key, and the share of price information to the terminal device of the seller; and a price indicating a desired price. Receive valuable digital information encrypted with the seller information encryption key corresponding to the share of information and the desired price from the terminal device of the seller, write the encrypted valuable digital information into its own database, Returning the encrypted second partial buyer information decryption key corresponding to the price; and encrypting the first partial buyer information corresponding to the full price. Transmitting the information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the share of the price information to the terminal device of the buyer; and the share of the price information indicating the desired price. And receiving valuable digital information encrypted with the buyer information encryption key corresponding to the desired price from the terminal device of the buyer, writing the encrypted valuable digital information into the database, and Returning the encrypted second split-seller information decryption key; updating the sell counter or the buy counter using a random number; and periodically updating the encrypted counter stored in the database. Broadcasting the buyer and seller's valuable digital information to the buyer and seller terminals. A computer program for causing executed.
[0016]
The invention according to claim 12 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A computer program used in a terminal device of a seller of a many-to-many matching system in which a market server that mediates valuable digital information, which is valuable digital information, is connected via a network. A first split seller information encryption key and a second split seller information encryption key obtained by splitting a seller information encryption key for encrypting information, and a buyer's valuable digital information indicating a matching desired price are decrypted. A first divided buyer information decryption key obtained by dividing the buyer information decryption key and a secret shared key corresponding to each market server; The encrypted text with the share of the price information is received from the market server for all prices, and the first divided seller information encryption key, the second divided seller information encryption key, and the first Selecting and decrypting a split buyer information decryption key and a share of price information; and obtaining a seller information encryption key corresponding to a desired price from the first partial seller information encryption key and the second partial seller information encryption key. Restoring and transmitting valuable digital information encrypted by the seller information encryption key and a share of price information corresponding to the desired price to the market server; and encrypting the market server corresponding to all prices from the market server. Receiving the second partial buyer information decryption key, selecting the second partial buyer information decryption key corresponding to the desired price, decrypting it with its own key, Restoring the buyer information decryption key corresponding to the desired price, and decrypting the encrypted buyer's valuable digital information broadcasted from the market server with the buyer information decryption key and receiving the matching valuable digital information And a step of causing a computer to execute the steps.
[0017]
The invention according to claim 13 provides a terminal device for a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and a seller and a buyer indicating matching desired prices. A computer program used for a buyer's terminal device of a many-to-many matching system in which a market server that mediates valuable digital information, which is valuable digital information, is connected via a network. A first split buyer information encryption key and a second split buyer information encryption key obtained by splitting a buyer information encryption key for encrypting information, and a buyer's valuable digital information indicating a matching desired price. A first divided seller information decryption key obtained by dividing the seller information decryption key and a secret shared key corresponding to each market server. The encrypted text with the share of the price information is received from the market server for all prices, and the first partial buyer information encryption key, the second partial buyer information encryption key, and the first Selecting and decrypting a split seller information decryption key and a share of price information; and obtaining a buyer information encryption key corresponding to a desired price from the first partial buyer information encryption key and the second partial buyer information encryption key. Restoring and transmitting valuable digital information encrypted with the buyer information encryption key and a share of price information corresponding to the desired price to the market server; and encrypting the market server corresponding to all prices from the market server. Receiving a second partial seller information decryption key, selecting a second partial seller information decryption key corresponding to a desired price, decrypting it with its own key, Restoring the seller information decryption key corresponding to the desired price, and decrypting the encrypted seller's valuable digital information broadcasted from the market server with the seller information decryption key and receiving the matching valuable digital information And a step of causing a computer to execute the steps.
[0018]
BEST MODE FOR CARRYING OUT THE INVENTION
Hereinafter, embodiments of the present invention will be described with reference to the drawings.
For convenience,
(Equation 1)

To X^y _zDescribe as follows.
1. Constitution
FIG. 1 is a block diagram showing a configuration of a many-to-many matching system according to an embodiment of the present invention. The valuable digital information exchanged by the many-to-many matching system may be electronic stock certificates, electronic tickets, electronic memberships, digital contents such as music or moving images, etc. It will be determined. Here, it is assumed that a market M that handles one type of electronic stock certificate is open.
[0019]
The market server 1 is a server of the market M, and is connected to the database 2-1 and the database 2-2 via a network N which is a public network such as the Internet or a local network such as a LAN (Local Area Network). Also, the seller U via the network N_STerminal device 3a and buyer U_BTerminal device 4a. And seller U_SOrder information O including price information X indicating the desired price and electronic stock certificate d from the terminal device 3a_S, And price information X indicating the desired price matched._BGenerates a buyer information decryption key for decrypting the electronic money m of_SHas a function of returning to the terminal device 3a, and a function of storing the electronic stock certificate d encrypted with the seller information encryption key in the database 2-1. Also, buyer U_BInformation X indicating the desired price and the purchase order information O including the electronic money m from the terminal device 4a._BU that has received the price information and transmitted the price information X indicating the desired price matched._SGenerates a seller information decryption key for decrypting the electronic stock certificate d of_BAnd a function of storing the electronic money m encrypted with the buyer information encryption key in the database 2-2. Further, the encrypted electronic money m and electronic stock d stored in the databases 2-1 and 2-2 are transferred to the buyer U._BTerminal device 3a and seller U_SHas a function of broadcasting to the terminal device 4a.
It should be noted that a matching rule for determining that “matched” in the main market M, that is, a match between the buy order and the sell order, will be described later.
[0020]
The databases 2-1 and 2-2 are databases of the market M, and are connected to the market server 1 via the network N or the private network. The database 2-1 stores the encrypted electronic stock certificate d, and the database 2-2 stores the encrypted electronic money m. The databases 2-1 and 2-2 may be directly connected to the market server 1, or may be provided inside the market server 1.
[0021]
The terminal device 3a is a seller U_SAnd is connected to the market server 1 via the network N. Then, the selling order information O including the price information X indicating the desired price and the electronic stock certificate d for the market server 1._SFunction to send and sell order information O_SAnd a function of decrypting the broadcasted encrypted electronic money m with the buyer information decryption key received from the market server 1 and receiving the matched electronic money m.
[0022]
The terminal device 4a is connected to the buyer U_BAnd is connected to the market server 1 via the network N. Then, the purchase order information O including the price information X indicating the desired price and the electronic money m is sent to the market server 1._BFunction and the transmitted purchase order information O_BAnd decrypts the broadcasted electronic stock certificate d using the seller information decryption key received from the market server 1 in response to the received electronic stock certificate d.
[0023]
2. Market model
Here, a market model of the many-to-many matching system according to the present embodiment will be described.
In the market, there are a plurality of sellers U who want to sell an electronic stock certificate of the same brand at each desired selling price._SAnd a plurality of buyers U who want to buy an electronic stock certificate of the same brand at the respective trading desired prices._BExists. Seller U_SAnd buyer U_BTogether with the orderer. And sell order information O_SAnd buy order information O_BThere is a market M which is a center that performs the matching. Market M is based on matching order rules used in the following general market and sell order information O_SAnd buy order information O_BIs performed. (1) Sell order information O for the same desired price_SAnd buy order information O_BTo match.
(2) Sell order information O for two or more same desired prices_SOr buy order information O of the same desired price_BIf there is, give priority to the order that arrived first in the market.
[0024]
Properties required for the matching of the present invention are listed below.
Justification of data exchange:
Seller U_SSell Order Information O_SAnd buyer U_BBuy order information O_BIs matched, the seller U_SIs buy order information O_BReceived the electronic money m included in the_BIs sell order information O_SReceives the electronic stock certificate d included in the.
Data confidentiality:
The market M cannot own all the electronic money m and the electronic stock certificate d. Also, all sellers U_SIs the matching buy order information O_BIt is not possible to obtain electronic money m other than electronic money m included in. And all buyers U_BIs the matching sell order information O_SCannot be obtained other than the electronic stock certificate d included in.
Secret price confidentiality:
All orderers and markets M have all buy order information O_BAnd sell order information O_SIt is not possible to know the desired price (hereinafter simply referred to as order) and the number of orders for each desired price.
Anonymity:
Not all orderers and markets M can know who has received the matched electronic money m, electronic stock certificate d.
Robustness:
The market M has robustness against a case where an illegal order is transmitted from the orderer. That is, the market M can reject an orderer who has performed an illegal operation or an illegal order.
[0025]
3. Basic cryptographic tools
Here, a basic encryption tool used in the present embodiment will be described.
3.1 Lost communication
Matching Oblivious Transfer (OT) means that when a sender sends multiple messages to a recipient, the recipient receives only one of the messages sent by the sender and the sender receives This is a protocol between two parties that cannot know which message has been received. In particular, (1, N) -OT indicates that the sender has N messages {D₁, D₂, ..., D_Nへ to the recipient, the recipient receives the index i∈ ｛1, 2,. . . . , N}, the result is that D_iThe communication is that the user receives only the i, but does not get anything for the other messages and the sender cannot know about the i received by the recipient.
[0026]
3.2 Verifiable secret sharing
Secret sharing (SS) means that the secret information s held by the dealer is divided into n shares and each share is distributed to n players, and each player has a certain number of players or more. The original secret information s can be restored by matching the shares, but this is a cryptographic scheme that performs distributed coding so that the secrets cannot be known from the shares distributed to oneself. In particular, at the (t, n) threshold value SS, the secret information s cannot be restored by matching the shares of t-1 or less players, but the secret information can be restored by matching the shares of t or more players. The information s can be restored.
On the other hand, the verifiable secret sharing (VSS) is an SS that allows each player to verify that the share distributed to him / her is correctly calculated from the secret information s.
Also, many SSs have homomorphism. That is, the secret information s₁With n shares ｛S_1,1, S_1,2,. . . , S_{1, n}｝, Secret information s₂With n shares ｛S_2,1, S_2,2,. . . , S_{2, n}Ｉ and the i-th player is S_{1, i}And S_{2, i}If you receive the secret information s₁And s₂S that is the sum of₁+ S₂Is the S of each player_{1, i}+ S_{2, i}｛S combined_1,1+ S_2,1, S_1,2+ S_2,2,. . . . , S_{1, n}+ S_{2, n}Can be restored from｝.
[0027]
4. Operation of many-to-many matching system
4.1 System Protocol
Here, a system protocol of the many-to-many matching system applied to the many-to-many matching system shown in FIG. 1 will be described.
It is assumed that the price i of the electronic stock certificate in the market M is in the range of 1 ≦ i ≦ l. And market server 1 sells counter C corresponding to price i (1 ≦ i ≦ l).^(S) _i, Buy counter C^(B) _iHold. In addition, selling counter C^(S) _iAnd buy counter C^(B) _iIs a random number, but takes the same initial value for the same price i.
Then, the market server 1 provides a selling counter C for the price i.^(S) _iIs calculated from the current value c of the public key. The calculated public key is a seller information encryption key PK for encrypting the electronic stock certificate d.^(S) _{i, c}Used as The secret key is the seller information encryption key PK^(S) _{i, c}Information decryption key SK for decrypting electronic stock certificate d encrypted by^(S) _{i, c}Used as
Similarly, the market server 1 provides the buy counter C for the price i.^(B) _iIs calculated from the current value c of the public key. The calculated public key is a buyer information encryption key PK for encrypting the electronic money m.^(B) _{i, c}Used as The secret key is the buyer information encryption key PK^(B) _{i, c}Information decryption key SK for decrypting electronic money m encrypted by^(B) _{i, c}Used as
That is, the seller information encryption key PK^(S) _{i, c}And seller information decryption key SK^(S) _{i, c}And the buyer information encryption key PK^(B) _{i, c}And buyer information decryption key SK^(B) _{i, c}Is a sell counter C for each sell or buy order^(S) _iOr buy counter C^(B) _iIs uniquely calculated by the current value c of And a certain seller information decryption key SK^(S) _{i, c}Or the buyer information decryption key SK^(B) _{i, c}From the other seller information decryption key SK^(S) _{i, c}And buyer information decryption key SK^(B) _{i, c}Must not be analogized. Such a key can be generated as follows as a format that can be used for ElGamal (Ergamal) encryption, which is a kind of public key encryption.
(Equation 2)

In the above, g, r, and α are public values, and p and q are large prime numbers that satisfy p−1 | qL (L ≧ 2l). Note that “|” indicates a divisor relationship, and indicates that (p−1) divides qL. Further, α is the L-th root on mod p (the remainder of p), r is a random number on the group whose order on mod p is q, and g is the generator of the group whose order is p. Note that the order q is the number of elements in a group that becomes 1 when raised to the power q. The generator is a number such that all elements of the group are represented by powers of the values.
[0028]
Also, Sell Counter C^(S) _iAnd buy counter C^(B) _iIs a random number r corresponding to the price i_iIs calculated using the following.
(Equation 3)

Seller U_STerminal device 3a has the desired price P_SSell Order Information O_SIs issued, the result of the sell order subprotocol described later, the desired price P_Sof
(Equation 4)

(Hereinafter, "Sell counter C^(S) _PS")).
(Equation 5)

(Hereinafter, "buyer information decryption key SK^(B) _{PS, c}"). And seller U_STerminal device 3a has the desired price P_Sof
(Equation 6)

Is transmitted from the market server 1 by the broadcast sub-protocol described later, the buyer information decryption key SK^(B) _{PS, c}, And the matched electronic money m can be received. Similarly, buyer U_BTerminal device 4a has the desired price P_BBuy order information O_BIs issued, as a result of the buy order subprotocol described later, the desired price P_Bof
(Equation 7)

(Hereafter, "Buy Counter C^(B) _PB")).
(Equation 8)

(Hereinafter, "Seller information decryption key SK^(S) _{PB, c}"). And the buyer U_BTerminal device 4a has the desired price P_Bof
(Equation 9)

Is transmitted from the market server 1 by the broadcast sub-protocol described later, the seller information decryption key SK^(S) _{PB, c}, And the matched electronic stock certificate d can be received.
[0029]
4.2 Basic Protocol
Here, consider a protocol that assumes that the market M is a reliable organization, that is, that the market server 1 is reliable, that all private information is not disclosed, and that there is no falsification.
(1) Setup
First, a procedure for setting up the market M will be described. FIG. 2 is a diagram showing a procedure for setting up the market M.
Before the market M is opened, the market server 1 stores all the buy counters C owned by itself.^(B) _iAnd Sell Counter C^(S) _iAre initialized to have the same value for the same price i. That is, the market server 1 generates a random number r for all prices i (1 ≦ i ≦ l)._iIs generated, and a counter is set by the following equation.
(Equation 10)

In FIG. 2, sell counter C for price 1^(S) ₁And buy counter C^(B) ₁Is a random number r₁Value "0263", the selling counter C for the price 2^(S) ₂And buy counter C^(B) ₂Is a random number r₂Value of “0428”, the selling counter C for the price i^(S) _iAnd buy counter C^(B) _iIs a random number r_iValue "8742", the selling counter C for the price l-1^(S) _l-1And buy counter C^(B) _l-1Is a random number r_l-1To the value "1327" and the selling counter C for the price l^(S) _lAnd buy counter C^(B) _lIs a random number r_lIs initialized to the value “2582”. Further, the market server 1 initializes the contents of the database 2-1 and the database 2-2.
[0030]
(2) Sell order subprotocol
Here, seller U_SOrder information O from the terminal device 3a of_SThe procedure of the sell order sub-protocol for receiving the "Sell Order" will be described. FIG. 3 is a diagram showing a procedure of the sell order sub-protocol.
Step S110:
Seller U_STerminal device 3a has a desired price of P_SSelling order information O of electronic stock certificate d_STo the market M. That is, seller U_STerminal device 3a has the desired price P_SShow
(Equation 11)

(Hereinafter, "Price information X^(PS)"). Price information X indicating price i^(I)Is an element X indicating each price^(I) _kSet ｛X of (1 ≦ k ≦ l)^(I) ₁, X^(I) ₂,. . . , X^(I) _l要素 and an element X where k = i^(I) _kIs set to “1” only for the element X other than k = i^(I) _kIs set to "0". Therefore, the desired price P_SPrice information X indicating^(PS)Is generated as follows.
(Equation 12)

Then, the terminal device 3a receives the price information X^(PS)And order information O consisting of electronic stock certificate d_SIs transmitted to the market server 1.
[0031]
Step S120:
Market server 1 is seller U_SOrder information O received from the terminal device 3a of_SVerify the validity of That is, the market server 1 transmits the price information X^(PS)Inside
(Equation 13)

Among them, it is verified that “1” is set for only one and “0” is set for all others. And "1" is set
[Equation 14]

By the seller U_SDesired price P_SGet.
[0032]
Step S130, step S135:
Market server 1 is a seller U_SDesired price P_SSell counter C corresponding to^(S) _PSFrom the current value c of
[Equation 15]

(Hereinafter, "Seller information encryption key PK^(S) _{PS, c}") (Step S130) and a buyer information decryption key SK for decrypting the matching electronic money m.^(B) _{PS, c}And (Step S135) are created by (Equation 2).
[0033]
Step S140:
The market server 1 converts the electronic stock certificate d into the seller information encryption key PK.^(S) _{PS, c}To encrypt.
(Equation 16)

Note that the left side EE transmits the electronic stock certificate d to the seller information encryption key PK.^(S) _{PS, c}2 shows the result of encryption using. The market server 1 stores the encrypted electronic stock certificate EE in the database 2-1.
[0034]
Step S150:
The market server 1 determines the buyer information decryption key SK created in step S135.^(B) _{PS, c}The seller U_STo the terminal device 3a.
[0035]
Step S160:
The market server 1 has the desired price P_SSell counter C corresponding to^(S) _PSUpdate the value of. That is, by executing the following equation, the desired price P_SSell counter C of price i corresponding to^(S) _iOnly the desired price P_SSell counter C with price i different from^(S) _iKeep the value as it is. Note that the random number r_iIs the selling counter C during setup^(S) _iRandom number r used to initialize_iIs the same as
[Equation 17]

[0036]
(3) Buy order sub-protocol
Next, buyer U_BOrder information O from the terminal device 4a of_BWill be described below.
Step S210:
Buyer U_BIs the terminal device 4a, the desired price is P_BOrder information O for electronic stock certificate d_BTo the market M. That is, buyer U_BTerminal device 4a has the desired price P_BShow
(Equation 18)

(Hereinafter, "Price information X^(PB)) Is set as follows.
[Equation 19]

Then, the terminal device 4a receives the price information X^(PB)And order information O consisting of electronic money m_BIs transmitted to the market server 1.
[0037]
Step S220:
The market server 1 receives the buy order information O_BVerify the validity of That is, first, the market server 1 stores the face value of the electronic money m and the price information X.^(PB)Desired price P_BVerify the integrity of Furthermore, price information X^(PB)Is verified by the same method as the sell order sub-protocol (step S120).
[0038]
Step S230, Step S235:
Market server 1 is a buyer U_BDesired price P_BBuy counter C corresponding to^(B) _PBTo encrypt the electronic money m from the current value c of
(Equation 20)

(Hereinafter referred to as “buyer information encryption key PK^(B) _{PB, c}") (Step S230) and a seller information decryption key SK for decrypting the matching electronic stock certificate d.^(S) _{PB, c}And (Step S235) are created by (Equation 2).
[0039]
Step S240:
The market server 1 transmits the electronic money m to the buyer information encryption key PK.^(B) _{PB, c}To encrypt.
(Equation 21)

Here, the left-side EP stores the electronic money m with the buyer information encryption key PK.^(B) _{PB, c}2 shows the result of encryption using. The market server 1 stores the encrypted electronic money EP in the database 2-2.
[0040]
Step S250:
The market server 1 determines the seller information decryption key SK created in step S235.^(S) _{PB, c}The buyer U_BTo the terminal device 4a.
[0041]
Step S260:
The market server 1 has the desired price P_BBuy counter C corresponding to^(B) _PBUpdate the value of. That is, by executing the following equation, the desired price P_BBuy counter C of price i corresponding to^(B) _iOnly the desired price P_BBuy counter C with price i different from^(B) _iKeep the value as it is. Note that the random number r_iIs the buy counter C during setup^(B) _iRandom number r used to initialize_iIs the same as
(Equation 22)

[0042]
(4) Broadcast sub-protocol
Next, the market server 1 sells U_STerminal device 3a and buyer U_BThe procedure of a broadcast sub-protocol for broadcasting the encrypted electronic stock certificate EE and the encrypted electronic money EP to the terminal device 4a will be described. FIG. 4 is a diagram showing a procedure of the broadcast sub-protocol. It should be noted that the broadcast is executed at regular intervals.
Step S310:
The market server 1 reads the encrypted electronic stock certificate EE stored in the database 2-1 and the encrypted electronic money EP stored in the database 2-2, and all sellers U_STerminal device 3a and buyer U_BTo the terminal device 4a.
[0043]
Step S320:
Seller U_STerminal device 3a transmits all the encrypted electronic money EP received from market server 1 to buyer information decryption key SK distributed in step S150 in FIG.^(B) _{PS, c}To verify the validity of the obtained electronic money m. That is, if there is a matched electronic money m that is correctly decrypted, the seller U_SReceives the electronic money m.
[0044]
Step S325:
Similarly, buyer U_BTerminal device 4a receives all the encrypted electronic stock certificates EE received from the market server 1 by using the seller information decryption key SK distributed in step S250 of (2).^(S) _{PB, c}To verify the validity of the obtained electronic stock certificate d. That is, if there is a matched electronic stock certificate d that is correctly decrypted, the buyer U_BReceives the electronic stock certificate d.
[0045]
Here, each buyer U_BInformation decryption key SK distributed to the terminal device 4a^(S) _{i, c}Are all different, the following holds for all encrypted electronic stock certificates EE.
(Equation 23)

The left side uses the encrypted electronic stock certificate EE as the seller information decryption key SK.^(S) _{i, c}Indicates the decrypted information. That is, the seller information decryption key SK^(S) _{i, c}Buyer U with_BCan receive only the matched electronic stock certificate d.
If buyer U_BBuy order information O_BEven if there is no encrypted electronic stock EE that matches at the time of the broadcast, if the encrypted electronic stock EE that matches in the future is stored in the database 2-1, the electronic stock d that matches in the future broadcast is Obtainable.
Also, seller U_SIn the terminal device 3a, the sales order information O_SThe same applies to the case where the electronic money m that matches is received.
[0046]
5. Many-to-many matching system with distributed market servers
The secrecy of the price can be realized by distributing the functions of the market server 1 to n servers, that is, the market servers 1-1 to 1-n. Here, of the n market servers 1-1 to 1-n, t-1 (n = 2t) protocols that can withstand unauthorized use are shown as changed from the basic protocol.
FIG. 5 is a block diagram showing a configuration of a many-to-many matching system in which market servers are dispersed. In this figure, the same parts as those in FIG. 1 are denoted by the same reference numerals.
In the case where the market server 1 is distributed, the seller U_STerminal device 3b and buyer U_BTerminal device 4b uses the VSS to obtain the desired price P_SAnd desired price P_BAre distributed to the market servers 1-1 to 1-n. Further, the market servers 1-1 to 1-n have a selling counter C^(S) _iAnd buy counter C^(B) _iThe value of (hereinafter simply referred to as a counter) is secretly shared using VSS so as not to be known alone, and all operations on the counter use (t, n) threshold VSS having homomorphism. Do it. In addition, only appropriate keys are distributed using the (1, l) -OT protocol while protecting the privacy of sellers and buyers.
In the present embodiment, the seller U_STerminal device 3b and buyer U_BTerminal device 4b transmits an unauthorized order, and the market servers 1-1 to 1-n transmit the desired price P_SAnd desired price P_BIn order to prevent the user from knowing the share information, assume a share generation server 5 that generates secret-distributed price information. However, the share generation server 5 is the seller U_SAnd buyer U_BDo not manipulate any information of.
[0047]
5.1 Configuration
The share generation server 5 is connected to the market servers 1-1 to 1-n via the network N or a local network. Then, a share of the price information X that is secretly shared and corresponding to each of the market servers 1-1 to 1-n is generated for each price, and an electronic signature is given to each of the shares._SOr buyer U_BHas a function of encrypting the information using the public key and transmitting the encrypted data to the market servers 1-1 to 1-n. Further, each market server 1-1 to 1-n is a seller U_STerminal device 3b or buyer U_BOf the price information X received from the terminal device 4b received from the terminal device 4b is generated from the share of the price information X to check the validity of the price information X while keeping the price secret. -N.
[0048]
The market servers 1-1 to 1-n are servers of the market M, and the other market servers 1-1 to 1-n, the database 2-1 and the database 2-2, and the share generation via the network N or the local network. Connected to server 5. Also, the seller U via the network N_STerminal device 3b and buyer U_BTerminal device 4b.
The market servers 1-1 to 1-n correspond to the seller U_STerminal device 3b or seller U_BHas a function of receiving a request for information for placing an order from the terminal device 4b, and notifying the other market servers 1-1 to 1-n and the share generation server 5. Also, seller U_SOr buyer U_BHas the function of receiving the share of the price information X encrypted with the public key and the validity confirmation data from the share generation server 5 and storing it internally.
Further, a first divided seller information encryption key obtained by dividing the seller information encryption key by two market servers and t-2 market servers among the n market servers 1-1 to 1-n. And a second split-seller information encryption key is generated._SAnd a first partial buyer information decryption key and a second partial buyer information decryption key generated by dividing the buyer information decryption key by n market servers 1-1 to 1-n. , Seller U_SAnd a function of encrypting with a public key. Further, the seller U corresponding to all prices is obtained by (1, l) -OT._SHas the function of transmitting the share of the price information X encrypted by the public key, the first and second divided seller information encryption keys, and the first divided buyer information decryption key. Then, the share of the price information X indicating the desired price and the encrypted electronic stock certificate d are transferred to the buyer U._SA function for confirming the validity of the share of the price information X based on the electronic signature of the share generation server 5 and the validity confirmation data received from the share generation server 5 when the validity is confirmed. , The encrypted electronic stock certificate d is written into the database 2-1 and the seller U_SHas a function of transmitting the second split buyer information decryption key encrypted with the public key of (1, l) -OT.
Similarly, of n market servers 1-1 to 1-n, two market servers and t-2 market servers respectively provide first divided buyer information encryption obtained by dividing the buyer information encryption key. Key and a second split buyer information encryption key, and_BAnd a first divided seller information decryption key and a second divided seller information decryption key generated by dividing the seller information decryption key by the n market servers 1-1 to 1-n. , Buyer U_BAnd a function of encrypting with a public key. Further, the buyer U corresponding to all prices can be obtained by (1, l) -OT._BHas the function of transmitting the share of the price information X encrypted by the public key, the first and second split buyer information encryption keys, and the first split seller information decryption key. Then, the share of the price information X indicating the desired price and the encrypted electronic money m are transmitted to the seller U._BA function for confirming the validity of the share of the price information X based on the electronic signature of the share generation server 5 and the validity confirmation data received from the share generation server 5 when the validity is confirmed. , Write the encrypted electronic money m to the database 2-2, and_BHas a function of transmitting the second divided seller information decryption key encrypted with the public key of (1,1) -OT.
In addition, the encrypted electronic money m and the electronic stock d stored in the databases 2-1 and 2-2 are transferred to the buyer U._BTerminal device 3b and seller U_SAnd a function of broadcasting to the terminal device 4b.
[0049]
The databases 2-1 and 2-2 are connected to the market servers 1-1 to 1-n, and have the same functions as the databases 2-1 and 2-2 in FIG.
[0050]
The terminal device 3b is a seller U_SIs connected to the market servers 1-1 to 1-n via a network N. The terminal device 3b receives, from the market servers 1-1 to 1-n, shares of price information X corresponding to all prices encrypted with its own public key by the (1, l) -OT, and the first and second shares. Has the function of receiving the partial seller information encryption key and the first partial buyer information decryption key, and selecting and decrypting information corresponding to the desired price. Also, the seller information encryption key is restored from the first split seller information encryption key and the second split seller information encryption key corresponding to the desired price, and the electronic stock certificate d encrypted by the seller information encryption key and the desired price are restored. It has a function of transmitting the share of the corresponding price information X to the market servers 1-1 to 1-n. Further, from the market servers 1-1 to 1-n, the second partial buyer information decryption key corresponding to the entire price encrypted with its own public key by (1, l) -OT is received, and the price is changed to the desired price. It has a function of selecting and decrypting the corresponding second partial buyer information decryption key and restoring the buyer information decryption key corresponding to the desired price from the first and second partial buyer information decryption keys. Then, the encrypted buyer U broadcasted from the market servers 1-1 to 1-n_BHas the function of decrypting the electronic money m with the restored buyer information decryption key and receiving the matching electronic money m.
[0051]
The terminal device 4b is connected to the buyer U_BIs connected to the market servers 1-1 to 1-n via a network N. The terminal device 4b receives, from the market servers 1-1 to 1-n, shares of price information X corresponding to all prices encrypted with its own public key using (1, l) -OT, and first and second shares. Has the function of receiving the partial buyer information encryption key and the first partial seller information decryption key, and selecting and decrypting information corresponding to the desired price. Also, the buyer information encryption key is restored from the first partial buyer information encryption key and the second partial buyer information encryption key corresponding to the desired price, and the electronic money m encrypted with the buyer information encryption key and the desired price are restored. It has a function of transmitting the share of the corresponding price information X to the market servers 1-1 to 1-n. Further, from the market servers 1-1 to 1-n, the second divisional seller information decryption key corresponding to all prices encrypted with its own public key by (1, l) -OT is received, and the price is changed to the desired price. It has a function of selecting and decrypting the corresponding second divided seller information decryption key, and restoring the seller information decryption key corresponding to the desired price from the first and second divided seller information decryption keys. Then, the encrypted seller U broadcasted from the market servers 1-1 to 1-n_SHas the function of decrypting the electronic stock certificate d with the restored seller information decryption key and receiving the matching electronic stock certificate d.
[0052]
5.2 Operation of many-to-many matching system with distributed market servers
(1) Setup
Each of the market servers 1-1 to 1-n has a selling counter C secretly shared by VSS.^(S) _iAnd buy counter C^(B) _i(1 ≦ i ≦ l) is stored. Then, in the initialization of the counter, each of the market servers 1-1 to 1-n jointly performs the random number r for all prices i (1 ≦ i ≦ l)._iIs generated, and initialization shown in (Equation 10) is performed.
In addition, all the buying counters C^(B) _iAnd Sell Counter C^(S) _iAre constantly distributed among the market servers 1-1 to 1-n, and the original counter value cannot be known for t or less of the market servers 1-1 to 1-n. Random number r_iAre also distributed among all market servers 1-1 to 1-n.
[0053]
(2) Sell order sub-protocol
FIG. 6 shows a procedure of a sell order subprotocol in a many-to-many matching system in which market servers are distributed.
Step S510:
Seller U_STerminal device 3b requests information for performing a sell order from any of the market servers 1-1 to 1-n, and any of the market servers 1-1 to 1-n that has received the request transmits the remaining information. This request is transferred to the market servers 1-1 to 1-n and the share generation server 5. Or seller U_SThe terminal device 3b may request the share generation server 5 for information for performing a sell order, and the share generation server 5 may transfer the request to the market servers 1-1 to 1-n.
[0054]
Step S515:
All market servers 1-1 to 1-n use the seller information encryption key PK^(S) _{i, c}Are generated so that they cannot be known, the market servers 1-1 to 1-n use two market servers and (t-2) market servers to perform the seller information encryption key PK.^(S) _{i, c}Is divided into a first divided seller information encryption key and a second divided seller information encryption key.
Sell counter C for price i held by market servers 1-1 to 1-n in a secret sharing manner^(S) _iThe current value of_i(Hereinafter, the “sell counter current value c_i"), The current value c of the selling counter held by the j-th market server 1-j_iShare of c_{i, j}(Hereinafter, "share c of the current value of the selling counter c_{i, j}"). As shown in (Equation 2) in section 4.1, the seller information encryption key PK^(S) _{i, c}Is
[Equation 24]

be equivalent to. on the other hand,
(Equation 25)

Holds. Here, λj is a Lagrange's interpolation coefficient used for restoring secret sharing. Therefore,
(Equation 26)

Holds.
Therefore, among the market servers 1-1 to 1-n, each of t market servers (here, the market server 1-j (1 ≦ j ≦ t)) has a total price i (1 ≦ i ≦ l) random number r generated in the setup_iFrom the share c of the current value of each selling counter_{i, j}Against
[Equation 27]

Is calculated locally. The two market servers (here, the market servers 1-1 and 1-2) are jointly used,
[Equation 28]

Is calculated. Then, the calculated first split seller information encryption key PK^{(S), (1)} _{i, c}The seller U_SPublic key PkU_SFor all prices i (1 ≦ i ≦ l)
(Equation 29)

Is calculated. Note that Enc <key> (mes) indicates that the message mes is encrypted with the public key. On the other hand, the remaining t-2 market servers and the market servers 1-3 to 1-t are respectively
[Equation 30]

To encrypt. The market servers 1-3 to 1-t jointly
[Equation 31]

Is calculated for all prices i (1 ≦ i ≦ l).
[0055]
Step S520:
The share generation server 5 is a seller U_STerminal device 3b has price information X^(PS)Order information O while keeping secret_SInformation X used to transmit the price to the market servers 1-1 to 1-n^(I)Are generated for all prices (1 ≦ i ≦ l), and the market servers 1-1 to 1-n communicate with the seller U._SPrice information X from terminal device 3b^(PS)Generates validity confirmation data for confirming that the URL has been received.
First, the share generation server 5 determines that all prices i (1 ≦ i ≦ l)
(Equation 32)

Is calculated. Then, the generated price information X of all prices i^(I)Element X of^(I) _kShare x for secretly sharing (i, k {1, 2, ..., l}) to all market servers 1-j (1 ≦ j ≦ n)^(I) _{k, j}(Hereinafter, "share of price information element x^(I) _{k, j}And a digital signature of its own. Next, seller U_SPublic key PkU_SFor all i, j, k (1 ≦ i ≦ 1, 1 ≦ j ≦ n, 1 ≦ k ≦ l), the share x of the price information element with this digital certificate^(I) _{k, j}Encrypts
[Equation 33]

Get.
Subsequently, the share generation server 5 determines the share x of the price information element.^(I) _{k, j}Is used, for each price i (1 ≦ i ≦ l) of each market server 1-j (1 ≦ j ≦ n).
[Equation 34]

Is calculated. Note that “H” is a one-way hash function that is difficult to collide with, and “‖” indicates a combination.
Further, the share generation server 5 selects the random replacement π. Then, in order to keep the price secret, the hash value H of the share of the element of the price information of each price i (1 ≦ i ≦ l)^(I) _jIs shuffled using the selected π, and is the validity confirmation data of each market server 1-j (1 ≦ j ≦ n).
(Equation 35)

Get.
Finally, the share generation server 5 determines that all prices i (1 ≦ i ≦ l)
[Equation 36]

To each market server 1-j (1 ≦ j ≦ n).
[0056]
Step S525:
Each market server 1-j (1 ≦ j ≦ n) has a current selling counter C^(S) _iShare of the current value of the sell counter of c_{i, j}Is used, the share SK of the buyer information decryption key for all prices i (1 ≦ i ≦ l)^(B) _{i, j, c}Is generated as follows.
(37)

Then, each market server 1-j (1 ≦ j ≦ n) determines the share SK of the calculated buyer information decryption key.^(B) _{i, j, c}about,
[Equation 38]

SK of the first split buyer information decryption key at random so as to satisfy^{(B), (1)} _{i, j, c}And share SK of second partial buyer information decryption key^{(B), (2)} _{i, j, c}Divided into Finally, each market server 1-j (1 ≦ j ≦ n) sets the share SK of the first partial buyer information decryption key.^{(B), (1)} _{i, j, c}And share SK of second partial buyer information decryption key^{(B), (2)} _{i, j, c}, The seller U_SPublic key of PkU_S, And encrypts the entire price i (1 ≦ i ≦ l).
[Equation 39]

(Equation 40)

Get.
[0057]
Step S530:
Each market server 1-j (1 ≦ j ≦ n) works together with the seller U_SOf all prices i (1 ≦ i ≦ l) for the terminal device 3b
(Equation 41)

(1, l) -OT of (1) is executed. In this OT, seller U_STerminal device 3b, the price i is the desired price P_SMatches
(Equation 42)

(Hereafter, “Order generation information DK_PS]) Only).
[0058]
Step S535:
FIG. 7 shows a continuation of the sell order subprotocol procedure in the many-to-many matching system in which the market server shown in FIG. 6 is distributed.
Seller U_STerminal device 3b, the price i is the desired price P_SOrder generation information DK that matches_PSIf you select, the desired price P_SFirst split seller information encryption key EPK^{(S), (1)} _{i, c}(I = P_S) And an encrypted second partial seller information encryption key EPK^{(S), (2)} _{i, c}(I = P_S) With the public key PkU_SDecrypted by the secret key corresponding to. here,
[Equation 43]

Otherwise, seller U_SThe terminal device 3b of the first decrypted first partial seller information encryption key PK^{(S), (1)} _{i, c}(I = P_S) And a second partial seller information encryption key PK^{(S), (2)} _{i, c}= (A₃, ..., a_t) (I = P_S) From the desired price P_SSeller information encryption key PK^(S) _{PS, c}To reconfigure.
[Equation 44]

[0059]
Step S540:
Seller U_SOf the desired price P calculated in step S535_SInformation encryption key PK corresponding to^(S) _{PS, c}Encrypts the electronic stock certificate d by
[Equation 45]

Is calculated.
[0060]
Step S545:
Seller U_STerminal device 3b has the desired price P_Sof
[Equation 46]

All the terms of the public key PkU_SDecrypted by the secret key corresponding to. And the desired price P_SOf all j, k (1 ≦ j ≦ n, 1 ≦ k ≦ l) corresponding to
[Equation 47]

(Hereinafter, "share of price information element x^(PS) _{k, j}").
[0061]
Step S550:
Seller U_STerminal device 3b has the desired price P_SSeller information encryption key PK^(S) _{PS, c}Electronic certificate EE and desired price P_SShare of price information element x^(PS) _{k, j}(1 ≦ k ≦ l) is transmitted to all corresponding market servers 1-j (1 ≦ j ≦ n).
[0062]
Step S555:
Each market server 1-j (1 ≦ j ≦ n) has a share x of an element of price information.^(PS) _{k, j}The validity of the digital signature of the share generation server 5 attached to (1 ≦ k ≦ l) is confirmed. Subsequently, each market server 1-j (1 ≦ j ≦ n) sends all desired prices P_SShare of price information element x^(PS) _{k, j}Is generated from the concatenated value of, and received from the share generation server 5 in step S520.
[Equation 48]

Make sure it is equal to one of
[0063]
Step S560:
The market servers 1-1 to 1-n correspond to the seller U_SThe encrypted electronic stock certificate EE received from the terminal device 3b is stored in the database 2-1. Then, the market servers 1-1 to 1-n use the (1, l) -OT and_STo the terminal device 3b of
[Equation 49]

Send
[0064]
Step S565:
All the market servers 1-1 to 1-n jointly operate as a selling counter C as follows.^(S) _iTo update.
[Equation 50]

[0065]
Step S570:
Seller U_STerminal device 3b, the price i is the desired price P_SMatches
(Equation 51)

(Hereinafter, “encrypted second partial buyer information decryption key ESK^{(B), (2)} _{PS, c}"). Then, the encrypted second divided buyer information decryption key ESK^{(B), (2)} _{PS, c}With the public key PkU_SIs decrypted using the secret key corresponding to_Sof
(Equation 52)

(Hereinafter, "share SK of second partial buyer information decryption key"^{(B), (2)} _{PS, j, c}"). Further, the desired price P selected in step S530_SOrder generation information DK corresponding to_iOf the first divided buyer information decryption key ESK^{(B), (1)} _{i, c}From the public key PkU_SDesired price P using the secret key corresponding to_Sof
(Equation 53)

(Hereinafter, "Share SK of first partial buyer information decryption key"^{(B), (1)} _{PS, j, c}"). Seller U_SThe terminal device 3b of the third share SK of the decrypted first partial buyer information decryption key^{(B), (1)} _{PS, j, c}And share SK of second partial buyer information decryption key^{(B), (2)} _{PS, j, c}From the buyer information decryption key SK^(B) _{PS, c}To restore.
[0066]
(3) Buy order sub-protocol and broadcast sub-protocol
The buy order sub-protocol is performed in the same manner as the sell order sub-protocol shown in (2) of this section. The broadcast subprotocol is the same as the broadcast subprotocol described in (4) of the basic protocol in section 4.2. The broadcast may be performed by any of the market servers 1-1 to 1-n.
[0067]
6. Other
According to the above-described embodiment, a many-to-many matching system that satisfies the validity of data exchange, confidentiality of data, confidentiality of desired price, anonymity, and robustness while suppressing communication cost and calculation cost. Can be provided.
The above-described market server 1, market servers 1-1 to 1-n, database 2-1 and database 2-2, terminal devices 3a and 3b, terminal devices 4a and 4b, and share generation server 5 It has a computer system inside. The above-described process of the operation is stored in a computer-readable recording medium in the form of a program, and the computer system reads and executes the program to perform the above-described processing. Here, the computer system includes an OS and hardware such as peripheral devices.
[0068]
The “computer-readable recording medium” refers to not only ROM but also portable media such as magnetic disks, magneto-optical disks, CD-ROMs, and DVD-ROMs, and storage devices such as hard disks built into computer systems. That means. Further, the “computer-readable recording medium” is a system such as a volatile memory (RAM) in a computer system which is a client when a program is transmitted through a network such as the Internet or a communication line such as a telephone line. In addition, those that hold programs for a certain period of time are also included.
[0069]
Further, the above program may be transmitted from a computer system storing the program in a storage device or the like to another computer system via a transmission medium or by a transmission wave in the transmission medium. Here, the “transmission medium” for transmitting a program refers to a medium having a function of transmitting information, such as a network (communication network) such as the Internet or a communication line (communication line) such as a telephone line.
Further, the program may be for realizing a part of the functions described above. Furthermore, what can implement | achieve the function mentioned above in combination with the program already recorded on the computer system, and what is called a difference file (difference program) may be sufficient.
[0070]
【The invention's effect】
According to the present invention, communication costs and calculation costs are suppressed, and even if the reliability of each server is not high, a specific market operator who is strong against fraud and has malicious intent can provide privacy and money such as a desired price of a seller and a buyer. While preventing the acquisition of valuable digital information, it performs many-to-many matching of seller and buyer orders, and securely delivers digital information of financial value between matched sellers and buyers. It is possible to construct a many-to-many matching system and service for exchanging and redeeming the money.
[Brief description of the drawings]
FIG. 1 is a block diagram showing a configuration of a many-to-many matching system according to an embodiment of the present invention.
FIG. 2 is a diagram showing a procedure for setting up a market M according to the embodiment.
FIG. 3 is a diagram showing a procedure of a sell order sub-protocol according to the embodiment.
FIG. 4 is a diagram showing a procedure of a broadcast sub-protocol according to the embodiment.
FIG. 5 is a block diagram showing a configuration of a many-to-many matching system in which market servers are distributed.
FIG. 6 is a diagram showing a procedure of a sell order subprotocol according to the configuration of FIG. 5;
FIG. 7 is a diagram showing a continuation of the procedure of the sell order sub-protocol of FIG. 6;
[Explanation of symbols]
1,1-1,1-2,1-3,1-t, 1-n ... market server
2-1, 2-2 ... Database
3a, 3b, 4a, 4b ... terminal device
5 ... Share generation server

Claims (13)

A terminal device of the orderer, a share generation server for generating a share of price information indicating the desired price of the orderer, and valuable digital information that is valuable digital information between the orderers indicating the matching desired price. A many-to-many matching system in which an intermediate market server is connected via a network,
The share generation server,
A share generation means for generating and transmitting a share of the price information secretly shared corresponding to each market server for each price,
The market server is:
Key generation means for generating an encryption key for encrypting the orderer's valuable digital information, and a decryption key for decrypting the orderer's valuable digital information indicating a matching desired price;
Order generation information transmission means for transmitting the encryption key and the decryption key generated by the key generation means to the terminal device of the orderer;
Order receiving means for receiving share of price information indicating a desired price and valuable digital information of the orderer encrypted by an encryption key corresponding to the desired price from a terminal device of the orderer;
Periodically comprising broadcast means for broadcasting the encrypted digital information of the orderer received by the order receiving means to the terminal devices of all the orderers,
The orderer's terminal device,
Receiving means for receiving an encryption key, a decryption key, and a share of price information corresponding to all prices, and selecting an encryption key, a decryption key, and a share of price information corresponding to a desired price from among them,
Order information transmitting means for transmitting valuable digital information encrypted by the selected encryption key and a share of price information corresponding to the desired price to the market server;
Decoding means for decoding encrypted valuable digital information broadcast from the market server using the decryption key, and receiving matching valuable digital information.
A many-to-many matching system. This is a many-to-many matching system in which a terminal device of an orderer and a market server that mediates valuable digital information, which is valuable digital information, between the orderers who have indicated a matching desired price are connected via a network. hand,
The market server is:
A key for generating an encryption key for encrypting the orderer's valuable digital information and a decryption key for decrypting the orderer's valuable digital information indicating the matching desired price, and encrypting with the orderer's key Generating means;
Order generation for transmitting the encryption key and the decryption key encrypted by the key of the orderer and the share of the price information encrypted by the key of the orderer to the terminal device of the orderer for all prices. Information transmission means;
Order receiving means for receiving share of price information indicating a desired price and valuable digital information of the orderer encrypted by an encryption key corresponding to the desired price from a terminal device of the orderer;
Periodically comprising broadcast means for broadcasting the encrypted digital information of the orderer received by the order receiving means to the terminal devices of all the orderers,
The orderer's terminal device,
An encrypted encryption key, decryption key, and share of price information corresponding to all prices are received from the market server, and an encryption key, decryption key, and share of price information corresponding to a desired price are received by the own key. Receiving means for selecting and decoding
Order information transmitting means for transmitting valuable digital information encrypted with the decrypted encryption key and a share of price information corresponding to the desired price to the market server;
Decoding means for decoding encrypted valuable digital information broadcast from the market server using the decryption key, and receiving matching valuable digital information.
A many-to-many matching system. A terminal device of the orderer, a share generation server for generating a share of price information indicating the desired price of the orderer, and valuable digital information that is valuable digital information between the orderers indicating the matching desired price. A many-to-many matching system in which an intermediate market server is connected via a network,
The share generation server,
A share generation means for generating a share of secretly distributed price information corresponding to each market server for each price, encrypting it with the orderer's key, and transmitting it to each market server,
The market server is:
Share receiving means for receiving, from the share generation server, a share of price information corresponding to all prices encrypted by the orderer's key,
Encryption key generating means for generating a first divided encryption key and a second divided encryption key by dividing an encryption key for encrypting valuable digital information of an orderer and encrypting the divided keys with the orderer's key; ,
A decryption key for generating a first partial decryption key and a second partial decryption key, which are obtained by dividing a decryption key for decrypting valuable digital information of an orderer who has indicated a matching desired price, and encrypting the decryption key with the orderer's key Generating means;
Order generation for transmitting the encrypted first divided encryption key, the second divided encryption key, the first divided decryption key, and the share of price information corresponding to all prices to the terminal device of the orderer Information transmission means;
A share of price information indicating a desired price and valuable digital information of the orderer encrypted with an encryption key corresponding to the desired price are received from the terminal device of the orderer, and the encrypted second information corresponding to all prices is received. Order receiving means for returning the divided decryption key of 2,
Periodically comprising broadcast means for broadcasting the encrypted digital information of the orderer received by the order receiving means to the terminal devices of all the orderers,
The orderer's terminal device,
A first divided encryption key, a second divided encryption key, a first divided decryption key, and a share of price information corresponding to all prices are received from the market server, and a desired price is obtained using its own key. Receiving means for selecting and decrypting a first divided encryption key, a second divided encryption key, a first divided decryption key, and a share of price information corresponding to
A seller information encryption key corresponding to a desired price is restored from the first divided encryption key and the second divided encryption key, and valuable digital information encrypted with the encryption key and a share of price information corresponding to the desired price are obtained. Order information transmitting means for transmitting to the market server,
Receiving an encrypted second divided decryption key corresponding to all prices from the market server, selecting a second divided decryption key corresponding to a desired price, decrypting the selected second decryption key with its own key, Key restoration means for restoring the decryption key corresponding to the desired price together with the decryption key;
Decoding means for decrypting the encrypted valuable digital information of the buyer broadcasted from the market server using the decryption key, and receiving matching valuable digital information,
A many-to-many matching system. Many-to-many matching in which a terminal device of a seller and a buyer is connected to a market server that mediates valuable digital information, which is valuable digital information between the seller and the buyer who has indicated a desired price, via a network The system
The market server is:
A seller information encryption key for encrypting the seller's valuable digital information and a buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price are generated and encrypted with the seller's key. First key generation means;
The first key generation means transmits the seller information encryption key and the buyer information decryption key encrypted with the seller key and the share of the price information encrypted with the seller key to the seller terminal device for all prices. First order generation information transmitting means for transmitting;
A buyer information encryption key for encrypting the buyer's valuable digital information and a seller information decryption key for decrypting the seller's valuable digital information indicating the matching desired price are generated and encrypted with the buyer's key. Second key generation means;
The buyer information encryption key and the seller information decryption key encrypted by the second key generation means with the buyer key and the share of the price information encrypted by the buyer key are transmitted to the buyer terminal device for all prices. Second order generation information transmitting means for transmitting;
Selling order receiving means for receiving, from the terminal device of the seller, valuable digital information of the seller encrypted by the share of price information indicating the desired price and the seller information encryption key corresponding to the desired price,
Buy order receiving means for receiving share of price information indicating a desired price and valuable digital information of the buyer encrypted by a buyer information encryption key corresponding to the desired price from the terminal device of the buyer,
Broadcast means for periodically broadcasting the encrypted valuable digital information of the buyer and the seller to terminal devices of the buyer and the seller,
The terminal device of the seller,
Receives the encrypted seller information encryption key, buyer information decryption key, and price information share corresponding to all prices from the market server, and uses its own key to encrypt the seller information encryption key and buyer information corresponding to the desired price. Receiving means for selecting and decrypting a key and a share of price information;
Selling order information transmitting means for transmitting valuable digital information encrypted with the decrypted seller information encryption key and a share of price information corresponding to the desired price to the market server,
Decrypting the encrypted buyer's valuable digital information broadcasted from the market server with the buyer information decryption key, and receiving matching valuable digital information;
The terminal device of the buyer,
Receives the encrypted buyer information encryption key, seller information decryption key, and price information share corresponding to all prices from the market server, and uses its own key to acquire the buyer information encryption key and seller information decryption corresponding to the desired price. Receiving means for selecting and decrypting a key and a share of price information;
Buy order information transmitting means for transmitting valuable digital information encrypted with the decrypted buyer information encryption key and a share of price information corresponding to the desired price to the market server,
Decrypting the encrypted seller's valuable digital information broadcasted from the market server with the seller information decryption key, and receiving matching valuable digital information;
A many-to-many matching system. A terminal device of a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating a matching desired price. A many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
The share generation server,
A share generation unit that generates a share of secretly distributed price information corresponding to each market server for each price, encrypts the information with a seller or buyer key, and transmits the encrypted information to each market server,
The market server is:
A database for storing encrypted valuable digital information,
Sell and Buy counters corresponding to the price and taking the same initial value for the matching price;
From the share generation server, share receiving means for receiving a share of price information corresponding to all prices encrypted by the seller or buyer key,
Based on the selling counter, a first divided seller information encryption key and a second divided seller information encryption key obtained by dividing a seller information encryption key for encrypting valuable digital information of a seller are generated in a distributed manner. First encryption key generation means for encrypting with the key of
Based on the buy counter, a first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing a buyer information encryption key for encrypting valuable digital information of a buyer are generated in a distributed manner. Second encryption key generation means for encrypting with the key of
Based on the sell counter, a first partial buyer information decryption key and a second partial buyer information decryption key are generated by dividing the buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price. And a first decryption key generating means for encrypting with the seller's key;
Based on the buy counter, a first divided seller information decryption key and a second divided seller information decryption key are generated by dividing a seller information decryption key for decrypting valuable digital information of a seller indicating a matching desired price. And a second decryption key generation means for encrypting with the buyer's key;
The terminal device of the seller is used to share the encrypted first split seller information encryption key, the second split seller information encryption key, the first split buyer information decryption key, and the share of price information corresponding to all prices. First order generation information transmitting means for transmitting to the
A share of price information indicating a desired price and valuable digital information encrypted by a seller information encryption key corresponding to the desired price are received from the terminal device of the seller, and the encrypted valuable digital information is written to the database. Selling order receiving means for returning the encrypted second partial buyer information decryption key corresponding to all prices;
The share of the first partial buyer information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the share of the price information corresponding to the entire price is transmitted to the terminal of the buyer. Second order generation information transmitting means for transmitting to the device;
A share of price information indicating a desired price and valuable digital information encrypted by a buyer information encryption key corresponding to the desired price are received from the buyer's terminal device, and the encrypted valuable digital information is written to the database. And a purchase order receiving means for returning the encrypted second partial seller information decryption key corresponding to all prices;
Counter updating means for updating the sell counter or the buy counter using a random number,
Periodically, broadcasting means for broadcasting encrypted digital information of buyers and sellers stored in the database to terminal devices of buyers and sellers,
The terminal device of the seller,
Receiving, from the market server, a first divided seller information encryption key, a second divided seller information encryption key, a first divided buyer information decryption key, and a share of price information corresponding to all prices; Receiving means for selecting and decrypting a first divided seller information encryption key, a second divided seller information encryption key, a first divided buyer information decryption key, and a share of price information corresponding to a desired price with its own key When,
A seller information encryption key corresponding to the desired price is restored from the first split seller information encryption key and the second split seller information encryption key, and the valuable digital information encrypted with the seller information encryption key and the desired price corresponding to the desired price are restored. Selling order information transmitting means for transmitting the share of the price information to the market server,
Receiving an encrypted second partial buyer information decryption key corresponding to all prices from the market server, selecting a second partial buyer information decryption key corresponding to the desired price, and decrypting the same using its own key; Key restoring means for restoring the buyer information decryption key corresponding to the desired price together with the first split buyer information decryption key;
Decrypting the encrypted buyer's valuable digital information broadcasted from the market server with the buyer information decryption key, and receiving matching valuable digital information;
The terminal device of the buyer,
Receiving, from the market server, a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to all prices; Receiving means for selecting and decrypting a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to a desired price with its own key When,
A buyer information encryption key corresponding to a desired price is restored from the first split buyer information encryption key and the second split buyer information encryption key, and the valuable digital information encrypted with the buyer information encryption key and the desired price are restored. Buy order information transmitting means for transmitting the share of the price information to the market server,
Receiving an encrypted second partial seller information decryption key corresponding to all prices from the market server, selecting a second partial seller information decryption key corresponding to the desired price, and decrypting the same with its own key; Key restoration means for restoring the seller information decryption key corresponding to the desired price together with the first split seller information decryption key;
Decrypting the encrypted seller's valuable digital information broadcasted from the market server with the seller information decryption key, and receiving matching valuable digital information;
A many-to-many matching system. The share generating means generates validity check data from each of the market information servers to confirm that the share of the price information received from the terminal device of the seller or the buyer is valid from the share of the price information, and conceals the price. And send it to the market server,
The selling order receiving means, based on the validity confirmation data received from the share generation server, determines that the share of the price information received from the terminal device of the seller is valid, the encrypted second Returns the split buyer information decryption key of
The buy order receiving means, based on the validity confirmation data received from the share generation server, determines that the share of the price information received from the terminal device of the buyer is valid, and Return the split seller information decryption key of
The many-to-many matching system according to claim 5, wherein: 7. The method according to claim 5, wherein the seller information encryption key, the buyer information encryption key, the seller information decryption key, and the buyer information decryption key are generated by a public key encryption method. Many-to-many matching system. A terminal device of the seller and the buyer, a share generation server for generating a share of price information indicating the desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating the matching desired price. A market server of a many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
A database for storing encrypted valuable digital information,
Sell and Buy counters corresponding to the price and taking the same initial value for the matching price;
From the share generation server, share receiving means for receiving a share of price information secretly shared corresponding to each market server encrypted with a seller or buyer key,
Based on the selling counter, a first divided seller information encryption key and a second divided seller information encryption key obtained by dividing a seller information encryption key for encrypting valuable digital information of a seller are generated in a distributed manner. First encryption key generation means for encrypting with the key of
Based on the buy counter, a first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing a buyer information encryption key for encrypting valuable digital information of a buyer are generated in a distributed manner. Second encryption key generation means for encrypting with the key of
Based on the sell counter, a first partial buyer information decryption key and a second partial buyer information decryption key are generated by dividing the buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price. And a first decryption key generating means for encrypting with the seller's key;
Based on the buy counter, a first divided seller information decryption key and a second divided seller information decryption key are generated by dividing a seller information decryption key for decrypting valuable digital information of a seller indicating a matching desired price. And a second decryption key generation means for encrypting with the buyer's key;
The terminal device of the seller is used to share the encrypted first split seller information encryption key, the second split seller information encryption key, the first split buyer information decryption key, and the share of price information corresponding to all prices. First order generation information transmitting means for transmitting to the
A share of price information indicating a desired price and valuable digital information encrypted by a seller information encryption key corresponding to the desired price are received from the terminal device of the seller, and the encrypted valuable digital information is written to the database. Selling order receiving means for returning the encrypted second partial buyer information decryption key corresponding to all prices;
The share of the first partial buyer information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the share of the price information corresponding to the entire price is transmitted to the terminal of the buyer. Second order generation information transmitting means for transmitting to the device;
A share of price information indicating a desired price and valuable digital information encrypted by a buyer information encryption key corresponding to the desired price are received from the buyer's terminal device, and the encrypted valuable digital information is written to the database. And a purchase order receiving means for returning the encrypted second partial seller information decryption key corresponding to all prices;
Counter updating means for updating the sell counter or the buy counter using a random number,
Periodically, broadcasting means for broadcasting the encrypted valuable digital information of the buyer and the seller stored in the database to terminal devices of the buyer and the seller,
A market server comprising: A terminal device of the seller and the buyer, a share generation server for generating a share of price information indicating the desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating the matching desired price. A terminal device of a seller of a many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
The first divided seller information encryption key and the second divided seller information encryption key obtained by dividing the seller information encryption key for encrypting the seller's valuable digital information, and the buyer's valuable digital information indicating the desired price that matches. A ciphertext of a first divided buyer information decryption key obtained by dividing a buyer information decryption key for decryption and a share of price information secretly shared corresponding to each market server is received from the market server for all prices. Receiving a decryption by selecting a first partial seller information encryption key, a second partial seller information encryption key, a first partial buyer information decryption key, and a share of price information corresponding to a desired price with its own key; Means,
A seller information encryption key corresponding to the desired price is restored from the first split seller information encryption key and the second split seller information encryption key, and the valuable digital information encrypted with the seller information encryption key and the desired price corresponding to the desired price are restored. Selling order information transmitting means for transmitting the share of the price information to the market server,
Receiving an encrypted second partial buyer information decryption key corresponding to all prices from the market server, selecting a second partial buyer information decryption key corresponding to the desired price, and decrypting the same using its own key; Key restoring means for restoring the buyer information decryption key corresponding to the desired price together with the first split buyer information decryption key;
Decoding means for decoding the encrypted valuable digital information of the buyer broadcasted from the market server by the buyer information decryption key, and receiving matching valuable digital information;
A seller's terminal device comprising: A terminal device of the seller and the buyer, a share generation server for generating a share of price information indicating the desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating the matching desired price. A terminal device of a buyer of a many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
The first divided buyer information encryption key and the second divided buyer information encryption key obtained by dividing the buyer information encryption key for encrypting the buyer's valuable digital information, and the buyer's valuable digital information indicating the matching desired price are obtained. A ciphertext of a first divided seller information decryption key obtained by dividing a seller information decryption key for decryption and a share of price information secretly shared corresponding to each market server is received from the market server for all prices. Receiving a decryption by selecting a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to a desired price with its own key; Means,
A buyer information encryption key corresponding to a desired price is restored from the first split buyer information encryption key and the second split buyer information encryption key, and the valuable digital information encrypted with the buyer information encryption key and the desired price are restored. Buy order information transmitting means for transmitting the share of the price information to the market server,
Receiving an encrypted second partial seller information decryption key corresponding to all prices from the market server, selecting a second partial seller information decryption key corresponding to the desired price, and decrypting the same with its own key; Key restoration means for restoring the seller information decryption key corresponding to the desired price together with the first split seller information decryption key;
Decryption means for decrypting the encrypted valuable digital information of the seller broadcasted from the market server by the seller information decryption key, and receiving matching valuable digital information;
A buyer's terminal device comprising: A terminal device of a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating a matching desired price. A computer program used for a market server of a many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
Initializing a sell counter and a buy counter corresponding to the price with the same value for the matching price;
Receiving, from the share generation server, a share of price information secretly shared corresponding to each market server encrypted with a seller or buyer key,
Based on the selling counter, a first divided seller information encryption key and a second divided seller information encryption key obtained by dividing a seller information encryption key for encrypting valuable digital information of a seller are generated in a distributed manner. Encrypting with the key of
Based on the buy counter, a first divided buyer information encryption key and a second divided buyer information encryption key obtained by dividing a buyer information encryption key for encrypting valuable digital information of a buyer are generated in a distributed manner. Encrypting with the key of
Based on the sell counter, a first partial buyer information decryption key and a second partial buyer information decryption key are generated by dividing the buyer information decryption key for decrypting the buyer's valuable digital information indicating the matching desired price. And encrypting with the seller's key;
Based on the buy counter, a first divided seller information decryption key and a second divided seller information decryption key are generated by dividing a seller information decryption key for decrypting valuable digital information of a seller indicating a matching desired price. Encrypting with the buyer's key;
The terminal device of the seller is used to share the encrypted first split seller information encryption key, the second split seller information encryption key, the first split buyer information decryption key, and the share of price information corresponding to all prices. Sending to
A share of price information indicating a desired price and valuable digital information encrypted by a seller information encryption key corresponding to the desired price are received from the seller's terminal device, and the encrypted valuable digital information is stored in its own database. And returning the encrypted second partial buyer information decryption key corresponding to all prices;
The share of the first partial buyer information encryption key, the second partial buyer information encryption key, the first partial seller information decryption key, and the share of the price information corresponding to the entire price is transmitted to the terminal of the buyer. Transmitting to the device;
A share of price information indicating a desired price and valuable digital information encrypted by a buyer information encryption key corresponding to the desired price are received from the buyer's terminal device, and the encrypted valuable digital information is written to the database. And returning the encrypted second partial seller information decryption key corresponding to all prices;
Updating the sell counter or the buy counter using a random number;
Periodically, broadcasting the valuable digital information of the buyer and seller stored in the database to the terminal device of the buyer and seller;
Computer program for causing a computer to execute the following. A terminal device of the seller and the buyer, a share generation server for generating a share of price information indicating the desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating the matching desired price. A computer program used for a terminal device of a seller of a many-to-many matching system in which a market server that mediates valuable digital information is connected via a network,
The first divided seller information encryption key and the second divided seller information encryption key obtained by dividing the seller information encryption key for encrypting the seller's valuable digital information, and the buyer's valuable digital information indicating the desired price that matches. A ciphertext of a first divided buyer information decryption key obtained by dividing a buyer information decryption key for decryption and a share of price information secretly shared corresponding to each market server is received from the market server for all prices. Selecting and decrypting a first partial seller information encryption key, a second partial seller information encryption key, a first partial buyer information decryption key, and a share of price information corresponding to a desired price with its own key. When,
A seller information encryption key corresponding to the desired price is restored from the first split seller information encryption key and the second split seller information encryption key, and the valuable digital information encrypted with the seller information encryption key and the desired price corresponding to the desired price are restored. Transmitting the share of the price information to the market server;
Receiving an encrypted second partial buyer information decryption key corresponding to all prices from the market server, selecting a second partial buyer information decryption key corresponding to the desired price, decrypting the selected partial buyer information decryption key with its own key, Restoring the buyer information decryption key corresponding to the desired price together with the first split buyer information decryption key;
Decrypting the encrypted buyer's valuable digital information broadcast from the market server with the buyer information decryption key, and receiving matching valuable digital information;
Computer program for causing a computer to execute the following. A terminal device of a seller and a buyer, a share generation server for generating a share of price information indicating a desired price of the seller or the buyer, and valuable digital information between the seller and the buyer indicating a matching desired price. A computer program used for a terminal device of a buyer of a many-to-many matching system, which is connected to a market server that mediates valuable digital information via a network,
The first divided buyer information encryption key and the second divided buyer information encryption key obtained by dividing the buyer information encryption key for encrypting the buyer's valuable digital information, and the buyer's valuable digital information indicating the desired price matched. A ciphertext of a first divided seller information decryption key obtained by dividing a seller information decryption key for decryption and a share of price information secretly shared corresponding to each market server is received from the market server for all prices. Selecting and decrypting a first partial buyer information encryption key, a second partial buyer information encryption key, a first partial seller information decryption key, and a share of price information corresponding to a desired price with its own key. When,
A buyer information encryption key corresponding to a desired price is restored from the first partial buyer information encryption key and the second partial buyer information encryption key, and the valuable digital information encrypted with the buyer information encryption key and the desired price corresponding to the desired price are restored. Transmitting the share of the price information to the market server;
Receiving an encrypted second partial seller information decryption key corresponding to all prices from the market server, selecting a second partial seller information decryption key corresponding to a desired price, decrypting the second partial seller information decryption key with its own key, Restoring the seller information decryption key corresponding to the desired price together with the first split seller information decryption key;
Decrypting the encrypted valuable digital information of the seller broadcasted from the market server with the seller information decryption key, and receiving matching valuable digital information;
Computer program for causing a computer to execute the following.

Images