Leakage-resilient coin tossing

摘要: The ability to collectively toss a common coin among $$n$$ n parties in the presence of faults is an important primitive arsenal randomized distributed protocols. In case dishonest majority, it was shown be impossible achieve less than $$\frac{1}{r}$$ 1 r bias $$O(r)$$ O ( ) rounds (Cleve STOC '86). honest contrast, unconditionally secure $$O(1)$$ -round protocols for generating perfectly unbiased coins follow from general completeness theorems on multi-party channels model (e.g., BGW, CCD '88). However, with must generate and hold local secret values which are assumed hidden malicious parties: assumption crucial proving resulting unbiased. This unfortunately does not seem practice, as attackers can launch side-channel attacks state leak information their secrets. this work, we present protocol coin, leakage parties. We tolerate $$t \le (\frac{1}{3} - \epsilon n$$ t ≤ 3 ∈ computationally unbounded statically scheduled Byzantine addition $$\varTheta (1)$$ ? -fraction each (honest) party's state. Our results memory (of Akavia, Goldwasser, Vaikuntanathan '08) adapted setting. Another contribution our work tool use collective flipping—leakage-resilient verifiable sharing (VSS). Informally, variant ordinary VSS secrecy guarantees maintained even if leaked individual shares secret.