Paper 2019/623
Exploring Constructions of Compact NIZKs from Various Assumptions
Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa
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 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 NP based on falsifiable pairingbased assumptions all require a proof size at least as large as $O(C k)$, where $C$ is a circuit computing the NP relation and $k$ 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) + poly(k)$, rather than a multiplicativeoverhead $C \cdot poly(k)$, 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) + poly(k)$, and make progress regarding the above situation. Our result is summarized below.  We construct CRSNIZK for all NP with proof size $C + poly(k)$ 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 NP relations in NC1, the proof size is $w \cdot poly(k)$ where $w$ is the witness, and in particular, it matches the stateoftheart UCNIZK proposed by Cohen, shelat, and Wichs (EPRINT'18) based on lattices.  We construct (multitheorem) DVNIZKs for NP with proof size $C+poly(k)$ 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 NP relation to be computable in NC1 and assume hardness of a (nonstatic) falsifiable DH type assumption over pairingfree groups, the proof size can be made as small as $w + poly(k)$. Another related but independent issue is that all (CRS, DV)NIZKs require the running time of the prover to be at least $C\cdot poly(k)$. 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 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 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.
Note: Added remarks on NC1 decryptable SKE (6/2/2020). Fixed minor typos (10/3/2019).
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A major revision of an IACR publication in CRYPTO 2019
 Keywords
 noninteractive zeroknowledgepairinghomomorphic equivocal commitmentshort proof
 Contact author(s)

shuichi katsumata @ aist go jp
yamadashota @ aist go jp
takashi yamakawa ga @ hco ntt co jp
takashi yamakawa obf @ gmail com
ryo nishimaki zk @ hco ntt co jp
ryo nishimaki @ gmail com  History
 20200602: last of 2 revisions
 20190603: received
 See all versions
 Short URL
 https://ia.cr/2019/623
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/623, author = {Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa}, title = {Exploring Constructions of Compact NIZKs from Various Assumptions}, howpublished = {Cryptology ePrint Archive, Paper 2019/623}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/623}}, url = {https://eprint.iacr.org/2019/623} }