Leakage-Resilient Coin Tossing

Elette Boyle, Shafi Goldwasser and Yael Tauman Kalai

Abstract: The ability to collectively toss a common coin among n parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than 1/r bias in O(r) rounds (Cleve STOC ’86). In the case of honest majority, in contrast, unconditionally secure O(1)-round protocols for generating common unbiased coins follow from general completeness theorems on multi-party secure protocols in the secure channels model (e.g., BGW, CCD STOC ’88).
However, in the protocols with honest majority, parties must generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.
In this work, we present an O(1)-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t ≤ ( 1/3 − ϵ)n computationally-unbounded Byzantine faults and in addition a Ω(1)-fraction leakage on each (honest) party’s secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan ’08) adapted to the distributed setting.
Additional contributions of our work are the tools we introduce to achieve the collective coin toss: a procedure for disjoint committee election, and leakage-resilient verifiable secret sharing.

Guest: Elette Boyle
Host: Yvonne-Anne Pignolet

Byzantine Agreement with Homonyms

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Anne-Marie Kermarrec, Eric Ruppert and Hung Tran-The

So far, the distributed computing community has either assumed that the processes of a distributed system all have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. In a sense, these are two extremes of the same general model: namely, n processes can use l authenticated identifiers, where 1 ≤ l ≤ n. This paper studies Byzantine agreement in this general model assuming several processes can share the same identifier.
We study Byzantine agreement in a message-passing system with homonyms. We assume up to t < n of the processes can be Byzantine. We prove the following results: (i) synchronous agreement is possible if and only if l > 3t; (ii) partially synchronous agreement is possible if and only if 3t < l ≤ n < 2l−3t; (iii) asynchronous eventual agreement is possible if and only if l > 3t.

Guset: Rachid Guerraoui
Host: Zvi Lotker