CryptoDB
Non-Interactive Zero-Knowledge Proofs for Composite Statements
| Authors: | |
|---|---|
| Download: |
|
| Conference: | CRYPTO 2018 |
| Abstract: | The two most common ways to design non-interactive zero-knowledge (NIZK) proofs are based on Sigma protocols and QAP-based SNARKs. The former is highly efficient for proving algebraic statements while the latter is superior for arithmetic representations. Motivated by applications such as privacy-preserving credentials and privacy-preserving audits in cryptocurrencies, we study the design of NIZKs for composite statements that compose algebraic and arithmetic statements in arbitrary ways. Specifically, we provide a framework for proving statements that consist of ANDs, ORs and function compositions of a mix of algebraic and arithmetic components. This allows us to explore the full spectrum of trade-offs between proof size, prover cost, and CRS size/generation cost. This leads to proofs for statements of the form: knowledge of x such that $$SHA(g^x)=y$$SHA(gx)=y for some public y where the prover’s work is 500 times fewer exponentiations compared to a QAP-based SNARK at the cost of increasing the proof size to 2404 group and field elements. In application to anonymous credentials, our techniques result in 8 times fewer exponentiations for the prover at the cost of increasing the proof size to 298 elements. |
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28802,
title={Non-Interactive Zero-Knowledge Proofs for Composite Statements},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10993},
pages={643-673},
doi={10.1007/978-3-319-96878-0_22},
author={Shashank Agrawal and Chaya Ganesh and Payman Mohassel},
year=2018
}