Paper 2018/557

Non-Interactive Zero-Knowledge Proofs for Composite Statements

Shashank Agrawal, Chaya Ganesh, and Payman Mohassel

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

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
Non-interactive zero-knowledgesigma protocolsSNARKproof of solvency
Contact author(s)
chaya ganesh @ gmail com
payman mohassel @ gmail com
shashank agraval @ gmail com
History
2018-06-04: received
Short URL
https://ia.cr/2018/557
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/557,
      author = {Shashank Agrawal and Chaya Ganesh and Payman Mohassel},
      title = {Non-Interactive Zero-Knowledge Proofs for Composite Statements},
      howpublished = {Cryptology ePrint Archive, Paper 2018/557},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/557}},
      url = {https://eprint.iacr.org/2018/557}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.