Cryptology ePrint Archive: Report 2008/097
Fairness with an Honest Minority and a Rational Majority
Shien Jin Ong and David Parkes and Alon Rosen and Salil Vadhan
Abstract: We provide a simple protocol for secret reconstruction in any threshold secret sharing scheme, and prove that it is fair when executed with many rational parties together with a small minority of honest parties. That is, all parties will learn the secret with high probability when the honest parties follow the protocol and the rational parties act in their own self-interest (as captured by the notion of a Bayesian subgame perfect equilibrium). The protocol only
requires a standard (synchronous) broadcast channel, and tolerates fail-stop deviations (i.e. early stopping, but not incorrectly computed messages).
Previous protocols for this problem in the cryptographic or economic models have either required an honest majority, used strong communication channels that enable simultaneous exchange of information, or settled for approximate notions of security/equilibria.
Category / Keywords: game theory, fairness, secret sharing
Date: received 3 Mar 2008, last revised 4 Mar 2008
Contact author: alon rosen at idc ac il
Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation
Version: 20080310:144304 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]