research-article

Public Access

Weak zero-knowledge beyond the black-box barrier

Authors:

Dakshita Khurana,

Omer PanethAuthors Info & Claims

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

Pages 1091 - 1102

https://doi.org/10.1145/3313276.3316382

Published: 23 June 2019 Publication History

Abstract

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. We obtain weak zero-knowledge for 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 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 ∈ 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.

References

[1]

William Aiello and Johan Håstad. 1991. Statistical Zero-Knowledge Languages can be Recognized in Two Rounds. J. Comput. Syst. Sci. 42, 3 (1991), 327–345.

Digital Library

[2]

William Aiello, Yuval Ishai, and Omer Reingold. 2001. Priced Oblivious Transfer: How to Sell Digital Goods. In EUROCRYPT (Lecture Notes in Computer Science), Vol. 2045. Springer, 119–135.

Digital Library

[3]

Prabhanjan Ananth and Abhishek Jain. 2017. On Secure Two-Party Computation in Three Rounds. In Theory of Cryptography - 15th International Conference, TCC Weak Zero-Knowledge Beyond the Black-Box Barrier STOC ’19, June 23–26, 2019, Phoenix, AZ, USA 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part I. 612–644.

[4]

Saikrishna Badrinarayanan, Sanjam Garg, Yuval Ishai, Amit Sahai, and Akshay Wadia. 2017. Two-Message Witness Indistinguishability and Secure Computation in the Plain Model from New Assumptions. In Advances in Cryptology - ASIACRYPT 2017. 275–303.

[5]

Boaz Barak. 2001. How to Go Beyond the Black-Box Simulation Barrier. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. 106–115.

Digital Library

[6]

Boaz Barak, Shien Jin Ong, and Salil P. Vadhan. 2007. Derandomization in Cryptography. SIAM J. Comput. 37, 2 (2007), 380–400. 050641958

[7]

Boaz Barak and Rafael Pass. 2004. On the Possibility of One-Message Weak Zero-Knowledge. In Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19-21, 2004, Proceedings. 121–132.

[8]

Mihir Bellare, Markus Jakobsson, and Moti Yung. 1997. Round-Optimal Zero-Knowledge Arguments Based on any One-Way Function. In Advances in Cryptology - EUROCRYPT ’97. 280–305.

[9]

Mihir Bellare and Adriana Palacio. 2004. Towards Plaintext-Aware Public-Key Encryption Without Random Oracles. In ASIACRYPT. 48–62.

[10]

Mihir Bellare, Igors Stepanovs, and Stefano Tessaro. 2016. Contention in Cryptoland: Obfuscation, Leakage and UCE. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part II. 542–564.

[11]

Nir Bitansky, Zvika Brakerski, Yael Tauman Kalai, Omer Paneth, and Vinod Vaikuntanathan. 2016. 3-Message Zero Knowledge Against Human Ignorance. In Theory of Cryptography - 14th International Conference, TCC 2016-B, Beijing, China, October 31 - November 3, 2016, Proceedings, Part I. 57–83.

Digital Library

[12]

Nir Bitansky, Ran Canetti, Alessandro Chiesa, Shafi Goldwasser, Huijia Lin, Aviad Rubinstein, and Eran Tromer. 2017. The Hunting of the SNARK. J. Cryptology 30, 4 (2017), 989–1066.

Digital Library

[13]

Nir Bitansky, Ran Canetti, Omer Paneth, and Alon Rosen. 2014. On the existence of extractable one-way functions. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31 - June 03, 2014. 505–514. 1145/2591796.2591859

Digital Library

[14]

Nir Bitansky, Yael Tauman Kalai, and Omer Paneth. 2018. Multi-collision resistance: a paradigm for keyless hash functions. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018. 671–684.

Digital Library

[15]

Nir Bitansky and Huijia Lin. 2018. One-Message Zero Knowledge and Non-Malleable Commitments. In Theory of Cryptography Conference, TCC 2018, Goa, India, November 11-14, 2018, Proceedings.

[16]

Nir Bitansky and Omer Paneth. 2012. Point Obfuscation and 3-Round Zero-Knowledge. In Theory of Cryptography - 9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings. 190–208.

Digital Library

[17]

