**Secure Sealed-Bid
Online Auctions Using Discreet Cryptographic Proofs **

Jose A. Montenegro and Rene Peralta (Advisor)

A secure multiparty computation (SMC) is a type of communication protocol that allows a set of participants to agree on the value of a public function of their private data without disclosing the data itself. For example, the data can be voter’s choices of candidate in an election and the value of the target function could be the winner. There are several generic solutions to SMC, but these tend to yield solutions that, although of polynomial complexity, are not practical. One such generic solution uses so-called “discreet cryptographic proofs” (DCP). These proofs are “discreet” in the sense that participants do not reveal private information.

The main objective of this research is to show that DCPs can be used in practice even for fairly complex target functions. For this purpose, we have chosen to implement online sealed-bid Vickrey auctions. In these auctions the winner is the bidder with the highest bid. The price paid, however, is the value of the second highest bid. The “discreetness” property sought is that the winning bid and sale price can be computed without the losing bids becoming known to anybody (not even the auctioneer). Among the performance goal is to use small amount of scarce resources such as bandwidth, total number of bits communicated, computation time, memory use, randomness, and interaction (protocols with many rounds of communication are less practical than those with fewer rounds).

Our measurements show that DCPs are practical. Because of the generality of the DCP method, our research opens the way for a large number of internet applications in commerce and government (elections, secure management of distributed health records, fair and secure procurement practices, etc.) as well as in the area of national security.

Jose A. Montenegro

montes@nist.gov

(Advisor: Rene Peralta)

Security Technology - Computer Security Division

Information Technology Laboratory

National Institute of Standards and Technology

100 Bureau Drive, Mail Stop 8920

Building 220, Room B352

Gaithersburg, MD 20899-8920

Tel: (301) 975-4391

Fax: (301) 975-8670

Sigma Xi membership: No

Category: Engineering