Practical secrecy-preserving, verifiably correct and trustworthy auctions

Abstract

A system and method for conducting verifiably correct auctions that preserves the secrecy of the bids while providing for verifiable correctness and trustworthiness of the auction is disclosed. Some of the elements of the method and apparatus are that the auction operator accepts all bids submitted and follows the published rules of the auction. In one embodiment, the bids are maintained secret from the auctioneer and all bidders until the auction closes and no bidder is able to change or repudiate her bid. In another embodiment, the auction operator computes the auction results and publishes proofs of the results' correctness. In yet another embodiment, any party can check these proofs of correctness via publicly verifiable to computations on encrypted bids.

1 . A computer implemented method for conducting a verifiably correct auction, the method comprising the acts of:
 receiving encrypted bid information from a plurality of bidders, wherein the encrypted bid information includes a bid amount encrypted using a published encryption key;   decrypting, by the auction server, the encrypted bid information to obtain the corresponding bid amounts;   determining, by the auction server, an outcome of the auction according to the bid amounts, wherein the act of determining the outcome of the auction includes determining one or more winning bids;   generating proof information by the auction server for verifying the correctness of the auction, wherein the proof information verifies the outcome of the auction without revealing at least one of the decrypted bid amounts;   communicating the proof information, wherein the act of communicating the proof information includes an act of communicating data used to generate at least a portion of the proof information.   
     
     
         2 . The method according to  claim 1 , further comprising acts of:
 closing the auction to bidding; and   receiving, by the auction server, before the auction is closed, a bid commitment binding at least one bidder to the encrypted bid information.   
     
     
         3 . The method according to  claim 2 , further comprising an act of receiving, by the auction server, information verifying the correspondence between the bid commitment and the encrypted bid information. 
     
     
         4 . The method according to  claim 3 , further comprising an act of receiving, by the auction server, a digital signature from at least one bidder proving that the encrypted bid information received from the bidder was generated by the bidder. 
     
     
         5 . The method according to  claim 1 , wherein the act of communicating the proof information includes an act of communicating an encrypted bid received as part of the encrypted bid information. 
     
     
         6 . The method according to  claim 1 , wherein the act of communicating the proof information includes an act of communicating the proof information to a publication service. 
     
     
         7 . The method according to  claim 6 , wherein the publication service includes a bulletin board accessible over a communication network. 
     
     
         8 . The method according to  claim 1 , wherein the step of determining the outcome includes ordering by the auction server the received encrypted bid information by respective bid amount. 
     
     
         9 . The method according to  claim 2 , wherein the encrypted bid information includes a digitally signed bid commitment, and the method further comprises an act of communicating encrypted bid information corresponding to the digitally signed bid commitment. 
     
     
         10 . The method according to  claim 3 , wherein the bid commitment includes a cryptographic commitment, wherein the cryptographic commitment is generated using at least the published encryption key and a help value. 
     
     
         11 . The method according to  claim 3 , wherein the bid commitment further comprises a bid and auction identifier and at least one of a cryptographic commitment and a cryptographic commitment generated from a random string. 
     
     
         12 . The method according to  claim 1 , further comprising an act of providing for the bidder to submit the encrypted bid information to a bulletin board. 
     
     
         13 . The method according to  claim 1 , further comprising the acts of:
 providing an additional encryption key through an encryption key revelation service;   providing for the bidder to generate an encrypted bid using the published encryption key and a help value; and   providing for the bidder to encrypt the encrypted bid using the additional encryption key.   
     
     
         14 . The method according to  claim 1 , further comprising the act of preventing the auction server from decrypting encrypted bid information prior to close of bidding. 
     
     
         15 . A system for conducting a verifiably correct auction, the system comprising:
 at least one processor operatively connected to a memory configured to conduct the verifiably correct auction, wherein the system is configured to:   receive encrypted bid information from a plurality of bidders, wherein the encrypted bid information includes a bid amount encrypted using a published encryption key;   decrypt the encrypted bid information to obtain the corresponding bid amounts;   determine an outcome of the auction according to the decrypted bid amounts, wherein the act of determining the outcome of the auction includes determining one or more winning bids;   generate proof information for verifying the correctness of the auction, wherein the proof information verifies the outcome of the auction without revealing at least one of the decrypted bid amounts;   communicate the proof information, wherein the act of communicating the proof information includes an act of communicating data used to generate at least a portion of the proof information.   
     
     
         16 . The system according to  claim 15 , wherein the system is further configured to order the received encrypted bid information by respective bid amount. 
     
     
         17 . The system according to  claim 15 , wherein the system is further configured to:
 close the auction to bidding; and   receive before the auction is closed a bid commitment binding at least one bidder to the encrypted bid information.   
     
     
         18 . The system according to  claim 15 , wherein the system is further configured to communicate an encrypted bid received from a bidder as part of the proof information. 
     
     
         19 . The system according to  claim 15 , wherein the encrypted bid information includes a digitally signed bid commitment and the system is further configured to communicate encrypted bid information corresponding to the digitally signed bid commitment. 
     
     
         20 . A non-transient computer-readable medium having computer-readable instructions that, as a result of being executed by a computer, instruct the computer to perform a method for conducting a verifiably correct auction, the method comprising the acts of:
 receiving encrypted bid information from a plurality of bidders, wherein the encrypted bid information includes a bid amount encrypted using a published encryption key;   decrypting the encrypted bid information to obtain the corresponding bid amounts;   determining an outcome of the auction according to the decrypted bid amounts, wherein the act of determining the outcome of the auction includes determining one or more winning bids;   generating proof information by the auction server for verifying the correctness of the auction, wherein the proof information verifies the outcome of the auction without revealing at least one of the decrypted bid amounts;   communicating the proof information, wherein the act of communicating the proof information includes an act of communicating data used to generate at least a portion of the proof information.