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

Available format(s)
Publication info
Keywords
Non-interactive zero-knowledgesigma protocolsSNARKproof of solvency
Contact author(s)
chaya ganesh @ gmail com
payman mohassel @ gmail com
shashank agraval @ gmail com
History
Short URL
https://ia.cr/2018/557

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.