JPH02118876A - 電子式入札システム - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 ［発明の目的〕 （産業上の利用分野） 本発明は、通信ネットワーク上に分散配置された複数の
入札者が電子的手段によって入札を行うプロトコルを実
現する電子式入札方式に関する。

（従来の技術） 電気通信システムを用いた電子式入札、すなわちネット
ワーク上に分散配置された入札者が電子的手段によって
競争入札する場合の入札プロトコルでは、入札額を他の
入札者に秘密裏に開札者に届ける必要がある。この対策
として、暗号化の手法が利用されている。また、通常の
入札では、入札者と開札者が一同に会して入札・開孔を
行うので、開札者の不正は困難であると考えられている
。しかしながら、電気通信を利用するときには、開札者
と入札者が物理的に離れているので、開札者がその立場
を悪用して落札額を不正に操作する恐れがある。この対
策として、入札額に署名するディジタル署名の手法が利
用されている。

従来、提案されている電子式入札方式としては、例えば
山村三朗による「ネットワーク上における入札の一手法
Ｊ　　（１９８８年暗号色情報セキュリティワークショ
ップ講演論文集、ＷＣｌ５８８−５．９ｐ、４ｌ−５０
）に開示されたものがある。

コノ山村民の方式では、暗号通信とディジタル署名と同
報通信とを組み合わせることにより上述した問題を解決
している。

（発明が解決しようとする課題） 通常の入札では、入札額は開札者のみが知っており、他
人に知られることはない。落札額以外の入札額は後日の
商活動などに影響するので、知られる範囲を必要最小限
にとどめることが好ましいものであるが、上述した山村
民の方法では、入札額が全員に知られてしまう問題があ
る。

本発明は、上記に鑑みてなされたもので、その目的とす
るところは、入札の主催者側である身元確認者と開札者
とが結託したとしても落札額以外の入札額と入札者との
対応関係を秘密にできる電子式入札方式を提供すること
にある。

［発明の構成］ （課題を解決するための手段） 上記目的を達成するため、本発明の電子式入札方式は、
開札者に対する複数の入札者からの入札を通信ネットワ
ークを利用して電子的に行う電子式入札方式であって、
入札者は入札額ｍの圧縮値αをα＝Ｈ（ｍ）で作成して
開札者に送信し、開札者はすべての入札者から圧縮値α
を受信して公開し、入札者は圧縮値αの公開後に入札額
ｍを開札者に送信し、開札者はすべての入札者から入札
額ｍを受信すると、入札額ｍに対する圧縮値Ｈ（ｍ）を
算出してα＝Ｈ（ｍ）が満たされることを検査してから
受信したすべての入札額ｍを公開して落札額を決定し、
これにより入札額用を公開する前に前記圧縮値Ｈ（ｍ）
を公開することで開札者が入札額用を見た後に入札でき
ないようにしたことを要旨とする。

また、本発明の電子式入札方式は、身元確認者によって
身元を確認された複数の入札者からの開札者に対する入
札を通信ネットワークを介して電子的に行う電子式入札
方式であって、入札者は乱数発生器からの乱数成分およ
び入札額ｍを撹乱器によって攪乱した入札額ｍに対応す
る通信文ｍを作成して身元確認者に送信し、身元確認者
は入札者の身元を確証した後に、攪乱された前記通信文
ｍ゛を証明器に人力し署名付き通信文Ｄ　（ｍ’　）を
作成して入札者に返送し、入札者は前記署名付き通信文
Ｄ　（ｍ”　）から乱数成分の影響を除去して入札額ｍ
に署名を施した署名値Ｄ　（ｍ）を求めた後、入札額ｍ
に対応する圧縮値αをα＝Ｈ（ｍ）で作成して開札者に
送信し、開札者はすべての入札者からの圧縮値αを受信
して公開し、入札者は圧縮値αの公開後に入札額ｍを開
札者に送信し、開札者はすべての入札者から入札額ｍを
受信すると、該入札額ｍに対する圧縮値Ｈ（ｍ）を算出
してα＝Ｈ（ｍ）が満たされていることを検査してから
受信したすべての入札額ｍを公開して落札額ｍｏを決定
し、落札額ｍｏを入札した入札者は落札額ｍｏに署名を
施した署名値Ｄ（ｍｏ）を開札者に送信し、開札者は該
署名値Ｄ（ｍｏ）が落札額ｍｏに対する正しい署名であ
ることを検査して落札者の身元が身元確認者によって承
認され、かつ落札者が真に落札額ｍｏを入札したことを
確認し、これにより身元確認者と開札者とが結託しても
開札者が落札者以外の入札額と入札者との対応関係を知
ることができないようにしたことを要旨とする。

