CryptoDB
Paper: Exploring Constructions of Compact NIZKs from Various Assumptions
Authors:  

Download: 

Abstract:  A noninteractive zeroknowledge (NIZK) protocol allows a prover to noninteractively convince a verifier of the truth of the statement without leaking any other information. In this study, we explore shorter NIZK proofs for all $$\mathbf{NP }$$ languages. Our primary interest is NIZK proofs from falsifiable pairing/pairingfree groupbased assumptions. Thus far, NIZKs in the common reference string model (CRSNIZKs) for $$\mathbf{NP }$$ based on falsifiable pairingbased assumptions all require a proof size at least as large as $$O(C \kappa )$$, where C is a circuit computing the $$\mathbf{NP }$$ relation and $$\kappa $$ is the security parameter. This holds true even for the weaker designatedverifier NIZKs (DVNIZKs). Notably, constructing a (CRS, DV)NIZK with proof size achieving an additiveoverhead $$O(C) + \mathsf {poly}(\kappa )$$, rather than a multiplicativeoverhead $$C \cdot \mathsf {poly}(\kappa )$$, based on any falsifiable pairingbased assumptions is an open problem.In this work, we present various techniques for constructing NIZKs with compact proofs, i.e., proofs smaller than $$O(C) + \mathsf {poly}(\kappa )$$, and make progress regarding the above situation. Our result is summarized below. We construct CRSNIZK for all $$\mathbf{NP }$$ with proof size $$C +\mathsf {poly}(\kappa )$$ from a (nonstatic) falsifiable DiffieHellman (DH) type assumption over pairing groups. This is the first CRSNIZK to achieve a compact proof without relying on either latticebased assumptions or nonfalsifiable assumptions. Moreover, a variant of our CRSNIZK satisfies universal composability (UC) in the erasurefree adaptive setting. Although it is limited to $$\mathbf{NP }$$ relations in $$\mathbf{NC }^1$$, the proof size is $$w \cdot \mathsf {poly}(\kappa )$$ where w is the witness, and in particular, it matches the stateoftheart UCNIZK proposed by Cohen, shelat, and Wichs (CRYPTO’19) based on lattices.We construct (multitheorem) DVNIZKs for $$\mathbf{NP }$$ with proof size $$C+\mathsf {poly}(\kappa )$$ from the computational DH assumption over pairingfree groups. This is the first DVNIZK that achieves a compact proof from a standard DH type assumption. Moreover, if we further assume the $$\mathbf{NP }$$ relation to be computable in $$\mathbf{NC }^1$$ and assume hardness of a (nonstatic) falsifiable DH type assumption over pairingfree groups, the proof size can be made as small as $$w + \mathsf {poly}(\kappa )$$. Another related but independent issue is that all (CRS, DV)NIZKs require the running time of the prover to be at least $$C\cdot \mathsf {poly}(\kappa )$$. Considering that there exists NIZKs with efficient verifiers whose running time is strictly smaller than C, it is an interesting problem whether we can construct proverefficient NIZKs. To this end, we construct proverefficient CRSNIZKs for $$\mathbf{NP }$$ with compact proof through a generic construction using laconic functional evaluation schemes (Quach, Wee, and Wichs (FOCS’18)). This is the first NIZK in any model where the running time of the prover is strictly smaller than the time it takes to compute the circuit C computing the $$\mathbf{NP }$$ relation.Finally, perhaps of an independent interest, we formalize the notion of homomorphic equivocal commitments, which we use as building blocks to obtain the first result, and show how to construct them from pairingbased assumptions. 
Video from CRYPTO 2019
BibTeX
@article{crypto201929928, title={Exploring Constructions of Compact NIZKs from Various Assumptions}, booktitle={Advances in Cryptology – CRYPTO 2019}, series={Lecture Notes in Computer Science}, publisher={Springer}, volume={11694}, pages={639669}, doi={10.1007/9783030269548_21}, author={Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa}, year=2019 }