Auction verification

Abstract

An auction verification subsystem provides verification, without revealing actual bid values, that bid values remained sealed prior to a closing time for the auction and that an announced winning bidder for the auction provided a highest bid. The verification subsystem receives encrypted bids from bidders and generates commitment data based on the bids and provides the commitment data to each of the bidders. In response to receiving the commitment data, the bidders provide decryption keys for the encrypted bids. In turn, the bids are decrypted and an auction is performed using the decrypted bids. The results of the auction can be verified based on bid representations that do not reveal the actual values of bids, thereby maintaining the secrecy of bids. Providing access to an exchange between bidders and the verification subsystem facilitates verification that the auction is performed as a sealed bid auction.

1 . A computer-implemented method, comprising:
 receiving auction results for a sealed bid auction, the auction results specifying bids that were used in the sealed bid auction;   generating bid representations for bids, the bid representations including seed bid representations generated based on a seed value and additional bid representations that are generated independent of the seed value;   receiving a consistency verification request that includes a request for verification that the additional bid representations are value consistent with the seed bid representations; and   providing consistency verification data for verifying that the additional bid representations are value consistent with the seed bid representations.   
     
     
         2 . The method of  claim 1 , wherein providing consistency verification data comprises:
 generating an additional bid representation and a seed bid representation;   providing the additional bid representation and the seed bid representation;   generating decryption keys for the additional bid representation and the seed bid representation.   providing the decryption keys that reveal a value component of the additional bid representation and the seed bid representation;   generating a verification factor being a value that satisfies a value consistency relationship for the component values of bid representations that represent a same bid value; and   providing the verification factor.   
     
     
         3 . The method of  claim 1 , wherein generating bid representations comprises:
 receiving a bid seed value from a bidder, the bid seed value specifying a value for initializing a pseudorandom number generator;   generating the seed bid representation based on a number from the pseudorandom number generator, each seed bid representation being a two value component representation of a bid;   generating first encryption keys based on an encryption seed specifying a value for initializing a pseudorandom number generator; and   encrypting each value component of the seed bid representations based on the first encryption keys.   
     
     
         4 . The method of  claim 3 , further comprising:
 generating additional bid representations independent of the bid seed value, each additional bid representation being a two value component representation of the bid;   generating second encryption keys independent of the encryption key; and   encrypting each value component of the additional bid representations based on the second encryption keys.   
     
     
         5 . A system, comprising:
 an advertisement management system including at least one processor operable to perform an auction based on a set of sealed bids; and   a verification subsystem coupled to the advertisement management system, the verification subsystem including at least one processor operable to generate and provide seed bid representations and additional bid representations for the sealed bids and further operable to generate and provide consistency verification data that verifies that the additional bid representations are value consistent with the seed bid representations, the seed bid representations being generated based on bid seed values, the additional bid representations being generated independent of the bid seed values.   
     
     
         6 . The system of  claim 5 , wherein the consistency verification data comprises:
 decryption keys that reveal a value component of the additional bid representation and the seed bid representation; and   a verification factor having a value that satisfies a value consistency relationship for the component values of bid representations that represent a same bid value.   
     
     
         7 . The system of  claim 6 , wherein the seed bid representations and the additional bid representations are two value component representations of bids. 
     
     
         8 . The system of  claim 5 , wherein each of the bid seed values is a value that initializes a pseudorandom number generator that generates a number with which the seed bid representations of a bid corresponding to the bid seed value are generated. 
     
     
         9 . The system of  claim 5 , wherein the verification subsystem is further operable to generate first encryption keys for the seed bid representations and second encryption keys for the additional bid representations, the first encryption keys being based on an encryption seed that initializes a pseudorandom number generator, the second encryption keys being independent of the encryption seed. 
     
     
         10 . A computer readable medium encoded with a computer program comprising instructions that when executed operate to cause a computer to perform operations:
 receiving auction results for a sealed bid auction, the auction results specifying bids that were used in the sealed bid auction;   generating bid representations for bids, the bid representations including seed bid representations generated based on a seed value and additional bid representations that are generated independent of the seed value;   receiving a consistency verification request that includes a request for verification that the additional bid representations are value consistent with the seed bid representations; and   providing consistency verification data for verifying that the additional bid representations are value consistent with the seed bid representations.   
     
     
         11 . A device, comprising:
 means for generating additional bid representations for bids of a sealed bid auction, each bid representation being a vector of at least two value components, a modular sum of which equal an actual value of the bid represented, at least a portion of the bid representations being based on a seed bid value that initializes a pseudorandom number generator; and   means for verifying that each of the bid representations for a same bid are value consistent based on a verification factor and only one value component of each bid representation.   
     
     
         12 . A computer implemented method, comprising:
 receiving, by a data processing device, a request from a verifier to verify sealed bid auction results;   generating and providing, by a data processing device, bid representations that represent each bid of the auction results, each bid representation being a multi-value component representation of the bid;   generating and providing at least two test sets, each test set including a set of values, a sum of which is less than a reference value, the reference value being a value that is higher than any of the bids;   in response to a request to reveal a test set, providing data that reveals only one of the at least two test sets;   in response to a request to reveal a value component of the bid representations, providing data that reveals only one of the multi-value components of each of the bids; and   generating and providing difference data that represents a modular difference between pairs of bids represented by the bid representations, the difference data for each pair of bids including at least two value components, a sum of which equal a difference between the pair of bids.   
     
     
         13 . The method of  claim 12 , wherein generating and providing the difference data comprises:
 for each of the pairs of bids:
 computing a sum of values from a test set that is concealed from the verifier, the sum of values being equal to a difference between the pairs of bids represented by bid representations; 
 representing the sum of values with two value components that have a modular sum equal to the difference between the pair of bids; and 
 encrypting each of the two value components with a different encryption key; and 
 providing the encrypted value components. 
   
     
     
         14 . The method of  claim 12 , wherein providing data that reveals only one test set from the at least two test sets comprises:
 selecting a decryption key for the only one test set; and   providing the decryption key to the verifier.   
     
     
         15 . The method of  claim 12 , wherein providing data that reveals only one of the multi-value components of each of the bids comprises:
 selecting decryption keys that reveal only one of the value components for each of the bids; and   providing the decryption keys to the verifier.   
     
     
         16 . The method of  claim 12 , further comprising selecting and providing a set of verification conditions that, when satisfied, demonstrate that a winning bid of the auction was a highest bid. 
     
     
         17 . A system, comprising:
 an advertisement management system including at least one processor operable to perform an auction based on a set of sealed bids; and   a verification subsystem coupled to the advertisement management system, the verification subsystem including at least one processor operable to generate and provide bid representations for the sealed bids, test sets, and result verification data that verify results of the auction based on the bid representations, test sets, and result verification data without revealing actual values of the bids.   
     
     
         18 . The system of  claim 17 , wherein the result verification data comprises:
 a set of verification conditions that, when satisfied, demonstrate that a winning bid is a highest bid;   first decryption keys that reveal one component value for each of the bid representations; and   a second decryption key that reveals one of the test sets.   
     
     
         19 . The system of  claim 18 , wherein first decryption keys reveal a same value component for each bid representation. 
     
     
         20 . The system of  claim 17 , wherein the set of verification conditions are a set of relationships that demonstrate that a winning bid was a highest bid in the auction based on each bid of the auction having a value that is less than a reference value and a modular difference between the winning bid and each other bid also being less than the reference value. 
     
     
         21 . A computer readable medium encoded with a computer program comprising instructions that when executed operate to cause a computer to perform operations:
 receiving a request from a verifier to verify sealed bid auction results;   providing bid representations that represent each bid of the auction results, each bid representation being a multi-value component representation of the bid;   providing at least two test sets, each test set including a set of values, a sum of which is less than a reference value, the reference value being a value that is higher than any of the bids;   in response to a request to reveal a test set, providing data that reveals one of the at least two test sets;   in response to a request to reveal a value component of the bid representations, providing data that reveals one of the multi-value components of the bids; and   providing difference data that represents a modular difference between pairs of bids represented by the bid representations, the difference data including at least two value components, a sum of which equal a difference between the pairs of bids.   
     
     
         22 . A device, comprising:
 means for verifying results of a sealed bid auction without revealing actual values of sealed bids used in the sealed bid auction, the results of the auction being verified based bid representations for the sealed bids, values selected from a test set, and a set of verification conditions, the test set including a set of values, a sum of which are less than a reference value.   
     
     
         23 . The device of  claim 22 , wherein the set of verification conditions demonstrate that each bid in the sealed bid auction is less than the reference value and that a difference between a winning bid and each other bid is less than the reference value.