Nir Bitansky and Omer Paneth. 2015. On Non-Black-Box Simulation and the Impossibility of Approximate Obfuscation. SIAM J. Comput. 44, 5 (2015), 1325– 1383.

Digital Library

[18]

Nir Bitansky and Omer Paneth. 2015. ZAPs and Non-Interactive Witness Indistinguishability from Indistinguishability Obfuscation. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part II. 401–427.

[19]

Manuel Blum and Silvio Micali. 1984. How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits. SIAM J. Comput. 13, 4 (1984), 850–864.

Digital Library

[20]

Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, and Amit Sahai. 2013. Secure Computation against Adaptive Auxiliary Information. In Advances in Cryptology - CRYPTO 2013. 316–334. 18

[21]

Elette Boyle and Rafael Pass. 2015. Limits of Extractability Assumptions with Distributional Auxiliary Input. In Advances in Cryptology - ASIACRYPT 2015.

Digital Library

[22]

Zvika Brakerski and Nico Döttling. 2018. Two-Message Statistical Sender-Private OT from LWE. IACR Cryptology ePrint Archive 2018 (2018), 530. https://eprint. iacr.org/2018/530

[23]

Zvika Brakerski and Vinod Vaikuntanathan. 2014. Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. SIAM J. Comput. 43, 2 (2014), 831–871.

[24]

Christina Brzuska and Arno Mittelbach. 2014. Indistinguishability Obfuscation versus Multi-bit Point Obfuscation with Auxiliary Input. In Advances in Cryptology - ASIACRYPT 2014. 142–161.

[25]

Yilei Chen, Vinod Vaikuntanathan, and Hoeteck Wee. 2018. GGH15 Beyond Permutation Branching Programs: Proofs, Attacks, and Candidates. In Advances in Cryptology - CRYPTO 2018. 577–607. 20

[26]

Kai-Min Chung, Huijia Lin, and Rafael Pass. 2013. Constant-Round Concurrent Zero Knowledge from P-Certificates. In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, 26-29 October, 2013, Berkeley, CA, USA. 50–59.

Digital Library

[27]

Kai-Min Chung, Edward Lui, and Rafael Pass. 2015. From Weak to Strong Zero-Knowledge and Applications. In Theory of Cryptography - 12th Theory of Cryptography Conference, TCC 2015, Warsaw, Poland, March 23-25, 2015, Proceedings, Part I. 66–92.

[28]

Kai-Min Chung, Rafael Pass, and Karn Seth. 2016. Non-Black-Box Simulation from One-Way Functions and Applications to Resettable Security. SIAM J. Comput. 45, 2 (2016), 415–458.

Digital Library

[29]

Ronald Cramer and Victor Shoup. 2002. Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In Advances in Cryptology - EUROCRYPT 2002. 45–64.

Digital Library

[30]

Yi Deng, Vipul Goyal, and Amit Sahai. 2009. Resolving the Simultaneous Resettability Conjecture and a New Non-Black-Box Simulation Strategy. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA. 251–260.

Digital Library

[31]

Cynthia Dwork and Moni Naor. 2007. Zaps and Their Applications. SIAM J. Comput. 36, 6 (2007), 1513–1543.

Digital Library

[32]

Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. 2003. Magic Functions. J. ACM 50, 6 (2003), 852–921.

Digital Library

[33]

Uriel Feige, Dror Lapidot, and Adi Shamir. 1999. Multiple NonInteractive Zero Knowledge Proofs Under General Assumptions. SIAM J. Comput. 29, 1 (1999), 1–28.

Digital Library

[34]

Uriel Feige and Adi Shamir. 1990. Witness Indistinguishable and Witness Hiding Protocols. In Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, May 13-17, 1990, Baltimore, Maryland, USA. 416–426.

Digital Library

[35]

Nils Fleischhacker, Vipul Goyal, and Abhishek Jain. 2018. On the Existence of Three Round Zero-Knowledge Proofs. In Advances in Cryptology - EUROCRYPT 2018. 3–33.

[36]

Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters. 2016. Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits. SIAM J. Comput. 45, 3 (2016), 882–929.

Digital Library

[37]

Sanjam Garg, Craig Gentry, Amit Sahai, and Brent Waters. 2013. Witness encryption and its applications. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. 467–476. 2488608.2488667

Digital Library

[38]

