CryptoDB
From Laconic Zero-Knowledge to Public-Key Cryptography
| Authors: | |
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | CRYPTO 2018 |
| Abstract: | Since its inception, public-key encryption ( $$\mathsf {PKE}$$ PKE) has been one of the main cornerstones of cryptography. A central goal in cryptographic research is to understand the foundations of public-key encryption and in particular, base its existence on a natural and generic complexity-theoretic assumption. An intriguing candidate for such an assumption is the existence of a cryptographically hard language .In this work we prove that public-key encryption can be based on the foregoing assumption, as long as the (honest) prover in the zero-knowledge protocol is efficient and laconic. That is, messages that the prover sends should be efficiently computable (given the witness) and short (i.e., of sufficiently sub-logarithmic length). Actually, our result is stronger and only requires the protocol to be zero-knowledge for an honest-verifier and sound against computationally bounded cheating provers.Languages in with such laconic zero-knowledge protocols are known from a variety of computational assumptions (e.g., Quadratic Residuocity, Decisional Diffie-Hellman, Learning with Errors, etc.). Thus, our main result can also be viewed as giving a unifying framework for constructing $$\mathsf {PKE}$$ PKE which, in particular, captures many of the assumptions that were already known to yield $$\mathsf {PKE}$$ PKE.We also show several extensions of our result. First, that a certain weakening of our assumption on laconic zero-knowledge is actually equivalent to $$\mathsf {PKE}$$ PKE, thereby giving a complexity-theoretic characterization of $$\mathsf {PKE}$$ PKE. Second, a mild strengthening of our assumption also yields a (2-message) oblivious transfer protocol. |
Video from CRYPTO 2018
BibTeX
@inproceedings{crypto-2018-28803,
title={From Laconic Zero-Knowledge to Public-Key Cryptography},
booktitle={Advances in Cryptology – CRYPTO 2018},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={10993},
pages={674-697},
doi={10.1007/978-3-319-96878-0_23},
author={Itay Berman and Akshay Degwekar and Ron D. Rothblum and Prashant Nalini Vasudevan},
year=2018
}