부산대학교 도서관

Summary: ``{\it 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 a vast range of distributed protocols. Interestingly, in BA protocols with the best overall communication, the demands of the parties are highly {\it unbalanced}: the amortized cost is ${\tilde{O}}(1)$ bits per party, but some parties must send $\Omega (n)$ bits. In best known {\it 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. In particular, is BA possible where {\it each} party communicates only ${\tilde{O}}(1)$ bits? Our contributions in this line are as follows: \roster \item"$\bullet$" We define a cryptographic primitive---{\it 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. \item"$\bullet$" The SRDS-based BA follows a paradigm of boosting from ``almost-everywhere'' agreement to full agreement, and does so in a single round. Complementarily, we prove that PKI setup and cryptographic assumptions are necessary for such protocols in which every party sends $o$($n$) messages. \item"$\bullet$" We further explore connections between a natural approach toward attaining SRDS and average-case succinct non-interactive argument systems (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product). \par Our results provide new approaches forward, as well as limitations and barriers, toward minimizing per-party communication of BA. In particular, we construct the first two BA protocols with ${\tilde{O}}(1)$ balanced communication, offering a trade-off between setup and cryptographic assumptions and answering an open question presented by King and Saia (DISC'09).'' \endroster