Cryptology ePrint Archive: Report 2020/130

Succinctly Reconstructed Distributed Signatures and Balanced Byzantine Agreement

Elette Boyle and Ran Cohen and Aarushi Goel

Abstract: Byzantine agreement (BA), the task of $n$ parties to agree on one of their input bits in the face of malicious agents, is a powerful primitive that lies at the core of virtually every multi-party cryptographic protocol. Interestingly, in protocols with the best overall communication complexity, the communication demands of the parties are highly unbalanced: the amortized cost is $\tilde O(1)$ bits per party, but some parties must send $\Omega(n)$ bits. In best known balanced protocols, the overall communication is sub-optimal, with each party communicating $\tilde O(\sqrt{n})$.

In this work, we ask whether asymmetry is inherent for optimizing total communication. Our contributions in this line are as follows:

1) We identify a cryptographic primitive, succinctly reconstructed distributed signatures (SRDS), that suffices for constructing $\tilde O(1)$ balanced BA. We provide two constructions of SRDS from different cryptographic and Public-Key Infrastructure (PKI) assumptions.

2) The SRDS-based BA follows a paradigm of boosting from "almost-everywhere" agreement to full agreement, and does so in a single round. We prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o(n)$ messages.

3) We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems for a particular type of "Subset-$f$" problems (generalizing Subset-Sum and Subset-Product).

Collectively, our results provide an initial mapping for the feasibility landscape of $\tilde O(1)$ balanced BA, including new approaches forward, as well as limitations and barriers. Our approach yields the first two BA protocols with $\tilde O(1)$ balanced communication, offering a tradeoff between setup and cryptographic assumptions, and answering an open question presented by King and Saia (DISC'09).

Category / Keywords: cryptographic protocols / Byzantine agreement; communication complexity

Date: received 6 Feb 2020, last revised 10 Feb 2020

Contact author: elette boyle at idc ac il,rancohen@ccs neu edu,aarushig@cs jhu edu

Available format(s): PDF | BibTeX Citation

Version: 20200210:201448 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]