## 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.