A solution to the persistent problem of
preventing collusion in Vickrey auctions.
by silVio micali and michael o. Rabin
IN THIS ARTICLE, we extend the methods of Rabin et al.10,11
in a major way and provide a solution to the long-standing
important problem of preventing collusion in second-price (Vickrey) auctions. The new tools presented are
deniable revelation of a secret value and uncontrollable
deniable bidding. In Rabin et al.,10,11 new highly efficient
methods for proving correctness of
announced results of computations
were introduced. These proofs completely conceal input values and inter-
Practically efficient secrecy of values
preserving proofs of correctness of
computations are useful for many
financial and social processes.
in particular, they supply a solution to
the long-standing open problem of
countering collusion of bidders in
second-price (Vickrey) auctions.
an important feature of these new
methods is their understandability by
a wide audience of potential users.
mediate results of the computation.
One application was to enable an
Auctioneer to announce outcome of a
sealed bid auction and provide verification of correctness of the outcome,
while keeping bid values information-theoretically secret. We quickly survey
these methods for completeness of
the discussion and because of their
wide applicability. Another example
of an application is to prove to participants of a stable matching process
such as the assignment residents to
hospitals, of the correctness of the announced assignment without revealing any preferences of residents with
respect to hospitals and vice-versa.