Paper 2011/291

Leakage-Resilient Coin Tossing

Elette Boyle, Shafi Goldwasser, and Yael Tauman Kalai


The ability to collectively toss a common coin among $n$ parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than $\frac{1}{r}$ bias in $O(r)$ rounds (Cleve STOC '86). In the case of honest majority, in contrast, unconditionally secure $O(1)$-round protocols for generating common perfectly {\it unbiased} coins follow from general completeness theorems on multi-party secure protocols in the perfectly secure channels model (e.g., BGW, CCD STOC '88). 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Leakage-resilient protocolscoin tossingdistributed computing
Contact author(s)
eboyle @ mit edu
2011-06-21: revised
2011-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Elette Boyle and Shafi Goldwasser and Yael Tauman Kalai},
      title = {Leakage-Resilient Coin Tossing},
      howpublished = {Cryptology ePrint Archive, Paper 2011/291},
      year = {2011},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.