Premium
A cryptographically t ‐private auction system
Author(s) -
Hinkelmann Markus,
Jakoby Andreas,
Moebius Nina,
Rompf Tiark,
Stechert Peer
Publication year - 2010
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.1684
Subject(s) - pseudorandom number generator , computer science , protocol (science) , common value auction , finite field , field (mathematics) , computation , discrete mathematics , theoretical computer science , mathematics , algorithm , statistics , alternative medicine , pathology , pure mathematics , medicine
We present a cryptographically t ‐private protocol for electronic auctions whose low resource demands make it viable for practical use. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNGs). Our protocol involves a field of ( t + 1) 2 parties for the generation of the garbled circuit and permits an arbitrary large number of bidders. The computational requirements are low: Only t + 1 parties of the field have to use the PRNG, the remaining parties execute only primitive computations (XOR, permutations and sharing). The bidders have to stay active for one round of communication, independent of each other. Each bidder has to compute only t + 1 XOR‐operations. We present an implementation and evaluate its performance. The observed running time of our protocol is linear in the size of the auction circuit and the number of bidders and, as expected, grows quadratically in the parameter t . Copyright © 2010 John Wiley & Sons, Ltd.