Cryptography and Preventing Collusion in Second Price (Vickery) Auctions

Michael Rabin
Harvard University and Columbia University
April 29, 2013

We present practically efficient methods for proving correctness of announced results of a computation while keeping input and intermediate values information theoretically secret. These methods are applied to solve the long standing problem of preventing collusion in second-price auctions.