Robust coin flipping

Gene Kopp, John Wiltshire-Gordon

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

14 Downloads (Pure)


Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias α, as a function of data she receives from p sources; she seeks privacy from any coalition of r of them. We show: If p/2 ≤ r < p, the bias can be any rational number and nothing else; if 0 < r < p/2, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the r = 1 case in his seminal paper [yao82]. We also provide an application to secure multiparty computation.
Original languageEnglish
Title of host publicationAdvances in Cryptology—EUROCRYPT 2012
PublisherSpringer Berlin Heidelberg
Number of pages23
Publication statusPublished - 15 Apr 2012


  • multiparty computation
  • outsourcing randomness
  • biased coin flip
  • algebraic number
  • projective duality
  • hyperdeterminant


Dive into the research topics of 'Robust coin flipping'. Together they form a unique fingerprint.

Cite this