Paper 2020/1447

Compressed $\Sigma$-Protocols for Bilinear Group Arithmetic Circuits and Application to Logarithmic Transparent Threshold Signatures

Thomas Attema, Netherlands Organisation for Applied Scientific Research
Ronald Cramer, Centrum Wiskunde & Informatica;
Matthieu Rambaud, Télécom ParisTech

Lai et al. (CCS 2019) have shown how Bulletproof’s arithmetic circuit zero-knowledge protocol (Bootle et al., EUROCRYPT 2016 and Bünz et al., S&P 2018) can be generalized to work for bilinear group arithmetic circuits directly, i.e., without requiring these circuits to be translated into arithmetic circuits. In a nutshell, a bilinear group arithmetic circuit is a standard arithmetic circuit augmented with special gates capturing group exponentiations or pairings. Such circuits are highly relevant, e.g., in the context of zero-knowledge statements over pairing-based languages. As expressing these special gates in terms of a standard arithmetic circuit results in a significant overhead in circuit size, an approach to zero-knowledge via standard arithmetic circuits may incur substantial additional costs. The approach due to Lai et al. shows how to avoid this by integrating additional zero-knowledge techniques into the Bulletproof framework so as to handle the special gates very efficiently. We take a different approach by generalizing Compressed $\Sigma$-Protocol Theory (CRYPTO 2020) from arithmetic circuit relations to bilinear group arithmetic circuit relations. Besides its conceptual simplicity, our approach has the practical advantage of reducing the communication costs of Lai et al.'s protocol by roughly a multiplicative factor 3. Finally, we show an application of our results which may be of independent interest. We construct the first k-out-of-n threshold signature scheme (TSS) that allows for transparent setup and that yields threshold signatures of size logarithmic in n. The threshold signature hides the identities of the k signers and the threshold k can be dynamically chosen at aggregation time.

Note: Change log w.r.t. Version 3 - March 10, 2021: (a) editorial changes throughout, (b) corrected a technical oversight in Appendix A without affecting the rest of the paper, and (c) added a short discussion on seemingly contradictory complexity assumptions (Section 5.2).

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2021
Zero-KnowledgeBilinear GroupsPairingsCompressed Sigma-Protocol TheoryThreshold Signature Schemes.
Contact author(s)
thomas attema @ tno nl
cramer @ cwi nl
rambaud @ enst fr
2023-01-10: last of 3 revisions
2020-11-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thomas Attema and Ronald Cramer and Matthieu Rambaud},
      title = {Compressed $\Sigma$-Protocols for Bilinear Group Arithmetic Circuits and Application to Logarithmic Transparent Threshold Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1447},
      year = {2020},
      doi = {10.1007/978-3-030-92068-5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.