JAIST Repository: An anonymous auction protocol with a single non-trusted center using binary trees

Japan Advanced Institute of Science and Technology

JAIST Repository

https://dspace.jaist.ac.jp/

Title

An anonymous auction protocol with a single

non-trusted center using binary trees

Author(s)

Omote, Kazumasa; Miyaji, Atsuko

Citation

Lecture Notes in Computer Science, 1975/2000:

461-490

Issue Date

2000

Type

Journal Article

Text version

author

URL

http://hdl.handle.net/10119/4456

Rights

This is the author-created version of Springer,

Kazumasa Omote, Atsuko Miyaji, Lecture Notes in

Computer Science, 1975/2000, 2000, 461-490.The

original publication is available at

www.springerlink.com,

http://www.springerlink.com/content/a48be4v3unhak

qpr

Description

Information security : third international

workshop, ISW 2000, Wollongong, Australia,

December 20-21, 2000 : proceedings / Josef

Pieprzyk, Eiji Okamoto, Jennifer Seberry (eds.).

non-trusted center using binary trees

KazumasaOMOTEyandAtsukoMIYAJIy

SchoolofInformationScience

JapanAdvancedInstituteofScienceandTechnology, Asahidai1-1,Tatsunokuchi,Nomi,Ishikawa,923-1292JAPAN

E-mail: fomote, [email protected]

Abstract. Someworksaboutanelectronic auctionprotocolhavebeen proposed[2 ,3 ,4,5,6,8,11 ,12]. Anelectronic auction protocol should satisfy the following seven properties: (a)Fair of bidders; (b)Security ofbids; (c)Anonymity;(d)Validityofwinningbids;(e)Non-repudiation; (f)Robustness; and (g)EÆcient bidding points. Asfor anonymity, pre-vious protocols assume some entities like a dealer or plural centers to be trusted.Inthis paper,anonymityis realizedwithout atrusted cen-ter,maintainingbothcomputationalandroundcomplexitylow. Further-more,werepresentabideÆcientlybyusingbinarytrees:for2

k

bidding points, the size of the representation of bidsis justk.Previous works investigatingasealed-bidauctionaimat\eÆciency"butnot \entertain-ment" seen inEnglish auction[2, 4,5, 6 , 11, 12 ]. We introduce a new idea ofentertainmenttotheopeningphasebydecreasingwinner candi-dateslittlebylittle.Ourprotocolhasthefollowingthreemainfeatures in addition to the above seven properties: perfect anonymity(a single non-trustedcenter),eÆcientbiddingpointsandentertainment.

keywordsanonymity,sealed-bidauction,biddingpoints,entertainment, one-wayfunction

1 Introduction

Auctionisaprice-decisionsystembasedonamarketprinciple,but notaxed price.An auction pricewould re ect amarket pricemoreclearly than axed pricesinceit isdecided bybidders.There are manydierenttypes ofauction. AnEnglishauctionisthemostfamiliartype.InanEnglishauction,eachbidder oers the higher price for goods one by one, and nally a bidder who oers thehighestpricegetsthe goods. Eachbidderparticipatesin theprice-decision processandenjoyit.SoanEnglishauctionhasafeatureofentertainmentaswell asaprice-decision system.A sealed-bid auction isanother type,in which each biddersecretlysubmitabidtoacenteronlyonce.Thereforeasealed-bidauction decidesthepricemoreeÆcientlythananEnglishauction. However,allbidders cannot enjoy the price-decision process. A sealed-bid auction would not have

asealed-bidauction[2,4,5,6,11,12].Wenotethatallelectronic auctionaims ateÆciencybut notafeatureofentertainment.

Thereare mainly threeentitiesin anauction, acenter(C),avendor(V)and abidder(B). This basiccomponentis also used in an electronic auction. Each roleisasfollows:

