Bit-Sli e Au tion Cir uit
Kaoru Kurosawa
and Wakaha Ogata
IbarakiUniversity,4-12-1 Nakanarusawa, Hita hi,Ibaraki,
316-8511, Japan kurosawa is.ibaraki.a .jp
TokyoInstitute of Te hnology, 2{12{1 O-okayama, Meguro-ku,
Tokyo152{8552, Japan. wakahass.tite h.a .jp
Abstra t
Inthispap er,weintro du eabit-sli eapproa hforau tionsandpresent
a more eÆ ient ir uit than the normalapproa h forthe highest-pri e
au tion. Our ir uit anb e ombined withany au tion proto ol based
on general ir uit evaluation. Esp e ially, if we ombine with the mix
andmat hte hnique,thenwe anobtainahighest-pri eau tionproto ol
whi h is at least seventimes faster. A se ond-pri e au tion proto ol is
alsoeasily onstru tedfromour ir uit.
Keyword. au tion,multipartyproto ol,bit-sli e, ir uit,mixandmat h
1 Introdu tion
1.1 Sealed-BidAu tion
Au tionsaregettingvery p opular intheInternet. They arenowamajorarea
inthewebele tri ommer e.
Asealed-bidau tion onsistsoftwophases,thebiddingphaseandtheop
en-ingphase. Inthebidding phase,allthebidderssubmit theirbiddingpri es to
the au tioneer. Inthe op ening phase (of the highest-pri e au tion), the
au -tioneerannoun esthehighest pri e andtheidentities ofthewinners.
In the se ond-pri e au tion (also known as Vi krey au tion), the highest
bidder wins, and the learing pri e, the pri e that the winner has to pay, is
equalto the se ond highest bid. (It is loser to the real life au tion than the
highest-pri eau tion.)
Throughoutthepap er,we assumethat:
Therearenservers.
Therearembidders, denotedbyA
1 ;A 2 ;:::;A m .
A preliminaryversionof thispap erwaspresentedatESORICS2002andapp earedin
Ea hbidder A
i
hasak -bitbidB
i =(b i ;:::;b i ) 2 . In general, X = (x (k 1) ;:::;x (0) ) 2
denotes a k -bit integer, where x (k 1)
denotesthemostsigni antbitandx (0)
denotestheleastsigni antbit.
1.2 Au tion Proto ols Based on Cir uit Evaluation
Inthetrivials heme whi hassumesasingletrusted au tioneer,theau tioneer
knowsallthebiddingpri es. Hemayalsotellalieab outthehighest pri eand
thewinners.
Hen e we need a ryptographi ally se ure au tion proto ol whi h satis es
priva y and orre tness. The orre tness means that the announ ed highest
pri eandtheidentitiesofthewinnersareguaranteedtob e orre t. Thepriva y
meansthat noadversary an omputeanyother information.
In prin iple, it is known that any fun tion an b e omputed se urely by
usinggeneral multipartyproto ols [25, 16, 5,9,17℄. (They are also known as
generalfun tionevaluationproto ols.) A problemis,however,thatthe ostof
ea hbidderisverylargeintheirgeneralforms. Therefore,severals hemeshave
b eenprop osed toa hieve eÆ ientandse ure au tions.
Intheau tionproto olofNaor,PinkasandSumner[22℄whi hinvolvestwo
servers,aproxyoblivioustransferproto olwasintro du edanditwas ombined
with Yao's garbled ir uit te hnique [25℄. Jakobsson and Juels p ointed out a
aw andit was xed by Juels and Szydlo[21℄. The xed proto olis se ure if
thetwoservers donot ollude. The ostofea h server isO (mk t), wheret isa
se urityparameter.
Jakobsson and Juels intro du ed a new general multipartyproto ol alled
mixand mat handshoweditsappli ationtoau tions[20℄.Themixand mat h
te hnique avoids the use of veri able se ret sharing s hemes (VSS) whi h is
intensively used in the other general multiparty proto ols. In their au tion
proto ol(JJau tionproto ol),therefore,ea hbidderA
i
hasonlytosubmither
en rypted bidding pri e without exe uting a VSS. The ost of ea h server is
O (mnk )exp onentiations.
Cramer,Damgardand Nielsen intro du ed anothergeneral multiparty
pro-to olwhi h avoidsVSS [10℄. It an also b e used for au tions. Whilethe mix
andmat h proto olisbased onthe DDHassumptionalone,itis notknownif
this is p ossiblefor this proto ol. On theother hand, theround omplexityis
O (d)whileitis O (n+d)inthemixandmat hproto ol,where disthedepth
ofthe ir uit ofagivenfun tion. Themessage omplexitiesarethesame.
BaudronandSternshowedanau tionproto olwhi hassumesasemi-trusted
au tioneer T [4℄. In this proto ol, T blindly andnonintera tively evaluates a
ir uitwhoseoutputtellsifA
i
isawinneror notforea hbidder A
i . A
i knows
ifheisawinnerbyde ryptingtheoutput iphertextofthis ir uit. T learnsno
informationifhedo es not olludewith anybidder. The ostof T is(mk m
).
(Thisproto ol isnotbased ongeneral ir uit evaluation. It uses somesp e ial
Ingeneral,amultipartyproto olfor omputingafun tionf(x
1 ;:::;x
n )is
de-signedas follows. First we drawa Bo olean ir uit C
f
whi h omputesf. We
next applyageneral gate evaluationte hnique to ea h gate ofC
f
. Therefore,
thesmallerthe ir uitsize is,themoreeÆ ienttheproto olis.
Thenormalapproa hfor ir uitdesignforau tionsisto omparethebidding
pri es one by one (in other words, to run amillionaire's problemproto ol in
order). Totheauthors'knowledge,thesmallestsize ir uitinthisapproa hfor
thehighest-pri eau tionrequires7mklogi algatesandmSele t
k
gates,where
alogi algate has2inputand1outputbits,andaSele t
k
gatehas2k+1input
andkoutputbits. (We presentsu ha ir uit inSe .2.)
In this pap er,we intro du ea bit-sli e approa h forau tions and present a
moreeÆ ient ir uit than the normal approa h for the highest-pri e au tion.
Theprop osed ir uitrequiresonly2mklogi algateswhilethenormalapproa h
ir uitrequires7mk logi algatesandmSele t
k
gates asshownab ove.
Supp ose thatB
max =(b (k 1) max ;:::;b (0) max ) 2
isthehighest biddingpri e,where
b (k 1)
max
denotes the most signi ant bit and b (0)
max
denotes the least signi ant
bit. Thentheprop osed approa h rstdeterminesb (k 1)
max
bylo okingatthemost
signi antbitsofallthebids. Itnextdeterminesb (k 2)
max
bylo okingatthese ond
mostsigni antbitsof allthebids,andsoon.
Our ir uit an b e ombined with any au tion proto ol based on general
ir uitevaluation. Esp e ially,ifwe ombineour ir uitwiththemixandmat h
te hnique,thenwe anfurtherredu e thenumb erofgates justtomkbyusing
thehomomorphi prop erty oftheen ryption fun tion. Hen e we an obtaina
proto olwhi hisatleastseventimesfasterthanJJau tion proto ol.
We also show that a se ond-pri e au tion proto ol (whi h is loser to the
real-lifeau tionthanthehighest-pri eau tion) anb eeasilyobtainedfromour
bit-sli e ir uit forthehighest-pri e au tion.
1.4 Other Related Works
Therearemanyau tionproto olswhi hdonotuse ir uitevaluation. However,
theyhave problemssu has follows.
The rst ryptographi au tions hemewasprop osedbyFranklinandReiter
[14℄. This s heme is not fully private, in the sense that it only ensures the
on dentialityofbidsuntiltheendoftheproto ol.
In the s heme of Ca hin [6℄ whi h involves twoservers, a partial order of
bidsisleakedtooneofthetwoservers. The ostofea h bidderisO (mk t)and
the ostofea h server isO (m 2
k t),where tisase urityparameter.
Inthes hemeofDiCres enzo[13℄whi hinvolvesasingleserver,ahonestbut
urious server do es notlearn any informationunder the quadrati residuosity
assumption. However, nothing is known ab out the se urity if the server is
mali ious. The ost of ea h bidder is O (m 2
k 2
) and the ost of server is also
O (m 2
k 2
Some other works require O (mn2 ) ost for ea h server [18, 23℄. In the
s heme of [3℄, the ost of a server is O (m2 k
) and the ost of ea h bidder is
O (2 k
). Notethatthese ostsaremu hlargerthanthe ostofau tionproto ols
basedon ir uit designsu h as[22,20℄.
1.5 Organization of the Paper
In Se .2, we present the normal approa h for ir uit design for au tions. In
Se .3,weprop ose abit-sli e ir uit forthehighest-pri eau tion. InSe .4,we
brie ydes rib ethemixandmat hte hnique. InSe .5,weshowanew
highest-pri e au tionproto olwhi h isobtainedby ombiningthebit sli e ir uit and
themix and mat h te hnique. InSe . 6, we present ourse ond-pri e au tion
proto ol.
2 Normal Approa h for Au tion Cir uit Design
Thenormalapproa h for ir uit designforau tions isto omparethebidding
pri es one by one (in other words, to run amillionaire's problemproto ol in
order). In this se tion, we present su h a ir uit whi h seems to b e the most
eÆ ient.
2.1 Primitive Gate
For twobitsxandy , de neBigger
1 and EQ 1 by Bigger 1 (x;y ) = 1 ifx>y 0 otherwise EQ 1 (x;y ) = 1 ifx=y 0 otherwise
Wenext de neagateSele t
whi hhas2+1inputbitsandoutputbits
asfollows. Sele t (b;x ( 1) ;:::;x (0) ;y ( 1) ;:::;y (0) )= (x ( 1) ;:::;x (0) ) ifb=1 (y ( 1) ;:::;y (0) ) ifb=0
2.2 Boolean Cir uit for the Millionaire's Problem
For X=(x (k 1) ;:::;x (0) ) 2 andY =(y (k 1) ;:::;y (0) ) 2 ,de ne Bigger k (X ;Y) = 1 ifX >Y 0 otherwise Max k (X ;Y) = X ifX >Y Y otherwise EQ k (X ;Y) = 1 ifX =Y 0 otherwise
k
k
whi hseemtob e themosteÆ ient.
Leta k =1. Fori=k 1to 1,do a i =a i+1 ^EQ 1 (x (i) ;y (i) ): Then Bigger k (X ;Y) = Bigger 1 (x (k 1) ;y (k 1) ) _(Bigger 1 (x (k 2) ;y (k 2) )^a k 1 ) . . . _(Bigger 1 (x (0) ;y (0) )^a 1 ): Max k (X ;Y) = Sele t k (Bigger k (X ;Y);X ;Y):
2.3 Boolean Cir uit for Au tion
Wenextpresenttwo ir uitsforthehighest-pri eau tion,HighestandWinner .
Highest outputsthe highest bidding pri e of m bids,B
1 ;:::;B
m
. It is
ob-tainedbyimplementingthefollowingalgorithmbya ir uit. LetB
max =0. For i=1;:::;m,do B max :=Max k (B max ;B i ):
Itis learthat the nalB
max
isthehighestbiddingpri e.
Winner isa ir uit whi houtputsthewinners. Thatis,
Winner (B 1 ;:::;B m )=(w 1 ;:::;w m ); where w i = 1 ifB i =B max 0 otherwise Ea h w i is obtainedasfollows. w i =EQ k (B i ;B max ):
Thesizesofthese ir uits willb egiveninSe .3.3.
3 Bit-Sli e Approa h
Inthisse tion,wepresentamoreeÆ ient ir uitthanthenormalapproa hby
usingabit-sli e approa hfor thehighest-pri e au tion. Supp ose that B
max = (b (k 1) max ;:::;b (0) max ) 2
isthehighest biddingpri e. Thentheprop osed ir uit rst
determinesb (k 1)
max
bylo okingatthemostsigni antbitsofallthebids. Itnext
determinesb (k 2)
max
bylo okingatthese ondmostsigni antbitsofallthebids,
andsoon.
Fortwom-dimensionalbinaryve torsX=(x
1 ;:::;x m )andY=(y 1 ;:::;y m ), de ne X^Y=(x 1 ^y 1 ;:::;x m ^y m ):
Ourideaisasfollows. LetD
j
b e thehighest pri e when onsideringtheupp er
j bitsofthebids. Thatis,
D 1 = (b (k 1) max ;0;0) 2 ; D 2 = (b (k 1) max ;b (k 2) max ;0;0) 2 ; et , D k =(b (k 1) max ;:::;b (0) max ) 2 =B max : Inthe rstround,we ndb (k 1) max
andtheneliminateallthebiddersA
i su hthat B i <D 1
. Inthese ondround,we ndb (k 2)
max
andtheneliminateallthebidders
A i su h that B i <D 2
, and so on. At the end, the remained bidders are the
winners. Forthatpurp ose, we up dateW=(w
1 ;:::;w m )su h that w i = 1 ifB i D j 0 otherwise forj=1tok .
Our ir uit isobtainedbyimplementingthefollowingalgorithm. Forgiven
mbids,B 1 ;:::;B m , de neV j as V j =(b (j) 1 ;:::;b (j) m )
forj =0;:::;k 1. That is, V
j
istheve tor onsisting ofthej+1thlowest
bitofea h bid.
LetW=(1;:::;1). Forj=k 1to0,do;
(Step1) ForW=(w 1 ;:::;w m ),let S j = W^V j = (w 1 ^b (j) 1 ;:::;w m ^b (j) m ); (1) b (j) max = (w 1 ^b (j) 1 )__(w m ^b (j) m ): (2) (Step2) Ifb (j) max =1,thenletW=S j .
Thenthehighest pri eis obtainedas B
max =(b (k 1) max ;:::;b (0) max ) 2
. Letthe nal
Wb e(w 1 ;:::;w m ). ThenA i
isawinnerifandonlyifw
i =1.
Were ordthis asthefollowingtheorem.
Theorem3.1 In theabove algorithm,
B
max
isthe highestbidding pri e.
Forthe nalW=(w
1 ;:::;w
m ),A
i
isawinnerifand only ifw
i =1.
Supp osethat m=4,k=5andea h bidis B 1 = 20=(1;0;1;0;0) 2 ; B 2 = 17=(0;1;1;1;1) 2 ; B 3 = 18=(1;0;0;1;0) 2 ; B 4 = 29=(1;1;1;0;1) 2 : ThenV 4 =(1;0;1;1),V 3
=(0;1;0;1)andet . LetW=(1;1;1;1).Now
1. S 4 =W^V 4 =(1;0;1;1),b (4) max =1andW:=S 4 =(1;0;1;1). 2. S 3 =W^V 3 =(0;0;0;1),b (3) max =1andW:=S 3 =(0;0;0;1). 3. S 2 =W^V 2 =(0;0;0;1),b (2) max =1andW:=S 2 =(0;0;0;1). 4. S 1 =W^V 1 =(0;0;0;0),b (1) max =0. 5. S 0 =W^V 0 =(0;0;0;1),b (0) max =1andW:=S 0 =(0;0;0;1).
Therefore, we obtain that the highest bidding pri e is (b (4) max ;:::;b (0) max ) 2 = (1;1;1;0;1) 2 =29andA 4 isthewinner.
3.3 Comparison of Cir uit Size
Inthis subse tion, we ompare the size of the normal ir uit shownin Se . 2
andthatofourbit-sli e ir uit forthehighest-pri e au tion. SeeTable1.
First the sizeof thenormal ir uit isgivenas follows. The ir uit Bigger
k
requiresk Bigger
1
gates, 2(k 1) AND gates,k 1ORgates and k 1EQ
1
gates. The ir uit Max
k
requiresone Sele t
k
gateand oneBigger
k
ir uit. The
ir uit Highestis obtainedbyimplementingmMax
k
ir uits. Inaddition,the
ir uitWinner requiresmEQ
k gates, whereanEQ k gate isimplementedbyk EQ 1
gatesand(k 1)ANDgates.
Therefore, the normal ir uits for the highest-pri e au tion, Highest and
Winner ,requiremk Bigger
1
gates,3m(k 1) ANDgates, m(k 1)ORgates,
m(2k 1) EQ
1
gatesand mSele t
k
gatesintotal.
Nextourbitsli e ir uitisgivenbyimplementingEq.(1)andEq.(2)ktimes.
Therefore,itrequiresmkANDgatesand(m 1)k ORgates.
Hen eroughlysp eaking,theprop osed ir uitrequiresonly2mklogi algates
whilethenormal ir uit requires7mk logi algatesand mSele t
k gates.
4 MIX and Mat h Proto ol
4.1 Overview
Inthisse tion, we brie ydes rib e themixandmat hte hniqueintro du ed by
AND OR Bigger 1 EQ 1 Sele t k Normal ir uit 3m(k 1) m(k 1) mk m(2k 1) m Bit-sli e ir uit mk (m 1)k 0 0 0
VSS.Instead,itusesahomomorphi en ryptions heme(forexample,ElGamal)
andaMIX net[8,1,2℄.
Thismo delinvolvesnplayers, denoted byP
1 ;P
2 ;:::;P
n
andassumesthat
thereexists apubli b oard. We onsideran adversary whomay orrupt upto
tplayers, wheren2t+1.
Theplayersagreeinadvan eonarepresentationofthetargetfun tionf as
a ir uit C
f
. Supp ose that C
f
onsists of N gates, G
1 ;:::;G
N
. Lettheinput
ofP
i
b e ak -bitinteger B
i
. Theaimof theproto olisfor players to ompute
f(B
1 ;:::;B
n
)withoutrevealinganyadditionalinformation. Itgo esasfollows.
Inputstage: Ea h P
i
omputes iphertexts ofthe bits of B
i
and broad asts
them. Sheprovesthatea h iphertextrepresents0or1inzero-knowledge
byusingthete hniqueof[11℄.
Mix andMat h stage: Theplayersblindlyevaluatesea hgate G
j
inorder.
Outputstage: After evaluating the last gate G
N
, the players obtain o
N , a iphertexten ryptingf(B 1 ;:::;B n
). Theyjointlyde ryptthis iphertext
valueto revealtheoutputofthefun tionf.
Thisproto olmeets these urityrequirementsformalizedbyCanetti [7℄for
se ure multipartyproto ols [20, page 171℄. The ostof ea h player is O (nN)
exp onentiationsandtheoverallmessage omplexityisalsoO (nN)(see[20,page
172℄).
Thedetailsoftheproto olaredes rib ed inthefollowingsubse tions.
4.2 Requirements for the En ryption Fun tion
LetEb eapubli -keyprobabilisti en ryptionfun tion. WedenotebyE(m)the
setofen ryptionsforaplaintextmandbye2E(m)aparti ularen ryptionof
m. Wesaythateisastandarden ryptionifitisen ryptedwithnorandomness.
E mustsatisfythefollowingprop erties.
homomorphi prop erty
There existsap olynomialtime omputableop erations, 1
and ,as
fol-lowsforalargeprimeq .
1. Ife2E(m),thene 1 2E( mmo dq ). 2. Ife 1 2E(m 1 )ande 2 2E(m 2 ),thene 1 e 2 2E(m 1 +m 2 mo dq ).
ae=eee
| {z }
a
:
randomre-en ryptability
Given e 2 E(m), there is a probabilisti re-en ryption algorithm that
outputse 0
2E(m),wheree 0
isuniformlydistributed overE(m).
thresholdde ryption
For a given iphertext e 2 E(m), any t out of n players an de rypt e
alongwithazero-knowledgepro ofofthe orre tness. However,anyt 1
outofnplayers annotde rypte.
Su hE() anb eobtainedbyslightlymo difyingElGamalen ryptions heme
overagroupGoforderjGj=q ,whereqisalargeprime. G anb e onstru ted
as a subgroup of Z
p
, where p is aprime su h that q j p 1. It an also b e
obtainedfromellipti urves.
Letgb eageneratorofG,i.e. G=hg i. These retkeyxisrandomly hosen
fromZ
q
andthepubli keyisy=g x . An en ryptionofmisgivenby (g r ;g m y r )2E(m); wherer2Z q
isarandomelement. For iphertexts,de ne 1 andas (u;v ) 1 =(u 1 ;v 1 ): (u 1 ;v 1 )(u 2 ;v 2 )=(u 1 u 2 ;v 1 v 2 ):
Then it is easy to see that the homomorphi prop erty is satis ed. A
re-en ryption of (u;v ) 2 E(m) is given by (u 0 ;v 0 ) = (g r 0 u;y r 0 v ) for a random elementr 0 2Z q .
For threshold de ryption, ea h player obtains a private share x
i
of x in
Shamir's(t+1;n)-threshold se ret-sharing s heme[24℄. Ea hg xi
ispublished.
For details, see [12, 15℄. Ea h player needs to broad ast O (1) messages and
omputeO (n) exp onentiationsinthresholdde ryption.
4.3 MIX Proto ol
AMIXproto oltakesalistof iphertexts (
1 ;:::;
L
)andoutputsap ermuted
and re-en rypted list of the iphertexts ( 0
1 ;:::;
0
L
) without revealingthe
re-lationshipb etween ( 1 ;:::; L ) and( 0 1 ;:::; 0 L ), where i or 0 i anb e asingle
iphertexte, or alist ofl iphertexts,(e
1 ;:::;e
l
),for somel >1. We further
require that anyb o dy(even anoutsider) an verify thevalidityof ( 0 1 ;:::; 0 L ) (publi veri ability).
ForsmallL,aMIXproto oliseÆ ientlyimplementedasshownin[1,2,19℄.
Inthisproto ol,ea hplayerneedsto omputeO (nl LlogL)exp onentiationsand
x 1 x 2 x 1 ^x 2 a 1 2E(0) b 1 2E(0) 1 2E(0) a 2 2E(0) b 2 2E(1) 2 2E(0) a 3 2E(1) b 3 2E(0) 3 2E(0) a 4 2E(1) b 4 2E(1) 4 2E(1)
4.4 Plaintext Equality Test
Given two iphertexts e
1 2 E(m 1 ) and e 2 2 E(m 2
), this proto ol he ks if
m 1 =m 2 . Lete 0 =e 1 e 1 2 .
(Step1) Forea h playerP
i
(wherei=1;:::;n):
P
i
ho oses a random element a
i 2 Z q and omputes z i = a i e 0 . He broad astsz i
andprovesthevalidityof z
i inzero-knowledge. (Step2) Letz=z 1 z 2 z n
. Theplayersjointlyde ryptzbythreshold
veri ablede ryptionandobtaintheplaintextm.
Thenitholdsthat
m = 0 if m 1 =m 2 ; r andom otherwise (3)
This proto ol is minimalknowledge under the DDH assumption(see [20,
page169℄). The ostofea h playerisO (n) exp onentiations.
4.5 Mix and Mat h Stage
For ea h logi al gate G(x
1 ;x
2
) of a given ir uit, n players jointly omputes
E(G(x 1 ;x 2 )) frome 1 2 E(x 1 )and e 2 2 E(x 2 ) keeping x 1 and x 2 se ret. For
simpli ity,we showamixandmat hstageforAND.
1. nplayers rst onsiderthestandard en ryptionofea hentry ofTable2.
2. ByapplyingaMIXproto oltothefourrowsofTable2,nplayersjointly
ompute blinded and p ermuted rows of Table 2. Let the ith row b e
(a 0 i ;b 0 i ; 0 i )for i=1;:::;4.
3. nplayersnext jointly ndtherowisu hthat theplaintextofe
1
isequal
to that of a 0
i
and the plaintext of e
2
is equal to that of b 0
i
by using the
plaintextequalitytestproto ol.
4. Forthisi,itholdsthat 0 i 2E(x 1 ^x 2 ).
5.1 Overview
We an obtainahighest-pri eau tionproto olby ombiningtheprop osed
ir- uit of Se . 3.1 with any general multipartyproto ol. Then a more eÆ ient
proto olisobtainedb e ause thebit-sli e ir uitis moreeÆ ient thanthe
nor-mal ir uitasshowninTable1.
Inthis se tion,weshowa ombinationwith themixandmat h te hnique,
as an example. In this ase, we an further improve the eÆ ien y. That is,
we an remove allthe OR omputationsof Eq.(2) by using thehomomorphi
prop erty oftheen ryptionfun tionas follows.Let
h j =(x 1 ^b (j) 1 )++(x m ^b (j) m ):
Thenitiseasyto seethat h
j
=0ifandonlyifb (j)
max
=0. Therefore,nservers
have only to exe ute a plaintext equality test proto ol for he king if h
j = 0
to de ide if b (j)
max
=0. Note that ea h server an omputesummation lo ally
by using the homomorphi prop erty of theen ryption s heme. Hen e we an
repla e(m 1)k OR omputationswithonlykplaintextequalitytests.
5.2 Bidding Phase
Ea h bidderA
i
omputesa iphertextof herbiddingpri e B
i as ENC i =(e i;k 1 ;:::;e i;0 ); where e i;j 2 E(b (j) i
), and submits ENC
i
. She also proves in zero-knowledge
thatb (j)
i
=0or1byusingthete hniqueof[11℄. (Thissubmissionmayb ealso
digitallysignedbyA
i .)
5.3 Opening Phase
Supp ose that e
1 2 E(b i ) and e 2 2 E(b 2 ), where b 1 and b 2
are binary. Let
Mul(e
1 ;e
2
)denote aproto olwhi houtputs
e2E(b
1 ^b
2 )
byapplyingamixand mat hproto olforAND.
Let f W=(w~ 1 ;:::;w~ m ),whereea hw~ j
2E(1)isthestandard en ryption.
(Step1) Forj=k 1to 0,do: (Step1-a) For f W=(w~ 1 ;:::;w~ m
),nservers jointly ompute
e S j =(Mul(w~ 1 ;e 1;j );:::;Mul(w~ m ;e m;j )):
AND OR Bigger 1 EQ 1 Sele t k JJ [20℄ 3m(k 1) m(k 1) mk m(2k 1) m Prop osed mk 0 0 0 0
(Step1-b) Ea hserver lo ally omputes
h j =Mul(w~ 1 ;e 1;j )Mul(w~ m ;e m;j ):
(Step1- ) n servers jointly he k if h
j
2 E(0) by using aplaintextequality
test. Let b (j) max = 0 ifh j 2E(0) 1 otherwise (Step1-d) Ifb (j) max =1,then let f W= e S j .
(Step2) Forthe nal f
W=(w~
1 ;:::;w~
m
),nserversjointlyde ryptea hw~
i by
threshold veri able de ryptionandobtaintheplaintextw
i .
Thehighest pri eis obtainedas B
max =(b (k 1) max ;:::;b (0) max ) 2 . A i is awinner ifandonlyifw i =1. 5.4 Comparison
If we ombine the normal ir uit with the mixand mat hte hnique, then JJ
au tion proto ol is obtained [20℄. Table 3 shows the omparison b etween JJ
au tionproto olandprop osed proto ol.
Inourproto ol,we anrepla e (m 1)kOR omputationsof Table1with
only k plaintext equality tests as shown inSe . 5.1. Therefore, our proto ol
requiresmkAND omputationsandk plaintextequalitytests.
We omit the ost of k plaintext equality tests in this table b e ause it is
mu hsmallerthan the ostfor ea h logi algate. For example, anAND
om-putationrequires8plaintextequalitytestsandaMIXproto oloffour itemsif
we implementtheproto olofSe .4.5. Hen e mkAND omputationsrequires
8mkplaintextequalitytestsandmkMIXproto olsoffouritems.Thisismu h
largerthanthe ostofk plaintextequalitytests.
Nowroughlysp eaking,ourproto olrequiresmk logi algates whileJJ
au -tionproto olrequires 7mk logi algates and mSele t
k
ir uit. Therefore,our
proto olisat leastseven timesfaster thanJJ au tionproto ol.
5.5 Dis ussion
We anslightlyimprovetheop eningphase bylettingtheinitialvalueof f Wb e f W=(e 1;k 1 ;;e m;k 1 ):
TheeÆ ien yisfurtherimprovedifea hbidisonlyk <kbitslong.(Of ourse,
this fa t is not known inadvan e.) The smallerk 0
is, thefaster themo di ed
versionis. Forexample,ifB
i
=(0;:::;0;b (0)
i
)foralli,thennomixandmat h
for AND is required. If B
i = (0;:::;0;b (1) i ;b (0) i
) for all i, then the mix and
mat hforANDis exe utedonlyon e,and soon.
Su hsp eed-up isimp ossibleinJJau tion proto ol.
6 Se ond-Pri e Au tion
Inthese ond-pri eau tion(alsoknownasVi kreyau tion),thehighestbidder
wins, and the learing pri e, thepri e that thewinner hasto pay, is equalto
these ondhighest bid. Therefore,Vi kreyau tions aremu h losertothereal
lifeau tionthanthehighest-pri eau tions. A ryptographi allyse ure
se ond-pri eau tions hemeshouldrevealonlytheidentitiesofthewinners(thehighest
bidders)andthese ond-highest bid.
In this se tion, we show that a se ond-pri e au tion proto ol is easily
ob-tainedfromourbit-sli e ir uitforthehighest-pri eau tion.
6.1 Normal Approa h Cir uit
If we use the normal approa h, we an obtain a se ond-pri e au tion ir uit
by keeping tra k of thetwohighest bidsfound so far, B
rst and B se ond , as follows. LetB rst =B se ond =0. Fori=1;:::;m,do X := Sele t k (Bigger k (B se ond ;B i );B se ond ;B i ): B se ond := Sele t k (Bigger k (B rst ;X);X ;B rst ): B rst := Sele t k (Bigger k (B rst ;X);B rst ;X):
Itis easyto see that the nalB
rst
is thehighest biddingpri e and B
se ond
isthese ond-highest pri e. Theidentitiesofthewinnersareobtainedsimilarly
toSe .2.3.
6.2 Bit-Sli e-Type Se ond-Pri e Au tion
We de ne two typ es of highest-pri e au tion s hemes, a winner-only s heme
and apri e-only s heme. A winner-only s heme reveals only the identities of
the winners, but not the highest pri e. A pri e-only s heme reveals only the
highestbid,but nottheidentitiesofthewinners.
Nowsupp osethatthereisawinner-onlys hemeQ
1
andapri e-onlys heme
Q
2
. Thenwe anobtainase ond-pri e au tions hemeas follows:
Step1. RunQ
1 .
Step2. DeletethewinnersofQ
1
2
Indeed, the ab ove s heme reveals only the identities of the winners of Q
1 ,
andthehighestbiddingpri eofQ
2
whi histhese ondhighestpri eamongthe
bidders.
Su h proto ols Q
1 andQ
2
are easily obtainedfromourbit-sli e ir uit for
thehighest-pri e au tionasfollows.
Applyanymultipartyproto oltothe ir uit ofSe .3.1andde ryptonly
b (k 1) max ;:::;b (0) max
(butnotW )intheoutputstage. Thenweobtaina
pri e-onlys heme.
Inthe ir uitofSe .3.1,repla e Step2with
W=Sele t m (b (j) max ;S j ;W ): (4)
Thenapplyanymultipartyproto oltotheab ove ir uitandde ryptonly
W(butnotb (k 1) max ;:::;b (0) max
)intheoutputstage. Wenowobtaina
winner-onlys heme.
6.3 Comparison
Table 4shows the omparisonof the sizes of the normalse ond-pri e au tion
ir uitandthebit-sli e ir uit.
Thesize ofthenormal ir uit isgivenas follows(see Se .6.1). The ir uit
whi h omputesthe se ond-highestbid, showninSe .6.1,requires3mSele t
k
gates and 2m Bigger
k
ir uits, where the ir uit Bigger
k
requires k Bigger
1
gates,2(k 1)ANDgates,k 1ORgatesandk 1EQ
1
gatesasmentionedin
se tion3.3.The ir uitwhi h omputesWinner ,as showninSe .2.3,requires
mkEQ
1
gatesandm(k 1)ANDgates. Therefore,thenormal ir uitsforthe
se ond-pri eau tionrequire2mkBigger
1
gates,5m(k 1)ANDgates,2m(k 1)
ORgates, m(3k 2)EQ
1
gatesand3mSele t
k
gates intotal.
Next our bit sli e ir uit onsists of the winner-only s heme Q
1 and the pri e-only s heme Q 2 . Q 1
is obtained by implementing Eq.(1), (2) and (4)
k times. Q
2
is obtained by implementingEq.(1) and (2) k times for m 1
bidders. Therefore, ourse ond-pri e au tion ir uit requires (2m 1)k AND
gates,(2m 3)kORgatesandkSele t
m gates.
Table4: Comparisonof these ond-pri e au tion ir uits
AND OR Bigger 1 EQ 1 Sele t k Sele t m Normal 5m(k 1) 2m(k 1) 2mk m(3k 2) 3m 0 Bitsli e (2m 1)k (2m 3)k 0 0 0 k
Next,supp osethatwe usethemixandmat hte hniqueasageneral
multi-partyproto ol. Inthis ase,thepri e-onlys hemeisobtainedbydeletingStep2
m
au tion proto ol obtained by ombining the normal ir uit and the mix and
mat hte hniquerequires11mklogi algatesand 3mSele t
k
gates. Weshowa
omparisoninTable5.
Table5: Comparisonofthese ond-pri eau tionproto ols
AND OR Bigger 1 EQ 1 Sele t k Sele t m Normal 5m(k 1) 2m(k 1) 2mk m(3k 2) 3m 0 Bitsli e (2m 1)k (m 2)k 0 0 0 k 7 Con lusion
Inthis pap er, we intro du ed abit-sli eapproa h for au tionsand presented a
moreeÆ ient ir uit than the normal approa h for the highest-pri e au tion.
Esp e ially, if we ombine our ir uit with themix and mat h te hnique, then
we an obtainanau tionproto olwhi his atleast seven timesfaster thanJJ
au tionproto ol.
Wealsoshowedthat ase ond-pri e au tionproto ol(whi h is loser to the
real-lifeau tionthanthehighest-pri eau tion) anb eeasilyobtainedfromour
bit-sli e ir uit forthehighest-pri e au tion.
Supp osethattherearewwinnerssu hthatw2. Thenour ir uitsreveals
the indetitiesof all the winners. However, there are some ases su h that we
must sele t just one winner randomly. It willb e afurther work to design an
eÆ ient ir uitor aproto olwhi h implementssu h anau tion.
A knowledgement
TheauthorsthankMartinHirtforprovidingmanyuseful omments.
Referen es
[1℄ M.Ab e,\Mix-Networksonp ermutationnetworks,"Pro .ofAsia rypt'99,
LNCSVol.1716,pp.258{273(1999).
[2℄ M.Ab eandF.Hoshino,\RemarksonMix-NetworkBasedonPermutation
Networks,"Pro .ofPKC2001,pp.317{324(2001).
[3℄ M.Ab eandK.Suzuki,\M1-stPri eAu tionUsingHomomorphi
En ryp-tion,"Pro .ofPKC2002,pp.115{124(2002).
[4℄ O. Baudron and J. Stern, \Non-Intera tive Private Au tions," Pro . of
non- ryptographi fault-tolerantdistributed omputation,"Pro eedings of
thetwentiethannualACMSymp.TheoryofComputing,STOC,pp.1{10,
May2{4(1988).
[6℄ C. Ca hin,\EÆ ient privatebiddingand au tionswithanobliviousthird
party,"ACM CSS'99,pp.120{127,ACM(1999).
[7℄ R. Canetti,\Se urityand omp ositionof multiparty ryptographi
proto- ols,"Journal ofCryptology,Vol.13,No.1,pp.143{202(2000).
[8℄ D. Chaum, \Untra eable ele troni mail, return addresses, and digital
pseudonyms,"Communi ationsoftheACM,Vol.24,pp.84{88(1981).
[9℄ D.Chaum,C. Crep eau, andI.Damgard.\Multiparty un onditionally
se- ureproto ols,"Pro .ofthetwentiethannualACMSymp.Theoryof
Com-puting,STOC,pp.11{19,May2{4(1988).
[10℄ R. Cramer, I. Damgard, and J. B. Nielsen, \Multiparty Computation
fromThresholdHomomorphi En ryption,"Pro .ofEuro rypt'01,LNCS
Vol.2045,pp.280{300(2001).
[11℄ R.Cramer,I.Damgard,andB.S ho enmakers,\Pro ofsofpartialknowledge
and simpli eddesignofwitness hidingproto ols,"Pro .of CRYPTO'94.
LNCSVol.839,pp.174{187(1994).
[12℄ Y. Desmedt and Y. Frankel, \Threshold ryptosystems," In Pro . of
Crypto '89,pp.307{315.
[13℄ G.DiCres enzo, \Privatesele tivepaymentproto ols,"InPro .of
Finan- ialCryptography'00,LNCSVol.1962,pp.72{89(2000).
[14℄ M. Franklin andM. Reiter, \TheDesignand Implementationof aSe ure
Au tion Servi e," IEEE Trans. on Software Engineering, Vol. 22, No. 5
(1996).
[15℄ R. Gennaro, S. Jare ki, H. Kraw zyk, and T. Rabin, \Robust threshold
DSS signatures," InPro ofEuro rypt '96,LNCSVol.1070,pp.354{371
(1996).
[16℄ O.Goldrei h,S.Mi ali,andA.Wigderson.\Howtoplayanymentalgame,"
InPro eedingsofthenineteenthannualACMSymp.TheoryofComputing,
STOC,pp.218{229,May25{27(1987).
[17℄ M. Hirt, U. Maurer,and B.Przydatek, \EÆ ientse ure multiparty
om-putation,"Pro .ofAsia rypt'2000,LNCSVol.1976,pp.143{161(2000).
[18℄ M.Harkavy,J.D.Tygar,andH.Kiku hi,\Ele troni au tionwithprivate
bids,"InThird USENIXWorkshoponEle troni Commer ePro eedings,
Te hni alrep ort99-33(June 1999).
[20℄ M.JakobssonandA. Juels,\MixandMat h: Se ureFun tionEvaluation
viaCiphertexts,"InPro .ofAsia rypt2000,LNCSVol.1976,pp.162{177
(2000).
[21℄ A. Juels andM. Szydlo, \An Two-Server Au tion Proto ol," InPro . of
Finan ialCryptography2002,(2002).
[22℄ M. Naor, B. Pinkas, and R. Sumner, \Priva y preserving au tions and
me hanism design," In 1st ACM Conferen e on Ele troni Commer e,
pp.129{140,ACM (1999).
[23℄ K. Sako, \An au tion proto ol whi h hides bids of losers," Pro . of
PKC'2000,LNCSVol.1751,pp.422{432(2000).
[24℄ A.Shamir,\HowtoShareaSe ret,"Communi ationsoftheACM,Vol.22,
pp.612-613(1979).
[25℄ A. Yao,\Proto olsforse ure omputations(extendedabstra t),"Pro .of
