International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Compact Designated Verifier NIZKs from the CDH Assumption Without Pairings

Authors:
Shuichi Katsumata
Ryo Nishimaki
Shota Yamada
Takashi Yamakawa
Download:
DOI: 10.1007/s00145-021-09408-w
Search ePrint
Search Google
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 NP NP do not have unbounded-soundness. Existing DV-NIZKs for 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|⋅poly(κ) | C | · poly ( κ ) , where | C | is the size of the circuit that computes the 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 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 NP NP with proof size |C|+poly(κ) | 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 NP NP relation to be computable in NC1 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|+poly(κ) | 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
}