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

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

**Abstract: **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.

**Category / Keywords: **foundations / Non-interactive zero-knowledge proofs, Diffie-Hellman assumptions, Homomorphic signatures

**Original Publication**** (with major differences): **IACR-EUROCRYPT-2019

**Date: **received 28 Feb 2019, last revised 1 Jun 2020

**Contact author: **shuichi katsumata at aist go jp, yamada-shota at aist go jp, takashi yamakawa ga at hco ntt co jp, ryo nishimaki zk at hco ntt co jp

**Available format(s): **PDF | BibTeX Citation

**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).

**Version: **20200602:041045 (All versions of this report)

**Short URL: **ia.cr/2019/255

[ Cryptology ePrint archive ]