In this work, we ask whether asymmetry is inherent for optimizing total communication. In particular, is BA possible where each party communicates only $tilde O(1)$ bits? Our contributions in this line are as follows:
1) We define 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. Complementarily, 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 (SNARGs) for a particular type of NP-Complete problems (generalizing Subset-Sum and Subset-Product).
Our results provide new approaches forward, as well as limitations and barriers, towards minimizing per-party communication of BA. In particular, we construct 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).
Go to Source of this post
Author Of this post: