Second price auctions: a case study of secure distributed computing

Ref: Bart De Decker, Gregory Neven, Frank Piessens and Erik Van Hoeymissen. In K. Zielinski, K. Geihs and A. Laurentowski, editors, New Developments in Distributed Applications and Interoperable Systems, IFIP TC6 / WG6.1 Third International Working Conference on Distributed Applications and Interoperable Systems, volume 198 of IFIP Conference Proceedings, pages 217-228. Kluwer Academic Publishers, 2001.

Abstract: Secure distributed computing addresses the problem of performing a computation with a number of mutually distrustful participants, in such a way that each of the participants, in such a way that each of the participants has only limited access to the information needed for doing the computation. Over the past two decades, a number of solutions requiring no trusted third party have been developed using cryptographic techniques. The disadvantage of these cryptographic solutions is the excessive communication overhead they incur.

In this paper, we use one of the SDC protocols for one particular application: second price auctions, in which the highest bidder acquires the item for sale at the price of the second highest bidder. The protocol assures that only the name of the highest bidder and the amount of the second highest bid are revealed. All other information is kept secret (the amount of the highest bid, the name of the second highest bidder,...). Although second price auctions may not seem very important, small variations on this theme are used by many public institutions: e.g., a call for tenders, where the contract is given to the lowest offer (or the second lowest).

The case study serves two purposes: we show that SDC protocols can be used for these kind of applications, and secondly, we assess the network overhead and how well these applications scale. To overcome the communication overhead, we use mobile agents and semi-trusted hosts.

PS | PDF | Powerpoint presentation