Robust Coin Flipping

DOI10.1007/978-3-642-29011-4_12MaRDI QIDQ2894407zbMATH OpenOpenAlexFDO

Authors Gene S. Kopp, John D. Wiltshire-Gordon

Publication date 29 June 2012

Published in Advances in Cryptology – EUROCRYPT 2012 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.4188

zbMATH Keywords

algebraic numberbiased coin fliphyperdeterminantmultiparty computationoutsourcing randomnessprojective duality

Mathematics Subject Classification ID

Combinatorial probability (60C05) Cryptography (94A60)

Abstract: 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/2leqr<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.

Recommendations

• Optimal coin flipping
• Coin tossing, revisited
• Random coin tossing
• An optimally fair coin toss
• An Optimally Fair Coin Toss
• Leakage-Resilient Coin Tossing
• Leakage-resilient coin tossing
• Weak coin flipping with small bias

Cited in

(2)

• Flipping a Coin over the Telephone
• Coin flipping from a cosmic source: On error correction of truly random bits

This page was built for publication: Robust Coin Flipping

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2894407)