更に、本発明の電子式入札方式は、身元確認者によって
身元を確認された複数の入札者からの開札者に対する入
札を通信ネットワークを介して電子的に行う電子式入札
方式であって、身元確認者は初期応答文を入札者に送信
し、入札者は該受信した初期応答文、乱数発生器からの
乱数成分および入札額ｍに対する問い合わせ文β、β゛
を作成して身元確認者に送信し、身元確認者は前記初期
応答文および前記受信した問い合わせ文に対応する応答
文を証明器を用いて生成して入札者に返送し、入札者は
前記応答文、前記乱数成分および前記問い合わせ文から
乱数成分の影響を除去して入札額ｍに対応する署名値２
゛を求めた後に、入札額ｍに対する圧縮値αをα＝Ｈ（
ｍ）で作成して開札者に送信し、開札者はすべての入札
者から圧縮値αを受信して公開し、入札者は圧縮値αの
公開後に入札額ｍを開札者に送信し、開札者はすべての
入札者からの入札額ｍを受信すると、入札額ｍに対する
圧縮値Ｈ（ｍ）を算出してα＝Ｈ（ｍ）を満たすことを
検査した後、受信したすべての入札額用を公開して落札
額ｍｏを決定し、落札額ｍｏを入札した入札者は落札額
ｍｏに対応する署名２　、βを開札者に送信し、開札者
は該署名２゛βが落札額ｍｏに対する正しい署名である
ことを検査して、落札者の身元が身元確認者によって承
認され、かつ落札者が落札額ｍｏを入札したことを確認
し、これにより身元確認者と開札者とが結託しても開札
者が落札者以外の入札額と入札者との対応関係を知るこ
とができないようにしたことを要旨とする。

（作用） 本発明の電子式入札方式においては、入札者から入札額
ｍに対する圧縮値を作成して開札者に送信し、開札者が
すべての入札者から圧縮値を受信して公開した後、入札
者は入札額ｍを開札者に送信し、これにより開札者が入
札額ｍを見た後に不正に入札できないようにしている。

開札者はすべての入札額ｍを受信して落札額ｍｏを決定
する。

また、入札者は圧縮値を開札者に送信する前に身元確認
者に身元を確認してもらい、入札額ｍの署名値を求めて
おき、落札者は前記署名値を開札者に送信し、開札者は
落札者の身元が身元確認者によって承認されていること
を確認する。身元確認者が署名するのは入札額そのもの
でなく、入札者のみが知る乱数成分を付加した値であり
、入札者はこの乱数成分の影響を除去して入札額に対す
る署名値を求めている。

（実施例） 以下、図面を用いて本発明の詳細な説明する。

第１図、第２図および第３図は、本発明の一実施例に係
わる電子式入札方式に使用される入札者用装置１００、
身元確認者用装置２００および開札者用装置３００の構
成を示すブロック図をそれぞれ示している。これらの入
札者用装置１００、身元確認者用装置２００および開札
者用装置３００はそれぞれ第４図に示すように通信回線
を介して接続されている。

本実施例に示す電子式入札方式においては、身元確認者
が入札者の身元を確認し、この確認を証明する署名を入
札者に送信し、入札者が入札額ｍから求めたデータ圧縮
値Ｈ（ｍ）を開札者に送信し、開札者がすべての圧縮値
Ｈ（ｍ）を公開した後に、入札者が入札額ｍを開札者に
送信し、開札者がその値を公開して落札額ｍｏを決定し
、落札者が落札額ｍｏに対する署名値を開札者に提示し
て、開札者が落札者の正当性を認定する。ここで、身元
確認者と開札者とが結託しても入札者と入札額の対応を
秘密にできるようにするために身元確認者に対して入札
額を秘密にしたまま身元確認者に署名されるようにして
いる。

身元確認者は、ｆ　（ｇ　（ｘ）　）　＝ｇ　（ｆ　（
ｘ）　）＝ｘ、ｇ　（ｘＸｙ）＝ｇ　（ｘ）Ｘｇ　（ｙ
）　、かつｆからｇを求めるのが困難な２つの関数の組
（ｆ。

ｇ）を選択して、関数〔を公開し、関数ｇを秘密にする
。

