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 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).