Computer Science – Computational Complexity
Scientific paper
2010-09-21
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.
Kopp Gene S.
Wiltshire-Gordon John D.
No associations
LandOfFree
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.
Profile ID: LFWR-SCP-O-698124