Robust Coin Flipping

Details Robust Coin Flipping Robust Coin Flipping

2010-09-21

arxiv.org/abs/1009.4188v3

Computer Science

Computational Complexity

22 pages, 1 figure

Scientific paper

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 $\alpha$, 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 \leq 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.

Affiliated with

Also associated with

No associations

Rating

Robust Coin Flipping does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Robust Coin Flipping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Coin Flipping will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-698124