(57)【特許請求の範囲】
【請求項１】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)と複数の入札装置{Bj}(1≦j≦b)(b：入札者数)が通信路を介して接続されていて、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は、入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数１】
0003690494.tif 000008
を決めて公開するステップ１と、
各入札装置Bjは、入札価格kj(１≦kj≦p)を決定し、秘密の乱数{Si,j｝(１≦i≦a)を生成し、入札価格kjに対する入札情報Bidj
【数２】
0003690494.tif 000009
を計算し、入札情報Bidjとその署名σj ＝SigBj (Bidj)を各開札装置に送信し公開するステップ２と、
各入札装置Bjは秘密の乱数Si,jを各開札装置Aiに暗号化して送信するステップ３と、
開札装置{Ai}(1≦i≦a)は、全入札装置Bjの入札{(Bidj,σj)｝(1≦j≦b)が揃ったら、署名σjの正当性を検証し、各開札装置Aiは１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するステップ４と、
ある開札装置はk＝pとして以下の計算を繰り返すステップ５と、
{hk(Si,j)}(1≦j≦b)を公開し、a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)全てが揃ったら、
【数３】
0003690494.tif 000010
を計算し、bj＝bj’を検証し、全てのjについて検証が不成立なら、k＝k−1としてステップ５へ戻るステップ６と、
あるjたちについて検証が成立なら、入札装置Bjによって入札した者たちを落札者、kを落札価格として公開するステップ７とを備えた、
落札者以外の入札価格が秘匿され、落札者および落札価格が正当であることを全入札者が検証可能であり、行った入札の否認や改竄などの不正が不可能であり、ハッシュ関数の連鎖によるコミットメントを用いることにより、効率的に入札を実現することを特徴とする電子入札開札方法。
【請求項２】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)と複数の入札装置{Bj}(1≦j
≦b)(b：入札者数)が通信路を介して接続されていて、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は、入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数４】
0003690494.tif 000011
を決めて公開するステップ１と、
各入札装置Bj は、入札価格kj(１≦kj≦p)を決定し、秘密の乱数{Si,j｝(１≦i≦a)を生成し、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数５】
0003690494.tif 000012
を計算し、入札情報Bidjとその署名σj＝SigBj(Bidj)を各開札装置に送信して公開するステップ２と、
秘密の乱数Si,jを各開札装置Ai に暗号化して送信するステップ３と、
開札装置{Ai}(1≦i≦a)は、全入札装置Biの入札{(Bidj,σj)｝(1≦j≦b)が揃ったら、署名σjの正当性を検証し、各開札装置Aiは１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するステップ４と、
ある開札装置は、k＝pとして以下の計算を繰り返すステップ５と、
{hk(Si,j)}(1≦j≦b)を公開し、a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)のうち少なくともt組揃ったら、
【数６】
0003690494.tif 000013
bj＝bj’を検証し、すべてのjについて検証が不成立なら、k＝k−1としてステップ５へ戻るステップ６と、
あるjたちについて検証が成立なら、入札装置Bjによって入札した者たちを落札者、kを落札価格として公開するステップ７とを備えた
落札者以外の入札価格が秘匿され、落札者および落札価格が正当であることを全入札者が検証可能であり、行った入札の否認や改竄などの不正が不可能であり、ハッシュ関数の連鎖によるコミットメントを用いることにより、効率的に入札を実現できることを特徴とする電子入札開札方法。
【請求項３】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)に通信路を介して接続される複数の入札装置{Bj}(1≦j≦b)(b：入札者数)において、
公開された入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数７】
0003690494.tif 000014
により、
各入札装置Bjは、入札価格kj(１≦kj≦p)を決定し、秘密の乱数{Si,j｝(１≦i≦a)を生成し、入札価格kjに対する入札情報Bidj
【数８】
0003690494.tif 000015
を計算し、入札情報Bidjとその署名σj ＝SigBj (Bidj)を各開札装置に送信し公開するステップ１と、
各入札装置Bjは秘密の乱数Si,jを各開札装置Aiに暗号化して送信するステップ２を備えたこと
を特徴とする電子入札方法。
【請求項４】
複数の入札装置{Bj}(1≦j≦b)(b：入札者数)に通信路を介して接続される複数の開札装置{Ai}(1≦i≦a)(a：開札者数)において、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数９】
0003690494.tif 000016
を決めて公開するステップ１と、
各入札装置で作成された、入札価格kjに対する入札情報Bidj
【数１０】
0003690494.tif 000017
とその署名σj ＝SigBj (Bidj)と、暗号化された秘密の乱数Si,jを受信するステップ２と、
全入札装置Bjの入札{(Bidj,σj)｝(1≦j≦b)が揃ったら、署名σjの正当性を検証し、各開札装置Aiは１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するステップ３と、
ある開札装置はk＝pとして以下の計算を繰り返すステップ４と、
{hk(Si,j)}(1≦j≦b)を公開し、a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)全てが揃ったら、
【数１１】
0003690494.tif 000018
を計算し、bj＝bj’を検証し、全てのjについて検証が不成立なら、k＝k−1としてステップ４へ戻るステップ５と、
あるjたちについて検証が成立なら、入札装置Bjによって入札した者たちを落札者、ｋを落札価格を決定して
公開するステップ６とを備えたこと
を特徴とする電子開札方法。
【請求項５】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)に通信路を介して接続される複数の入札装置{Bj}(1≦j≦b)(b：入札者数)において、
公開された入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数１２】
0003690494.tif 000019
により、各入札装置Bjは、入札価格kj(１≦kj≦p)を決定し、秘密の乱数{Si,j}(１≦i≦a)を生成し、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数１３】
0003690494.tif 000020
を計算し、入札情報Bidjとその署名σj＝SigBj(Bidj)を各開札装置に送信して公開するステップ１と、
秘密の乱数Si,jを各開札装置Aiに暗号化して送信するステップ２を備えたことと、
を特徴とする電子入札方法。
【請求項６】
複数の入札装置{Bj}(1≦j≦b)(b：入札者数)に通信路を介して接続される複数の開札装置{Ai}(1≦i≦a)(a：開札者数)において、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数１４】
0003690494.tif 000021
を決めて公開するステップ１と、
各入札装置で作成された、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数１５】
0003690494.tif 000022
とその署名σj＝SigBj(Bidj)及び暗号化された秘密の乱数Si,jを受信するステップ２と、  全入札装置Biの入札{(Bidj,σj)}(1≦j≦b)が揃ったら、署名σjの正当性を検証し、各開札装置Aiは１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するステップ３と、
ある開札装置は、k＝pとして以下の計算を繰り返すステップ４と、
{hk(Si,j)}(1≦j≦b)を公開し、a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)のうち少なくともt組揃ったら、
【数１６】
0003690494.tif 000023
bj＝bj’を検証し、すべてのjについて検証が不成立なら、k＝k−1としてステップ４へ戻るステップ５と、
あるjたちについて検証が成立なら、入札装置Bjによって入札した者たちを落札者、kを落札価格として公開するステップ６とを備えたこと
を特徴とする電子開札方法。
【請求項７】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)と複数の入札装置{Bj}(1≦j
≦b)(b：入札者数)が通信路を介して接続されていて、   開札装置{Ai}(1≦i≦a)のうち
、ある開札装置は、
入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数１７】
0003690494.tif 000024
を決めて公開する入札価格・ハッシュ関数公開手段を備え、
各入札装置Bjは、
秘密の乱数{Si,j}(１≦i≦a)を生成する乱数生成手段と、
入札価格kj(１≦kj≦p)を決定し、入札価格kjに対する入札情報Bidj
【数１８】
0003690494.tif 000025
を計算する入札情報計算手段と、
署名σj ＝SigBj (Bidj)を計算する署名計算手段と、
入札情報Bidjとその署名σjを各開札装置に送信する送信手段と、
秘密の乱数Si,jを各開札装置Aiに暗号化して送信する乱数暗号化送信手段を備え、
各開札装置{Ai}(1≦i≦a)は、
入札情報Bidjとその署名σj及び暗号化した秘密の乱数Si,jを受信し、入札情報Bidjとその署名σjを公開する公開手段と、
全入札装置Bjの入札{(Bidj,σj)}(1≦j≦b)が揃ったら、署名σjの正当性を検証する署名検証手段と、
暗号化した秘密の乱数Si,jを復号し、１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するハッシュ関数連鎖計算手段と、
ある開札装置は、
k＝pとして以下の演算を繰り返す演算手段と、
{hk(Si,j)}(1≦j≦b)を公開する公開手段を備え、
a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)全てが揃ったら、
【数１９】
0003690494.tif 000026
を計算し、bj＝bj’を検証する検証手段と、
全てのjについて検証手段の検証が不成立なら、k＝k−1として前記演算手段の演算を再度行う指示手段と、
あるjたちについて検証手段の検証が成立なら、入札装置Bjによって入札した者たちを落札者、ｋを落札価格として公開する公開手段とを備えた
落札者以外の入札価格が秘匿され、落札者および落札価格が正当であることを全入札者が検証可能であり、行った入札の否認や改竄などの不正が不可能であり、ハッシュ関数の連鎖によるコミットメントを用いることにより、効率的に入札を実現することを特徴とする電子入札開札装置。
【請求項８】
複数の開札装置{Ai}(1≦i≦a)(a：開札者の数)と複数の入札装置{Bj}(1≦j≦b)(b：入札者の数)が通信路を介して接続されていて、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は、
入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数２０】
0003690494.tif 000027
を決めて公開する入札価格表・ハッシュ関数公開手段を備え、
各入札装置Bj は、
秘密の乱数{Si,j}(１≦i≦a)を生成する乱数生成手段と、
入札価格kj(１≦kj≦p)を決定し、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数２１】
0003690494.tif 000028
を計算する入札情報計算手段と、
署名σj＝SigBj(Bidj)を計算する署名計算手段と、
入札情報Bidjとその署名σjを各開札装置に送信する送信手段と、
秘密の乱数Si,jを暗号化して各開札装置Aiに送信する乱数暗号化送信手段と、  開札装置{Ai}(1≦i≦a)は、
入札情報Bidjとその署名σj及び暗号化した秘密の乱数Si,jを受信し、入札情報Bidjとその署名σjを公開する公開手段と、
全入札装置Biの入札{(Bidj,σj)}(1≦j≦b)が揃ったら、署名σjの正当性を検証する署名検証手段と、
暗号化した秘密の乱数Si,jをを復号し、１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するハッシュ関数連鎖計算手段と、
ある開札装置は、
k＝pとして以下の演算を繰り返す演算手段と、
{hk(Si,j)}(1≦j≦b)を公開する公開手段を備え、
a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)のうち少なくともt組揃ったら、
【数２２】
0003690494.tif 000029
bj＝bj’を検証する検証手段と、
すべてのjについて検証手段の検証が不成立なら、k＝k−1として前記演算手段の演算を再度行う指示手段と、
あるjたちについて検証手段の検証が成立なら、入札装置Bjによって入札した者たちを落札者、kを落札価格として決定する落札者・落札価格決定手段と、
この落札者、落札価格を公開する公開手段とを備えた、
落札者以外の入札価格が秘匿され、落札者および落札価格が正当であることを全入札者が検証可能であり、行った入札の否認や改竄などの不正が不可能であり、ハッシュ関数の連鎖によるコミットメントを用いることにより、効率的に入札を実現できることを特徴とする電子入札開札装置。
【請求項９】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)に通信路を介して接続される複数の入札装置{Bj}(1≦j≦b)(b：入札者数)において、
公開された入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数２３】
0003690494.tif 000030
により、
各入札装置Bjは、秘密の乱数{Si,j}(１≦i≦a)を生成する乱数生成手段と、
入札価格kj(１≦kj≦p)を決定し、入札価格kjに対する入札情報Bidj
【数２４】
0003690494.tif 000031
を計算する入札情報計算手段と、
署名σj ＝SigBj (Bidj)を計算する署名計算手段と、
入札情報Bidjとその署名σjを各開札装置に送信する送信手段と、
入札情報Bidjとその署名σjを公開する公開手段と、
各入札装置Bjは秘密の乱数Si,jを各開札装置Aiに暗号化して送信する暗号化送信手段とを備えたこと
を特徴とする電子入札装置。
【請求項１０】
複数の入札装置{Bj}(1≦j≦b)(b：入札者数)に通信路を介して接続される複数の開札装置{Ai}(1≦i≦a)(a：開札者数)において、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数２５】
0003690494.tif 000032
を決めて公開する公開手段と、
各入札装置で作成された、入札価格kjに対する入札情報Bidj
【数２６】
0003690494.tif 000033
とその署名σj ＝SigBj (Bidj)と、暗号化された秘密の乱数Si,jを受信する受信手段と、
全入札装置Bjの入札{(Bidj,σj)}(1≦j≦b)が揃ったら、署名σjの正当性を検証する署名検証手段と、
各開札装置Aiは１≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し、公開されているhp+1(Si,j)と等しいことを確認するハッシュ関数連鎖計算手段と、
ある開札装置はk＝pとして以下の演算を繰り返す演算手段と、
{hk(Si,j)}(1≦j≦b)を公開する公開手段を備え、
a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)全てが揃ったら、
【数２７】
0003690494.tif 000034
を計算し、bj＝bj’を検証する検証手段と、
全てのjについて検証手段の検証が不成立なら、k＝k−1として前記演算手段の演算を再度行う指示手段と、
あるjたちについて検証手段の検証が成立なら、入札装置Bjによって入札した者たちを落札者、ｋを落札価格として公開する公開手段を備えたこと
を特徴とする電子開札装置。
【請求項１１】
複数の開札装置{Ai}(1≦i≦a)(a：開札者数)に通信路を介して接続される複数の入札装置{Bj}(1≦j≦b)(b：入札者数)において、
公開された入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数２８】
0003690494.tif 000035
により、各入札装置Bjは、秘密の乱数{Si,j}(１≦i≦a)を生成する乱数生成手段と、
入札価格kj(１≦kj≦p)を決定し、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数２９】
0003690494.tif 000036
を計算する入札情報計算手段と、
署名σj＝SigBj(Bidj)を計算する署名計算手段と、
入札情報Bidjとその署名σjを各開札装置に送信する送信手段と、
秘密の乱数Si,jを各開札装置Aiに暗号化して送信する乱数暗号化送信手段を備えたこと
を特徴とする電子入札装置。
【請求項１２】
複数の入札装置{Bj}(1≦j≦b)(b：入札者数)に通信路を介して接続される複数の開札装置{Ai}(1≦i≦a)(a：開札者数)において、
開札装置{Ai}(1≦i≦a)のうち、ある開札装置は入札価格表{1,・・・,k,・・・,p}、およびハッシュ関数h
【数３０】
0003690494.tif 000037
を決めて公開する入札価格・ハッシュ関数公開手段と、
各入札装置で作成された、ランダムな有限体Fq上のt−1次多項式Fj(x)∈Fq[x]を生成し、入札価格kjに対する入札情報Bidj
【数３１】
0003690494.tif 000038
とその署名σj＝SigBj(Bidj)及び暗号化された秘密の乱数Si,jを受信する受信手段と、
全入札装置Biの入札{(Bidj,σj)｝(1≦j≦b)が揃ったら、署名σjの正当性を検証する署名検証手段と、
1≦j≦bについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)を計算し公開されているhp+1(Si,j)と等しいことを確認するハッシュ関数連鎖計算手段と、
ある開札装置は、k＝pとして以下の演算を繰り返す演算手段と、
{hk(Si,j)}(1≦j≦b)を公開する公開手段を備え、
a組の値{{hk(Si,j)}(1≦j≦b)}(1≦i≦a)のうち少なくともt組揃ったら、
【数３２】
0003690494.tif 000039
bj＝bj’を検証する検証手段と、
すべてのjについて検証手段の検証が不成立なら、k＝k−1として前記演算手段の演算を再度行う指示手段と、
あるjたちについて検証手段の検証が成立なら、入札装置Bjによって入札した者たちを落札者、kを落札価格として決定する落札者・落札価格決定手段と、
この落札者及び落札価格を公開する公開手段を備えたこと
を特徴とする電子開札装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、情報セキュリティ技術の応用技術に関するものであり、インターネットなどに通信ネットワーク上に分散された複数の入札者が、電子的な通信を利用して入札を行う電子入札開札方法及び装置に関する。
【０００２】
【従来の技術】
従来の入札方法の代表的な例として、K.Sako,Universally verifiable auction protocol which hides losing bids,Proc. of Public Key Cryptography 2000,pp.35-39,2000.がある。
この入札方法は、(1)開札者は、複数の価格が示された入札価格表を公開する。(2)各入札者は、入札価格表から入札価格を決定して各価格p毎に異なる公開鍵kpと価格pに対する入札メッセージMpを用いて暗号化Enc kp(Mp)する。(3)開札者は、この入札情報Enc kp(Mp)を受信して復号鍵を用いて入札メッセージMpを復号する。
【０００３】
この入札方法においては、各入札者は公開鍵を用いた暗号化、及び開札者はこれに対する（すなわち、入札価格表に示された価格の数×入札者の数×開札者の数）復号鍵を用いた復号を行う必要がある。
【０００４】
【発明が解決しようとする課題】
従来方法においては公開鍵暗号により入札情報を生成していたが、公開鍵を用いた暗号化および復号鍵を用いた復号化に多くの計算を必要とするため、効率がよくないという問題点があった。
【０００５】
【課題を解決するための手段】
本発明で提案する電子入札開札方法及び電子入札開札装置は、ハッシュ関数の連鎖を用いて構成されているため、ハッシュ関数としてSHA-1などの実用的なハッシュ関数を用いることにより、公開鍵暗号を用いていた従来方法よりも、計算量的に数万倍効率的な入札開札方法及び入札開札装置を実現している。
また、開札は開札者のみでできるので、入札者は開札時には開札者と通信する必要はなく入札時のみ通信すればよいため、通信量的にも効率的な入札方法を実現している。
【０００６】
さらに、電子入札方法として必要な[価格秘匿性]、[検証可能性]、[否認不可性]を満たしている。
【０００７】
【発明の実施の形態】
（実施例１）
以下では、本発明の実施例１について説明する。
本発明の全体構成は、開札装置（開札者）{Ai}(1≦i≦a)(a：開札者数)と入札装置（入札者）{Bj}(1≦j≦b)(b：開札者数)が通信路を介して接続されている。上記の入札開札装置において、ある開札装置Aiが開札を行い、他の開札装置は開札装置Aiの開札に協力する。従って、ある開札装置Aiのみでは開札を行うことができないために不正を防止できる。
【０００８】
まず開札装置（開札者）{Ai}(1≦i≦a)は[前処理]を行い、次に各入札装置（各入札者）Bjは[入札手順]により入札を行い、最後に開札装置（開札者）{Ai}(1≦i≦a)は[開札手順]により協力して開札を行う。
[前処理]
各開札装置{Ai}(1≦i≦a)のうち、ある開札装置Aiは入札価格表{1,・・・,k,・・・p}およびハッシュ関数
【０００９】
【数３３】
0003690494.tif 000002
【００１０】
を決めて公開掲示板等で公開する。実際にはhとしてSHA-1などの実用的なハッシュ関数を用いる。
[入札手順]
各入札装置Bjは入札手順(ステップ110-150)により入札を行う。
（ステップ110)
各入札装置Bjは入札価格kj(1≦kj≦p)を決定する。
（ステップ120)
各入札装置Bjは乱数生成部で秘密の乱数{Si,j}(1≦i≦a)を生成する。
（ステップ130）
各入札装置Bjは入札価格kjに対する入札情報Bidj
【００１１】
【数３４】
0003690494.tif 000003
【００１２】
（ステップ140）
各入札装置は入札情報Bidjと、その署名σj＝SigBj(Bidj)を署名SigBj計算部で計算し、各開札装置に送信し、公開掲示板等により公開する。
（ステップ150）
各入札装置は秘密の乱数Si,jを各開札者Aiに秘密通信路により送信する。（例えば、各開札者Aiの公開鍵で暗号化して送信する。）
[開札手順]
開札装置{Ai}(1≦i≦a)は、開札手順(ステップ210-250)により協力して開札を行い、落札者Bj、落札価格kを決定する。
（ステップ210）
各開札装置Aiは全入札者Bjの入札{(Bidj,σj)}(1≦ｊ≦ｂ)が揃ったら、入札者の署名σjを署名検証部で正当性を検証する。
（ステップ220）
各開札装置Aiは1≦ｊ≦ｂについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)をハッシュ関数h計算部で計算し、予め公開されているhp+1（Si,j)と等しいことを確認する。
（この時、hp（Si,j)を公開するとpで入札されたことが分かるので入札価格表の最高価格以上の価格に対するハッシュ関数を公開する。）
（ステップ225）
ある開札装置はk＝pとして以下を繰り返す。
（ステップ230）
各開札装置Aiは1≦ｊ≦ｂ（全入札者）についてhk(Si,j)を公開する。ある開札装置はa組の値{{hk(Si,j)}(1≦ｊ≦ｂ)}(1≦i≦ａ)が全て揃ったら
【００１３】
【数３５】
0003690494.tif 000004
【００１４】
を計算し、既に公開されているbj(ステップ130）と比較して検証する。
（ステップ240）
全てのjについて検証が不成立なら、k＝k−1（入札価格を下げる）として（ステップ230）へ戻る。
（ステップ250）
あるjたちについて検証が成立なら、この入札者Bjたちを落札者、kを落札価格として公開掲示板等により公開する。
（実施例２）
以下では、本発明の実施例２について説明する。
【００１５】
実施例２は実施例１のt out of a閾値版であり、開札者{Ai}(1≦i≦a)のうちｔ人の開札者が協力すれば開札を行うことができる。
本発明の全体構成は、実施例１と同様に開札装置（開札者）{Ai}(1≦i≦a)と入札装置（入札者）{Bj}(1≦j≦b)が通信路を介して接続されている。
まず開札装置（開札者）{Ai}(1≦i≦a)は[前処理]を行い、次に各入札装置（入札者）Bjは[入札手順]により入札を行い、最後に開札装置（開札者）{Ai}(1≦i≦a)は[開札手順]により協力して開札を行う。
[前処理]
開札装置（開札者）{Ai}(1≦i≦a)のうち、ある開札装置は入札価格表{1,・・・,k,・・・p}およびハッシュ関数
【００１６】
【数３６】
0003690494.tif 000005
【００１７】
および閾値ｔを決めて公開掲示板等により公開する。実際にはhとしてSHA-1などの実用的なハッシュ関数を用いる。
[入札手順]
各入札装置Bjは入札手順（ステップ110-150）により入札を行う。
（ステップ110)
各入札装置Bjは入札価格kj(1≦kj≦p)を決定する。
（ステップ120)
各入札装置Bjは秘密の乱数{Si,j}(1≦i≦a)を乱数生成部で生成し、およびランダムな有限体Fq上のｔ−１次多項式Fj(x)∈Fq[x]を生成する。
（ステップ130）
各入札装置Bjは入札価格kjに対する入札情報Bidj
【００１８】
【数３７】
0003690494.tif 000006
【００１９】
を計算する。（ただし、sa,j：価格指標の分散情報を示す。）
（ステップ140）
各入札装置は入札情報Bidjとその署名σj＝SigBj(Bidj)を各開札装置に送信し、公開掲示板等により公開する。
（ステップ150）
各入札装置Bjは秘密の乱数Si,jを各開札者Aiに秘密通信路により送信する。（例えば、各開札者Aiの公開鍵で暗号化して送信する。）
[開札手順]
開札装置{Ai}(1≦i≦a)は、開札手順[210-250]により協力して開札を行い、落札者Bj、落札価格k（入札価格の最大値）を決定する。
（ステップ210）
各開札装置Aiは全入札者Bjの入札{(Bidj,σj)}(1≦ｊ≦ｂ)が揃ったら、署名σjの正当性を署名検証部で検証する。
（ステップ220）
各開札装置Aiは1≦ｊ≦ｂについてハッシュ関数の連鎖{hk(Si,j)}(1≦k≦p+1)をハッシュ関数h計算部で計算し、予め公開されているhp+1(Si,j)と等しいことを確認する。
（この時、hp（Si,j)を公開するとpで入札されたことが分かるので入札価格表の最高価格以上の価格に対するハッシュ関数を公開する。）
（ステップ225）
ある開札装置はk＝pとして以下を繰り返す。
（ステップ230）
各開札装置Aiは1≦ｊ≦ｂについてhk(Si,j)を公開掲示板等で公開する。ある開札装置はa組の値{{hk(Si,j)}(1≦ｊ≦ｂ)}(1≦i≦ａ)のうち少なくともｔ組揃ったら、
【００２０】
【数３８】
0003690494.tif 000007
【００２１】
（ステップ240）
ある開札装置はすべてのjについて検証が不成立なら、k＝k−1として（ステップ230）へ戻る。
（ステップ250）
ある開札装置はあるjたちについて検証が成立なら、入札者Bjたちを落札者、kを落札価格として公開する。
【００２２】
【発明の効果】
本発明の提案する電子入札開札方法及び装置は、ハッシュ関数の連鎖を用いて構成されているため、ハッシュ関数としてSHA-1などの実用的なハッシュ関数を用いることにより、公開鍵暗号を用いていた従来方法よりも、計算量的に数万倍効率的な入札開札方法及び装置を実現している。
また、開札は開札者のみでできるので、入札者は開札時には開札者と通信する必要はなく入札ときにのみ通信すればよいため、通信量的にも効率的な入札方法を実現している。
【００２３】
さらに、電子入札方法として要求される次のような性質を満たしている。
[価格秘匿性]
落札者がでたところで開札は終了し、落札者がでてきた以降のハッシュ関数の連鎖の値hk(Si,j)は秘密なので、落札価格以外の入札価格は秘匿されている。
[検証可能性]
入札情報{Bidj}1≦ｊ≦ｂは公開されているので、ハッシュ関数の連鎖の正しさ、よって落札者および落札価格の正当性はだれでも検証することができる。
[否認不可性]
各入札情報Bidjには入札者Bjの署名σj＝SigBj(Bidj)が付いているので、入札行為は否認できない。
【００２４】
また、入札情報Bidjが公開されているので、行った入札の否認や改竄をするためにはハッシュ関数hの衝突を見つけなければならないが、ハッシュ関数hの衝突困難性によりこれは不可能である。
【図面の簡単な説明】
【図１】本発明の概要構成図。
【図２】本発明の実施例１である入札者Bjの入札を説明する図。
【図３】入札装置Bjのブロック図。
【図４】開札装置Aiのブロック図。
【図１】
0003690494.tif 000040
【図２】
0003690494.tif 000041
【図３】
0003690494.tif 000042
【図４】
0003690494.tif 000043