Paper 2018/548
From Laconic Zero-Knowledge to Public-Key Cryptography
Itay Berman, Akshay Degwekar, Ron D. Rothblum, and Prashant Nalini Vasudevan
Abstract
Since its inception, public-key encryption (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 the intersection of NP and SZK. 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 NP 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 NP 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 PKE which, in particular, captures many of the assumptions that were already known to yield 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 PKE, thereby giving a complexity-theoretic characterization of PKE. Second, a mild strengthening of our assumption also yields a (2-message) oblivious transfer protocol.
Metadata
- Available format(s)
- Publication info
- Published by the IACR in CRYPTO 2018
- Keywords
- Public Key Cryptographyzero knowledge
- Contact author(s)
-
itayberm @ mit edu
akshayd @ mit edu
ronr @ mit edu
prashvas @ mit edu - History
- 2018-06-04: received
- Short URL
- https://ia.cr/2018/548
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/548, author = {Itay Berman and Akshay Degwekar and Ron D. Rothblum and Prashant Nalini Vasudevan}, title = {From Laconic Zero-Knowledge to Public-Key Cryptography}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/548}, year = {2018}, url = {https://eprint.iacr.org/2018/548} }