この性質を満たす関数として、例えばＲ８Ａ暗号の暗号
化関数と復号化関数がある。Ｒ８Ａ暗号（Ｒｌｖｅｓｔ
　、　Ｒ，Ｌ、ｅｔａｌ、　　−Ａ　　Ｍｅｔｈｏｄ　
ｆ’ｏｒＯｂｔａｉｎｉｎｇ　　Ｄｉｇｉｔａｌ　　Ｓ
ｉｇｎａｔｕｒｅｓ　ａｎｄ　Ｐｕｂｌｌｃ　−Ｋｅｙ
　　Ｃｒｙｐｔｏｓｙｓｔｅｍｓ　　、　Ｃｏｍ５＋ｕ
ｎｌｃａｔｌｏｎｓｏｆ’　ｔｈｅ　　ＡＣＭ、　Ｖｏ
ｌ、　２１．　Ｎｏ　、　　２．　ｐｐ、　　１２０−
１２６．　　（１９７８））を用いた（ｆ、　　ｇ）の
構成例は以下の通りである。

身元確認者は暗号化鍵（ｅ、Ｎ）と復号化鍵（ｄ、　Ｎ
）を Ｎ＝ＰＸＱ ｅＸｄＥｌ　（ｍｏｄＬ） 但しＬ−ＬＣＭ　＋　（Ｐ−１）、　　（Ｑ−１））を
満たすように生成し、暗号化鍵を公開し、復号化鍵を秘
密に管理する。

ここで、ＬＣＭ　（ａ、ｂ）は整数ａとｂの最小公倍数
を表して、ＰとＱは相異なる２つの大きな素数とする。

また、ａ＝ｂ　（ｍｏｄ　Ｌ）はａ−ｂがＬの倍数であ
ることを表す。

Ｒ８Ａ暗号は、Ｎが大きいときＮの素因数分解が困難な
ことに安全性の根拠を持つ暗号であり、公開された暗号
化鍵（Ｎ、ｅ）から秘密の復号化鍵のｄ成分を求めるこ
とは困難である。

暗号化関数ｆと復号化関数ｇを ｆ　（Ｍ）−Ｍ＠（ｍｏｄ　Ｎ） ｇ　（Ｃ）　＝Ｃ’　　（＋＋＋ｏｄ　Ｎ）で定義する
と、Ｏ≦ｘ＜Ｎを満たす整数Ｘに対して ｇ　　（ｆ　　（ｘ）　）　　−ｆ　　（ｇ　　（ｘ）
　）　　＝ｘが成り立つことを示せる。ここで、ａ　（
ｍｏｄ　Ｎ）は、ａをＮで割ったときの余りを表す。更
に、０≦ｘ、ｙ＜Ｎを満たす整数ｘ、　　ｙに対してｇ
　（ｘＸｙ）−ｇ　（ｘ）Ｘｇ　（ｙ）が成り立つこと
が示せる。

以下では、関数ｇを署名関数として使用し、関数ｆを認
証関数として使用する。ｆおよびｇとしてＲ３Ａ暗号を
用いる場合のｆ計算器とｇ計算器の効率のよい計算方法
は、例えば池野、小山による「現代暗号理論」、電子通
信学会、ｐｐ、１６−１７、（１９８６）に示されてい
る。

次に、第５図に示す交信順序例および第１図〜第４図を
参照して詳細に説明する。

まず、入札者は入札者用装置１００の乱数発生器１１０
を使用して乱数Ｒを生成し、撹乱器１２０に供給する。

該撹乱器１２０では、関数ｆを計算するｆ計算器１２１
を用いて、乱数Ｒに対するｆ　（Ｒ）を算出し、乗算器
１２２に供給する。それから、この乗算器１２２には入
札額ｍが入力される。乗算器１２２は、入札額ｍおよび
ｆ　（Ｒ）を整数と見なし、公開されたＮを用いて撹乱
された通信文ｍ°を次式により計算する。

ｍ’　＝ｍＸ　ｆ　（Ｒ）　　（ｍｏｄ　Ｎ）そして、
この計算された通信文ｍ°を身元確認者用装置２００に
送信する（第５図のステ・ツブ１１０）。なお、この時
、入札者−身元確認者間は署名通信を行うとよい。

身元確認者用装置２００における身元確認者は入札者用
装置１００から送信されてきた通信文ｍを受信すると、
入札者の身元を確認し、それから入札者用装置１００か
らの通信文ｍ゛を証明器２１０に供給する。証明器２１
０は、関数ｇを計算するｇ計算器２１１を用いて通信文
ｍ°に対応する署名付き通信文Ｓ°を次式により計算す
る。

