Paper 2022/1683
Powers of Tau in Asynchrony
Abstract
The $q$-Strong Diffie-Hellman ($q$-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive argument of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon. The only existing method to generate these parameters securely is highly sequential, requires strong network synchrony assumptions, and has very high communication and computation cost. For example, to generate parameters for any given $q$, each party incurs a communication cost of $\Omega(nq)$ and requires $\Omega(n)$ rounds. Here $n$ is the number of parties in the secure multiparty computation protocol. Since $q$ is typically large, i.e., on the order of billions, the cost is highly prohibitive. In this paper, we present Tauron, a distributed protocol to generate $q$-SDH parameters in an asynchronous network. In a network of $n$ parties, Tauron tolerates up to one-third of malicious parties. Each party incurs a communication cost of $O(q + n^2\log q)$ and the protocol finishes in $O(\log q + \log n)$ expected rounds. We provide a rigorous security analysis of our protocol. We implement Tauron and evaluate it with up to 128 geographically distributed parties. Our evaluation illustrates that Tauron is highly scalable and results in a 2-6$\times$ better runtime and 4-13$\times$ better per-party bandwidth usage.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Powers of Tau Asynchrony q-Strong Diffie-Hellman
- Contact author(s)
-
souravd2 @ illinois edu
xiangzhuolun @ gmail com
renling @ illinois edu - History
- 2022-12-05: approved
- 2022-12-03: received
- See all versions
- Short URL
- https://ia.cr/2022/1683
- License
-
CC0
BibTeX
@misc{cryptoeprint:2022/1683, author = {Sourav Das and Zhuolun Xiang and Ling Ren}, title = {Powers of Tau in Asynchrony}, howpublished = {Cryptology ePrint Archive, Paper 2022/1683}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1683}}, url = {https://eprint.iacr.org/2022/1683} }