TY - GEN

T1 - Weak zero-knowledge beyond the black-box barrier

AU - Bitansky, Nir

AU - Khurana, Dakshita

AU - Paneth, Omer

N1 - Funding Information:
N. Bitansky is supported by the Alon Young Faculty Fellowship, by Len Blavatnik and the Blavatnik Family foundation, and an ISF grant 18/484. O. Paneth is supported by NSF Grants CNS-1350619 and CNS-1414119, and the Defense Advanced Research Projects Agency (DARPA) and the U.S. Army Research Office under contracts W911NF-15-C-0226 and W911NF-15-C-0236.Any opinions, findings and conclusions or recommendations expressed are those of the author(s) and do not necessarily reflect the views of the DARPA and ARO.
Publisher Copyright:
© 2019 Association for Computing Machinery.

PY - 2019/6/23

Y1 - 2019/6/23

N2 - The round complexity of zero-knowledge protocols is a longstanding 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. We obtain weak zero-knowledge for NP in two messages, assuming the existence of quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known based on the quasipolynomial hardness of Learning with Errors), and subexponentially-secure one-way functions. We also obtain weak zero-knowledge for NP in three messages under standard polynomial assumptions (following for example from fully homomorphic encryption and factoring). We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language L ∈ NP that has a witness encryption scheme. This protocol is publicly verifiable. Our technique is based on a new homomorphic trapdoor paradigm, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.

AB - The round complexity of zero-knowledge protocols is a longstanding 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. We obtain weak zero-knowledge for NP in two messages, assuming the existence of quasipolynomially-secure fully-homomorphic encryption and other standard primitives (known based on the quasipolynomial hardness of Learning with Errors), and subexponentially-secure one-way functions. We also obtain weak zero-knowledge for NP in three messages under standard polynomial assumptions (following for example from fully homomorphic encryption and factoring). We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language L ∈ NP that has a witness encryption scheme. This protocol is publicly verifiable. Our technique is based on a new homomorphic trapdoor paradigm, which can be seen as a non-black-box analog of the classic Feige-Lapidot-Shamir trapdoor paradigm.

KW - Homomorphic trapdoor

KW - Non black-box simulation

KW - Witness hiding

KW - Zero-knowledge

UR - http://www.scopus.com/inward/record.url?scp=85068752680&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85068752680&partnerID=8YFLogxK

U2 - 10.1145/3313276.3316382

DO - 10.1145/3313276.3316382

M3 - Conference contribution

AN - SCOPUS:85068752680

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 1091

EP - 1102

BT - STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing

A2 - Charikar, Moses

A2 - Cohen, Edith

PB - Association for Computing Machinery

T2 - 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019

Y2 - 23 June 2019 through 26 June 2019

ER -