However, in the multi-party protocols with faulty minority, parties need to generate and hold local secret values which are assumed to be {\it perfectly hidden} from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.
In this work, we present an $O(1)$-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate $t \le (\frac{1}{3} - \epsilon) n$ computationally-unbounded Byzantine faults and in addition a $\Omega(1)$-fraction leakage on each (honest) party's secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan '08) adapted to the distributed setting.
Another contribution of our work is a tool we use to achieve collective coin flipping -- {\it leakage-resilient verifiable secret sharing}. Informally, this is a variant of ordinary VSS in which secrecy guarantees are maintained even if information is leaked on individual shares of the secret.
Category / Keywords: cryptographic protocols / Leakage-resilient protocols, coin tossing, distributed computing Date: received 1 Jun 2011, last revised 21 Jun 2011 Contact author: eboyle at mit edu Available format(s): PDF | BibTeX Citation Version: 20110621:224443 (All versions of this report) Short URL: ia.cr/2011/291 Discussion forum: Show discussion | Start new discussion