Welcome to the resource topic for 2020/1447
Title:
Compressed \Sigma-Protocols for Bilinear Group Arithmetic Circuits and Applications
Authors: Thomas Attema, Ronald Cramer, Matthieu Rambaud
Abstract: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.
ePrint: https://eprint.iacr.org/2020/1447
Talk: https://www.youtube.com/watch?v=tMVJd1tlUTA
Slides: https://iacr.org/submit/files/slides/2021/asiacrypt/asiacrypt2021/87/slides.pdf
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .