CryptoDB
Towards Non-Interactive Zero-Knowledge for NP from LWE
| Authors: | |
|---|---|
| Download: | |
| Conference: | PKC 2019 |
| Abstract: | Non-interactive zero-knowledge ( $$\mathsf {NIZK}$$ ) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Despite this, general purpose constructions of $$\mathsf {NIZK}$$ proof systems are only known under a rather limited set of assumptions that are either number-theoretic (and can be broken by a quantum computer) or are not sufficiently well understood, such as obfuscation. Thus, a basic question that has drawn much attention is whether it is possible to construct general-purpose $$\mathsf {NIZK}$$ proof systems based on the learning with errors ( $$\mathsf {LWE}$$ ) assumption.Our main result is a reduction from constructing $$\mathsf {NIZK}$$ proof systems for all of $$\mathbf {NP}$$ based on $$\mathsf {LWE}$$ , to constructing a $$\mathsf {NIZK}$$ proof system for a particular computational problem on lattices, namely a decisional variant of the Bounded Distance Decoding ( $$\mathsf {BDD}$$ ) problem. That is, we show that assuming $$\mathsf {LWE}$$ , every language $$L \in \mathbf {NP}$$ has a $$\mathsf {NIZK}$$ proof system if (and only if) the decisional $$\mathsf {BDD}$$ problem has a $$\mathsf {NIZK}$$ proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008).To construct our $$\mathsf {NIZK}$$ proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling ( $$\mathsf {POCS}$$ ), which we believe to be of independent interest. This notion extends the idea of oblivious ciphertext sampling, which allows one to sample ciphertexts without knowing the underlying plaintext. Specifically, we augment the oblivious ciphertext sampler with access to an (untrusted) prover to help it accomplish this task. We show that the existence of encryption schemes with a $$\mathsf {POCS}$$ procedure, as well as some additional natural requirements, suffices for obtaining $$\mathsf {NIZK}$$ proofs for $$\mathbf {NP}$$ . We further show that such encryption schemes can be instantiated based on $$\mathsf {LWE}$$ , assuming the existence of a $$\mathsf {NIZK}$$ proof system for the decisional $$\mathsf {BDD}$$ problem. |
BibTeX
@inproceedings{pkc-2019-29310,
title={Towards Non-Interactive Zero-Knowledge for NP from LWE},
booktitle={Public-Key Cryptography – PKC 2019},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11443},
pages={472-503},
doi={10.1007/978-3-030-17259-6_16},
author={Ron D. Rothblum and Adam Sealfon and Katerina Sotiraki},
year=2019
}