Craig Gentry. 2009. A fully homomorphic encryption scheme. Ph.D. Dissertation. Stanford University. crypto.stanford.edu/craig.

Digital Library

[39]

Craig Gentry. 2009. Fully homomorphic encryption using ideal lattices. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009. 169–178. 1536414.1536440

Digital Library

[40]

Oded Goldreich and Hugo Krawczyk. 1996. On the Composition of Zero-Knowledge Proof Systems. SIAM J. Comput. 25, 1 (1996), 169–192.

Digital Library

[41]

Oded Goldreich, Silvio Micali, and Avi Wigderson. 1991. Proofs that Yield Nothing But Their Validity for All Languages in NP Have Zero-Knowledge Proof Systems. J. ACM 38, 3 (1991), 691–729.

Digital Library

[42]

Oded Goldreich and Yair Oren. 1994. Definitions and Properties of Zero-Knowledge Proof Systems. J. Cryptology 7, 1 (1994), 1–32.

Digital Library

[43]

Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1989. The Knowledge Complexity of Interactive Proof Systems. SIAM J. Comput. 18, 1 (1989), 186–208.

Digital Library

[44]

Rishab Goyal, Susan Hohenberger, Venkata Koppula, and Brent Waters. 2017. A Generic Approach to Constructing and Proving Verifiable Random Functions. In Theory of Cryptography - 15th International Conference, TCC 2017, Baltimore, MD, USA, November 12-15, 2017, Proceedings, Part II. 537–566. 978-3-319-70503-3_18

[45]

Rishab Goyal, Venkata Koppula, and Brent Waters. 2017. Lockable Obfuscation. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. 612–621. 2017.62

[46]

Vipul Goyal. 2013. Non-black-box simulation in the fully concurrent setting. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013. 221–230.

Digital Library

[47]

Jens Groth, Rafail Ostrovsky, and Amit Sahai. 2012. New Techniques for Noninteractive Zero-Knowledge. J. ACM 59, 3 (2012), 11:1–11:35.

Digital Library

[48]

Satoshi Hada and Toshiaki Tanaka. 1998. On the Existence of 3-Round Zero-Knowledge Protocols. In Proceedings of the 18th Annual International Cryptology Conference. 408–423.

Digital Library

[49]

Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, and Erez Petrank. 2011. Black-Box Constructions of Protocols for Secure Computation. SIAM J. STOC ’19, June 23–26, 2019, Phoenix, AZ, USA Nir Bitansky, Dakshita Khurana, and Omer Paneth Comput. 40, 2 (2011), 225–266.

Digital Library

[50]

Iftach Haitner, Alon Rosen, and Ronen Shaltiel. 2009. On the (Im)Possibility of Arthur-Merlin Witness Hiding Protocols. In Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings. 220–237.

Digital Library

[51]

Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. 1999. A Pseudorandom Generator from any One-way Function. SIAM J. Comput. 28, 4 (1999), 1364–1396.

Digital Library

[52]

Pavel Hubáček and Daniel Wichs. 2015. On the Communication Complexity of Secure Function Evaluation with Long Output. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015. 163–172.

Digital Library

[53]

Abhishek Jain, Yael Tauman Kalai, Dakshita Khurana, and Ron Rothblum. 2017. Distinguisher-Dependent Simulation in Two Rounds and its Applications. In Advances in Cryptology - CRYPTO 2017. 158–189. 978-3-319-63715-0_6

[54]

Jonathan Katz. 2012. Which Languages Have 4-Round Zero-Knowledge Proofs? J. Cryptology 25, 1 (2012), 41–56.

Digital Library

[55]

Moni Naor. 1991. Bit Commitment Using Pseudorandomness. J. Cryptology 4, 2 (1991), 151–158.

Digital Library

[56]

Rafail Ostrovsky, Anat Paskin-Cherniavsky, and Beni Paskin-Cherniavsky. 2014. Maliciously Circuit-Private FHE. In Advances in Cryptology - CRYPTO 2014. 536– 553.

[57]

Rafael Pass. 2003. Simulation in Quasi-Polynomial Time, and Its Application to Protocol Composition. In Advances in Cryptology - EUROCRYPT 2003. 160–176.

Digital Library

[58]

