## CryptoDB

### Paper: Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings

Authors: Shuichi Katsumata Ryo Nishimaki Shota Yamada Takashi Yamakawa DOI: 10.1007/s00145-021-09408-w Search ePrint Search Google In a non-interactive zero-knowledge (NIZK) proof, a prover can non-interactively convince a verifier of a statement without revealing any additional information. A useful relaxation of NIZK is a designated verifier NIZK (DV-NIZK) proof, where proofs are verifiable only by a designated party in possession of a verification key. A crucial security requirement of DV-NIZKs is unbounded-soundness, which guarantees soundness even if the verification key is reused for multiple statements. Most known DV-NIZKs (except standard NIZKs) for $\mathbf{NP}$ NP do not have unbounded-soundness. Existing DV-NIZKs for $\mathbf{NP}$ NP satisfying unbounded-soundness are based on assumptions which are already known to imply standard NIZKs. In particular, it is an open problem to construct (DV-)NIZKs from weak paring-free group assumptions such as decisional Diffie–Hellman (DH). As a further matter, all constructions of (DV-)NIZKs from 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 )$ | C | · poly ( κ ) , where | C | is the size of the circuit that computes the $\mathbf{NP}$ NP relation. In this work, we make progress of constructing DV-NIZKs from DH-type assumptions that are not known to imply standard NIZKs. Our results are summarized as follows: DV-NIZKs for $\mathbf{NP}$ NP from the computational DH 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). DV-NIZKs for $\mathbf{NP}$ NP with proof size $|C|+\mathsf {poly}(\kappa )$ | C | + poly ( κ ) from the computational DH assumption over specific pairing-free groups. This is the first DV-NIZK that achieves a compact proof from a standard DH type assumption. Moreover, if we further assume the $\mathbf{NP}$ NP relation to be computable in $\mathbf{NC} ^1$ NC 1 and assume hardness of a (non-static) falsifiable DH type assumption over specific pairing-free groups, the proof size can be made as small as $|w| + \mathsf {poly}(\kappa )$ | w | + poly ( κ ) .
##### BibTeX
@article{jofc-2021-31751,
title={Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings},
journal={Journal of Cryptology},
publisher={Springer},
volume={34},
doi={10.1007/s00145-021-09408-w},
author={Shuichi Katsumata and Ryo Nishimaki and Shota Yamada and Takashi Yamakawa},
year=2021
}