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

Recent developments in zero-knowledge have yielded various communication-efficient protocols for proving correctness of statements captured by arithmetic circuits. 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 Σ-Protocol Theory (CRYPTO 2020) from arithmetic circuit relations to bilinear group arithmetic circuit relations. Besides its conceptual simplicity our approach also has practical advantages; we reduce the communication costs by roughly a factor 3. The generalized commitment scheme required for bilinear circuit rela tions is also advantageous to standard arithmetic circuit ZK protocols, since its application immediately results in a square root reduction of public parameters size. The implications of this improvement can be sig nificant, because many application scenarios result in very large sets of public parameters. As an application of our generalization, 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 are either of size linear in k or require a trusted setup. Recently, it has been shown that a generalization of our TSS, requiring additional compression techniques outside of the scope of this submission, allows the so-far quadratic communication costs of consensus protocols to be reduced down to quasi-linear. 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