From Laconic Zero-Knowledge to Public-Key Cryptography

by Itay Berman, Akshay Degwekar, Ron Rothblum, and Prashant Nalini Vasudevan

Oded's comments

This work relates versions of statistical zero-knowledge (SZK) to the existence of secure public-key encryption schemes. The main result transforms a proof system for a ``hard'' promise problem into a secure public-key encyption scheme, where hardness is in a sense analogous to one-way functions, and the proof system should have an efficient prover that sends very few bits, and be statistical zero-knowledge (but only with respect to the honest verifier). Furthermore, it suffices that the proof system be computationally-sound (only). A weakening of the hypothesis is shown to be equivalent to the existence of secure public-key encyption schemes, whereas a strengthening yields 2-round oblivious transfer.

The original 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 $L \in NP \cap 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.

See ECCC TR17-172.


Back to list of Oded's choices.