eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2019/255

Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions

Shuichi Katsumata, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa


In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. Thus far, numerous constructions of NIZKs have been provided in the common reference string (CRS) model (CRS-NIZK) from various assumptions, however, it still remains a long standing open problem to construct them from tools such as pairing-free groups or lattices. Recently, Kim and Wu (CRYPTO'18) made great progress regarding this problem and constructed the first lattice-based NIZK in a relaxed model called NIZKs in the preprocessing model (PP-NIZKs). In this model, there is a trusted statement-independent preprocessing phase where secret information are generated for the prover and verifier. Depending on whether those secret information can be made public, PP-NIZK captures CRS-NIZK, designated-verifier NIZK (DV-NIZK), and designated-prover NIZK (DP-NIZK) as special cases. It was left as an open problem by Kim and Wu whether we can construct such NIZKs from weak paring-free group assumptions such as DDH. As a further matter, all constructions of NIZKs from Diffie-Hellman (DH) type assumptions (regardless of whether it is over a paring-free or paring group) require the proof size to have a multiplicative-overhead $|C| \cdot \mathsf{poly}(\kappa)$, where $|C|$ is the size of the circuit that computes the $\mathbf{NP}$ relation. In this work, we make progress of constructing (DV, DP, PP)-NIZKs with varying flavors from DH-type assumptions. Our results are summarized as follows: 1. DV-NIZKs for $\mathbf{NP}$ from the CDH assumption over pairing-free groups. This is the first construction of such NIZKs on pairing-free groups and resolves the open problem posed by Kim and Wu (CRYPTO'18). 2. DP-NIZKs for $\mathbf{NP}$ with short proof size from a DH-type assumption over pairing groups. Here, the proof size has an additive-overhead $|C|+\mathsf{poly}(\kappa)$ rather then an multiplicative-overhead $|C| \cdot \mathsf{poly}(\kappa)$. This is the first construction of such NIZKs (including CRS-NIZKs) that does not rely on the LWE assumption, fully-homomorphic encryption, indistinguishability obfuscation, or non-falsifiable assumptions. 3. PP-NIZK for $\mathbf{NP}$ with short proof size from the DDH assumption over pairing-free groups. This is the first PP-NIZK that achieves a short proof size from a weak and static DH-type assumption such as DDH. Similarly to the above DP-NIZK, the proof size is $|C|+\mathsf{poly}(\kappa)$. This too serves as a solution to the open problem posed by Kim and Wu (CRYPTO'18). Along the way, we construct two new homomorphic authentication (HomAuth) schemes which may be of independent interest.

Note: Added remarks on NC1 decryptable SKE (6/2/2020). Corrected an error in the proof of non-adaptive zero-knowledge in Appendix A (7/9/2019).

Available format(s)
Publication info
A major revision of an IACR publication in EUROCRYPT 2019
Non-interactive zero-knowledge proofsDiffie-Hellman assumptionsHomomorphic signatures
Contact author(s)
shuichi katsumata @ aist go jp
yamada-shota @ aist go jp
takashi yamakawa ga @ hco ntt co jp
ryo nishimaki zk @ hco ntt co jp
2020-06-02: last of 3 revisions
2019-02-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
      title = {Designated Verifier/Prover and Preprocessing NIZKs from Diffie-Hellman Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/255},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/255}},
      url = {https://eprint.iacr.org/2019/255}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.