Paper 2020/1447
Compressed $\Sigma$Protocols for Bilinear Group Arithmetic Circuits and Application to Logarithmic Transparent Threshold Signatures
Abstract
Lai et al. (CCS 2019) have shown how Bulletproof’s arithmetic circuit zeroknowledge 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 zeroknowledge statements over pairingbased languages. As expressing these special gates in terms of a standard arithmetic circuit results in a significant overhead in circuit size, an approach to zeroknowledge via standard arithmetic circuits may incur substantial additional costs. The approach due to Lai et al. shows how to avoid this by integrating additional zeroknowledge 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 koutofn 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).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2021
 DOI
 10.1007/9783030920685
 Keywords
 ZeroKnowledgeBilinear GroupsPairingsCompressed SigmaProtocol TheoryThreshold Signature Schemes.
 Contact author(s)

thomas attema @ tno nl
cramer @ cwi nl
rambaud @ enst fr  History
 20230110: last of 3 revisions
 20201119: received
 See all versions
 Short URL
 https://ia.cr/2020/1447
 License

CC BY
BibTeX
@misc{cryptoeprint:2020/1447, 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/9783030920685}, url = {https://eprint.iacr.org/2020/1447} }