{ Center(C):Thisincludesanauctioneer.Acentersponsorsseveralauctions. { Vendor(V):Vendorwantstosellher/hisgoodsandisregisteredtoacenter. { Bidder(B):Bidderwantstobuy goodsandisregisteredto acenter.

VonlyrequestsanauctiontoCandcommunicateswithneitherCnorBwhilean auctionisheld.AnauctionprocessisconductedbetweenCandB.Thefollowing aresevenpropertiesthatarerequiredinanelectronicauctionprotocol:

(a) Fair of bidders:allbidderscanlook aproperpollingonInternet. (b) Securityof bids:nobodycanforge(falsify) andtapabid.

(c) Anonymity: nobody know the correspondence of abidder to a bid even aftertheopeningphase.Notethat,inelectronicauction,thisdoesnotmean the secrecy of loosing bids. Anonymity that dose not reveal which bidder exceptforawinnerhasbidatwhatbidcanberealizedevenifsomeloosing bidsarerevealed.

(d) Validity of winning bids:aprotocol canprovethatawinningbidisthe highestor thelowest valuesofallbids.

(e) Non-repudiation:awinnercannotdenythathe/shesubmittedthewinning bidafterthebidis opened.

(f) Robustness: even ifa biddersends an invalid bid, the auction process is unaected.

(g) EÆcientbiddingpoints:ifthebiddingpointsaresetupdiscretely,many biddingpointsaredesirable.

Inaddition totheabovesevenproperties,asealed-bidauctionrequiresthe fol-lowingproperty.

(h) Secrecyof loosingbids:aprotocolkeepsloosingbidssecret.

ApparentlythesecrecyofloosingbidsisnotrequiredinanEnglishauctionsince allloosing bids are revealed. Therefore thenecessity ofsecrecy ofloosing bids dependsontargetingwhatelectronicauction.Aswewilldescribebelow,weaim at a sealed-bid auction with afeature of an English auction. So our protocol revealsonlypartofdistributionofbidsbutnotrevealloosing bidsdirectly.

Variousworksaboutelectronic auctionhavebeenproposed [2,3, 4, 5, 6, 8, 11, 12]. In [8], the timing is considered when each bidder sends a bid in real-timeelectronicauctiononInternet.Asealed-bidauctionprotocolisinvestigated in [2, 4,5, 6, 11, 12] and asecond-price auction protocol is discussedin [3]. A second-price auction is a kind of sealed-bid auction: a bidder who oers the

technique[13]. In thistechnique, however,anonymityon thecorrespondenceof abidderto abidshould leak outby adealer[2]oracollusion ofcenters form-ing a quorum[3, 4, 11]. On the other hand, the scheme[6] cannot satisfy the anonymityforthecenter,inwhichthesecretsharingtechniqueisnotused. To sumup,thepreviousprotocolsassumethatsomeentitieslikeadealerorcenters to betrusted. Usually plural centers require morecommunicationcost[2, 3, 4] ormorecomputationamount[11].Onthe otherhand,[5,12] realizeanonymity withoutatrustedcenter,howeverunfortunatelybothcomputationalandround complexitytobiddersareratherhigh intheopeningphase.[5]usesnota pub-lic key cryptosystem but a one-way hash function by introducing the way of \PayWord"[10], which exceedinglydecrease the computationalcomplexity. Al-thoughsuch atechniqueis used, high round complexity to biddersis required foranonymitywithoutatrustedcenter. Inthispaper,anonymityonthe corre-spondence ofabiddertoabidisrealizedwithoutatrustedcenter,maintaining bothcomputationaland roundcomplexity low.Inasenseourprotocolrealizes \perfectanonymity",andalsorealizes\non-trustedcenter".

The bidding points are set up discretely in advance in order to realize an anonymity[3, 4, 5, 11, 12]. Therefore the more bidding points are set up, the lessprobabilityoftiedecreases.In[4],thesizeofrepresentationofbidsdirectly depends on thenumberof biddingpoints:for kbidding points, thesize of the representationof bids is just k. Therefore the morebidding points areset up, themorecommunicationamountisrequiredinthebiddingphase.Althoughthe biddingpointsareexpressed rathereÆciently bylogarithm expression[3], both protocols[3, 4] can handle neither tie bids nor invalid bids well: they cannot specify the winners or how many winners there are if the same winning bids or invalid bids are submitted. On the other hand, in [11] a bid is expressed eÆciently as an encryption of a known message, which does not depend on thenumberofbidding points.Thereforeitimprovestherepresentationofbids. However,unfortunatelyitcostsmuchcomputationtimeintheopeningphase:it repeatsntimesdecryptionofElGamalorRSAcryptosystemsuntilthewinning bidsaredecided,where nisthenumberofbidders.Apparentlyitis notsuited for handling many bidders. In this paper, a bid is represented eÆciently by usingbinary trees: for2

k

bidding points,the size ofthe representationof bids isjustk.Furthermore,thecomputationalandroundcomplexityintheopening phasedepends ononly (probabilisticly)k,but notthenumberof bidders.Our protocol canwellhandlebothtiebidsandmanybidders,andalsorepresentsa bideÆcientlyformanybiddingpoints.

Uptothepresent,allauctionprotocols[2,3,4,5,6,8,11,12]aimatrealizing sealed-bid auction faithfully, whose concern is \anonymity" and \eÆciency". Entertainmentseenin arealEnglishauctionhasnotbeendiscussedbefore. In this paper, weintroducea newideaof entertainmentto the openingphase by decreasing winner candidates little by little. Our price-decision process looks like a winner-decision process in lottery tickets. Note that the computational

only(probabilisticly)kfor2 biddingpoints,butnotonthenumberofbidders. Our electronic auction protocol satises the above seven properties. Main featuresinourprotocolisasfollows:

{ Perfect anonymity with low computational and low round

com-plexity (a single non-trusted center): Perfect anonymity means that nobody(including acenter)can identify abidderfor her/hisbidexceptfor a winning bid even after the opening phase. Our protocol realizesperfect anonymitywithbothlowcomputationalandlowroundcomplexity.

{ EÆcient bidding points: abid isrepresentedeÆcientlyby usingbinary trees:for2

k

biddingpoints,thesize oftherepresentationofbidsisjustk. { Entertainment: Entertainment means that many bidders can enjoy the

openingphasebydecreasingwinnercandidateslittlebylittle.

Thispaperisorganizedasfollows.Section2summarizesasapreviouswork. Section3explainsourbasicmodelandpresentstwopracticalschemes,onebased onDLPandtheotherbasedonaone-wayhashfunction.Section 4investigates attacksagainstour scheme. Section 5discusses thepropertiesof our protocol. Section6presentsperformanceofourprotocol.

2 Previous Work

Inthissection,wesummarizetheoutlineof[4]anddiscusstheweaknesses.

2.1 Outline

First C sets L bidding points fv 1

;


;v t

;


;v L

g and L encryption function fE 1


;E t


;E L

gaccordingtoeachbiddingpoint.C keepseachinverse func-tionfE

1 t

g.Awinnerwhobidsthehighestvaluegetsgoodsinthehighestvalue. WedescribehowB

i

withanidentityinformationID i placesabidv bi . Thebid vectorM i (t)forB i is asfollows: M i (t)=  E t (ID i ) if b i t; 0 otherwise:

Weexplain howtondthehighestbidfromthebidvectors.Givenbid-vectors ofallbidders,eachelementin thesamebidding pointareaddedto sum-vector M(t): M(t)= X i M i (t) (1tL): (1)

IfM(t)iszero,itmeansthatnobodybidsv t

.Thewinningbidv t

isgivenbythe rstt that M(t) isnon-zero.If onlyonebidderbidsv

t

(a winning bid),he/she isidentiedbyID

i

usingtheinversefunctionE 1 t

.

This protocol usessecretsharingtechnique[13]since C can knowthe corre-spondenceofabiddertoabidfromM

i

(t).EachbidvectorM i

Therearefourweaknessesin[4].

{ Anonymityonthecorrespondenceofabiddertoabidshould leakoutbya collusionofcentersformingaquorum.

{ Thisprotocolcanhandleneithertiebidsnorinvalidbidswell: theycannot specifythewinnersorhowmanywinnersthereare,ifthesamewinningbids orfaultybidsaresubmitted.

{ Thesizeofrepresentationofbiddingpointsdirectlydependsonthenumber ofbiddingpoints:forkbiddingpointsthesizeoftherepresentationofbids isjust k.

{ A winner is decided assoon assum-vector M is computed.Therefore any bidderscannotenjoytheopeningphase.

3 Our Protocol

Weproposeanauctionprotocolwhichsatisesaperfectanonymityonthe cor-respondenceofabiddertoabidexceptforawinningbidevenaftertheopening phase,eÆcientbidrepresentationbyusingbinarytrees, andafeature of enter-tainmentin theopeningphase.Forsimplicity,weassumethewinnerstobethe onewhobidsthehighestvalueamongasetofbiddingpoints.

3.1 Explanationof Notations

Notationsaredened asfollows:

n :numberofbidders

k :numberofbidclass

L :numberofbiddingpoints (L=2

k ) i :anindex forB (i=1;


;n) r i ;R i

:arandomnumberforB i x

i

:asecretkeyforB i y

i

:apublickeyforB i M

i

:abidvectorforB i

f(
) :aone-wayfunction(e.g.DLP,ahashfunction)

3.2 Preliminary

{ Initialization: Csetsupaone-wayfunction f andpublishesf toallB. { Requestingby vendor: V requestsanauctiontoC tosellher/hisgoods. { Entry ofbidders: Beforestartinganauction,bidderswhichwanttobuy

goodsexecutethefollowingprocedure:rstmakeapairofsecretkeyx i and publickeyy i ,send y i

toC andgetitscerticatebyacenter. { Settingupofbiddingpoints: CsetsupL=2

k

biddingpointsforgoods requestedbyL.

111

110

101

100

011

010

001

000

1

0

1

1

0

0

0

0

0

0

1

1

1

1

Class 1

Class 2

Class 3

Fig.1.ExampleofBiddingPoints

3.3 BiddingPoints

Abinarynumberdenotesthevalueofabiddingpoint.Forexample,weseethat eightbiddingpointsaregivenbythree classesin Figure1.Generally,thereare 2

k

(= L) bidding points for k classes. Note that a bid is represented by abid vectorM

i

, whose size depends on onlyk. As aresult, it is possible to handle manybiddingpoints.

Inourprotocol,biddingpointshavetwopropertiesasfollows:

1. Inarepresentationofabid,abinarynumber0or1expresseswhetherabid opensthenextclassornot.

2. A binary expression can set up more bidding points. This can reduce the probabilityoftie.

3.4 BiddingPhase

Abid sent byB i

to C isrepresentedby abidvectorM i . Theformat ofM i is denedasfollows: M i

=[class1; class2;


; classk; ID i

]:

The bid vector M i

consists of the value expressing 0 or 1 in each class and theidentication informationofB

i

inthelastrow.This ID i

cannotbeopened unlessB

i

isawinnercandidate.ThereforeanonymityevenforCissatised.M i isopened from class1to ID

i

oneby one.Byusing ID i

, we canconrm who placesahighestbids.WeexplainhowB

i

placesabid.Forsimplicity,B i places abidv b i =(1


1 t  01


11 k 1 

01)thatt-th and(k 1)-thbitsare0.Thenbid vectorM i isasfollows: M i =  f k (r i )+f k 1 (r i );


; f k t+1 (r i )+R i;k t ;f k t (r i )+f k t 1 (r i );


; f 2

(ri)+Ri;1; f(ri)+ri; ri+xi 

i i;s

Step 1. B

i

generates a random number r i and computesf(r i );


;f k (r i ) by usingaonewayfunctionf andr

i . Step2.B

i

constructsabidvectorM i correspondingtov bi : (1sk) M i;s =  f k s+1 (r i )+f k s (r i ) (if s-thofv bi =1) f k s+1 (r i )+R i;k s (if s-thofv bi =0); M i;k +1 = r i +x i ; whereR i;k s

isarandomnumberandx i isB i 'ssecretkey. Step 3. B i has to keep fr i ;f(r i );


;f k (r i

)g secret, but has to posses only ff k (r i );f k t (r i );f(r i )gas openingkeys. Step 4. B i sends M i to C, where M i

doesnotneed to be encrypted,because B

i

keepstheopeningkeyf k

(r i

)secrettoconcealthevalueofv b

i . Ourbidvectorhasthefollowingfeatures:

1. Anonymityofthecorrespondenceofabiddertoabidissatisedaslongas openingkeysarekeptsecret.

2. Ifoneopeningkeyisposted,theneachrowofM i

isopenedonebyonetill therowcorrespondingto\0"inabid.Howevertherownextto\0"inabid isneveropenedaslongasthenextopeningkeyiskeptsecret.

3. Everybodycan verify thevalidityof abidvectorbycheckingf k s+1 (r i )= f(f k s (r i

)),bothofwhich areopentoeverybody.

4. Bid vectorsfor only bidders whoplace the highestbid are opened one by onetillthelastrow,inwhichtheirsecretkeyisset.Furthermoreeverybody can conrmthatthevalidityofboththehighestbidandwinners.

3.5 OpeningPhase

Thissectionpresentstheopeningphaseinourprotocol.FirstCopensbotheach bidvectorandeach publickeyforbidderson Internet. Notethat nobody gets

1 1 0 1 0

1 0 1 0 1

1 1 1 0 1

Class

1 2 3 4 5

Secret Key

x

1

x

2

M

1

M

M

2

3

Bid Vector

M

4

1 1 0 1 1

x

4

x

3

weassumethat abidv bj

forB j

in section3.4isthehighestin thisauction.

[Step1] EachB i

sendstherstopeningkeyf k

(r i

)to C.Theneachbidvector M

i

isopenedtilltherowcorrespondingto\0",whilef k t+1 (r i )=f(f k t (r i )) isconrmed.Ontheotherhand,everybodycanconrm0oft-th rowinM

i by checkingf k t+1 (r i )6=f(R i;k t ).

[Step2] Only biddersB i

whose bidvectorsareopenedto thelowestbidsend thenextopeningkey(e.g.M

3

inFigure2).Inthiscase,thenextopeningkeyis f

k t (r

i

).InthesamewayasStep 1,thisprocedurecontinuestillthelastrow. NotethatB

i

'ssecretkeyisnotopenedaslongasB i

keepsthenalopeningkey secret.

[Step 3] Everybody can conrm that B j

is the winner of bid vector M j

by checkingapairofpublic keyy

j

andthesecretkeyx j

, which isrevealed inthe lastrow.

3.6 Schemes basedon a practical one-way function

Wewillpresenttwoexamplesofone-wayfunctionf,oneisDLP[1]andtheother ishashfunction.

[DLP] Cselectsalargeprimepandg2Z  p

withprimeorderq.Thenaone-way functionf issetto f(r)=g

r

(modp).

[One-wayhashfunction] Leth(
)beacryptographicallystronghashfunction suchasSHA-1[7]orMD5[9].Thenaone-wayfunction f issettof(r)=h(r)in thesamewayas"PayWord"[10].

4 Attacks

Thissectiondiscussessomeattacksagainstourprotocol.

4.1 Invalid bidvector

Weinvestigatethat any invalid bid doesnot havean in uence onthe auction proceedings.Figure3showstwotypesofinvalidbidvector:

1. abidderdoesnotembedher/hissecretkeyintothelastclassinabidvector [Figure3-M

3 ],

2. abidder doesnotembed theproper opening keyintoa bidvector[Figure 3-M ].

1 1 0 1 0

1 0 1 0 1

1 1 1 0 1

Class

1 2 3 4 5

Secret Key

x

1

x

2

Random

1

2

3

Bid Vector

4

1 1 0 # #

x

4

M

M

M

M

Fig.3.Examplesofinvalidbid

First we discuss the case 1. Unless M 3

is a winner candidate, there is no problem:M

3

issimplyignored.IfM 3

isawinnercandidatelikeFigure3,nobody canidentify B 3 , because M 3 is not embedded B 3

's secretkey. In such a case, M

3

issimplyremovedfromthisauctionasaninvalidbid.Inourprotocol,abid vector isopenedfrom thehighest bid. Thereforethe auction proceedings may justcontinueexceptforaninvalidbidvector.

Next wediscussthecase2.Both M 1

andM

4

arewinner candidatesexcept forM

3

.However,nobodycanopentheclass4ofM 4

sinceM 4

isnotembedded into the proper opening keyin theclass 4.In such a case,B

4

is also ignored. ThereforeM

1

isanonlywinnercandidate.Theopeningphasecontinuesexcept forM

3

andM

4 .

In ourprotocol, wecannot identify the invalid biddersin thesame way as [3, 4, 5, 11, 12]. However our protocol has a feature that each bid vector of bidders is independently opened. Therefore even if an invalid bidder places a bidvector,theauctionproceedingswillbeunaected:allinvalidbidsaresimply ignored.Soourprotocolsatisesdisturbingresistance,i.e.robustness.

4.2 Group Collusion

Weinvestigate groupcollusionattacks by somebidders:attackerswantto get goods in the lowestprice available.Forsimplicity,let fI

1 ;I 2 ;I 3 g be aninvalid group.TherearethreecasesofgroupcollusionseeninFigure4,whichexpresses apartofbinarytreein bids:

Case1(Figure4-(a)):thereareonlypluralinvalidbiddersI 1 ,I 2 andI 3 inhigher trees(Tree1).

Case 2(Figure4-(b)): thereareonlyoneinvalidbidderI 1

in highertrees. Case3(Figure4-(c)):Thereisnoinvalidbidderbuttherearesomevalidbidders V 1 ,V 2 andV 3 in highertrees.

Inthecase1,attackerscangetgoodsinthelowestbidofI 3 bycancelingtwo bidsofI 1 andI 2

.Howeverinbothcase2andcase3,itisimpossibleforattackers tocontrolthewinningbid.Furthermore,ifanattackerI placesthehighestbid

Only invalid bidders

Tree 1

Tree 2

I

I

I

1

2

3

Only one invalid bidder

Tree 1

Tree 2

I

1

Only valid bidders

Tree 1

Tree 2

V

V

V

1

2

3

(a) : Case 1

(b) : Case 2

(c) : Case 3

Fig.4.GroupCollusion

ofallbidpoints,thenI 1

cannotdenythewinningbidaftertheopeningphase.To sumup,attackerscancontrolthewinningbidonlyinthecase1sinceattackers cannotget goods in the lowerpricethan that of valid bidders.Therefore such collusionattackershavelittlein uenceontheauctionproceedings.

CmaysolvethisgroupcollusionbyplacingsomebidsrandomlysinceCmakes it hard for invalid bidders to control awinning bid. Of courseC should place somebidsnearthewinningbid.

5 Properties

Ourprotocolsatisesthefollowingproperties:

{ Fair of bidders|Allbidderscanlook aproperpollingonInternet. { Security of bids | Security of bids means that: 1. Before the opening,

a bid cannot berevealed. 2. Any bidder can check whether her/hisbid is notforged.Inourprotocol,eachrowofabidvectorconsistsoftworandom numbersf(r i )+r i andr i +r 0 i

byusingaone-wayfunction f andarandom numberr

i andr

0 i

.Asfortheformer,r i

iskeptsecretaslongasf(r i

)isnot opened,whosesecuritydependsonf.Asforthelatter,r

0 i

ischosenrandomly, and r

i

is kept secretas longasthe nextrowis not opened. Thereforethe securityalsodependsonf.Thesecurityonattacksofusingallrowdatain abidvectoralsodependsonf.Ontheotherhand,ifabidisfalsied,then thecorrespondingbiddercaneasilynoticethefaultybidsinceallbidvectors areopenedonInternet.

{ Anonymity|Inourprotocol,onlyawinner'ssecretkeyisrevealed,which identiesthecorrespondingbidder.Ontheotherhand,othersecretkeysare keptsecreteven after theopeningphase. As aresult,nobody(including a center)canknowthecorrespondenceofabiddertoabidexceptforawinner. { Validityofwinningbids|Sincebidvectorsareopenedonebyonefrom

Totalcommunicationamount(bit)Eachbidder'scomputationamount

Bidding Opening Bidding Opening

[4 ] 1024(2 k 1)mn 0 P
2 k 0 DLP 1024(k+1)n 1024 2 1 2 k
n D
k 0 Hash 160(k+1)n 160 2 1 2 k
n H
k 0

thevalidityofabidvectoriseasilycheckedbyaone-wayfunctionandsecret key.

{ Non-repudiation|AwinnerB

j

cannotdenyher/hisbidsinceB j

'ssecret keyisrevealed.

{ Robustness |Ourprotocol hasafeature that each bidis independently opened.Thereforeifinvalidbidsareplaced,theauctionproceedingswillbe unaected:invalidbidsaresimplyignored.

{ Entertainment| Englishauctionhas anentertainmentthat it doesnot only decide a winner but also pleases all participants until the winner is decided. In our protocol, we introduce a feature of entertainment to the opening phase by decreasing winner candidates one by one, which looks likeawinner-decisionprocessinlotterytickets.Sinceweaimatafeatureof entertainment,ourprotocolrevealsonlypartofdistributionofbids.However our protocol doesnot reveal the whole distribution of bidslike [2, 6],and what isstill better,satisesanonymity.

{ Tie|Inelectronicauctionprotocol,biddingpointsareoftensetdiscretely[3, 4,5,11,12].Insuchasituation,twopropertiesshouldberequired:1. Win-nersshouldbespeciedeveniftwoormorebiddersplacethesamewinning bid. 2. The probability of tie should be reduced by setting many bidding points.Asfortheformer,ourprotocolcanspecifythewinnersinthecaseof thesamewinningbids.Asforthelatter,ourprotocolcansetmanybidding pointslike2

k

,maintainingcomputational,communicationalandround com-plexityof B

i

orC low, allwhich depend onk. Furthermore theprobability oftiecanbereduced.

6 Performance

In this section, we compare our protocol with [4] from the point of view of communicationandcomputationamount,whichareshowninTable1.Herelet thenumberofbiddingpointsandbiddersbe2

k

andn,respectively.In[4],plural centersarerequired,whosenumberisdenotedbym(2).Weassumeaone-way functionf tobeDLPora160-bitoutputone-wayhashfunction,whoseoutput size is denoted byjfj. In[4], thecommunicationamountin thebidding phase

Thereforethecommunicationamountcanbedramaticallyreduced.

Next wediscussthecommunicationamountin theopeningphase.Sincewe aimat afeatureofentertainment,communicationbetweenB

i

andC isrequired intheopeningphase.ButwewillseeinTable1thatthecommunicationamount intheopeningphaseisnegligiblesmall.Forsimplicity,weassumethatthereare

n 2

i

biddersineachbranchofclassiontheaverage,whosendanopeningkeyin probability

1 2

. Thereforethecommunicationamountintheopeningisatmost

jfj n+ k X i=1 n 2 i ! =jfj  2 1 2 k  n:

Lastlywediscuss thecomputation amount.Let P becomputation amount to computethe distributioninformation of the secretsharing technique, D be computationamount to computeamodulusexponent, andH becomputation amount to compute a one-way hash function. In the same discussion as the communication amount, the computation amount of [4] depends on 2

k while thatofourprotocoldependsononlyk.

7 Conclusion

We have proposed an anonymous auction protocol with a single non-trusted center.Ourprotocolrealizesthefollowingfeatures:

Perfect anonymity with low computational and low round

com-plexity:Nobodycanidentifyabidderfromher/hisbidexceptforawinning bidevenaftertheopeningphase.

EÆcientbiddingpoints:For2 k

biddingpoints,thesizeofthe represen-tationofbidsisreducedto justkbyusingbinarytrees.

Entertainment:Manybidderscanenjoytheopeningphasebydecreasing winnercandidateslittlebylittle.

Robustness : Even if a bidder sends an invalid bid vector, the auction processisunaected.

Application:Ourprotocolcanbeeasilyappliedtoapowerauction,which decidesthepluralwinners.

References

1. T.ElGamal. APublicKeyCryptosystemandaSignatureSchemeBasedon Dis-creteLogarithms. IEEETrans.onInformationTheory,pages469{472,1985. 2. M.Franklinand M.Reiter. The designand implementation ofa secure auction

service. IEEE TransactionsonSoftware Engineering,5:302{312,1996.

cols. In Proceedings of the First IEEE Workshopon Dependable and Real-Time E-CommerceSystems, pages62{69,1998.

5. K.KobayashiandM.Morita. EÆcient sealed-bidauction withquantitative com-petitionusingone-wayfunctions. ISEC99-30,pages31{37,1999.

6. M.Kudo. Secureelectronic sealed-bid auctionprotocolwithpublickey cryptog-raphy.IEICE Trans.Fundamentals,E81-A(1):20{27,1998.

7. NIST. SecureHashStandard(SHS).FIPSPublication180-1,April1995. 8. C-S. Peng, M.Pulido, J.Lin, and M.Blough. TheDesign of an Internet-based

RealTimeAuctionSystems. InProceedingsof theFirst IEEE Workshopon De-pendable andReal-Time E-Commerce Systems,pages70{78,1998.

9. R.L.Rivest. TheMD5message-digestalgorithm. InternetRequest forComments, pages302{312,April1992.

10. R.L.Rivest and A.Shamir. PayWord and MicroMint:Two simple micropayment schemes. ToAppearattheRSA'96 Conference,May1996.

11. K.Sako. An Auction Protocol Which Hides Bids of Losers. In Proceedings of PKC2000,pages422{432,2000.

12. K.SakuraiandS.Miyazaki. ABulletin-boardbaseddigitalauction schemewith biddingdownstrategy-towardsanonymouselectronicbiddingwithoutanonymous channels nor trustedcenters inCryptographic Techniques and E-Commerce. In Proceedings ofthe1999InternationalWorkshoponCryptographicTechniquesand E-Commerce(CryTEC'99),1999.

13. A.Shamir.Howtoshareasecret. CommunicationsoftheACM,22:612{613,1979.

Thisarticle wasprocessedusingtheL A