Paper 2019/242

New Constructions of Reusable Designated-Verifier NIZKs

Alex Lombardi and Willy Quach and Ron D. Rothblum and Daniel Wichs and David J. Wu

Abstract

Non-interactive zero-knowledge arguments (NIZKs) for NP are an important cryptographic primitive, but we currently only have instantiations under a few specific assumptions. Notably, we are missing constructions from the plain learning with errors (LWE) assumption or the Diffie-Hellman (CDH/DDH) assumption. In this paper, we study a relaxation of NIZKs to the designated-verifier setting (DV-NIZK), where a trusted setup generates a common reference string together with a secret key for the verifier. We want reusable schemes, which allow the verifier to reuse the secret key to verify many different proofs, and soundness should hold even if the malicious prover learns whether various proofs are accepted or rejected. Such reusable DV-NIZKs were recently constructed under the CDH assumption, but it was open whether they can also be constructed under LWE. In this work, we give a new construction using generic primitives that can be instantiated under CDH or LWE. We also consider an extension of reusable DV-NIZKs to the malicious designated-verifier setting (MDV-NIZK). In this setting, the only trusted setup consists of a common random string. However, there is also an additional untrusted setup in which the verifier chooses a public/secret key needed to generate/verify proofs, respectively. We require that zero-knowledge holds even if the public key is chosen maliciously by the verifier. Such reusable MDV-NIZKs were recently constructed under the ``one-more CDH'' assumption. In this work, we give a new construction using generic primitives that can be instantiated under DDH or LWE.