ｓ’　　＝ｇ　　（ｍ’　） それから、この計算した署名付き通信文Ｓ°を入札者用
装置１００に送信する（ステ・ツブ１２０）。

入札者は、入札者用装置１００によって身元確認者用装
置２００からの署名付き通信文Ｓ゛を乱数成分除去器１
３０で受信する。また、この乱数成分除去器１３０には
、前記乱数発生器１１０からの乱数Ｒおよび前記公開さ
れたＮが供給されているので、乱数成分除去器１３０は
身元確認者用装置２００から受信した署名付き通信文Ｓ
゛、乱数Ｒおよび公開されたＮから次式によって入札額
ｍに対応する署名値Ｓを計算する。

Ｓそｓ　’　／Ｒ（ｓｈｏｄ　Ｎ） そして、この計算した署名値Ｓをメモリ１４０に記憶す
る。

また、入札者は、入札額ｍをデータ圧縮器１５０に供給
し、次式により入札額ｍに対応する圧縮値αを計算する
。

α＝Ｈ（ｍ） この計算された圧縮値αを開札者に送信する（ステップ
１３０）。

開札者は、開札者用装置３００によって入札者用装置１
００から送信された圧縮値αを順次受信し、すべての入
札者からの圧縮値αを受信すると、その値を公開ファイ
ル３１０に登録して公開する（ステップ１４０）。

入札者は、すべての圧縮値αが公開された後、入札額ｍ
を開札者用装置３００に送信する（ステップ１５０）。

開札者は、開札者用装置３００によって入札者からの入
札額ｍを受信すると、該入札者をデータ圧縮器３２０に
供給し、該データ圧縮器３２０で圧縮された出力結果が
前記公開ファイル３１０に登録されたいずれかの圧縮値
αと一致するか否かを比較器３２５で比較して検査し、
それから入札額用を公開する（ステップ１６０）。そし
て、登録されたすべての入札額ｍがら落札額ｍｏを決定
する。

落札額ｍｏを決定された入札者（以下、落札者と称する
）は、落札額ｍｏに対応する署名値Ｓを前記メモリ１４
０から読み出して開札者用装置３００に送信する（ステ
ップ１７０）。

開札者は、開札者用装置３００によって入札者からの署
名値Ｓを受信すると、該署名値Ｓを検査器３３０に供給
し、検査値３３０のｆ計算器３３１で該署名値Ｓに対応
するｆ　（ｓ）を計算し、この計算されたｆ　（ｓ）を
比較器３３２に供給し、該比較器３３２において前記落
札額ｍｏと比較して一致することを検査し、署名値Ｓが
落札額ｍｏに対応した署名値であることを認定する。

第６図、第７図および第８図は、本発明の他の実施例に
係わる電子式入札方式に使用される入札者用装置１０１
、身元確認者用装置２０１および開札者用装置３０１の
構成を示すブロック図をそれぞれ示している。なお、こ
れらの装置１０１゜２０１．３０１はそれぞれ前述した
第１図〜第３図に示した装置１００，２００．３００に
対応するものであり、該装置１００，２００．３００と
共通の構成要素は省略して図示されている。また、前述
した第１図〜第３図に示す実施例はＲ８Ａ暗号を利用す
るのに対して、この第６図〜第８図に示す実施例は、Ｆ
ｉａｔとＳｈａｍｉｒの認証方式を利用している。

このＦ　ｉ　ａ　ｔ−３ｈａｍｔ　ｒ法は、信頼できる
センタが個人識別情報としてＩＤを用いる利用者に対し
て、次の手順でに個の秘密情報５ｉ（１≦ｊ≦ｋ）を生
成する。ここで、ｋは安全性を定めるパラメータであり
、１以上の値である。また、Ｎは公開情報であり、秘密
の素数ＰとＱとを用いて、Ｎ＝ＰＸＱと表せる。ｆは一
方向性関数であり、公開されている。

すなわち、まず、一方向性関数ｆを用いて、ｖ　ｊ＝ｆ
　（ＩＤ、Ｊ）　　　　（１≦ｊ≦ｋ）を計算する。

それから、各ｖｊに対してＮの素因数ＰとＱを用いて、 Ｓｊ＝　　１／ｖｊ　　　　（ｍｏｄＮ）を計算する。

