Paper 2020/1447

Compressed $\Sigma$-Protocols for Bilinear Group Arithmetic Circuits and Applications

Thomas Attema, Ronald Cramer, and Matthieu Rambaud


Recent developments in zero-knowledge have yielded various communication-efficient protocols for proving correctness of statements captured by an arithmetic circuit. Since any relation can be translated into an arithmetic circuit relation, these primitives are extremely powerful and widely applied. However, this translation often comes at the cost of losing conceptual simplicity and modularity in cryptographic protocol design. For this reason, Lai et al. (CCS 2019), show how Bulletproof's 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, without requiring these circuits to be translated into arithmetic circuits. For many natural relations their approach is actually more efficient than the indirect circuit ZK approach. We take a different approach by generalizing Compressed $\Sigma$-Protocol Theory (CRYPTO 2020). Besides its conceptual simplicity our approach also has practical advantages; we reduce the communication costs by roughly a factor $3$. As a first application, we construct the first $k$-out-of-$n$ threshold signature scheme (TSS) with both transparent setup and threshold signatures of size logarithmic in $n$. Each individual signature is of a so-called BLS type, the threshold signature hides the identities of the $k$ signers and the threshold $k$ can be dynamically chosen at aggregation time. Prior TSSs either have signature size linear in $k$ or require a trusted setup. As a second application, we give an explicit and direct construction for a proof that many signed messages satisfy a public predicate. The applications of this generic functionality are numerous. For instance, it implies a compiler from crash-fault tolerant distributed protocols into maliciously secure ones. Recently, it was shown that this in turn allows the so-far quadratic costs of certain consensus mechanisms to be reduced down to quasi linear in the number of players. Moreover, our construction finds applications in digital transaction and anonymous credential systems. The main benefit of this direct construction is that it avoids the large arithmetic circuits that are typically encountered when relying on the black-box application of circuit ZK systems, thereby achieving concretely efficient protocols.

Note: Change log w.r.t. Version 1 - November 17, 2020: (a) minor editorial changes throughout, and (b) included a second application of our techniques. Change log w.r.t. Version 2 - March 10, 2021: corrected a typo in the abstract.

Available format(s)
Cryptographic protocols
Publication info
Zero-KnowledgeBilinear GroupsPairingsCompressed Sigma-Protocol TheoryThreshold Signature Schemes.
Contact author(s)
thomas attema @ tno nl
cramer @ cwi nl
rambaud @ enst fr
2021-03-10: last of 2 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 Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1447},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.