(57)【特許請求の範囲】
【請求項１】
開札側の開札者Ａに対する入札側の複数の入札者Ｂi(i=1,2,・・・,n)による入札に際して、開札側に備えた開札装置と入札側に備えた入札装置とをネットワークを介して接続し、入札を行なう電子入札方法において、
入札装置は、開札者Ａが公開している入札価格表ωj(j=1,2,・・・,v,・・・,x)および一方向性関数Ｈを入手する手順１と、
入札者Ｂiの入札価格ωviに対して入札値bi,1=bi,2=・・・=bi,vi-1=no（落札しない）、bi,vi=yes（落札する）を計算する手順２と、
入札値に対して一方向性関数Ｈの連鎖によるコミットメントLi,j＝Ｈ（bi,j,Li,j+1）を計算し、コミットメントLi,1とその署名σiの組（Li,1,σi）を入札として開札装置に送信する手順３と、
開札装置は送信されてきた入札（Li,1,σi）を受信する手順４と、
全入札者の入札装置からの入札が揃ったら署名σiが正当であることを検証し、全入札者の入札装置からの入札を公開する手順５と、
j=1とする手順６と、
入札装置からの入札値（bi,j,Li,j+1）を受信し、全入札者の入札値が揃ったらコミットメントLi,jの正当性Li,j＝Ｈ（bi,j,Li,j+1）を検証し、全入札値｛（bi,j,Li,j+1）｝を公開する手順７と、
全てのiに対して入札値bi,j=noならj=j+1として手順７へ戻る手順８と、
あるiに対して入札値bi,j=yesならＢiを落札者、ωjを落札価格として決定すると共に公開する手順９とを有することを特徴とする電子入札方法。
【請求項２】
入札装置は開札者Ａが公開している入札価格表ωj(j=1,2,・・・,v,・・・,x)及び一方向関数Ｈを入手する手順１と、
入札者Ｂi(i=1,2,・・・,n)が入札価格表ωjから選択した入札価格ωviに対して入札値bi,1=bi,2=・・・=bi,vi-1=no（落札しない）、bi,vi=yes（落札する）を計算する手順２と、
入札値bi,jに対して一方向性関数Ｈの連鎖によるコミットメントLi,j＝Ｈ（bi,j,Li,j+1）を計算し、コミットメントLi,1とその署名σiの組（Li,1,σi）を入札として開札装置に送信する手順３と、入札が公開されると、入札値（ｂｉ，１Ｌｉ，２）を開札装置へ送信し、この入札値（ｂｉ，ｊ,Ｌｉ，ｊ＋１）が公開される毎に、順次、入札値（bi,j＋１,Li,j+２）、（bi,j＋２,Li,j+３）・・・を開札装置に送信する手順４と、を有することを特徴とする入札方法。
【請求項３】
請求項２に記載した入札方法の各手順を、入札装置を構成するコンピュータに実行させるための入札プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項４】
開札装置は入札装置から送信された入札（Li,1,σi）を受信する手順１と、ただし、ｉ＝１，２，・・・ｎ、入札値bi,1は入札価格表をωj(j=1,2,・・・,v,・・・,x)とした場合のω1に対する入札値（yes：落札する、no：落札しない）、Li,1＝Ｈ（bi,1,Li,2）は入札値（ｂｉ１，・・・ｂｉ,ｖｉ−１,ｂｉ,ｖｉ）が（ｎｏ,・・・,ｎｏ,ｙｅｓ）の場合、Ｌｉ,ｖｉ＋１を初期値として、入札値ｂｉ，ｊに対する一方向性関数Ｈの連鎖Ｌｉ,ｊ＝Ｈ（ｂｉ,ｊ,Ｌｉ,ｊ＋１）により計算した入札値bi,1のコミットメント、σi はコミットメントLi,1の署名であり、
全入札者の入札装置からの入札が揃ったら署名σiが正当であることを検証し、全入札者の入札装置からの入札を公開する手順２と、
j=1とする手順３と、
入札装置からの入札値（bi,j,Li,j+1）を受信し、全入札者の入札値が揃ったらコミットメントLi,jの正当性Li,j ＝Ｈ（bi,j,Li,j+1）を検証し、全入札値｛（bi,j,Li,j+1）｝を公開する手順４と、
全てのiに対して入札値bi,j=noならj=j+1として手順４へ戻る手順５と、
あるiに対して入札値bi,j=yesなら入札者Ｂiを落札者、ωjを落札価格として決定すると共に公開する手順６とを有すること  を特徴とする開札方法。
【請求項５】
請求項４に記載した開札方法の各手順を、開札装置を構成するコンピュータに実行させるための開札プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項６】
電子入札装置は、ネットワークを介して接続された入札装置と開札装置から構成され、
入札装置は、入札価格選択手段，入札値計算手段、コミットメント計算手段、署名計算手段及び一方向性関数記憶手段とから構成され、
入札価格選択手段は、入札者Bi(i=1,2,・・・,n)が入札価格表ωj(j=1,2,・・・,v,・・・,x)から入札価格ωviを選択する手段であり、入札値計算手段は、選択された入札価格ωviに対して入札値bi,1=bi,2=・・・=bi,vi-1=no（落札しない）、bi,vi=yes（落札する）を計算し、コミットメント計算手段は、一方向性関数Ｈの連鎖を用いて入札値bi,jに対するコミットメントLi,j＝Ｈ（bi,j,Li,j+1）を計算し、署名計算手段は、コミットメントLi,1に対しての署名σiを計算し、入札装置は、入札（Li,1,σi）を開札装置へ送信し、全入札が公開されると、入札値（ｂｉ,１Ｌｉ,２）を開札装置へ送信し、この入札値（bi,j,Li,j+１）が公開されると、順次、入札値（bi,j+1,Li,j+2）、（bi,j+2,Li,j+3）、・・・を送信し、
開札装置は、署名検証手段、全入札公開手段、コミットメント検証手段、全入札値公開手段、落札計算手段、落札者・落札価格公開手段及び一方向性関数記憶手段とから構成され、
署名検証手段と全入札公開手段は、入札（Li,1,σi）を受信して、署名σiの正当性を検証すると共に、全入札を公開し、コミットメント検証手段と全入札値公開手段は、入札値（bi,j,Li,j+1）を受信し、コミットメントLi,jの正当性Li,j＝Ｈ（bi,j,Li,j+1）を検証すると共に、全入札値｛（bi,j,Li,j+1）｝を公開し、落札計算手段は、全てのiに対して入札値bi,j＝noならば、j=j+1としてコミットメント検証手段、全入札値公開手段に送信し、あるiに対して入札値bi,j＝yesならば、落札と判断して落札者・落札価格公開手段に送信し、落札者・落札価格公開手段は落札者、落札価格を公開することを特徴とする電子入札装置。
【請求項７】
入札価格選択手段，入札値計算手段、コミットメント計算手段、署名計算手段及び一方向性関数記憶手段とから構成され、
入札価格選択手段は、入札者Bi(i=1,2,・・・,n)が入札価格表ωj(j=1,2,・・・,v,・・・,x)から入札価格ωviを選択する手段であり、入札値計算手段は、入札価格ωviに対して入札値bi,1=bi,2=・・・=bi,vi-1=no（落札しない）、bi,vi=yes（落札する）を計算し、コミットメント計算手段は、一方向性関数Ｈの連鎖を用いて入札値bi,jに対するコミットメントLi,j＝Ｈ（bi,j,Li,j+1）を計算し、署名計算手段は、コミットメントLi,1に対しての署名σiを計算し、入札（Li,1,σi）を開札装置へ送信し、入札が公開されると、入札値（ｂｉ，１Ｌｉ，２）を開札装置へ送信し、この入札値（ｂｉ，ｊＬｉ，ｊ＋１）が公開されると、順次、入札値（bi,j+1,Li,j+2）、（bi,j+2,Li,j+3）、・・・を送信することを特徴とする入札装置。
【請求項８】
署名検証手段、全入札公開手段、コミットメント検証手段、全入札値公開手段、落札計算手段、落札者・落札価格公開手段、一方向性関数記憶手段及び入札価格表ωj(j=1,2,・・・,v,・・・,x)とから構成され、
署名検証手段と全入札公開手段は、入札者Bi(i=1,2,・・・,n)の入札（Li,1,σi）を受信して、署名σiの正当性を検証すると共に、全入札｛（Li,1,σi）｝を公開し、コミットメント検証手段と全入札値公開手段は、入札値（bi,j,Li,j+1）を受信し、コミットメントLi,jの正当性Li,j＝Ｈ（bi,j,Li,j+1）を検証すると共に、全入札値｛（bi,j,Li,j+1）｝を公開し、また、落札計算手段は、全てのiに対して入札値bi,j＝noならば、j=j+1としてコミットメント検証手段、全入札値公開手段に送信し、あるiに対して入札値bi,j＝yesならば、落札と判断して落札者、落札価格公開手段に送信し、落札者・落札価格公開手段は落札者・落札価格を公開することを特徴とする開札装置、ただし、入札値bi,1はω1に対する入札値（yes：落札する、no：落札しない）、Li,1 は入札値bi,1 のコミットメント、σi はコミットメントLi,1の署名である。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報セキュリティ技術の応用技術に関するものであり、インターネットなどの通信ネットワ−ク上に分散配置された複数の入札者が、電子的な通信を利用して入札を行う、電子入札装置並びに電子入札方法及び電子入札方法を記録した記録媒体に関する。
【０００２】
【従来の技術】
従来方式の代表的な例として、宮崎、櫻井による電子入札方式（Ｓ．Ｍｉｙａｚａｋｉ，Ｋ．Ｓａｋｕｒａｉ，公開掲示板を用いた秘策可能な電子入札システム、ＳＣＩＳ’９９  ４１−４６  （１９９９））がある。
【０００３】
【発明が解決しようとする課題】
従来方式においては否認不可署名（入札者がある価格で入札していないことを証明できる署名方式）によるコミットメントが用いられていたが、否認不可署名は署名の作成／確認／否認手順に多くの計算および通信を必要とするため効率がよくないという問題点があった。
【０００４】
【課題を解決するための手段】
本発明が提案する電子入札装置及び方法は、一方向性関数の連鎖によるコミットメントを用いて構成されているため、一方向性関数として例えばＳＨＡ−１などの実用的な一方向性関数を用いることにより、従来方式よりも効率的な入札方法を実現している。
【０００５】
【発明の実施の形態】
以下では、本発明の一実施例について説明する。
図１は、本発明の全体構成を示す図である。入札者Ｂ１，Ｂ２，・・・，Ｂｎ（１００）が開札者Ａ（２００）と通信路（３００）を介して結合されている。
実施例１
図２に示すように、まず開札者Ａは［前処理］を行い、次に各入札者Ｂｉ（ｉ＝１，・・・，ｎ）は［入札手順］（１１０−１５０）により入札を行ない、最後に開札者Ａは［開札手順］（２１０−２５０）により開札を行なう。
【０００６】
図３に入札者Ｂｉ（１００）の入札手順のブロック図を示す。
図４に開札者Ａ（２００）の開札手順のブロック図を示す。
［前処理］
開札者Ａは入札価格表｛ω１，・・・，ωｖ−１，ωｖ，・・・，ωｘ｝（例えば、中古車の販売で｛１００万円，・・・，６０万円，５０万円，・・・，１０万円｝、すなわち、開札者は価格１００万円から１０万円の範囲と具体的な入札価格を提示する。）および一方向性関数
Ｈ：｛０，１｝ｓ×｛０，１｝ｔ→｛０，１｝ｔ
（ただし、｛０，１｝ｓは｛０，１｝の集合から成るｓビットのビット列の全体集合、｛０，１｝ｔ  は｛０，１｝の集合から成るｔビットのビット列の全体集合を示す。）を決めて公開する。実際には、一方向性関数としてＳＨＡ−１などの実用的な一方向性関数を用いる。また、ｎｏ（落札しないメッセージ）、ｙｅｓ（落札するメッセージ）∈｛０，１｝ｓ  を公開する。
［入札手順］
入札者Ｂｉは、図４に示す入札手順（１１０−１５０）により入札を行う。
（ステップ１１０）
入札者Ｂｉは、入札価格表｛ω１，・・・，ωｖ−１，ωｖ，・・・，ωｘ｝から入札価格ωｖｉを選択する（例えば、５０万円）。
（ステップ１２０）
入札価格ωｖｉに対する入札値
0003619401.tif 000002
を計算する。
【０００７】
（例えば、入札者Ｂｉは、６０万円，・・・，１００万円では落札を希望せず、５０万円で希望する場合には、｛ω１（１００万円），・・・，ωｖ−１（６０万円）  ，ωｖｉ（５０万円）  ｝に対する｛ｂｉ１，・・・ｂｉ，ｖｉ−１，ｂｉ，ｖｉ｝は｛ｎｏ，・・・，ｎｏ，ｙｅｓ｝となる。）
（ステップ１３０）
入札値ｂｉ，ｊに対するコミットメント
Ｌｉ，ｊ＝Ｈ（ｂｉ，ｊ，Ｌｉ，ｊ＋１）（１≦ｊ≦ｖｉ）
を計算する。
【０００８】
（上記の計算は、｛０，１｝ｔからランダムに選んだＬｉ，ｖｉ＋１を初期値として、Ｌｉ，ｖｉ＝Ｈ（ｂｉ，ｖｉ，Ｌｉ，ｖｉ＋１），・・・，Ｌｉ，２＝Ｈ（ｂｉ，２，Ｌｉ，３），Ｌｉ，１＝Ｈ（ｂｉ，１，Ｌｉ，２）により行う。）
（ステップ１４０）
ｂｉ，１に対するコミットメントＬｉ，１に対して、署名σｉ＝ＳｉｇＢｉ（Ｌｉ，１）を計算する。
（この署名により入札は確かに入札者Ｂｉが行ったものであることがわかる。）
（ステップ１５０）
ｂｉ，１に対するコミットメントＬｉ，１とその署名σｉの組（Ｌｉ，１、σｉ  ）を入札として、開札者Ａに送信する。
［開札手順］
開札者Ａは、図４に示す開札手順（２１０−２５０）により開札を行い、全入札者Ｂｉ（ｉ＝１，２，・・・，ｎ）に入札値｛ｂ１，１，ｂ１，２，・・・，ｂ１，ｖｉ｝（入札者Ｂ１），・・・｛ｂｉ，１，ｂｉ，２，・・・，ｂｉ，ｖｉ｝（入札者Ｂｉ），・・・，｛ｂｎ，１，ｂｎ，２，・・・，ｂｎ，ｖｉ｝（入札者Ｂｎ）〕を順に送信させて開札手順（２１０−２５０）により開札を行う。
（ステップ２１０）
入札者Ｂｉから入札（Ｌｉ，１，σｉ  ）を受信し、全入札者Ｂｉ（ｉ＝１，２，・・・，ｎ）からの入札｛Ｌｉ，１，σｉ｝（ｉ＝１，２，・・・，ｎ）が揃ったら、署名σｉの正当性を検証し、全入札｛（Ｌｉ，１，σｉ）｝（ｉ＝１，２，・・・，ｎ）を公開する。（例えば、｛（Ｌ１，１，σ１），・・・，（Ｌｎ，１，σｎ）｝を表示装置に表示して公開する。（この表示からは具体的な入札価格は知ることはできない。ただし、その後、入札価格等が改竄されれば｛（Ｌ１，１，σ１），・・・，（Ｌｎ，１，σｎ）｝が変わり、改竄されたことがわかる。）
（ステップ２２０）
ｊ＝１（すなわち、入札価格ω１に対する全入札者Ｂｉ（ｉ＝１，２，・・・，ｎ）の入札値｛ｂ１，１，ｂ２，１，・・・，ｂｎ，１｝、ｊ＝２（すなわち、入札価格ω２に対する全入札者（Ｂ１，・・・，Ｂｉ，・・・，Ｂｎ）の入札値｛ｂ１，２，ｂ２，２，・・・，ｂｎ，２｝、・・・を順に公開すると共に、ｊ＝１，２，・・・毎に以下のステップ  （２３０−２５０）を行う。
（ステップ２３０）
入札者Ｂｉから入札値（ｂｉ，ｊ，Ｌｉ，ｊ＋１）を受信し、全入札値｛（ｂｉ，ｊ，Ｌｉ，ｊ＋１）｝（ｉ＝１，２，・・・ｎ）が揃ったら、コミットメントの正当性
Ｌｉ，ｊ＝Ｈ（ｂｉ，ｊ、Ｌｉ，ｊ＋１）
を検証し、全入札値｛（ｂｉ，ｊ、Ｌｉ，ｊ＋１）｝（ｉ＝１，２，・・・，ｎ）を公開する。
（ステップ２４０）
全てのｉに対して入札値ｂｉ，ｊ＝ｎｏなら、ｊ＝ｊ＋１として（ステップ２３０）へ戻る。
（ステップ２５０）
あるｉに対して入札値ｂｉ，ｊ＝ｙｅｓなら、ｖ＝ｊとして、Ｂｉを落札者、ωｖを落札価格として公開する。
【０００９】
実施例２
図５は、本発明の電子入札装置のブロック図を示す。
電子入札装置１は、入札装置２と開札装置３から構成される。
入札装置１は、入札価格選択手段４，入札値計算手段５、コミットメント計算手段６、署名計算手段７及び一方向性関数記憶手段８とから構成される。
【００１０】
入札者Ｂｉ（ｉ＝１，２，・・・，ｎ）は、公開されている入札価格表ωｊ（ｊ＝１，２，・・・，ｖ，・・・，ｘ）９を参照して入札価格選択手段４により入札価格ωｖｉを選択する。入札値計算手段５は、入札価格ωｖｉに対する入札価格ωｖｉに対して入札値ｂｉ，１＝ｂｉ，２＝・・・＝ｂｉ，ｖｉ−１＝ｎｏ（落札しない）、ｂｉ，ｖｉ＝ｙｅｓ（落札する）を計算する。コミットメント計算手段６は、一方向性関数Ｈの連鎖を用いて入札値ｂｉ，ｊ  に対するコミットメントＬｉ，ｊ＝Ｈ（ｂｉ，ｊ、Ｌｉ，ｊ＋１）を計算する。署名計算手段７は、コミットメントＬｉ，１に対しての署名σｉ  を計算する。そして、入札装置２は、入札（Ｌｉ，１，σｉ）を開札装置へ送信し、開札装置が署名σｉが正当であることを検証すると共に、全入札を公開し、さらに、入札装置は、入札値（ｂｉ，ｊ，Ｌｉ，ｊ＋１）を開札装置へ送信し、開札装置がコミットメントＬｉ，ｊ  の正当性を検証し、この入札値の公開を確認したら、順次、入札値（ｂｉ，ｊ＋１，Ｌｉ，ｊ＋２）、（ｂｉ，ｊ＋２，Ｌｉ，ｊ＋３）、・・・を送信する。
【００１１】
開札装置３は、署名検証手段１０−１、全入札公開手段１０−２、コミットメント検証手段１１−１、全入札値公開手段１１−２、落札計算手段１２、落札者・落札価格公開手段１３及び一方向性関数記憶手段８とから構成される。
署名検証手段１０−１と全入札公開手段１０−２は、入札（Ｌｉ，１，σｉ）を受信して、署名σｉの正当性を検証すると共に、全入札｛（Ｌｉ，１，σｉ）｝（ｉ＝１，２，・・・，ｎ）を公開する。コミットメント検証手段１１−１と全入札値公開手段１１−２は、入札値（ｂｉ，ｊ，Ｌｉ，ｊ＋１）を受信し、一方向性関数Ｈを用いてコミットメントＬｉ，ｊの正当性を検証すると共に、全入札値｛（ｂｉ，ｊ，Ｌｉ，ｊ＋１）｝（ｉ＝１，２，・・・，ｎ）  を公開する。また、落札計算手段１２は、入札値ｂｉ，ｊを受信し、全てのｉに対して入札値ｂｉ，ｊ＝ｎｏならば、ｊ＝ｊ＋１としてコミットメント検証手段１１−１、全入札値公開手段１１−２に送信し、あるｉに対して入札値ｂｉ，ｊ＝ｙｅｓならば、落札と判断して落札者・落札価格公開手段１３に送信し、落札者・落札価格を公開する。
［例外処理］
入札値（ｂｉ，ｊ，Ｌｉ，ｊ＋１）を公開しない入札者Ｂｉがいる場合、その入札者Ｂｉを除いて、再度入札をやり直す。（現実には、公開しない入札者Ｂｉに対しては、さらに預かり金没収などの罰則を設けて対処することとなる。）
【００１２】
【発明の効果】
本発明で提案する電子入札方法および装置は、一方向性関数の連鎖によるコミットメントを用いて構成されているためＳＨＡ−１などの実用的な一方向性関数を用いることにより、否認不可署名によるコミットメントを用いていた従来方式よりも効率的な電子入札方法及び装置を実現している。
【００１３】
さらに、電子入札方法及び装置として必要な次のような性質を備えている。
［正確性］
順に入札を開示していくので、最小のｖに対応するωｖで入札した入札者が落札する。
［検証可能性］
入札｛ｂｉ，１，ｂｉ，２，・・・，ｂｉ，ｖ｝とコミットメント｛Ｌｉ，１，Ｌｉ，２，・・・，Ｌｉ，ｖ＋１｝は公開されているので、だれでも改竄の検証をすることができる。
［公平性］
開札以前に公開されているのはコミットメントＬｉ，１のみなので、開札までは他の入札者の入札価格はわからない。
［価格秘匿性］
落札者が出たところで開札は終了し、落札者が出てきた以降の入札｛ｂｉ，ｖ＋１，ｂｉ，ｖ＋２，・・・，ｂｉ，ｖｉ｝は公開されないので、落札価格以外の入札価格は秘匿されている。
［否認不可性］
コミットメントＬｉ，１には入札者の署名σｉ＝ＳｉｇＢｉ（Ｌｉ，１）が付いているので否認できない。
［不正者特定可能性］
コミットメントＬｉ，ｊ  が公開されているので入札ｂｉ，ｊを偽った者は特定できる。また、一方向性関数Ｈの一方向性により、コミットメントＬｉ，ｊ  を後から改竄することはできない。
【図面の簡単な説明】
【図１】本発明の全体構成を示す図。
【図２】本発明の全体的な手順を示す図。
【図３】入札者Ｂｉ    の入札手順のブロック図。
【図４】開札者Ａの開札手順を示すブロック図。
【図５】本発明の電子入札装置のブロック図。
【符号の説明】
１        電子入札装置
２        入札装置
３        開札装置
４        入札価格選択手段
５        入札値計算手段
６        コミットメント計算手段
７        署名計算手段
８        一方向性関数記憶手段
９        入札価格表
１０−１      署名検証手段
１０−２      全入札公開手段
１１−１      コミットメント検証手段
１１−２      全入札値公開手段
１２        落札計算手段
１３        落札者・落札価格公開手段
【図１】
0003619401.tif 000003
【図２】
0003619401.tif 000004
【図３】
0003619401.tif 000005
【図４】
0003619401.tif 000006
【図５】
0003619401.tif 000007