すなわち、Ｓ　ｊ２＝１／ｖ　ｊ　　（ｍｏｄＮ）とな
る。

更に、利用者に対してに個のｓｊを秘密に発行し、一方
向性関数ｆと合成数Ｎを公開する。

（ｍｏｄ　Ｎ）における平方根の計算は、Ｎの素因数（
ＰとＱ）がわかっているときのみ実行できる。

その方法は、例えばＲａｂｉｎ、Ｍ、Ｏ，：“Ｄｌｇｌ
　ｔａｌｌｚｅｄＳｉｇｎａｔｕｒｅ　ａｎｄ　Ｐｕｂ
ｌｉｃ−Ｋｅｙ　Ｆｕｎｃｔｌｏｎｓ　ａｓ　１ｎＬｒ
ａｃｔａｂｌｅ　ａｓ　Ｆ’ａｃｔｏｒＩｚａＬＩｏ”
　、　Ｔｅｃｈ、Ｒｅｐ、旧Ｔ／ＬＣ３／ＴＲ−２１２
ＨＩＴ　Ｌａｂ、Ｃｏｍｐｕｔ、Ｓｃ１．１９７９に示
されている。

平方根の計算装置の具体的な構成例は特願昭６１−１６
９３５０　（公開鍵暗号システム）に開示されている。

また、Ｆ　ｉ　ａ　ｔ−８ｈａｍｉ　ｒ法による利用者
の認定方式は次の通りである。

証明者Ａは検証者Ｃに対して、Ａが本物であることを次
の手順で証明する。

まず、ＡがＩＤをＣに送る。

それから、Ｃは次式を計算する。

ｖｊ＝ｆ　（ＩＤ、ｊ）　　　　（１≦ｊ≦ｋ）次に、
ｉ−１，・・・・・・、ｔについて以下の手順を繰り返
す（ｔは安全性を定めるパラメータであり、１以上の値
である）。

まず、乱数ｒ、を生成して、 ｘｉ−ｒｉ２　　　　（ｍｏｄＮ） を計算して、Ｃに送る。

それから、Ｃが０．　１のビット列（ｅｌｌ＋　・・・
・・・ｅｌ、）を生成して、Ａに送る。

更に、Ａが署名文ｙｉを ｙｉ＝ｒｉ　　Ｕ　　ｓｊ　　　（ｍｏｄＮ）ｅｌｊ＝
１ で生成して、Ｃに送る。

また、Ｃは、 ｘｉ＝ｙ１２Ｕ　　ｖｊ　　　　（ｍｏｄ　Ｎ）ｅｌｊ
＝１ が成り立つことを検査する。

ｙｉの作り方よりｙ　１２ＩＩｖ　ｉ＝ｒ　１２ＩＩ　
（ｓｅｉｊ＝ｌ　　　　ｅｌｊ−１ ら、を回の検査にすべて合格した場合、検証者ＣはＡが
本物あると認める。

以上では、利用者の認証方式について説明したが、メツ
セージの認証方式は上記の手順を次のように変更して実
現できる。

メツセージ（ｍ）と（Ｘｌ、・・・・・・、Ｘ、）に一
方向性関数ｆを施して得たｆ（ｍ、ｘ、、・・・・・・
ｘ、）の先頭のｋｘｔビットを上記手順のビット列（ｅ
、＋）とみなして、署名文として、（ＩＤ。

ｒＴ１＋　　（ｅ　ＩＩ）　＋　　Ｖ　ｌ　＊　・・・
・・・、ｙ＋）を署名つき通信文として検証者に送信す
る。

次に、第９図に示す交信順序例および第６図〜第８図を
参照して詳細に説明する。なお、本実施例では、身元確
認者−入札者間ではＦｉａｔ−８ｈａｍｉｒ法の利用者
認証法を利用し、入札者−開札者間ではＦ　ｉａ　ｔ−
３ｈａｍｉ　ｒ法のメツセージ認証法を利用している。

２つの認証法を対応づける情報を入札者において秘密に
することで、身元確認者と開札者が結託しても入札者と
入札額の対応を秘密にしている。

ｉ２　ｘＶ、）＝ｒ、　　２　＝ｘ （ｍｏｄＮ）であるか Ｆ　ｉ　ａ　ｔ−３ｈａｍｉ　ｒ法の場合と同様に、信
頼できるセンタが合成数Ｍと一方向性関数ｆを公開し、
更に証明者Ａの識別情報ＩＤに対応する秘密情報Ｓを計
算して、ＳをＡに配送する。以下の説明では、ｋ＝１の
場合について説明する。

