Due to their round-robin structure, protocols of this class inherently require $n$ sequential broadcast rounds, where $n$ is the number of participants.
We describe how to compile them generically into protocols that require only $O(\sqrt{n})$ broadcast rounds. Our compiled protocols guarantee output delivery against any dishonest majority. This stands in contrast to prior techniques, which require $\Omega(n)$ sequential broadcasts in most cases (and sometimes many more). Our compiled protocols permit a certain amount of adversarial bias in the output, as all sampling protocols with guaranteed output must, due to Cleve's impossibility result (STOC'86). We show that in the context of the aforementioned applications, this bias is harmless.
Category / Keywords: cryptographic protocols / multiparty computation, guaranteed output delivery, round compression, distributed sampling, setup ceremonies, powers of tau, SNARKs, mixnets Original Publication (with major differences): IACR-EUROCRYPT-2022 Date: received 26 Feb 2022, last revised 28 Feb 2022 Contact author: j at ckdoerner net Available format(s): PDF | BibTeX Citation Version: 20220302:140132 (All versions of this report) Short URL: ia.cr/2022/257