Cryptographic Combinatorial Clock-Proxy Auctions
| Title: | Cryptographic Combinatorial Clock-Proxy Auctions |
| Author: |
Parkes, David C.; Rabin, Michael O.; Thorpe, Christopher Andrew
Note: Order does not necessarily reflect citation order of authors. |
| Citation: | Parkes, David C., Michael O. Rabin, and Christopher Thorpe. 2009. Cryptographic combinatorial clock-proxy auctions. In Financial Cryptography and Data Security, ed. R. Dingledine, P. Golle, 305-324. Berlin: Springer. Previously published in Lecture Notes In Computer Science 5628: 305-324. |
| Full Text & Related Files: |
Parkes_Cryptographic.pdf (482.8Kb; PDF) 
|
| Abstract: | We present a cryptographic protocol for conducting efficient, provably correct and secrecy-preserving combinatorial clock-proxy auctions. The "clock phase" functions as a trusted auction despite price discovery: bidders submit encrypted bids, and prove for themselves that they meet activity rules, and can compute total demand and thus verify price increases without revealing any information about individual demands. In the sealed-bid "proxy phase", all bids are revealed the auctioneer via time-lapse cryptography and a branch-and-bound algorithm is used to solve the winner-determination problem. Homomorphic encryption is used to prove the correctness of the solution, and establishes the correctness of the solution to any interested party. Still an NP-hard optimization problem, the use of homomorphic encryption imposes additional computational time on winner-determination that is linear in the size of the branch-and-bound search tree, and thus roughly linear in the original (search-based) computational time. The result is a solution that avoids, in the usual case, the exponential complexity of previous cryptographically-secure combinatorial auctions. |
| Published Version: | doi:10.1007/978-3-642-03549-4_19 |
| Other Sources: | http://www.eecs.harvard.edu/econcs/pubs/fc_ccpa.pdf |
| Terms of Use: | This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4000813 |
| Downloads of this work: |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [15509]
Contact administrator regarding this item (to report mistakes or request changes)
