We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions. Our main results are:
\begin{itemize} \item Weak zero-knowledge for $NP $in two messages, assuming quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known from quasipolynomial hardness of Learning with Errors), as well as subexponentially-secure one-way functions.
\item Weak zero-knowledge for $NP$ in three messages under standard polynomial assumptions (following for example from fully-homomorphic encryption and factoring).
\end{itemize}
We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language $L \in NP$ that has a witness encryption scheme. This protocol is also publicly verifiable.
Our technique is based on a new {\em homomorphic trapdoor paradigm}, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.
Category / Keywords: cryptographic protocols / zero knowledge, non-black-box techniques, fully-homomorphic encryption Original Publication (with minor differences): STOC 2019 Date: received 23 Sep 2018, last revised 31 Jul 2019 Contact author: nbitansky at gmail com Available format(s): PDF | BibTeX Citation Version: 20190731:084849 (All versions of this report) Short URL: ia.cr/2018/895