A Cryptographically t-Private Auction System

We present a feasible cryptographically t-private protocol for electronic auctions. Our construction is based on Yao's garbled circuits and pseudorandom number generators (PRNG). 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 simple primitives (XOR, permuting and sharing). Independently from each other, the bidders have to stay active for one round of communication. Furthermore, each bidder has to compute t+1 XOR-operations, only. 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.