Cryptology ePrint Archive: Report 2019/236

Designated-verifier pseudorandom generators, and their applications

Geoffroy Couteau and Dennis Hofheinz

Abstract: 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 instantiations:

– 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., PKC 2019).

Category / Keywords: foundations / non-interactive zero-knowledge, computational Diffie-Hellman, learning with errors, verifiable pseudorandom generators

Original Publication (with minor differences): IACR-EUROCRYPT-2019

Date: received 27 Feb 2019

Contact author: geoffroy couteau at kit edu, dennis hofheinz@kit edu

Available format(s): PDF | BibTeX Citation

Version: 20190228:190649 (All versions of this report)

Short URL: ia.cr/2019/236


[ Cryptology ePrint archive ]