Paper 2022/257

Guaranteed Output in $O(\sqrt{n})$ Rounds for Round-Robin Sampling Protocols

Ran Cohen
Jack Doerner
Yashvanth Kondi
abhi shelat

We introduce a notion of round-robin secure sampling that captures several protocols in the literature, such as the "powers-of-tau" setup protocol for pairing-based polynomial commitments and zk-SNARKs, and certain verifiable mixnets. 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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2022
multiparty computation guaranteed output delivery round compression distributed sampling setup ceremonies powers of tau SNARKs mixnets
Contact author(s)
j @ ckdoerner net
2022-09-28: last of 2 revisions
2022-03-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen and Jack Doerner and Yashvanth Kondi and abhi shelat},
      title = {Guaranteed Output in $O(\sqrt{n})$ Rounds for Round-Robin Sampling Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2022/257},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.