入札者は、身元確認者の力を借りて、次の手順で入札額
ｍに署名する。

まず、身元確認者は、ＩＤを入札者用装置１０１および
開札者用装置３０１に送信する（第９図のステップ２１
０）。

それから、身元確認者、入札者および開札者は、それぞ
れ身元確認者用装置２０１、入札者用装置１０１および
開札者用装置３０１のデータ圧縮器２２０．１６０およ
び３５０を用いて、ｘ＝ｆ（ＩＤ）を計算する。

更に、身元確認者は、初期応答文発生器２３０を用いて
ｔ個の初期応答文ｘ’　、（ｉ＝１．２゜・・・・・・
、ＢからなるＸ“を計算し、この初期応答文Ｘ°を入札
者用装置１０１に送信する（ステップ２２０）。

なお、初期応答文発生器２３０は、乱数発生器２３１お
よび剰余付き乗算器２３２から構成され、乱数発生器２
３１からｔ個のｒｉを発生し、剰余付き乗算器２３２を
用いて、 ｘ’　　＝ＸＸｒ　ｌ　　　　　　（ｇｏｄ　Ｎ）（ｉ
＝１．２．・・・・・・、１） で、を個のＸ’　ｌを計算する。

前記初期応答文Ｘ°が入札者用装置１０１で受信される
と、乱数発生器１７０を用いてｔ組のビットｅ１と乱数
ｕ１のペアを発生し、その値を受信したｔ個のＸ”１と
先に生成したＸとともに初期応答文撹乱器１７５に入力
し、を個の撹乱された初期応答文ｘ°°１を計算してＸ
　”ｗ　（Ｘ　ｔ＋１゜・・・・・・Ｔ　　Ｘ”ｔ）を
問い合わせ文発生器１８０に供給する。

例えば、初期応答文撹乱器１７５を剰余付き乗算器で構
成し、乱数発生器１７０が生成したｔ組のｅｌとｕｌ、
受信したｔ個の初期応答文ＸおよびＸを剰余付き乗算器
１７５に入力し、Ｘ”ｉ　＝ｕ＋　２ｘＸ−”　ｘＸ’
　ｌ　　（ａ＋ｏｄ　Ｎ）（ｉ−１，２，・・・・・・
、　　Ｂ でｔ個のｘ”ｉを計算する。

次に入札者は、入札額ｍとｔ個のｘ　”、入札者用装置
１０１の問い合わせ文発生器１８０に入力して、問い合
わせ文β、β′を作成し、β′を身元確認者用装置２０
１に送信しくステップ２３０）、βを乱数成分除去器１
９０に供給する。

例えば、問い合わせ文発生器１８０をデータ圧縮器１８
１および排他的論理和計算器１８２で構成し、これによ
り （β１．・・・・・・、βｌ） ””　ｆ　　（ｍ、Ｘ　　１．”””、Ｘ’　＋　）β
　１＝β＋　＋ｅ、　　　　（ｍｏｄ　Ｎ）（ｉ＝１．
２．　・・・・・・、Ｂ で、β＝（β１．・・・・・・、β１）とβ′＝（β゛
１．・・・・・・、β′、）を求める。

それから、身元確認者用装置２０１は入札者用装置１０
１から問い合わせ文β′を受信すると、証明器２４０を
用いて、先に発生した乱数ｒｉと受信した問い合わせ文
β゛から、応答文２を計算して入札者用装置１０１に送
信する（ステップ２４０）。

例えば、証明器２４０を秘密情報格納器２４１および剰
余付き乗算器２４２で構成し、秘密情報格納器２４１か
ら秘密情報Ｓを読み出し、初期応答文発生器２３０から
供給された乱数ｒと受信した応答文β”を剰余付き乗算
器２４２に人力し、ｚ、＝ｒ、ｘｓ”’　　　　（ｍｏ
ｄ　Ｎ）（ｉ＝１．２．・・・・・・、１） で計算したｚｌを用いて、ｚ＝　（ｚｌ　、・・川・　
２１）を求める。

入札者用装置１０１が前記応答文２を受信すると、該応
答文２と先に生成したＸとｔ組の（ｅいｕ、）を乱数成
分除去器１９０に入力し、応答文ｚ′を計算し、応答文
２°と問い合わせ分βを入札額ｍに対する署名としてメ
モリ１４０に記憶する。

