Towards Non-Interactive Zero-Knowledge from CDH and LWE
We provide a generic construction of non-interactive zero-knowledge
(NIZK) schemes. Our construction is a refinement of Dwork
and Naor’s (FOCS 2000) implementation of the hidden bits model using
verifiable pseudorandom generators (VPRGs). Our refinement simplifies
their construction and relaxes the necessary assumptions considerably.
As a result of this conceptual improvement, we obtain interesting new
– A designated-verifier NIZK (with unbounded soundness) based on
the computational Diffie-Hellman (CDH) problem. If a pairing is
available, this NIZK becomes publicly verifiable. This constitutes the
first fully secure CDH-based designated-verifier NIZKs (and more
generally, the first fully secure designated-verifier NIZK from a non-generic
assumption which does not already imply publicly-verifiable
NIZKs), and it answers an open problem recently raised by Kim and
Wu (CRYPTO 2018).
– A NIZK based on the learning with errors (LWE) assumption, and
assuming a non-interactive witness-indistinguishable (NIWI) proof
system for bounded distance decoding (BDD). This simplifies and
improves upon a recent NIZK from LWE that assumes a NIZK for
BDD (Rothblum et al., CRYPTO 2018).