Paper 2018/895

Weak Zero-Knowledge Beyond the Black-Box Barrier

Nir Bitansky, Dakshita Khurana, and Omer Paneth


The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box. 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.STOC 2019
zero knowledgenon-black-box techniquesfully-homomorphic encryption
Contact author(s)
nbitansky @ gmail com
2019-07-31: last of 4 revisions
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nir Bitansky and Dakshita Khurana and Omer Paneth},
      title = {Weak Zero-Knowledge Beyond the Black-Box Barrier},
      howpublished = {Cryptology ePrint Archive, Paper 2018/895},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.