Robust Coin Flipping

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;...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2012-01
Main Authors: Kopp, Gene S, Wiltshire-Gordon, John D
Format: Article
Language:English
Subjects:
Bias
Computer simulation
Probabilistic methods
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1009.4188