例えば、乱数成分除去器１９０を条件判定器１９１およ
び剰余付き乗算器１９２で構成し、）　ｕ　Ｉｘ　ｚ　
１　ｘ　ｘ　−’　　　（ｆｆｉｏｄ　Ｎ）で計算した
Ｚ’ｌを用いて、Ｚ””（Ｚ’ｔ＋　・・・・・・、Ｚ
’＋）を求める。

次は、前述したステップ１３０〜１６０と同様に、第９
図のステップ２５０〜２８０で示すように、入札者は入
札額ｍに対応する圧縮値αを開札者用装置３０１に送信
しくステップ２５０）、開札者はすべての圧縮値αを公
開する（ステップ２６０）。それから、入札者はすべて
の圧縮値αが公開された後、入札額ｍを開札者用装置３
０１に送信する（ステップ２７０）。入札者は入札額ｍ
を受信すると、前記公開した圧縮値αと一致するか否か
を比較検査し、それからすべての入札額ｍを公開する（
ステップ２８０）。そして、すべての入札額ｍから落札
額ｍｏを決定する。

落札者ｍｏを決定された入札者、すなわち落札者は、落
札額ｍｏに対する署名β、ｚ°を前記メモリ１４０から
読み出し、開札者用装置３０１に送信する（ステップ２
９０）。

開札者は該通信文β、ｚ′を受信すると、該通信文およ
び落札額ｍｏを検査器３６０に供給して、これらの正当
性を検査する。

この検査器３６０は、例えば剰余付き乗算器３６１、デ
ータ圧縮器３６２および比較器３６３で構成され、 Ｘ”、＝Ｚ’　、　２ＸＸＩβ’　　（ｍｏｄ　Ｎ）で
ｘ゛°１を求めて、 β−ｆ　（ｍ、　Ｘ”１　、・・・・・・、Ｘ”ｔ）が
成立するかを検査する。

以上の実施例では、Ｆ　ｉ　ａ　ｔ−３ｈａｍｉ　ｒ法
をベースにした認証方法について説明したが、Ｆｉ　ａ
　ｔ−３ｈａｍｉ　ｒ法はＮの素因数分解が困難な場合
に（ｓｏｄ　Ｎ）での平方根の計算が困難なことに基づ
いている。離散対数問題などの困難性を利用した認証法
をベースにしても同様の方式を構成できる。

［発明の効果］ 以上説明したように、本発明によれば、入札者は入札額
ｍから圧縮値を作成して開札者に送信し、開札者がすべ
ての入札者から圧縮値を受信して公開した後に開札者が
入札額ｍを開札者に送信しているので、開札者が入札額
ｍを見た後に不正に入札できない。また、落札者のみが
署名値を開札者に送信して、落札者の身元を承認するの
で、落札額以外の入札額と入札者との対応関係を秘密に
できる。特に、身元確認者が署名するのは、入札額その
ものでなく、入札者のみが知る乱数成分を付加した値で
あり、入札者はその乱数成分の影響を除去して入札値に
対する署名値を求めるので、入札の主催者である身元確
認者と開札者とが結託しても落札者と落札額以外の入札
額ｍと入札者との対応関係を秘密にすることができ、入
札主催者による不正行為、入札額の漏洩などを防止する
ことができる。

【図面の簡単な説明】

第１図、第２図および第３図は本発明の一実施例に係わ
る電子式入札方式に使用される入札者用装置、身元確認
者用装置および開札者用装置の構成をそれぞれ示すブロ
ック図、第４図は電子式入札方式において通信ネットワ
ークを介して接続される身元確認者、入札者および開札
者を示す図、第５図は第１図〜第３図の実施例における
交信順序を示す説明図、第６図、第７図および第８図は
本発明の他の実施例に係わる電子式入札方式に使用され
る入札者用装置、身元確認者用装置および開札者用装置
の構成をそれぞれ示すブロック図、第９図は第６図〜第
８図の実施例における交信順序を示す説明図である。 １００．１０１・・・入札者用装置 １１．０・・・乱数発生器 １２０・・・撹乱器 １７０・・・乱数成分除去器 １４０・・・めもり １５０・・・データ圧縮器 ２００．２０１・・・身元確認者用装置２１０・・・証
明器 ３００゜ ３０１・・・開札者用装置 ３１０・・・公開ファイル ３２０・・・データ圧縮器 ３３０・・・検査器

Claims (3)

