CryptoDB
Toward Non-interactive Zero-Knowledge Proofs for NP from LWE
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Non-interactive zero-knowledge ( $$\mathsf {NIZK}$$ NIZK ) is a fundamental primitive that is widely used in the construction of cryptographic schemes and protocols. Our main result is a reduction from constructing $$\mathsf {NIZK}$$ NIZK proof systems for all of $$\mathbf {NP}$$ NP based on $$\mathsf {LWE}$$ LWE , to constructing a $$\mathsf {NIZK}$$ NIZK proof system for a particular computational problem on lattices, namely a decisional variant of the bounded distance decoding ( $$\mathsf {BDD}$$ BDD ) problem. That is, we show that assuming $$\mathsf {LWE}$$ LWE , every language $$L \in \mathbf {NP}$$ L ∈ NP has a $$\mathsf {NIZK}$$ NIZK proof system if (and only if) the decisional $$\mathsf {BDD}$$ BDD problem has a $$\mathsf {NIZK}$$ NIZK proof system. This (almost) confirms a conjecture of Peikert and Vaikuntanathan (CRYPTO, 2008). To construct our $$\mathsf {NIZK}$$ NIZK proof system, we introduce a new notion that we call prover-assisted oblivious ciphertext sampling ( $$\mathsf {POCS}$$ 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}$$ POCS procedure, as well as some additional natural requirements, suffices for obtaining $$\mathsf {NIZK}$$ NIZK proofs for $$\mathbf {NP}$$ NP . We further show that such encryption schemes can be instantiated based on $$\mathsf {LWE}$$ LWE , assuming the existence of a $$\mathsf {NIZK}$$ NIZK proof system for the decisional $$\mathsf {BDD}$$ BDD problem. |
BibTeX
@article{jofc-2021-31789,
title={Toward Non-interactive Zero-Knowledge Proofs for NP from LWE},
journal={Journal of Cryptology},
publisher={Springer},
volume={34},
doi={10.1007/s00145-020-09365-w},
author={Ron D. Rothblum and Adam Sealfon and Katerina Sotiraki},
year=2021
}