(57)【要約】【課題】電子的な通信手段を介して入札を行う電子入札において、入札の談合を防止する。【解決手段】電子入札装置２において、秘密鍵を用いることにより、乱数設定手段２ｃにおいて設定された第１の乱数と、入札価格情報入力手段２ｄにおいて入力された第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成し、それを電子開札装置３に開示する。また、電子入札装置２から電子開札装置３に、専用回線４を介し、上記第１の乱数を送信する。電子開札装置３は、送られたこれらの情報を用い開札処理を行う。【選択図】　　　　図１
2004118654.tif 000002
【特許請求の範囲】
【請求項１】
入札者が電子的に入札処理を行う電子入札装置において、
秘密鍵の設定を行う秘密鍵設定手段と、
公開鍵の設定を行う公開鍵設定手段と、
入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数を設定する乱数設定手段と、
入札価格に対応する価格レベルを特定するための第１の入札価格情報の入力を受け付ける入札価格情報入力手段と、
前記乱数設定手段において設定された前記第１の乱数と、前記入札価格情報入力手段において入力された前記第１の入札価格情報とを、前記公開鍵設定手段において設定された前記公開鍵によって暗号化した暗号化情報であって、前記秘密鍵設定手段において設定された前記秘密鍵を用いることにより、前記第１の乱数と、前記第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、前記第１の乱数とは異なる第２の乱数と、前記第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成する落し戸付コミットメント生成手段と、
前記落し戸付コミットメント生成手段において生成された前記落し戸付コミットメントを開示する落し戸付コミットメント開示手段と、
前記乱数設定手段において設定された前記第１の乱数を、開札者の電子開札装置に、該開札者の電子開札装置に電気的に接続される専用回線を通じて送信する乱数送信手段と、
を有することを特徴とする電子入札装置。
【請求項２】
ゼロ知識証明によって、前記秘密鍵、及び前記落し戸付コミットメントの生成に用いられた前記第１の乱数と前記第１の入札価格情報との組み合わせ内容、を認知していることを前記開札者の電子開札装置に証明するゼロ知識証明手段をさらに有する、
ことを特徴とする請求項１記載の電子入札装置。
【請求項３】
前記第１の乱数を複数の乱数シェアに秘密分散する乱数秘密分散手段、をさらに有し、
前記乱数送信手段は、
前記乱数秘密分散手段において秘密分散された複数の前記乱数シェアを、複数の前記開札者の電子開札装置に分散させて送信する手段である、
ことを特徴とする請求項１或いは２何れかに記載の電子入札装置。
【請求項４】
前記落し戸付コミットメント開示手段は、
署名付きの前記落し戸付コミットメントを開示する手段であり、
前記乱数送信手段は、
署名付きの前記第１の乱数を送信する手段である、
ことを特徴とする請求項１から３何れかに記載の電子入札装置。
【請求項５】
落し戸付コミットメント生成手段は、
乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する前記公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する前記第１の乱数をｒ（ｓ，ｊ）とし、入札を行わない価格レベルであることを示す前記第１の入札価格情報をＭ０とし、入札を行う価格レベルであることを示す前記第１の入札価格情報をＭ１とした場合において、価格レベルｓが入札を行う価格レベルでないときには、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるときには、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、これらの演算結果を前記落し戸付コミットメントとする手段である、
ことを特徴とする請求項１から４何れかに記載の電子入札装置。
【請求項６】
開札者が電子的に開札処理を行う電子開札装置において、
入札者によって開示された落し戸付コミットメントを取得する落し戸付コミットメント取得手段と、
前記入札者の電子入札装置に電気的に接続される専用回線を通じ、該入札者の電子入札装置から送信された、入札者と複数の価格レベルとの組み合わせごとに対応付けられた乱数を受信する乱数受信手段と、
前記落し戸付コミットメント取得手段において取得された前記落し戸付コミットメントと、受信された前記乱数と、の照合を行い、該照合が成立した前記乱数に対応する価格レベルを落札価格とし、該照合が成立した前記乱数に対応する入札者を落札者とする落札決定手段と、
を有することを特徴とする電子開札装置。
【請求項７】
前記落札決定手段は、
第１の価格レベルに対応する前記乱数と、前記落し戸付コミットメントと、の照合を行った結果、該照合が不成立であった場合、該第１の価格レベルよりも値段の安い第２の価格レベルに対応する前記乱数と、前記落し戸付コミットメントと、の照合を行う手段である、
ことを特徴とする請求項６記載の電子開札装置。
【請求項８】
前記乱数を複数に秘密分散した乱数シェアの一部を受信する前記乱数受信手段と、
他の電子開札装置において受信された前記乱数シェアを取得する乱数シェア通信手段と、
前記乱数受信手段において取得された前記乱数シェアと、前記乱数シェア通信手段において取得された前記乱数シェアと、を用い、多項式補間によって、前記乱数を復元する多項式補間手段と、
を有することを特徴とする請求項６或いは７何れかに記載の電子開札装置。
【請求項９】
前記落札決定手段は、
前記落し戸付コミットメントをＣｓ，ｊとし、乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する前記乱数をｒ（ｓ，ｊ）とし、入札を行う価格レベルであることを示す入札価格情報をＭ１とした場合における、ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、該演算結果がＣｓ，ｊとなった場合には、照合が成立したものと判断する手段である、
ことを特徴とする請求項６から８何れかに記載の電子開札装置。
【請求項１０】
入札者が電子的に入札処理を行う電子入札方法において、
秘密鍵の設定を行う秘密鍵設定ステップと、
公開鍵の設定を行う公開鍵設定ステップと、
入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数を設定する乱数設定ステップと、
入札価格に対応する価格レベルを特定するための第１の入札価格情報の入力を受け付ける入札価格情報入力ステップと、
前記乱数設定ステップにおいて設定された前記第１の乱数と、前記入札価格情報入力ステップにおいて入力された前記第１の入札価格情報とを、前記公開鍵設定ステップにおいて設定された前記公開鍵によって暗号化した暗号化情報であって、前記秘密鍵設定ステップにおいて設定された前記秘密鍵を用いることにより、前記第１の乱数と、前記第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、前記第１の乱数とは異なる第２の乱数と、前記第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成する落し戸付コミットメント生成ステップと、
前記乱数設定ステップにおいて設定された前記第１の乱数を、開札者の電子開札装置に電気的に接続される専用回線を通じ、該開札者の電子開札装置に送信する乱数送信ステップと、
を有することを特徴とする電子入札方法。
【請求項１１】
開札者が電子的に開札処理を行う電子開札方法において、入札者によって開示された落し戸付コミットメントを取得する落し戸付コミットメント取得ステップと、
前記入札者の電子入札装置に電気的に接続される専用回線を通じ、該入札者の電子入札装置から送信された、入札者と複数の価格レベルとの組み合わせごとに対応付けられた乱数を受信する乱数受信ステップと、
前記落し戸付コミットメント取得ステップにおいて取得された前記落し戸付コミットメントと、前記乱数受信ステップにおいて受信された前記乱数と、の照合を行い、該照合が成立した前記乱数に対応する価格レベルを落札価格とし、該照合が成立した前記乱数に対応する入札者を落札者とする落札決定ステップと、
を有することを特徴とする電子開札方法。
【請求項１２】
請求項１から５の何れかに記載された電子入札装置としてコンピュータを機能させるための電子入札プログラム。
【請求項１３】
請求項６から９の何れかに記載された電子開札装置としてコンピュータを機能させるための電子開札プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報セキュリティの応用技術に関し、特に、複数の入札者が、電子的な通信を利用して入札を行う電子入札装置、電子開札装置、電子入札方法、その機能をコンピュータに実行させるための電子入札プログラム及び電子開札プログラムに関する。
【０００２】
【従来の技術】
従来より、通信ネットワーク上に分散配置された複数の入札者が、電子的な通信手段を用いて入札を行う電子入札方法が提案されている（例えば、非特許文献１参照。）。
一般に、入札とは、売買・請負等の一方の当事者となるために、相互に競合する多数の入札者が、開札者に対し、文書等によって価格等についての意思表示を行う行為であり、その当事者契約は、落札によって成立する。この入札手続は、各入札者が入札価格等の意思表示を行う入札段階と、この入札内容を開札者が検証し、落札者を決定する開札段階とに分けられる。そして、この入札段階では、各入札者の公平を保つため、各入札者が提示した入札価格等は秘密に保たれ、さらに、入札価格等が開示される開札段階に入った以降は、新たな入札や入札価格等の変更は禁止されるのが一般的である。
【０００３】
電子入札の場合、これらの一連の入札処理を電子的な通信手段を用いて行うことになるが、電子入札において、この入札段階での入札価格等の秘密保持、及び開札段階以降での新たな入札及び入札価格等の変更の禁止を、電子的に実現する方法としてコミットと呼ばれる手法が用いられることがある。
このコミットによる電子入札を行う場合、まず、各入札者は、入札段階において、自己の入札価格等の情報をコミットメントと呼ばれる情報に変換し、このコミットメントを開札者に送信する。このコミットメントは、例えば、開札者が公開した乗法群Ｚ＊ｐの位数ｑの部分群の生成元ｇ（ｐ，ｑは、ｐ＝２ｑ＋１を満たす十分大きな素数。）に対し、入札価格ｓを指数とする指数演算を行った結果（ｇｓの演算結果）であり、このコミットメントが送信された時点では、開札者は、その入札価格（ｓ）を知ることはできないが、後の開札段階においてこの入札価格（ｓ）が変更された場合には、その事実を知ることができるという性格のものである。
【０００４】
入札段階が終了し、開札段階に入ると、各入札者は、入札段階でコミットメントに変換した入札価格等と同じ入札価格等の情報を開札者に送信する。この入札価格等の情報を受け取った開札者は、この情報と、入札段階において受信したコミットメントとを照合し、入札価格の正当性を検証する。具体的には、上述のｇに対し、開札段階で受信した入札価格等（ｓ）を指数とする指数演算を行い、その演算結果が、入札段階で受信したコミットメントと等しいか否か検証する。ここで、これらが等しかった場合には、入札段階での入札価格と、開札段階で開示された入札価格とが等しいことが判り、逆に等しくなかった場合には、開札段階以降に、新たな入札或いは入札価格等の変更があったことが判断できる。これにより、電子入札における公平性が保たれることになる。
【０００５】
【非特許文献１】
Ｓ．Ｍｉｙａｚａｋｉ，Ｋ．Ｓａｋｕｒａｉ，公開掲示板を用いた秘策可能な電子入札システム，ＳＣＩＳ’９９　４１−４６（１９９９）
【０００６】
【発明が解決しようとする課題】
しかし、従来の電子入札方法では、入札段階において公開されたコミットメントを証拠として、第三者に入札者が入札価格等を証明できるため、入札の談合を誘発しやすいという問題点がある。
例えば、入札の談合を実施しようとしている脅迫者や買収者等（以下、「談合主催者」という。）が、各入札者に対して一定価格以上の入札価格を提示しないように指示し、特定の入札者に対して落札が行われるように計画したとする。この談合主催者は、この入札に関し第３者であるため、通常、各入札者の入札価格を知ることはできないが、入札段階において公開したコミットメントは知ることができる。前述のように、入札者以外の者は、このコミットメントから入札価格自体を知ることはできないが、ある入札価格が、このコミットメントに対応する入札価格であるか否かは知ることができる。従って、この談合主催者が各入札者から入札価格を聞き出し、聞き出した入札価格とコミットメントとを照合することにより、入札者から聞き出した入札価格が正しいか否かを判断することができる。これにより、談合主催者は、買収や脅迫によって各入札者の入札価格をコントロールすることが容易になり、結果、入札の談合を誘発してしまうこととなる。
【０００７】
本発明はこのような点に鑑みてなされたものであり、第三者に入札者が入札価格等を証明できないようにし、入札の談合を抑制することが可能な電子入札装置を提供することを目的とする。
また、本発明の他の目的は、第三者に入札者が入札価格等を証明できないようにし、入札の談合を抑制することが可能な電子開札装置を提供することである。さらに、本発明の他の目的は、第三者に入札者が入札価格等を証明できないようにし、入札の談合を抑制することが可能な電子入札方法を提供することである。
また、本発明の他の目的は、第三者に入札者が入札価格等を証明できないようにし、入札の談合を抑制することが可能とする処理をコンピュータに実行させるための電子入札プログラムを提供することである。
さらに、本発明の他の目的は、第三者に入札者が入札価格等を証明できないようにし、入札の談合を抑制することが可能とする処理をコンピュータに実行させるための電子開札プログラムを提供することである。
【０００８】
【課題を解決するための手段】
本発明では上記課題を解決するために、第１の乱数と、第１の入札価格情報とを、公開鍵によって暗号化した暗号化情報であって、秘密鍵を用いることにより、第１の乱数と、第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成する。そして、生成した落し戸付コミットメント開示し、さらに、第１の乱数を、開札者の電子開札装置に、該開札者の電子開札装置に電気的に接続される専用回線を通じて送信する。
これにより、第三者に入札者が入札価格を証明できないようにすることができる。
【０００９】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
ここでは、まず、本形態の概略について説明を行い、その後、本形態の詳細について説明を行っていく。
図１は、本形態における電子入札システム１の概略を説明するための概念図である。
図１に例示するように、この例の電子入札システム１は、入札者が電子的に入札処理を行う電子入札装置２、開札者が電子的に開札処理を行う電子開札装置３、及び電子入札装置２と電子開札装置３とを結ぶ専用回線４を有している。なお、図１では、説明の簡略化のため、１つの電子入札装置２と１つの電子開札装置３と１つの専用回線４のみを例示しているが、複数の電子入札装置２、電子開札装置３を、それぞれ複数の専用回線４で結ぶ構成としてもよい。
【００１０】
ここで、この例の電子入札装置２は、例えば、秘密鍵の設定を行う秘密鍵設定手段２ａ、公開鍵の設定を行う公開鍵設定手段２ｂ、入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数を設定する乱数設定手段２ｃ、入札価格に対応する価格レベルを特定するための第１の入札価格情報の入力を受け付ける入札価格情報入力手段２ｄ、乱数設定手段２ｃにおいて設定された第１の乱数と、入札価格情報入力手段２ｄにおいて入力された第１の入札価格情報とを、公開鍵設定手段２ｂにおいて設定された公開鍵によって暗号化した暗号化情報であって、秘密鍵設定手段２ａにおいて設定された秘密鍵を用いることにより、第１の乱数と、第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成する落し戸付コミットメント生成手段２ｅ、落し戸付コミットメント生成手段２ｅにおいて生成された落し戸付コミットメントを開示する落し戸付コミットメント開示手段２ｆ、及び乱数設定手段２ｃにおいて設定された第１の乱数を、開札者の電子開札装置３に、該開札者の電子開札装置３に電気的に接続される専用回線４を通じて送信する乱数送信手段２ｇを有している。なお、この例の専用回線４は、例えば、物理的に送信内容が盗聴できない電子入札端末装置２から電子開札装置３への通信路であり、送信内容が秘匿されるだけではなく、暗号通信路のように、通信データから通信内容を証明することもできない通信路である。
【００１１】
また、この例の電子開札装置３は、例えば、入札者によって開示された落し戸付コミットメントを取得する落し戸付コミットメント取得手段３ａ、入札者の電子入札装置２に電気的に接続される専用回線４を通じ、該入札者の電子入札装置２から送信された、入札者と複数の価格レベルとの組み合わせごとに対応付けられた乱数を受信する乱数受信手段３ｂ、及び落し戸付コミットメント取得手段３ａにおいて取得された落し戸付コミットメントと、乱数受信手段３ｂにおいて受信された乱数と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とする落札決定手段３ｃを有している。
【００１２】
なお、「入札価格」とは、入札時に入札者が開札者に示す意思表示が価格である場合における当該価格を意味する他、当該意思表示が価格以外であった場合における当該意思表示の内容をも含む概念とする。また、「価格レベル」とは、入札時に入札者が開札者に示す意思表示が価格である場合における当該価格自体を意味する数値、或いは、当該価格に対応する識別子を示す数値を意味する他、当該意思表示が価格以外であった場合における当該意思表示の内容自体を示す数値、或いは、当該意思表示に対応する識別子を示す数値を意味する概念である。
この電子入札システム１において電子入札を行う場合、例えばまず、電子開札装置３は、前処理として、入札価格表Ｐ＝｛ｓ｜ｓ＝１，２，・・・，ｍ｝と、大きな素数（ｐ＝２ｑ＋１，ｑ）と、乗法群Ｚ＊ｐの位数ｑの部分群の生成元ｇと、「入札しないこと」及び「入札すること」をそれぞれ示すメッセージＭ０，Ｍ１∈Ｚ＊ｐとを公開する。なお、ここで入札価格表Ｐの「ｓ」は、入札価格表Ｐの各価格レベルを示すものとする。
【００１３】
電子入札を行う各入札者｛Ｂｊ｜ｊ＝１，２，・・・，ｂ｝は、例えば、談合主催者から監視・命令を受けることなく自由に入札を行うことができるブース内において、電子入札装置２を用い、入札処理を行う。入札処理を行う場合、各入札者Ｂｊは、例えばまず、秘密鍵設定手段２ａにおいて秘密鍵ｘｊ∈Ｚ＊ｐを、公開鍵設定手段２ｂにおいて公開鍵ｈｊ＝ｇｘｊをそれぞれ生成し、生成した公開鍵ｈｊを署名をつけて公開する。また、各入札者Ｂｊは、乱数設定手段２ｃにおいて、入札価格表Ｐの複数の価格レベルｓと、入札者Ｂｊと、の組み合わせにそれぞれ対応する乱数ｒ（ｓ，ｊ）∈Ｚ＊ｐ（ｓ＝１，２，・・・，ｍ）を設定する。その後、各入札者Ｂｊは、希望する入札価格を決定し、この入札価格に対応する価格レベルを特定するための入札価格情報であるｐｊ∈Ｐを入札価格情報入力手段２ｄに入力する。
【００１４】
これらの情報が集まると、電子入札装置２は、例えば次に、落し戸付コミットメント生成手段２ｅにおいて、各入札者Ｂｊごとの落し戸付コミットメントの生成を行う。この例での落し戸付コミットメントは、例えば、乱数設定手段２ｃにおいて設定された乱数ｒ（ｓ，ｊ）と、入札価格情報入力手段２ｄにおいて入力された入札価格情報ｐｊとを、公開鍵設定手段２ｂにおいて設定された公開鍵ｈｊによって暗号化した暗号化情報であって、秘密鍵設定手段２ａにおいて設定された秘密鍵ｘｊを用いることにより、乱数ｒ（ｓ，ｊ）と、入札価格情報ｐｊと、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、乱数ｒ（ｓ，ｊ）とは異なる乱数と、入札価格情報ｐｊによって特定される価格レベルとは異なる価格レベルを特定するための入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な情報である。具体的には、例えば、落し戸付コミットメント生成手段２ｅにおいて、価格レベルｓ＝１，２，・・・，ｍそれぞれに対し、価格レベルｓが入札を行う価格レベルでないとき（ｓ≠ｐｊ）には、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるとき（ｓ＝ｐｊ）には、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、これらの演算結果を落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，・・・，　Ｃｍ，ｊ）として生成する。
【００１５】
このように生成された各入札者Ｂｊの落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）は、例えば、落し戸付コミットメント開示手段２ｆにおいて署名付きで開示され、さらに、乱数設定手段において設定された各乱数ｒ（ｓ，ｊ）は、例えば、乱数送信手段２ｇにおいて、専用回線４を介し、電子開札装置３に送信される。なお、この各乱数ｒ（ｓ，ｊ）の送信は、例えば、各乱数ｒ（ｓ，ｊ）と、入札価格表Ｐの各価格レベルｓと各入札者Ｂｊとの組み合わせ、との対応が取れるように行う。
一方、開札処理を行う電子開札装置３は、例えば、落し戸付コミットメント取得手段３ａによって、公開されている落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ，　・・・，　Ｃｍ，ｊ）を取得し、乱数受信手段３ｂにおいて、送信された各乱数ｒ（ｓ，ｊ）を受信する。
【００１６】
これらの情報を受信した電子開札装置３は、例えば、落札決定手段３ｃにおいて、落し戸付コミットメント取得手段３ａにおいて取得された落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）と、乱数受信手段３ｂにおいて受信された各乱数ｒ（ｓ，ｊ）と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とする落札処理を行う。なお、この例の場合、例えば、すべての入札者Ｂｊ（ｊ＝１，２，・・・，ｂ）について、ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、この演算結果がＣｓ，ｊとなった場合に、この照合が成立したものと判断する。
【００１７】
以上の各処理に関し、各入札者Ｂｊは、入札段階において落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）を公開しているが、各乱数ｒ（ｓ，ｊ）については、電子開札装置３０に専用回線４を介して送信しているだけで、第三者には公開していない。よって、第三者である談合主催者は、各乱数ｒ（ｓ，ｊ）を知らず、公開された落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）を知っているだけである。この場合、各入札者Ｂｊは、談合主催者に対し、入札価格を偽ることができる。
つまり、前述のように、この例の場合、落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）は、価格レベルｓ＝１，２，・・・，ｍそれぞれに対し、価格レベルｓが入札を行う価格レベルでないとき（ｓ≠ｐｊ）には、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるとき（ｓ＝ｐｊ）には、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行った結果の集合である。したがって、入札者Ｂｊが談合主催者に入札価格を偽る場合、この偽った入札価格に対してＣｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）及びＣｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）を満たす乱数ｒ（ｓ，ｊ）をも選択できなければ、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）及びＣｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の等号が成立しないことを証拠に、入札者Ｂｊは、入札者Ｂｊが偽りの入札価格を談合主催者に教えたことを、談合主催者に証明できてしまう。一般に、Ｃｓ，ｊの演算結果のみから、この偽った入札価格に対応する乱数ｒ（ｓ，ｊ）を演算することは困難である。しかし、各入札者Ｂｊは、自己の秘密鍵ｘｊを知っており、この秘密鍵ｘｊを用いることによって容易に偽った入札価格に対応する乱数ｒ（ｓ，ｊ）を演算することができる。すなわち、公開鍵ｈｊ＝ｇｘｊから、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ，１）＝ｇＭ１（ｇｘｊ）ｒ（ｓ，ｊ，１）となり、両辺の対数をとることにより、ｌｏｇｇＣｓ，ｊ＝Ｍ１＋ｘｊｒ（ｓ，ｊ，１）となり、それを変形したｒ（ｓ，ｊ，１）＝（ｌｏｇｇＣｓ，ｊ―Ｍ１）／ｘｊから容易に偽った入札価格に対応する乱数ｒ（ｓ，ｊ，ｅ）を求めることができる。同様に、偽りの入札価格以外の価格レベルに対応する乱数もｒ（ｓ，ｊ，０）＝（ｌｏｇｇＣｓ，ｊ―Ｍ０）／ｘｊから容易に求めることができる。これにより、入札者Ｂｊは、偽りの入札価格と、それに対応する偽りの乱数とを談合主催者に示すことが可能となり、談合主催者は、入札者Ｂｊから示された入札価格が正しい入札価格なのか偽りの入札価格なのかを判断することができない。結果、談合主催者が入札者の入札価格をコントロールすることが困難となり、入札の談合を抑制することが可能となる。
【００１８】
次に、本形態の詳細について説明する。
図２は、本形態における電子入札システム１０の全体構成の詳細を説明するための概念図である。
図２に例示するように、この例の電子入札システム１０は、例えば、入札者が入札処理を行う電子入札装置２０〜４０、及び開札者が落札処理を行う電子開札装置５０〜７０を有している。そして、この電子入札装置２０〜４０は、電子開札装置５０〜７０と、専用回線８０を介して電気的に接続され、或いは接続可能な状態となっており、電子開札装置５０〜７０は、ネットワーク９０を介し相互に電気的に接続され、或いは接続可能な状態となっている。
【００１９】
電子入札装置２０〜４０及び電子開札装置５０〜７０は、例えば、モデム、ＤＳＵ（Ｄｉｇｉｔａｌ　Ｓｅｒｖｉｃｅ　Ｕｎｉｔ）、ＮＣＵ（Ｎｅｔｗｏｒｋ　Ｃｏｎｔｏｒｏｌ　Ｕｎｉｔ）、ＴＡ（Ｔｅｒｍｉｎａｌ　Ａｄａｐｔｅｒ）等のデータ回線終端装置が具備され、或いは接続されたコンピュータである。
専用回線８０は、通信内容が第三者によって物理的に盗聴されないように構成された通信回線であり、具体的には、例えば、電子入札装置２０〜４０を、電子開札装置５０〜７０に、それぞれポイントツーポイント方式で接続する有線又は無線の通信回線である。
【００２０】
また、ネットワーク９０は、例えば、インターネット、イントラネット、エクストラネット、ＬＡＮ（Ｌｏｃａｌ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ　Ａｒｅａ　Ｎｅｔｗｏｒｋ）、ＶＡＮ（Ｖａｌｕｅ　Ａｄｄｅｄ　Ｎｅｔｗｏｒｋ）等であり、その形態について特に制限はない。また、その通信回線も、専用回線、交換回線等、どのようなものでもよく、ネットワーク接続形態もリング型、メッシュ型、スター型、バス型、ツリー型等、特に制限はない。さらに、その回線接続方式も、ポイントツーポイント方式、マルチポイント方式、集線方式等、特に制限はなく、どのようなものであってもよい。ただし、ネットワーク９０が専用回線である場合、本システムの安全性が向上するため、ネットワーク９０は専用回線であることがより望ましい。
【００２１】
なお、図２では、３つずつの電子入札装置２０〜４０、及び電子開札装置５０〜７０によって、電子入札システム１０を構成しているが、電子入札装置２０〜４０及び電子開札装置５０〜７０を、これより多く設けることとしてもよく、少なく設けることとしてもよい。
図３は、電子入札装置２０のハードウェア構成を例示したブロック図である。
図３に例示するように、電子入札装置２０は、例えば、ＣＰＵ（Ｃｅｎｔｒａｌ　ｐｒｏｃｅｓｓｉｎｇ　Ｕｎｉｔ：中央処理装置）２１、主記憶装置２２、外部記憶装置２３、入力装置２４、記録媒体読書き装置２５、出力装置２６、通信制御装置２７及びバス２８を有しており、通信制御装置２７を介し、ネットワーク９０と通信可能なように接続され、或いは接続可能なように構成されている。
【００２２】
ＣＰＵ２１は、例えば、制御装置と演算装置を有するＣＩＳＣ（Ｃｏｍｐｌｅｘ　Ｉｎｓｔｒｕｃｔｉｏｎ　Ｓｅｔ　Ｃｏｍｐｕｔｅｒ）方式、或いはＲＩＳＣ（Ｒｅｄｕｃｅｄ　Ｉｎｓｔｒｕｃｔｉｏｎ　Ｓｅｔ　Ｃｏｍｐｕｔｅｒ）方式の中央処理装置であり、図示していない発信器から供給されるクロック信号に同期し、主記憶装置２２に格納されたオペレーティングシステム、アプリケーションプログラム等の各種プログラムの実行を行い、周辺機器の制御、必要データの呼び出し、呼び出したデータの演算・加工、演算・加工後のデータのメモリへの格納、周辺機器への出力等の各種処理を行う。
主記憶装置２２は、例えば、ＣＰＵ２１が直接データを読み書きできる記憶装置である。主記憶装置２２には、例えば、オペレーティングシステム、アプリケーションプログラム、データ、周辺機器を制御するドライバ等が読み込まれ、ＣＰＵ２１は、この主記憶装置２２に読み込まれたオペレーティングシステム等を実行することにより、一連の処理を行う。主記憶装置２２には、例えば、半導体メモリ等の高速処理可能な記憶素子を用い、この主記憶装置２２内の物理アドレスは、ページング方式、セグメンテーション方式等の方法により、外部記憶装置２３の仮想アドレス空間に対応付けられる。
【００２３】
外部記憶装置２３は、例えば、磁性体が蒸着された薄い円盤を高速回転させ、この磁性体を磁気ヘッドによって磁化することでデータの記録を行うハードディスク装置等である。
入力装置２４は、例えば、キーボードやマウス等の入出力デバイスである。
記録媒体読書き装置２５は、例えば、フレキシブルディスク等への情報の読書き、コンパクト・ディスク等からの情報の読み出し等を行う装置である。
出力装置２６は、例えば、画面表面の蛍光素材に電子ビームを当てることによって映像の表示を行うＣＲＴ（Ｃａｔｈｏｄｅ−ｒａｙ　Ｔｕｂｅ）ディスプレイ、或いは、電圧を加えた際に分子配列が変化する液晶の性質を利用した液晶ディスプレイ等であり、供給されたアナログ信号をもとに、所定の映像の表示を行う。
【００２４】
通信制御装置２７は、例えば、例えば、ＵＳＡＲＴ（Ｕｎｉｖｅｒｓａｌ　Ｓｙｎｃｈｒｏｎｏｕｓ　ａｎｄ　Ａｓｙｎｃｈｒｏｎｏｕｓ　Ｒｅｃｅｉｖｅｒ−Ｔｒａｎｓｍｉｔｔｅｒ）等の汎用同期・非同期送受信回路であり、ネットワーク９０を介したデータ送受信時にデータの直列変換等を行う。
バス２８は、例えば、データバス、アドレスバス、コントロールバス等によって構成され、ＣＰＵ２１、主記憶装置２２、外部記憶装置２３、入力装置２４、記録媒体読書き装置２５、出力装置２６、通信制御装置２７間のデータ、アドレス情報、制御情報の受け渡しを行う。
なお、ここでは説明を省略するが、この例の場合、電子入札装置３０、４０、及び電子開札装置５０〜７０も電子入札装置２０と同様なハードウェア構成をとるものとする。
【００２５】
図４は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築される電子入札装置２０の処理機能を例示した機能ブロック図である。
図４に例示するように、この例の電子入札装置２０は、電子開札装置５０によって提供された前処理情報を取得する前処理情報取得手段２０ａ、秘密鍵の設定を行う秘密鍵設定手段２０ｂ、公開鍵の設定を行う公開鍵設定手段２０ｃ、入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数を設定する乱数設定手段２０ｄ、入札価格に対応する価格レベルを特定するための第１の入札価格情報の入力を受け付ける入札価格情報入力手段２０ｅ、公開鍵情報を開示する公開鍵情報開示手段２０ｆ、乱数設定手段２０ｄにおいて設定された第１の乱数と、入札価格情報入力手段２０ｅにおいて入力された第１の入札価格情報とを、公開鍵設定手段２０ｃにおいて設定された公開鍵によって暗号化した暗号化情報であって、秘密鍵設定手段２０ｂにおいて設定された秘密鍵を用いることにより、第１の乱数と、第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成する落し戸付コミットメント生成手段２０ｇ、第１の乱数を複数の乱数シェアに秘密分散する乱数秘密分散手段２０ｈ、ゼロ知識証明によって、秘密鍵、及び落し戸付コミットメントの生成に用いられた第１の乱数と第１の入札価格情報との組み合わせ内容、を認知していることを開札者の電子開札装置５０〜７０に証明するゼロ知識証明手段２０ｉ、落し戸付コミットメント生成手段２０ｇにおいて生成された落し戸付コミットメントを開示する落し戸付コミットメント開示手段２０ｊ、乱数設定手段２０ｄにおいて設定された第１の乱数を、開札者の電子開札装置５０〜７０に、該開札者の電子開札装置５０〜７０に電気的に接続される専用回線８０を通じて送信する乱数送信手段２０ｋ、ゼロ知識証明に必要な情報を送信するゼロ知識証明通信手段２０ｍ、電子署名を行う電子署名手段２０ｎ、各種情報を記憶する記憶手段２０ｐ、及び電子入札装置２０全体を制御する制御手段２０ｑを処理機能として有している。
【００２６】
なお、詳細は後述するが、この例の場合、乱数送信手段２０ｋは、例えば、乱数秘密分散手段２０ｈにおいて秘密分散された複数の乱数シェアを、複数の開札者の電子開札装置５０〜７０に分散させて送信する手段である。また、落し戸付コミットメント開示手段２０ｊは、例えば、署名付きの落し戸付コミットメントを開示する手段であり、乱数送信手段２０ｋは、例えば、署名付きの第１の乱数を送信する手段である。さらに、落し戸付コミットメント生成手段２０ｇは、例えば、乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する第１の乱数をｒ（ｓ，ｊ）とし、入札を行わない価格レベルであることを示す第１の入札価格情報をＭ０とし、入札を行う価格レベルであることを示す第１の入札価格情報をＭ１とした場合において、価格レベルｓが入札を行う価格レベルでないときには、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるときには、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、これらの演算結果を落し戸付コミットメントとする手段である。
【００２７】
また、図４に例示するように、前処理情報取得手段２０ａ、秘密鍵設定手段２０ｂ、公開鍵設定手段２０ｃ、乱数設定手段２０ｄ、入札価格情報入力手段２０ｅ、公開鍵情報開示手段２０ｆ、落し戸付コミットメント生成手段２０ｇ、乱数秘密分散手段２０ｈ、ゼロ知識証明手段２０ｉ、落し戸付コミットメント開示手段２０ｊ、乱数送信手段２０ｋ、ゼロ知識証明通信手段２０ｍ、電子署名手段２０ｎ、及び記憶手段２０ｐは、制御手段２０ｑへの情報の提供、或いは制御手段２０ｑからの情報の受け取りの、少なくとも一方が可能なように構成されており、前処理情報取得手段２０ａは、専用回線８０からの情報の受信が、公開鍵情報開示手段２０ｆ、落し戸付コミットメント開示手段２０ｊ、乱数送信手段２０ｋ、ゼロ知識証明通信手段２０ｍは、専用回線８０への情報の送信が、それぞれ可能なように構成されている。
【００２８】
なお、ここでは説明を省略するが、この例における電子入札装置３０、４０の機能ブロック構成は、上記の電子入札装置２０の機能ブロックと同様とする。
図５は、図３に例示したハードウェアにおいて所定のプログラム（ソフトウェア）を実行させることにより、このハードウェアとソフトウェアとが協働した具体的手段によって構築される電子開札装置５０の処理機能を例示した機能ブロック図である。
図５に例示するように、電子開札装置５０は、ゼロ知識証明に必要な情報を電子入札装置２０〜４０から受信するゼロ知識証明受信手段５０ａ、ゼロ知識証明の検証を行うゼロ知識証明検証手段５０ｂ、入札者の電子入札装置２０〜４０に電気的に接続される専用回線８０を通じ、該入札者の電子入札装置２０〜４０から送信された、入札者と複数の価格レベルとの組み合わせごとに対応付けられた乱数を受信する乱数受信手段５０ｃ、乱数シェアを取得する乱数シェア通信手段５０ｄ、入札者によって開示された落し戸付コミットメントを取得する落し戸付コミットメント取得手段５０ｅ、多項式補間を行う多項式補間手段５０ｆ、落し戸付コミットメント取得手段５０ｅにおいて取得された落し戸付コミットメントと、乱数受信手段５０ｃにおいて受信された乱数と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とする落札決定手段５０ｇ、署名の検証を行う署名検証手段５０ｈ、前処理情報を公開する前処理情報公開手段５０ｉ、各種の情報を記憶する記憶手段５０ｊ、及び電子開札装置５０全体を制御する制御手段５０ｋを処理機能として有している。
【００２９】
なお、詳細は後述するが、この例の落札決定手段５０ｇは、例えば、第１の価格レベルに対応する乱数と、落し戸付コミットメントと、の照合を行った結果、該照合が不成立であった場合、該第１の価格レベルよりも値段の安い第２の価格レベルに対応する乱数と、落し戸付コミットメントと、の照合を行う手段である。また、例えば、乱数受信手段５０ｃは、例えば、乱数を複数に秘密分散した乱数シェアの一部を受信する手段であり、乱数シェア通信手段５０ｄは、他の電子開札装置６０、７０において受信された乱数シェアを取得する手段であり、多項式補間手段５０ｆは、乱数受信手段５０ｃにおいて取得された乱数シェアと、乱数シェア通信手段５０ｄにおいて取得された乱数シェアと、を用い、多項式補間によって、乱数を復元する手段である。さらに、例えば、落札決定手段は、落し戸付コミットメントをＣｓ，ｊとし、乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する乱数をｒ（ｓ，ｊ）とし、入札を行う価格レベルであることを示す入札価格情報をＭ１とした場合における、ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、該演算結果がＣｓ，ｊとなった場合には、照合が成立したものと判断する手段である。
【００３０】
また、図５に例示するように、ゼロ知識証明受信手段５０ａ、ゼロ知識証明検証手段５０ｂ、乱数受信手段５０ｃ、乱数シェア通信手段５０ｄ、落し戸付コミットメント取得手段５０ｅ、多項式補間手段５０ｆ、落札決定手段５０ｇ、署名検証手段５０ｈ、前処理情報公開手段５０ｉ及び記憶手段５０ｊは、制御手段５０ｋへの情報の提供、或いは制御手段５０ｋからの情報の受け取りの、少なくとも一方が可能なように構成されており、ゼロ知識証明受信手段５０ａ、乱数受信手段５０ｃ、落し戸付コミットメント取得手段５０ｅ及び前処理情報公開手段５０ｉは、専用回線８０を介した情報の受信が可能なように、乱数シェア通信手段５０ｄは、ネットワーク９０を介した情報の送信が可能なように、それぞれ構成されている。
【００３１】
なお、ここでは説明を省略するが、この例における電子開札装置６０、７０の機能ブロック構成は、上記の電子開札装置５０の機能ブロックと同様とする。
次に、本形態における本形態における電子入札システム１０の処理動作について説明する。
図６〜図９は、本形態における電子入札システム１０の処理動作を説明するためのフローチャートである。ここで、ステップＳ１は前処理を行うステップを、ステップＳ２〜Ｓ１１は入札処理を行うステップを、ステップＳ１２〜Ｓ１５は開札処理を行うステップを、それぞれ示している。なお、この例では、３つの開札者｛Ａｉ｜ｉ＝１，２，３｝と、３つの入札者｛Ｂｊ｜ｊ＝１，２，３｝との間で電子入札を行う場合を例にとって説明するが、入札者及び開札者の数は、これよりも多くても少なくてもよい。また、ここでは、説明の簡略化のため、電子入札装置２０及び電子開札装置５０〜７０の処理のみを説明するが、この例では、電子入札装置３０、４０は電子入札装置２０と同様な処理を行うものとする。さらに、ここでは、説明を容易にするため、便宜的に図６〜図９のような処理の流れにそって処理動作の説明を行うが、電子入札装置２０、電子開札装置５０〜７０それぞれが、このフローチャートの流れと異なる順序で処理を行うこととしてもよく、また、電子入札装置２０及び電子開札装置５０〜７０の少なくとも一部が平行して、同時にそれぞれの処理を行うこととしてもよい。以下、このフローチャートを用いて電子入札システム１０の処理動作の説明を行っていく。
【００３２】
ステップＳ１：
本ステップでは、電子開札装置５０において、前処理情報の公開を行う。
本ステップにおける前処理情報の公開は、例えば、記憶手段５０ｊに格納されている入札価格表Ｐ＝｛ｓ｜ｓ＝１，２，・・・，ｍ｝と、大きな素数（ｐ＝２ｑ＋１，ｑ）と、乗法群Ｚ＊ｐの位数ｑの部分群の生成元ｇと、「入札しないこと」及び「入札すること」をそれぞれ示すメッセージＭ０，Ｍ１∈Ｚ＊ｐとを、制御手段５０ｋによって抽出し、これらの情報を前処理情報公開手段５０ｉにおいて、専用回線８０を介して公開することにより行われる。
図１２は、本ステップにおいて公開される入札価格表１００の構成を例示した概念図である。
図１２に例示するように、この例の入札価格表１００は、入札価格の各価格レベル１０１及び、各価格レベル１０１に一対一で対応する価格１０２の情報によって構成されている。この例の場合、ｍ＝１００となっており、価格レベル１０１として「１」「２」「３」・・・「１００」が、それらに対応する価格１０２として「１００，００」「２００，００」「３００，００」・・・「１０，０００，００」が、それぞれ設定されている。
このように公開された前処理情報は、例えば、電子入札装置２０の前処理情報取得手段２０ａによって受信され、電子入札装置２０の制御手段２０ｑを介して記憶手段２０ｐに記憶される。
【００３３】
ステップＳ２：
本ステップでは、電子入札装置２０において、秘密鍵（ｘｊ）及び公開鍵（ｈｊ）を生成する。
この例の場合、例えば、電子入札装置２０の秘密鍵設定手段２０ｂにおいて、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、この擬似乱数を用いて秘密鍵（ｘｊ）を生成する。そして、公開鍵設定手段２０ｃにおいて、秘密鍵設定手段２０ｂで生成した秘密鍵（ｘｊ）及び記憶手段２０ｑに記憶されている生成元ｇを用いて、ｈｊ＝ｇｘｊの演算を行い、この演算結果を公開鍵（ｈｊ）とする。このように設定された秘密鍵（ｘｊ）及び公開鍵（ｈｊ）は、制御手段２０ｑを介して記憶手段２０ｑに記憶される。
【００３４】
ステップＳ３：
本ステップでは、電子入札装置２０において、公開鍵（ｈｊ）を公開する。
この例の場合、電子入札装置２０の制御手段２０ｑによって、記憶手段２０ｐに記憶されている公開鍵（ｈｊ）を抽出し、抽出した公開鍵（ｈｊ）に、電子署名手段２０ｎによって電子署名（ＲＳＡ署名等）を付し、その演算結果を公開鍵情報開示手段２０ｆにおいて、専用回線８０を介し、電子開札装置５０〜７０に開示する。
【００３５】
ステップＳ４：
本ステップでは、電子入札装置２０において、乱数ｒ（ｓ、ｊ）の設定を行う。
この例の場合、電子入札装置２０の乱数設定手段２０ｄにおいて、例えば、ＳＨＡ−１等の一方向性ハッシュ関数を用いて構成される、計算量理論に基づく擬似乱数生成アルゴリズム等を用いて擬似乱数を発生させ、これらを乱数ｒ（ｓ、ｊ）として設定する。なお、この例の場合、乱数ｒ（ｓ、ｊ）は、各入札者Ｂｊごとに、ステップＳ１で取得した入札価格表Ｐの価格レベル数ｍ分だけ、生成され、生成された各乱数ｒ（ｓ、ｊ）は、各価格レベルｓと各入札者Ｂｊとの組み合わせに対応付けられる。例えば、乱数ｒ（５０、１）は、入札者Ｂ１の価格レベル５０に対応する乱数を意味する。
このように設定された乱数ｒ（ｓ、ｊ）は、例えば、制御手段２０ｑを介して記憶手段２０ｐに記憶され、次のステップの処理に移る。
【００３６】
ステップＳ５：
本ステップでは、電子入札装置２０において、入札価格情報の入力を行う。
この例における入札価格情報とは、入札価格に対応する価格レベルを特定するための情報であり、具体的には、例えば、入札価格表Ｐのどの価格レベルに対応する価格を入札価格とするかを特定するための情報である。また、この例での入札価格情報の入力は、電子入札装置２０の入札価格情報入力手段２０ｅに対し、入札者Ｂｊが価格レベルの選択入力等を行うことによって行われる。
このように入力された入札価格情報は、例えば、制御手段２０ｑを介して記憶手段２０ｐに記憶され、次のステップの処理に移る。
【００３７】
ステップＳ６：
本ステップでは、電子入札装置２０において、落し戸付コミットメント（Ｃｓ，ｊ）の生成を行う。
この例の場合、制御手段２０ｑによって、記憶手段２０ｐに記憶されている乱数ｒ（ｓ、ｊ）及び入札価格情報を抽出し、抽出したこれらの情報を用い、落し戸付コミットメント生成手段２０ｇにおいて、各入札者Ｂｊごとの落し戸付コミットメント（Ｃｓ，ｊ）を生成する。この例の場合、落し戸付コミットメント生成手段２０ｇにおいて、価格レベルｓ＝１，２，・・・，ｍそれぞれに対し、価格レベルｓが入札を行う価格レベルでないとき（ｓ≠ｐｊ）には、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるとき（ｓ＝ｐｊ）には、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、これらの演算結果を落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ　，　・・・，　Ｃｍ，ｊ）として生成する。
このように生成された落し戸付コミットメント（Ｃｓ，ｊ）は、例えば、制御手段２０ｑを介して記憶手段２０ｐに記憶され、次のステップの処理に移る。
【００３８】
ステップＳ７：
本ステップでは、電子入札装置２０において、落し戸付コミットメント（Ｃｓ，ｊ）を公開する。この例の場合、まず、制御手段２０ｑにおいて記憶手段２０ｐに記憶されている落し戸付コミットメント（Ｃｓ，ｊ）を抽出し、この落し戸付コミットメント（Ｃｓ，ｊ）に対して、電子署名手段２０ｎにおいてＲＳＡ署名等の方法により電子署名を付し、その結果を落し戸付コミットメント開示手段２０ｊによって、専用回線８０を介して電子開札装置５０に開示する。このように開示された落し戸付コミットメント（Ｃｓ，ｊ）は、電子開札装置５０の落し戸付コミットメント取得手段５０ｅによって受信され、制御手段５０ｋを介して、記憶手段５０ｊに記憶される。
【００３９】
ステップＳ８：
本ステップでは、電子入札装置２０において、秘密鍵（ｘｊ）と、落し戸付コミットメント（Ｃｓ，ｊ）の生成に用いられた乱数ｒ（ｓ、ｊ）と入札価格情報との組み合わせ内容（ｌｏｇｇＣｓ，ｊ）とを、認知していることを、ゼロ知識証明によって開札者の電子開札装置５０に証明する。
この例でのゼロ知識証明は、電子入札装置２０のゼロ知識証明手段２０ｉによって生成された証明情報を、ゼロ知識証明通信手段２０ｍにおいて、専用回線８０を介して電子開札装置５０に送信し、この証明情報を電子開札装置５０のゼロ知識証明受信手段５０ａにおいて受信し、ゼロ知識証明検証手段５０ｂにおいて検証することによって行われる。この詳細については後述する。
【００４０】
なお、ゼロ知識証明とは、検証者に証明内容を開示することなく、証明者がその証明内容を知っていることを検証者に証明することであり、例えば、フィアット・シャミア認証方式等がこれに該当する。この例の場合、電子入札装置２０において、この電子入札装置２０が、秘密鍵（ｘｊ）と、落し戸付コミットメント（Ｃｓ，ｊ）の生成に用いられた乱数ｒ（ｓ、ｊ）と入札価格情報との組み合わせ内容（ｌｏｇｇＣｓ，ｊ）とを知っていることを、これらの内容を電子開札装置５０に開示することなく、電子開札装置５０に証明する。
このゼロ知識証明により、談合主催者が自ら公開鍵（ｈｊ）を生成し、その秘密鍵を談合主催者側で秘密に保ったまま、その公開鍵（ｈｊ）を入札者Ｂｊに渡し、入札者Ｂｊに対し、この公開鍵（ｈｊ）を用いて入札処理を行うように強制する不正を防止することができる。つまり、このような不正が行われた場合、入札者Ｂｊは、秘密鍵の内容を知らないことになり、前述の概略説明で述べたように、偽った入札価格に対応する乱数も選択できないため、入札価格を談合主催者に偽ることもできなくなる。しかし、ここで上述のゼロ知識証明を要件としておくことにより、入札者Ｂｊが偽った入札価格に対応する乱数を設定できることが保障され、結果、入札の談合を抑制することが可能となる。
【００４１】
ステップＳ９：
本ステップでは、電子入札装置２０において、乱数ｒ（ｓ、ｊ）を秘密分散し、乱数シェアｒｉ（ｓ、ｊ）の生成を行う。
乱数ｒ（ｓ、ｊ）の秘密分散とは、乱数ｒ（ｓ、ｊ）を複数個の乱数シェアｒｉ（ｓ、ｊ）（乱数ｒ（ｓ、ｊ）のｔ−ｏｕｔ−ｏｆ−ａ秘密分散シェア）に分散することである。この秘密分散された乱数シェアｒｉ（ｓ、ｊ）を用いて元の乱数ｒ（ｓ、ｊ）を復元するためには、所定数以上の乱数シェアｒｉ（ｓ、ｊ）が必要であり、この乱数シェアｒｉ（ｓ、ｊ）の数が所定数未満の場合、元の乱数ｒ（ｓ、ｊ）を復元することはできない。このように乱数ｒ（ｓ、ｊ）を秘密分散することにより、各乱数シェアｒｉ（ｓ、ｊ）を受け取った者が所定数以上協力し合わない限り、乱数ｒ（ｓ、ｊ）の内容は秘密に保たれることになる。
【００４２】
具体的には、例えば、多項式ｆ（ｘ）＝Σｉ＝０ｔ−１ａｉｘｉを設定し（Ｚｐ（ｘ）∋ｆ（ｘ））、この定数項ａ０＝乱数ｒ（ｓ、ｊ）とおき、各乱数シェアｒｉ（ｓ、ｊ）＝ｆ（ｉ）とする。この場合、各乱数シェアｒｉ（ｓ、ｊ）＝ｆ（ｉ）がｔ個以上集まれば、それらを用いた連立方程式により多項式ｆ（ｘ）＝Σｉ＝０ｔ−１ａｉｘｉが完全に定まり、その定数項となっている乱数ｒ（ｓ、ｊ）も特定できる。しかし、各乱数シェアｒｉ（ｓ、ｊ）＝ｆ（ｉ）がｔ−１個以下の場合、多項式ｆ（ｘ）＝Σｉ＝０ｔ−１ａｉｘｉは完全に定まらず、定数項となっている乱数ｒ（ｓ、ｊ）も特定できない。なお、このように乱数シェアｒｉ（ｓ、ｊ）のようなシェア情報を用いて乱数ｒ（ｓ、ｊ）のような秘密情報を復元することを多項式補間という。
【００４３】
図１３は、このように生成された乱数シェアｒｉ（ｓ、ｊ）を例示した概念図である。
図１３に例示するように、乱数シェア１１３は、その元となった乱数ｒ（ｓ、ｊ）に対応付けられている入札者１１１及び価格レベル１１２に関連付けられた乱数シェア情報１１０として生成される。この例の場合、（入札者１１１，価格レベル１１２）＝（１，１）（１，２）（１，３）（１，４）（１，５）（１，６）・・・（１，１００）に対し、乱数シェア１１３として「１２３４５６」「６５４３２１」「１１１１１１」「９９９１１１」「２２２８８８」「３２１６５４」「９８７６５４」が対応付けられている。なお、この例では、入札者Ｂ１の乱数シェア情報１１０のみを例示しているが、その他の入札者Ｂｊについても同様に生成される。
このように生成された乱数シェアｒｉ（ｓ、ｊ）は、例えば、制御手段２０ｑを介して記憶手段２０ｐに記憶され、次のステップの処理に移る。
【００４４】
ステップＳ１０：
本ステップでは、電子入札装置２０において、乱数シェアｒｉ（ｓ、ｊ）の送信を行う。
この例の場合、制御手段２０ｑにおいて、記憶手段２０ｐから乱数シェアｒｉ（ｓ、ｊ）を抽出し、抽出した乱数シェアｒｉ（ｓ、ｊ）を、乱数送信手段２０ｋにより、専用回線８０を介して、電子開札装置５０〜７０に分散して送信する。なお、ここでの送信は、例えば、小さな価格レベルに関連付けられた乱数に対応する乱数シェアｒｉ（ｓ、ｊ）から順番に送信する等、各乱数シェアｒｉ（ｓ、ｊ）と、その乱数シェアｒｉ（ｓ、ｊ）の元となっている乱数ｒ（ｓ、ｊ）に対応する（入札者Ｂｊ，価格レベルｓ）と、の対応が、電子入札装置２０から電子開札装置５０〜７０に伝わるように行う。また、例えば、この送信される乱数シェアｒｉ（ｓ、ｊ）には、電子署名手段２０ｎによって電子署名（ＲＳＡ署名等）が付される。
【００４５】
ステップＳ１１：
本ステップでは、電子開札装置５０〜７０において、自装置に割り当てられた乱数シェアｒｉ（ｓ、ｊ）を受信する。
この例の場合、乱数受信手段５０ｃにおいて、乱数シェアｒｉ（ｓ、ｊ）を受信する。この点、電子開札装置６０、７０についても同様である。各電子開札装置５０〜７０において受信された乱数シェアｒｉ（ｓ、ｊ）は、それぞれの記憶手段５０ｊにおいて記憶される。
【００４６】
ステップＳ１２：
本ステップでは、電子開札装置６０、７０において乱数シェアｒｉ（ｓ、ｊ）の送信を行う。
この乱数シェアｒｉ（ｓ、ｊ）の送信は、例えば、開札処理開始時にネットワーク９０を介し、電子開札装置６０、７０から電子開札装置５０に対して行われる。なお、ここでの送信も、例えば、小さな価格レベルに関連付けられた乱数に対応する乱数シェアｒｉ（ｓ、ｊ）から順番に送信する等、各乱数シェアｒｉ（ｓ、ｊ）と、その乱数シェアｒｉ（ｓ、ｊ）の元となっている乱数ｒ（ｓ、ｊ）に対応する（入札者Ｂｊ，価格レベルｓ）と、の対応が、電子開札装置６０、７０から電子開札装置５０に伝わるように行う。また、例えば、この送信される乱数シェアｒｉ（ｓ、ｊ）には、入札者Ｂｊの電子署名（ＲＳＡ署名等）が付されている。
【００４７】
ステップＳ１３：
本ステップでは、電子開札装置５０において、乱数シェアｒｉ（ｓ、ｊ）を受信する。
この例の場合、電子開札装置５０の乱数シェア通信手段５０ｄにおいて、電子開札装置６０、７０からそれぞれ送信された乱数シェアｒｉ（ｓ、ｊ）を受信する。
このように受信された乱数シェアｒｉ（ｓ、ｊ）は、例えば、制御手段５０ｋを介して記憶手段５０ｊに記憶され、次のステップの処理に移る。
【００４８】
ステップＳ１４：
本ステップでは、電子開札装置５０において、落し戸付コミットメント（Ｃｓ，ｊ）の検証を行う。
この例の場合、まず、多項式補間手段５０ｆにおいて、乱数ｒ（ｓ、ｊ）の復元を行い、制御手段５０ｋにより、記憶手段５０ｊに記憶されている落し戸付コミットメント（Ｃｓ，ｊ）と、生成元ｇ、メッセージＭ１、公開鍵ｈｊを抽出し、これらの情報により、落札決定手段５０ｇにおいて、抽出した落し戸付コミットメント（Ｃｓ，ｊ）の検証を行う。この検証では、例えば、この落し戸付コミットメント（Ｃｓ，ｊ）と、乱数ｒ（ｓ，ｊ）と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とする落札処理を行う。この例の場合、例えば、すべての入札者Ｂｊ（ｊ＝１，２，３）について、ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、この演算結果がＣｓ，ｊとなった場合に、この照合が成立したものと判断する。なお、本ステップにおける処理の詳細については後述する。
【００４９】
ステップＳ１５：
本ステップでは、電子開札装置５０において落札価格の公開を行う。
落札価格の公開は、例えば、ネットワーク９０を介し、各電子入札装置に対して電子的に行うこととしてもよく、文書の送付、刊行物への公開等によって行うことしてもよい。
なお、上述したように、公開鍵（ｈｊ）、落し戸コミットメント（Ｃｓ，ｊ）、乱数シェアｒｉ（ｓ、ｊ）には署名が付されており、これらの情報を受信した電子開札装置５０は、その署名検証手段５０ｈによって署名を検証し、送信された公開鍵（ｈｊ）、落し戸コミットメント（Ｃｓ，ｊ）、乱数シェアｒｉ（ｓ、ｊ）の正当性、しいては入札の正当性を検証することができる。
【００５０】
図１０は、図７におけるステップＳ８の処理の詳細を説明するためのフローチャートである。以下、このフローチャートを用いてステップＳ８の処理の詳細を説明する。なお、この説明では、秘密鍵ｘｊを、電子入札装置２０が電子開札装置５０にゼロ知識証明を行う手順を述べるが、落し戸付コミットメント（Ｃｓ，ｊ）の生成に用いられた乱数ｒ（ｓ、ｊ）と入札価格情報との組み合わせ内容、すなわち乱数ｒ（ｓ、ｊ）とそれに対応するメッセージＭ１、Ｍ２との組み合わせ情報（ｌｏｇｇＣｓ，ｊ）の証明も同様な手順によって行う。
【００５１】
ステップＳ２０：
本ステップでは、例えば、電子入札装置２０のゼロ知識証明手段２０ｉにおいて、Ｒ＝ｇｒの演算を行う。なお、ここでｒはｒ∈Ｚｑを満たす任意の数を意味する。このように演算されたＲを特定するための情報は、例えば、制御手段２０ｑを介し、記憶手段２０ｐに記憶される。
【００５２】
ステップＳ２１：
本ステップでは、例えば、電子入札装置２０において、ＣＲ＝Ｈ（Ｒ）の演算を行う。ここで、Ｈとは、例えば、電子開札装置５０によってあらかじめ与えられたＳＨＡ−１等の一方向性ハッシュ関数を意味する。この例の場合、例えば、ステップＳ２０において記憶手段２０ｐに記憶されたＲを特定するための情報を制御手段２０ｑによって取り出し、取り出した情報をゼロ知識証明手段２０ｉに送り、ゼロ知識証明手段２０ｉにおいて、ＣＲ＝Ｈ（Ｒ）の演算を行う。
ステップＳ２２：
本ステップでは、例えば、電子入札装置２０のゼロ知識証明手段２０ｉにおいて、ｙ＝ｒ＋ＣＲ・ｘｊの演算を行う。
【００５３】
ステップＳ２３：
本ステップでは、例えば、ゼロ知識証明手段２０ｉのゼロ知識証明通信手段２０ｍにおいて、ステップＳ２２で演算されたｙとステップＳ２１で演算されたＣＲとを特定するための情報（以下、「（ｙ，ＣＲ）を特定するための情報」という。）を、専用回線８０を介して、電子開札装置５０に送信する。
ステップＳ２４：
本ステップでは、例えば、電子入札装置２０から送信された（ｙ，ＣＲ）を特定するための情報を、電子開札装置５０のゼロ知識証明受信手段５０ａにおいて受信する。
【００５４】
ステップＳ２５：
本ステップでは、例えば、電子開札装置５０において、ＲｈｊＣＲ＝ｇｙの成立の有無を検証する。この例の場合、制御手段５０ｋにおいて記憶手段５０ｊからｙを特定するための情報を抽出し、この情報とステップＳ２４で受信した（ｙ，ＣＲ）を特定するための情報とをゼロ知識証明検証手段５０ｂに送り、このゼロ知識証明検証手段５０ｂにおいてＲｈｊＣＲ＝ｇｙの成立の有無を検証する。
ここで、ＲｈｊＣＲ＝ｇｙが成立した場合には、ステップＳ２６に進み、成立しなかった場合には、ステップＳ２７に進む。
【００５５】
ステップＳ２６：
電子入札装置２０がｘｊの内容を認知していることの証明が成立する。
つまり、前述のように、公開鍵であるｈｊは、ｈｊ＝ｇｘｊによって演算された結果である。したがって、電子入札装置２０がｘｊの内容を知っている場合、ｇｙ＝ｇ（ｒ＋ＣＲ・ｘｊ）＝ｇｒ・ｇＣＲ・ｘｊ＝Ｒ・ｇＣＲ・ｘｊ＝Ｒ・（ｇｘｊ）ＣＲ＝ＲｈｊＣＲが成立することになる。これによりＲｈｊＣＲ＝ｇｙが成立した場合、電子入札装置２０がｘｊの内容を知っていることが証明されることとなる。
なお、この例では、ハッシュ関数を用いて、電子入札装置２０でＣＲを生成することとしたが（ステップＳ２１）、電子開札装置５０がＲを受信した後、乱数ＣＲ∈Ｚｑを生成し、この生成したＣＲを電子開札装置５０から電子入札装置２０に送信する構成としてもよい。
【００５６】
ステップＳ２７：
電子入札装置２０がｘｊの内容を認知していることの証明は成立しない。
つまり、電子入札装置２０がｘｊの内容を知らない場合、ｇｙ＝ｇ（ｒ＋ＣＲ・ｅｘ）＝ｇｒ・ｇＣＲ・ｅｘ＝Ｒ・ｇＣＲ・ｅｘ＝Ｒ・（ｇｅｘ）ＣＲとなり（ｅｘ≠ｘｊ）、この結果はＲｈｊＣＲと等しくならない。これによりＲｈｊＣＲ＝ｇｙが成立しない場合、電子入札装置２０がｘｊの内容を知っていることは証明されない。
図１１は、図９におけるステップＳ１５の処理の詳細を説明するためのフローチャートである。以下、このフローチャートを用いてステップＳ１５の処理の詳細を説明する。なお、以下の説明では入札者の数を３とし、価格表の価格レベルが１から１００まで１刻みで設定されているものとする。
【００５７】
ステップＳ３０：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、価格レベルｓ＝１００の演算を行い、この結果を、例えば、記憶手段５０ｊに格納する。
ステップＳ３１：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、入札者識別子ｊ＝１の演算を行い、この結果を、例えば、記憶手段５０ｊに格納する。
ステップＳ３２：
本ステップでは、電子開札装置５０において、乱数ｒ（ｓ、ｊ）の復元を行う。
この例における乱数ｒ（ｓ、ｊ）の復元は、まず、制御手段５０ｋによって、記憶手段５０ｊから乱数シェアｒｉ（ｓ、ｊ）を抽出し、多項式補間手段５０ｆにおいて、抽出した乱数シェアｒｉ（ｓ、ｊ）を用いた多項式補間を行い、乱数ｒ（ｓ、ｊ）を復元する。
図１４は、このように復元された乱数ｒ（ｓ、ｊ）を例示した概念図である。図１４に例示するように、乱数シェア１２３は、それに対応付けられている入札者１２１及び価格レベル１２２に関連付けられた乱数情報１２０として生成される。この例の場合、価格レベルｓ＝１００、入札者識別子ｊ＝１の場合の乱数ｒ（１００、１）が復元されており、図１４では、（入札者１２１，価格レベル１２２）＝（１，１００）に対し、乱数１２３「９８７６５４」が復元されている。
このように生成された乱数ｒ（ｓ、ｊ）は、例えば、制御手段５０ｋを介して記憶手段５０ｊに記憶され、次のステップの処理に移る。
【００５８】
ステップＳ３３：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）が成立するか否かの検証を行う。
ステップＳ３４：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、入札者識別子ｊ＝ｊ＋１の演算を行い、その結果を、例えば、記憶手段５０ｊに格納する。
ステップＳ３５：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、ｊ＞３であるか否かを判断する。ここで、ｊ＞３であった場合には、ステップＳ３６に進み、ｊ＞３でなかった場合には、ステップＳ３２に進む。
ステップＳ３６：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の成立の有無を判断する。ここで、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）が成立した場合、処理を終了し、成立しなかった場合、ステップＳ３７に進む。
【００５９】
ステップＳ３６：
本ステップでは、電子開札装置５０の落札決定手段５０ｇにおいて、ｓ＝ｓ−１の演算を行い、その結果を、例えば、記憶手段５０ｊに格納する。
図１５は、図１１に例示したフローチャートによる処理を説明するための概念図である。
図１１のフローチャートにおいて、まずステップＳ３０においてｓ＝１００が、ステップＳ３１においてｊ＝１が設定され、ステップＳ３２において乱数ｒ（ｓ、ｊ）が復元され、ステップＳ３３において、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の検証がされているが、これは、価格レベル１００、入札者１についての乱数ｒ（１００、１）が復元され、図１５における価格レベル１００、入札者１についてのＣ１００，１＝ｇＭ１ｈｊｒ（１００，１）の検証が行われていることになる。図１５の例の場合、この検証結果は「不成立」となっている。
【００６０】
その後、ステップＳ３４において、ｊ＝ｊ＋１の演算が行われ、ｊ＝２となるため、ステップＳ３５で「Ｎｏ」となり、ステップＳ３２に進む。次にステップＳ３２では、価格レベル１００、入札者２についての乱数ｒ（１００、２）が復元され、ステップＳ３３では、図１５における価格レベル１００、入札者２についてのＣ１００，２＝ｇＭ１ｈｊｒ（１００，２）検証が行われていることになり、図１５の例の場合、この検証結果は「不成立」となっている。
その後、同様に処理を繰り返し、ｊ＞３となった場合、ステップＳ３６の処理が行われるが、図１５の場合、価格レベル１００、入札者１、２，３についてのＣｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の検証は成立していない。したがって、ステップＳ３７に進み、ｓ＝ｓ−１＝９９の演算が行われステップＳ３１〜Ｓ３６の処理が繰り返される。これは、図１５でいうところの、価格レベル９９、入札者１、２，３についてのＣｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の検証を行うことになる。
【００６１】
その後同様に、価格レベルを下げながら同様な検証を繰り返し、図１５に例示するように、価格レベル９８、入札者２，３で検証が成立したものとする。この場合、この検証処理は終了し、その後の価格レベルに関しての乱数ｒ（ｓ、ｊ）の復元及び検証は行われない。なお、この例の場合、落札価格レベル（ｓ）は「９８」となり、その落札者（ｂｊ）は「２」と「３」になる。
このように、本形態の電子入札装置２０〜４０は、秘密鍵設定手段２０ｂにおいて秘密鍵（ｘｊ）の設定を行い、公開鍵設定手段２０ｃにおいて公開鍵（ｈｊ）の設定を行い、乱数設定手段２０ｄにおいて入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数（ｒ（ｓ，ｊ））を設定し、入札価格情報入力手段２０ｅにおいて、入札価格に対応する価格レベル（ｓ）を特定するための第１の入札価格情報の入力を受け付け、落し戸付コミットメント生成手段２０ｇにおいて、乱数設定手段２０ｄにおいて設定された第１の乱数（ｒ（ｓ，ｊ））と、入札価格情報入力手段２０ｅにおいて入力された第１の入札価格情報とを、公開鍵設定手段２０ｃにおいて設定された公開鍵（ｈｊ）によって暗号化した暗号化情報であって、秘密鍵設定手段２０ｂにおいて設定された秘密鍵（ｘｊ）を用いることにより、第１の乱数（ｒ（ｓ，ｊ））と、第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成し、落し戸付コミットメント開示手段２０ｊにおいて、落し戸付コミットメント生成手段２０ｇにおいて生成された落し戸付コミットメントを開示し、乱数送信手段２０ｋにおいて、乱数設定手段２０ｄにおいて設定された第１の乱数（ｒ（ｓ，ｊ））を、開札者の電子開札装置５０〜７０に、該開札者の電子開札装置５０〜７０に電気的に接続される専用回線８０を通じて送信することとしたため、前述のように、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【００６２】
また、本形態の例では、ゼロ知識証明手段２０ｉにおいて、ゼロ知識証明により、秘密鍵（ｘｊ）、及び落し戸付コミットメントの生成に用いられた第１の乱数（ｒ（ｓ，ｊ））と第１の入札価格情報との組み合わせ内容（ｌｏｇｇＣｓ，ｊ）を認知していることを開札者の電子開札装置に証明することとしたため、談合主催者が自ら公開鍵（ｈｊ）を生成し、その秘密鍵を談合主催者側で秘密に保ったまま、その公開鍵（ｈｊ）を入札者Ｂｊに渡し、入札者Ｂｊに対し、この公開鍵（ｈｊ）を用いて入札処理を行うように強制する不正を防止することができ、結果、入札の談合を抑制することが可能となる。
【００６３】
さらに、本形態の例では、第１の乱数（ｒ（ｓ，ｊ））を複数の乱数シェア（ｒｉ（ｓ，ｊ））に秘密分散する乱数秘密分散手段２０ｈ、をさらに有し、乱数送信手段２０ｋにおいて、乱数秘密分散手段２０ｈにおいて秘密分散された複数の乱数シェア（ｒｉ（ｓ，ｊ））を、複数の開札者の電子開札装置５０〜７０に分散させて送信することとしたため、複数の電子開札装置５０〜７０が協力しなければ乱数（ｒ（ｓ，ｊ））を復元できず、結果、何れかの開札者が開札前に入札価格を閲覧するという不正を抑制することができる。
また、本形態の例において、落し戸付コミットメント開示手段２０ｊにおいて、署名付きの落し戸付コミットメント（Ｃｓ，ｊ）を開示し、乱数送信手段２０ｋにおいて署名付きの第１の乱数（ｒ（ｓ，ｊ））を乱数シェア（ｒｉ（ｓ，ｊ））として送信し、開札時に開示することにより、誰でも入札の正当性を検証することができる。
【００６４】
さらに、本形態の例では、落し戸付コミットメント生成手段２０ｇにおいて、乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する第１の乱数をｒ（ｓ，ｊ）とし、入札を行わない価格レベルであることを示す第１の入札価格情報をＭ０とし、入札を行う価格レベルであることを示す第１の入札価格情報をＭ１とした場合において、価格レベルｓが入札を行う価格レベルでないときには、Ｃｓ，ｊ＝ｇＭ０ｈｊｒ（ｓ，ｊ）の演算を行い、価格レベルｓが入札を行う価格レベルであるときには、Ｃｓ，ｊ＝ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、これらの演算結果を落し戸付コミットメント（Ｃ１，ｊ　，　Ｃ２，ｊ，　・・・，　Ｃｍ，ｊ）として生成することとしたため、前述のように、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【００６５】
また、本形態における電子開札装置５０では、落し戸付コミットメント取得手段５０ｅにおいて、入札者によって開示された落し戸付コミットメント（Ｃｓ，ｊ）を取得し、乱数受信手段５０ｃにおいて、入札者の電子入札装置２０〜４０に電気的に接続される専用回線８０を通じ、該入札者の電子入札装置２０〜４０から送信された、入札者（Ｂｊ）と複数の価格レベル（ｓ）との組み合わせごとに対応付けられた乱数（ｒ（ｓ，ｊ））を、乱数シェア（ｒｉ（ｓ，ｊ））として受信し、落札決定手段５０ｇにおいて、落し戸付コミットメント取得手段５０ｅにおいて取得された落し戸付コミットメント（Ｃｓ，ｊ）と、受信された乱数（ｒ（ｓ，ｊ））と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とすることとしたため、前述のように、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【００６６】
また、図１１及び図１５を用いて説明したように、本形態の例では、落札決定手段５０ｇにおいて、第１の価格レベルに対応する乱数と、落し戸付コミットメントと、の照合を行った結果、該照合が不成立であった場合、該第１の価格レベルよりも値段の安い第２の価格レベルに対応する乱数と、落し戸付コミットメントと、の照合を行うこととしたため、落札者がでた以降、乱数（ｒ（ｓ、ｊ））の復元及び落し戸付コミットメント（（Ｃｓ，ｊ））の検証を行わないことにより、落札価格よりも安い入札価格が公開されることを防止することができる。これにより、談合主催者が入札価格をコントロールすることが困難となり、結果、入札時の談合を抑制することが可能となる。
【００６７】
さらに、本形態の例では、乱数受信手段５０ｃにおいて、乱数（ｒ（ｓ、ｊ））を複数に秘密分散した乱数シェア（ｒｉ（ｓ，ｊ））の一部を受信し、乱数シェア通信手段５０ｄにおいて、他の電子開札装置において受信された乱数シェア（ｒｉ（ｓ，ｊ））を取得し、多項式補間手段５０ｆにおいて、乱数受信手段５０ｃにおいて取得された乱数シェアと、乱数シェア通信手段５０ｄにおいて取得された乱数シェアと、を用い、多項式補間によって、乱数を復元することとしたため、複数の電子開札装置５０〜７０が協力しなければ乱数（ｒ（ｓ，ｊ））を復元できず、結果、何れかの開札者が開札前に入札価格を閲覧するという不正を抑制することができる。
【００６８】
また、本形態の例では、落札決定手段５０ｇにおいて、落し戸付コミットメントをＣｓ，ｊとし、乗法群の部分群の生成元をｇとし、入札者Ｂｊに対応する公開鍵をｈｊとし、価格レベルｓ、入札者Ｂｊに対応する乱数をｒ（ｓ，ｊ）とし、入札を行う価格レベルであることを示す入札価格情報をＭ１とした場合における、ｇＭ１ｈｊｒ（ｓ，ｊ）の演算を行い、該演算結果がＣｓ，ｊとなった場合には、照合が成立したものと判断することとしたため、前述のように、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【００６９】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、本形態では、電子開札装置６０、７０から電子開札装置５０への乱数シェアの送信を、ネットワーク９０を介して行うこととしたが、この送信を、専用回線を介して行うこととしてもよい。また、電子入札装置２０〜４０から電子開札装置５０〜７０への公開鍵（ｈｊ）、落し戸付コミットメント（（Ｃｓ，ｊ））及びゼロ知識証明に関する証明情報の送信を専用回線以外のネットワークを介して行うこととしてもよい。
また、本形態では、電子開札装置５０が落札処理を行うこととしたが、その他の電子開札装置が落札処理を行うこととしてもよく、さらに、落札処理のみを行う別の端末を設け、この端末に落札処理を行わせる構成としてもよい。
【００７０】
また、本形態における入札価格表１００は、入札価格の各価格レベル１０１及び、各価格レベル１０１に一対一で対応する価格１０２の情報によって構成されているものとしたが、価格１０２を設けず、各価格レベル１０１自体が価格を示すこととしてもよい。
さらに、本形態では、図９に例示したフローチャートのステップ１３において、電子開札装置５０によってすべての乱数シェアを受信することとしたが、このステップ１３での電子開札装置５０による乱数シェアの受信を行わず、図１１にフローチャートのステップＳ３２の処理時において、検証中の落札者Ｂｊ及び価格レベルｓのみの乱数シェアを、電子開札装置５０によって受信することとしてもよい。これにより、電子開札装置５０でさえ、落札以降の各入札価格を知ることができなくなり、入札の公平性がさらに向上する。
【００７１】
また、本形態では、コンピュータ上で所定のプログラムを実行させることにより、本形態における電子入札装置及び電子開札装置を構成することとしたが、これらの処理内容の少なくとも一部を電子回路によってハードウェア的に実現することとしてもよい。
さらに、上述のように、上記の処理機能は、コンピュータによって実現することができる。この場合、電子入札装置及び電子開札装置が有すべき機能の処理内容はプログラムによって記述され、このプログラムをコンピュータで実行することにより、上記処理機能をコンピュータ上で実現することができる。
【００７２】
また、この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Ｄｉｇｉｔａｌ　Ｖｅｒｓａｔｉｌｅ　Ｄｉｓｃ）、ＤＶＤ−ＲＡＭ（Ｒａｎｄｏｍ　Ａｃｃｅｓｓ　Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ（Ｃｏｍｐａｃｔ　Ｄｉｓｃ　Ｒｅａｄ　Ｏｎｌｙ　Ｍｅｍｏｒｙ）、ＣＤ−Ｒ（Ｒｅｃｏｒｄａｂｌｅ）／ＲＷ（ＲｅＷｒｉｔａｂｌｅ）等を、光磁気記録媒体として、ＭＯ（Ｍａｇｎｅｔｏ−Ｏｐｔｉｃａｌ　ｄｉｓｃ）等を用いることができる。
【００７３】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Ａｐｐｌｉｃａｔｉｏｎ　Ｓｅｒｖｉｃｅ　Ｐｒｏｖｉｄｅｒ）型のサービスによって、上述の処理を実行する構成としてもよい。
【００７４】
なお、上記におけるプログラムとは、電子計算機に対する指令であって、一の結果を得ることができるように組合されたものをいい、その他電子計算機による処理の用に供する情報であってプログラムに準ずるものをも含むものとする。
【００７５】
【発明の効果】
以上説明したように本発明の電子入札装置では、秘密鍵設定手段において秘密鍵の設定を行い、公開鍵設定手段において公開鍵の設定を行い、乱数設定手段において入札者と複数の価格レベルとの組み合わせごとに対応付けられる第１の乱数を設定し、入札価格情報入力手段において、入札価格に対応する価格レベルを特定するための第１の入札価格情報の入力を受け付け、落し戸付コミットメント生成手段において、乱数設定手段において設定された第１の乱数と、入札価格情報入力手段において入力された第１の入札価格情報とを、公開鍵設定手段において設定された公開鍵によって暗号化した暗号化情報であって、秘密鍵設定手段において設定された秘密鍵を用いることにより、第１の乱数と、第１の入札価格情報と、の組み合わせからなる第１の組み合わせ情報の復号を行うことも、第１の乱数とは異なる第２の乱数と、第１の入札価格情報によって特定される価格レベルとは異なる価格レベルを特定するための第２の入札価格情報と、の組み合わせからなる第２の組み合わせ情報の復号を行うことも、自由に選択することが可能な落し戸付コミットメントを生成し、落し戸付コミットメント開示手段において、落し戸付コミットメント生成手段において生成された落し戸付コミットメントを開示し、乱数送信手段において、乱数設定手段において設定された第１の乱数を、開札者の電子開札装置に、該開札者の電子開札装置に電気的に接続される専用回線を通じて送信することとしたため、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【００７６】
また、本発明の電子開札装置では、落し戸付コミットメント取得手段において、入札者によって開示された落し戸付コミットメントを取得し、乱数受信手段において、入札者の電子入札装置に電気的に接続される専用回線を通じ、該入札者の電子入札装置から送信された、入札者と複数の価格レベルとの組み合わせごとに対応付けられた乱数を受信し、落札決定手段において、落し戸付コミットメント取得手段において取得された落し戸付コミットメントと、受信された乱数と、の照合を行い、該照合が成立した乱数に対応する価格レベルを落札価格とし、該照合が成立した乱数に対応する入札者を落札者とすることとしたため、第３者である談合主催者に入札者が入札価格を証明できないようになり、結果、入札の談合を抑制することが可能となる。
【図面の簡単な説明】
【図１】電子入札システムの概略を説明するための概念図。
【図２】電子入札システムの全体構成の詳細を説明するための概念図。
【図３】電子入札装置のハードウェア構成を例示したブロック図。
【図４】電子入札装置の処理機能を例示した機能ブロック図。
【図５】電子開札装置の処理機能を例示した機能ブロック図。
【図６】電子入札システムの処理動作を説明するためのフローチャート。
【図７】電子入札システムの処理動作を説明するためのフローチャート。
【図８】電子入札システムの処理動作を説明するためのフローチャート。
【図９】電子入札システムの処理動作を説明するためのフローチャート。
【図１０】図７におけるステップＳ８の処理の詳細を説明するためのフローチャート。
【図１１】図９におけるステップＳ１５の処理の詳細を説明するためのフローチャート。
【図１２】入札価格表の構成を例示した概念図。
【図１３】乱数シェアを例示した概念図。
【図１４】復元された乱数を例示した概念図。
【図１５】図１１に例示したフローチャートによる処理を説明するための概念図。
【符号の説明】
１、１０　電子入札システム
２、２０〜４０　電子入札装置
３、５０〜７０　電子開札装置
【図１】
2004118654.tif 000003
【図２】
2004118654.tif 000004
【図３】
2004118654.tif 000005
【図４】
2004118654.tif 000006
【図５】
2004118654.tif 000007
【図６】
2004118654.tif 000008
【図７】
2004118654.tif 000009
【図８】
2004118654.tif 000010
【図９】
2004118654.tif 000011
【図１０】
2004118654.tif 000012
【図１１】
2004118654.tif 000013
【図１２】
2004118654.tif 000014
【図１３】
2004118654.tif 000015
【図１４】
2004118654.tif 000016
【図１５】
2004118654.tif 000017