【特許請求の範囲】
1. （１）開札者に対する複数の入札者からの入札を通信ネ
   ットワークを利用して電子的に行う電子式入札方式であ
   って、入札者は入札額ｍの圧縮値αをα＝Ｈ（ｍ）で作
   成して開札者に送信し、開札者はすべての入札者から圧
   縮値αを受信して公開し、入札者は圧縮値αの公開後に
   入札額ｍを開札者に送信し、開札者はすべての入札者か
   ら入札額ｍを受信すると、入札額ｍに対する圧縮値Ｈ（
   ｍ）を算出してα＝Ｈ（ｍ）が満たされることを検査し
   てから受信したすべての入札額ｍを公開して落札額を決
   定し、これにより入札額ｍを公開する前に前記圧縮値Ｈ
   （ｍ）を公開することで開札者が入札額ｍを見た後に入
   札できないようにしたことを特徴とする電子式入札方式
   。
2. （２）身元確認者によって身元を確認された複数の入札
   者からの開札者に対する入札を通信ネットワークを介し
   て電子的に行う電子式入札方式であって、入札者は乱数
   発生器からの乱数成分および入札額ｍを撹乱器によって
   撹乱した入札額ｍに対応する通信文ｍ′を作成して身元
   確認者に送信し、身元確認者は入札者の身元を確証した
   後に、撹乱された前記通信文ｍ′を証明器に入力し署名
   付き通信文Ｄ（ｍ′）を作成して入札者に返送し、入札
   者は前記署名付き通信文Ｄ（ｍ′）から乱数成分の影響
   を除去して入札額ｍに署名を施した署名値Ｄ（ｍ）を求
   めた後、入札額ｍに対応する圧縮値αをα＝Ｈ（ｍ）で
   作成して開札者に送信し、開札者はすべての入札者から
   の圧縮値αを受信して公開し、入札者は圧縮値αの公開
   後に入札額ｍを開札者に送信し、開札者はすべての入札
   者から入札額ｍを受信すると、該入札額ｍに対する圧縮
   値Ｈ（ｍ）を算出してα＝Ｈ（ｍ）が満たされているこ
   とを検査してから受信したすべての入札額ｍを公開して
   落札額ｍｏを決定し、落札額ｍｏを入札した入札者は落
   札額ｍｏに署名を施した署名値Ｄ（ｍｏ）を開札者に送
   信し、開札者は該署名値Ｄ（ｍｏ）が落札額ｍｏに対す
   る正しい署名であることを検査して落札者の身元が身元
   確認者によって承認され、かつ落札者が真に落札額ｍｏ
   を入札したことを確認し、これにより身元確認者と開札
   者とが結託しても開札者が落札者以外の入札額と入札者
   との対応関係を知ることができないようにしたことを特
   徴とする電子式入札方式。
3. （３）身元確認者によって身元を確認された複数の入札
   者からの開札者に対する入札を通信ネットワークを介し
   て電子的に行う電子式入札方式であって、身元確認者は
   初期応答文を入札者に送信し、入札者は該受信した初期
   応答文、乱数発生器からの乱数成分および入札額ｍに対
   する問い合わせ文β、β′を作成して身元確認者に送信
   し、身元確認者は前記初期応答文および前記受信した問
   い合わせ文に対応する応答文を証明器を用いて生成して
   入札者に返送し、入札者は前記応答文、前記乱数成分お
   よび前記問い合わせ文から乱数成分の影響を除去して入
   札額ｍに対応する署名値ｚ′を求めた後に、入札額ｍに
   対する圧縮値αをα＝Ｈ（ｍ）で作成して開札者に送信
   し、開札者はすべての入札者から圧縮値αを受信して公
   開し、入札者は圧縮値αの公開後に入札額ｍを開札者に
   送信し、開札者はすべての入札者からの入札額ｍを受信
   すると、入札額ｍに対する圧縮値Ｈ（ｍ）を算出してα
   ＝Ｈ（ｍ）を満たすことを検査した後、受信したすべて
   の入札額ｍを公開して落札額ｍｏを決定し、落札額ｍｏ
   を入札した入札者は落札額ｍｏに対応する署名ｚ′、β
   を開札者に送信し、開札者は該署名ｚ′、βが落札額ｍ
   ｏに対する正しい署名であることを検査して、落札者の
   身元が身元確認者によって承認され、かつ落札者が落札
   額ｍｏを入札したことを確認し、これにより身元確認者
   と開札者とが結託しても開札者が落札者以外の入札額と
   入札者との対応関係を知ることができないようにしたこ
   とを特徴とする電子式入札方式。