CryptoDB
Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings
| Authors: | |
|---|---|
| Download: | |
| 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. 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
}