Amit Sahai and Salil P. Vadhan. 1997. A Complete Promise Problem for Statistical Zero-Knowledge. In 38th Annual Symposium on Foundations of Computer Science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997. 448–457. org/10.1109/SFCS.1997.646133

Digital Library

Cited By

Lou PManohar NSahai A(2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58740-5_6
Deng YZhang X(2023)Knowledge Encryption and Its Applications to Simulatable Protocols with Low Round-ComplexityAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_12(334-362)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-22969-5_12
Bitansky NFreizeit S(2022)Statistically Sender-Private OT from LPN and DerandomizationAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_21(625-653)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15982-4_21
Show More Cited By

Index Terms

Weak zero-knowledge beyond the black-box barrier
1. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography
2. Theory of computation
  1. Computational complexity and cryptography
    1. Cryptographic protocols

Recommendations

Weak Zero-Knowledge beyond the Black-Box Barrier

The round complexity of zero-knowledge protocols is a long-standing open question and is 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. ...
New and improved constructions of non-malleable cryptographic protocols
STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

We present a new constant round protocol for non-malleable zero-knowledge. Using this protocol as a subroutine, we obtain a new constant-round protocol for non-malleable commitments. Our constructions rely on the existence of (standard) collision ...
Zero-knowledge from secure multiparty computation
STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing

We present a general construction of a zero-knowledge proof for an NP relation R(x,w) which only makes a black-box use of a secure protocol for a related multi-partyfunctionality f. The latter protocol is only required to be secure against a small ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

June 2019

1258 pages

ISBN:9781450367059

DOI:10.1145/3313276

General Chair:
Moses Charikar
Stanford University
,
Program Chair:
Edith Cohen
Google, USA / Tel Aviv University, Israel

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '19

Sponsor:

SIGACT

STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing

June 23 - 26, 2019

AZ, Phoenix, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

20
Total Citations
View Citations
489
Total Downloads

Downloads (Last 12 months)114
Downloads (Last 6 weeks)14

Reflects downloads up to 19 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lou PManohar NSahai A(2024)Witness Semantic SecurityAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58740-5_6(155-184)Online publication date: 29-Apr-2024
https://doi.org/10.1007/978-3-031-58740-5_6
Deng YZhang X(2023)Knowledge Encryption and Its Applications to Simulatable Protocols with Low Round-ComplexityAdvances in Cryptology – ASIACRYPT 202210.1007/978-3-031-22969-5_12(334-362)Online publication date: 25-Jan-2023
https://doi.org/10.1007/978-3-031-22969-5_12
Bitansky NFreizeit S(2022)Statistically Sender-Private OT from LPN and DerandomizationAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15982-4_21(625-653)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15982-4_21
Kiyoshima S(2022)Public-Coin 3-Round Zero-Knowledge from Learning with Errors and Keyless Multi-Collision-Resistant HashAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_16(444-473)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15802-5_16
Kluczniak K(2022)Lockable Obfuscation from Circularly Insecure Fully Homomorphic EncryptionPublic-Key Cryptography – PKC 202210.1007/978-3-030-97131-1_3(69-98)Online publication date: 27-Feb-2022
https://doi.org/10.1007/978-3-030-97131-1_3
VISCONTI IPointcheval D(2022)Zero‐Knowledge ProofsAsymmetric Cryptography10.1002/9781394188369.ch3(63-84)Online publication date: 30-Nov-2022
https://doi.org/10.1002/9781394188369.ch3
Chardouvelis OMalavolta G(2021)The Round Complexity of Quantum Zero-KnowledgeTheory of Cryptography10.1007/978-3-030-90459-3_5(121-148)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_5
Bitansky NKellner MShmueli O(2021)Post-quantum Resettably-Sound Zero KnowledgeTheory of Cryptography10.1007/978-3-030-90459-3_3(62-89)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_3
Kiyoshima S(2021)Black-Box Impossibilities of Obtaining 2-Round Weak ZK and Strong WI from Polynomial HardnessTheory of Cryptography10.1007/978-3-030-90459-3_13(369-400)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90459-3_13
Chia NChung KYamakawa T(2021)A Black-Box Approach to Post-Quantum Zero-Knowledge in Constant RoundsAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84242-0_12(315-345)Online publication date: 11-Aug-2021
https://doi.org/10.1007/978-3-030-84242-0_12
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents