Estimating gaps in martingales and applications to coin-tossing: constructions and hardness

DOI10.1007/978-3-030-36033-7_13MaRDI QIDQ2175944zbMATH OpenOpenAlexFDO

Authors Hamidreza Amini Khorasgani, Hemanta K. Maji, Tamalika Mukherjee

Publication date 30 April 2020

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

zbMATH Keywords

distributed coin-tossing protocol

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Abstract: Consider designing a distributed coin-tossing protocol for n processors such that the probability of heads is X0 in [0,1], and an adversary can reset one processor to change the distribution of the final outcome. For X0=1/2, in the non-cryptographic setting, Blum's majority protocol is $frac1sqrt2pin$ insecure. For computationally bounded adversaries and any X0 in [0,1], the protocol of Moran,Naor,Segev (2009) is only O(1/n) insecure. In this paper, we study discrete-time martingales (X0,X1,..,Xn) such that Xi in [0,1], for all i in {0,..,n}, and Xn in {0,1}. In particular, for any X0 in [0,1], we construct martingales that yield $frac12sqrtfrac{X}_0(1-X_0)n$ insecure coin-tossing protocols with n-bit communication; irrespective of the number of bits required to represent the output distribution. Note that for sufficiently small X0, we achieve higher security than Moran et al's protocol even against computationally unbounded adversaries. For X0=1/2, our protocol requires only 40% of the processors to obtain the same security as the majority protocol. We introduce a new inductive technique that uses geometric transformations to estimate the large gaps in these martingales. For any X0 in [0,1], we show that there exists a stopping time $T$ such that $mathbbE[|X_T-X_{T-1}|]geqfrac2sqrt2n-1cdot{X}_0(1-X_0)$. The inductive technique also constructs martingales that demonstrate the optimality of our bound - we construct optimal martingales such that any $T$ has$mathbbE[|X_T-X_{T-1}|]leqfrac1sqrtncdotsqrt{X}_0(1-X_0)$. Our lower-bound holds for all X0 in [0,1]; while the previous bound of Cleve,Impagliazzo (1993) exists only for positive constant X0. Our approach only employs elementary techniques and avoids the complex probabilistic tools inherent to the approaches of Cleve,Impagliazzo (1993) and Beimel,Haitner,Makriyannis,Omri (2018).

Recommendations

• Tighter bounds on multiparty coin flipping via augmented weak martingales and differentially private sampling
• Protocols for multiparty coin toss with dishonest majority
• Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious
• Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious
• Fair coin flipping: tighter analysis and the many-party case

Cites work

• \(1/p\)-secure multiparty computation without honest majority and the best of both worlds
• A full characterization of functions that imply fair coin tossing and ramifications to fairness
• Adaptively secure coin-flipping, revisited
• Almost-optimally fair multiparty coin-tossing with nearly three-quarters malicious
• An Optimally Fair Coin Toss
• Can optimally-fair coin tossing be based on one-way functions?
• Complete Characterization of Fairness in Secure Two-Party Computation of Boolean Functions
• Complete fairness in secure two-party computation
• Does Privacy Require True Randomness?
• Estimating gaps in martingales and applications to coin-tossing: constructions and hardness
• Extracting randomness: A survey and new constructions
• Fair coin flipping: tighter analysis and the many-party case
• scientific article; zbMATH DE number 871932 (Why is no real title available?)
• Limits on the Usefulness of Random Oracles
• On the Black-Box Complexity of Optimally-Fair Coin Tossing
• On the classification of finite Boolean functions up to fairness
• Partial fairness in secure two-party computation
• Probability Inequalities for Sums of Bounded Random Variables
• Protocols for multiparty coin toss with dishonest majority
• Simulating BPP using a general weak random source
• Some extremal problems arising from discrete control processes
• Theory of Cryptography
• Tighter bounds on multiparty coin flipping via augmented weak martingales and differentially private sampling
• Towards characterizing complete fairness in secure two-party computation
• Weighted sums of certain dependent random variables

Cited in

(5)

• Black-box use of one-way functions is useless for optimal fair coin-tossing
• Estimating gaps in martingales and applications to coin-tossing: constructions and hardness
• Polynomial-time targeted attacks on coin tossing for any number of corruptions
• Tighter bounds on multiparty coin flipping via augmented weak martingales and differentially private sampling
• Completeness theorems for adaptively secure broadcast

This page was built for publication: Estimating gaps in martingales and applications to coin-tossing: constructions and hardness

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