Article

Zero knowledge with efficient provers

Authors:

Minh-Huyen Nguyen,

Salil VadhanAuthors Info & Claims

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

Pages 287 - 295

https://doi.org/10.1145/1132516.1132559

Published: 21 May 2006 Publication History

Abstract

We prove that every problem in NP that has a zero-knowledge proof also has a zero-knowledge proof where the prover can be implemented in probabilistic polynomial time given an NP witness. Moreover, if the original proof system is statistical zero knowledge, so is the resulting efficient-prover proof system. An equivalence of zero knowledge and efficient-prover zero knowledge was previously known only under the assumption that one-way functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. Our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.

References

[1]

W. Aiello and J. Håstad. Statistical zero-knowledge languages can be recognized in two rounds. J. Comput. Syst. Sci., 42(3):327--345, June 1991.]]

Digital Library

[2]

L. Babai and S. Moran. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci., 36:254--276, 1988.]]

Digital Library

[3]

B. Barak. How to go beyond the black-box simulation barrier. Proc. of the 42nd FOCS, 2001.]]

Digital Library

[4]

M. Bellare and S. Goldwasser. The complexity of decision versus search. SIAM Journal on Computing, 23(1):97--119, Feb. 1994.]]

Digital Library

[5]

M. Bellare, S. Micali, and R. Ostrovsky. Perfect zero-knowledge in constant rounds. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 482--493, 1990.]]

Digital Library

[6]

M. Bellare and E. Petrank. Making zero-knowledge provers efficient. In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 711--722, 1992.]]

Digital Library

[7]

M. Ben-Or, O. Goldreich, S. Goldwasser, J. Håstad, J. Kilian, S. Micali, and P. Rogaway. Everything provable is provable in zero-knowledge, CRYPTO '88.]]

Digital Library

[8]

M. Blum. How to prove a theorem so no one else can claim it. In Proceedings of the International Congress of Mathematicians, Vol. 1, 2 (Berkeley, Calif., 1986), pages 1444--1451, Providence, RI, 1987.]]

[9]

T. M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc., 2nd edition, 1991.]]

Digital Library

[10]

Y. Ding, D. Harnik, A. Rosen, and R. Shaltiel. Constant-round oblivious transfer in the bounded storage model. In Proceedings of the First Theory of Cryptography Conference, pages 446--472, 2004.]]

[11]

S. Even, A. L. Selman, and Y. Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159--173, May 1984.]]

Digital Library

[12]

L. Fortnow. The complexity of perfect zero-knowledge. In S. Micali, editor, Advances in Computing Research, volume 5, pages 327--343. JAC Press, Inc., 1989.]]

[13]

O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, 2001.]]

Digital Library

[14]

O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(1):691--729, 1991.]]

Digital Library

[15]

O. Goldreich, A. Sahai, and S. Vadhan. Honest verifier statistical zero-knowledge equals general statistical zero-knowledge. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 399--408, Dallas, 23--26 May 1998.]]

Digital Library

[16]

O. Goldreich, A. Sahai, and S. Vadhan. Can statistical zero-knowledge be made non-interactive?, or On the relationship of SZK and NISZK. In Advances in Cryptology---CRYPTO '99.]]

Digital Library

[17]

O. Goldreich and S. Vadhan. Comparing entropies in statistical zero-knowledge with applications to the structure of SZK. In Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, pages 54--73, 1999.]]

Digital Library

[18]

S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186--208, February 1989.]]

Digital Library

[19]

S. Goldwasser and M. Sipser. Private coins versus public coins in interactive proof systems. In S. Micali, editor, Advances in Computing Research, volume 5, pages 73--90. JAC Press, Inc., 1989.]]

[20]

J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364--1396 (electronic), 1999.]]

Digital Library

[21]

R. Impagliazzo and M. Yung. Direct minimum-knowledge computations. In Advances in Cryptology---CRYPTO '87, pages 40--51.]]

Digital Library

[22]

T. Itoh, Y. Ohta, and H. Shizuya. A language-dependent cryptographic primitive. Journal of Cryptology, 10(1):37--49, 1997.]]

Digital Library

[23]

A. R. Klivans and D. van Melkebeek. Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. In Proceedings of the Thirty-first Annual ACM Symposium on Theory of Computing, pages 659--667, 1999.]]

Digital Library

[24]

D. Micciancio and S. Vadhan. Statistical zero-knowledge proofs with efficient provers: lattice problems and more. In D. Boneh, editor, Advances in Cryptology---CRYPTO '03, pages 282--298.]]

[25]

P. B. Miltersen and N. V. Vinodchandran. Derandomizing arthur-merlin games using hitting sets. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS '99), pages 71--80, 1999.]]

Digital Library

[26]

M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology, 4(2):151--158, 1991.]]

Digital Library

[27]

M. Naor, R. Ostrovsky, R. Venkatesan, and M. Yung. Perfect zero-knowledge arguments for np using any one-way permutation. Journal of Cryptology, 11(2):87--108, 1998.]]

Digital Library

[28]

T. Okamoto. On relationships between statistical zero-knowledge proofs. Journal of Computer and System Sciences, 60(1):47--108, February 2000.]]

Digital Library

[29]

R. Ostrovsky. One-way functions, hard on average problems, and statistical zero-knowledge proofs. In Proceedings of the Sixth Annual Structure in Complexity Theory Conference, pages 133--138, 1991.]]

[30]

R. Ostrovsky and A. Wigderson. One-way functions are essential for non-trivial zero-knowledge. In Proceedings of the Second Israel Symposium on Theory of Computing and Systems, 1993.]]

[31]

A. Sahai and S. Vadhan. A complete problem for statistical zero knowledge. Journal of the ACM, 50(2):196--249, March 2003.]]

Digital Library

[32]

S. P. Vadhan. A Study of Statistical Zero-Knowledge Proofs. PhD thesis, Massachusetts Institute of Technology, August 1999.]]

Digital Library

[33]

S. P. Vadhan. On transformations of interactive proofs that preserve the prover's complexity. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 200--207, Portland, OR, May 2000.]]

Digital Library

[34]

S. P. Vadhan. An unconditional study of computational zero knowledge. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS '04), pages 176--185.]]

Digital Library

Cited By

Mu CNassar SRothblum RVasudevan P(2024)Strong Batching for Non-interactive Statistical Zero-KnowledgeAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_9(241-270)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_9
Kaslasi IRothblum RVasudevanr P(2021)Public-Coin Statistical Zero-Knowledge Batch Verification Against Malicious VerifiersAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77883-5_8(219-246)Online publication date: 16-Jun-2021
https://doi.org/10.1007/978-3-030-77883-5_8
Kaslasi IRothblum GRothblum RSealfon AVasudevan P(2020)Batch Verification for Statistical Zero Knowledge ProofsTheory of Cryptography10.1007/978-3-030-64378-2_6(139-167)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64378-2_6
Show More Cited By

Index Terms

Zero knowledge with efficient provers
1. Theory of computation
  1. Models of computation
    1. Interactive computation

Recommendations

An Unconditional Study of Computational Zero Knowledge

We prove a number of general theorems about ZK, the class of problems possessing (computational) zero-knowledge proofs. Our results are unconditional, in contrast to most previous works on ZK, which rely on the assumption that one-way functions exist. ...
On efficient zero-knowledge PCPs
TCC'12: Proceedings of the 9th international conference on Theory of Cryptography

We revisit the question of Zero-Knowledge PCPs, studied by Kilian, Petrank, and Tardos (STOC '97). A ZK-PCP is defined similarly to a standard PCP, except that the view of any (possibly malicious) verifier can be efficiently simulated up to a small ...
Definitions and properties of zero-knowledge proof systems

In this paper we investigate some properties of zero-knowledge proofs, a notion introduced by Goldwasser, Micali, and Rackoff. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '06: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing

May 2006

786 pages

ISBN:1595931341

DOI:10.1145/1132516

Program Chair:
Jon Kleinberg
Cornell University, Ithaca, NY

Copyright © 2006 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC06

Sponsor:

STOC06: Symposium on Theory of Computing

May 21 - 23, 2006

WA, Seattle, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

35
Total Citations
View Citations
495
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mu CNassar SRothblum RVasudevan P(2024)Strong Batching for Non-interactive Statistical Zero-KnowledgeAdvances in Cryptology – EUROCRYPT 202410.1007/978-3-031-58751-1_9(241-270)Online publication date: 26-May-2024
https://dl.acm.org/doi/10.1007/978-3-031-58751-1_9
Kaslasi IRothblum RVasudevanr P(2021)Public-Coin Statistical Zero-Knowledge Batch Verification Against Malicious VerifiersAdvances in Cryptology – EUROCRYPT 202110.1007/978-3-030-77883-5_8(219-246)Online publication date: 16-Jun-2021
https://doi.org/10.1007/978-3-030-77883-5_8
Kaslasi IRothblum GRothblum RSealfon AVasudevan P(2020)Batch Verification for Statistical Zero Knowledge ProofsTheory of Cryptography10.1007/978-3-030-64378-2_6(139-167)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64378-2_6
Vadhan S(2019)Computational entropyProviding Sound Foundations for Cryptography10.1145/3335741.3335767(693-726)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335741.3335767
Micciancio D(2019)Interactive proofs for lattice problemsProviding Sound Foundations for Cryptography10.1145/3335741.3335763(565-597)Online publication date: 4-Oct-2019
https://dl.acm.org/doi/10.1145/3335741.3335763
Chen YGöös MVadhan SZhang JServedio R(2018)A tight lower bound for entropy flatteningProceedings of the 33rd Computational Complexity Conference10.5555/3235586.3235609(1-28)Online publication date: 22-Jun-2018
https://dl.acm.org/doi/10.5555/3235586.3235609
Berman IDegwekar ARothblum RVasudevan P(2018)From Laconic Zero-Knowledge to Public-Key CryptographyAdvances in Cryptology – CRYPTO 201810.1007/978-3-319-96878-0_23(674-697)Online publication date: 19-Aug-2018
https://dl.acm.org/doi/10.1007/978-3-319-96878-0_23
Alamati NPeikert CStephens-Davidowitz N(2018)New (and Old) Proof Systems for Lattice ProblemsPublic-Key Cryptography – PKC 201810.1007/978-3-319-76581-5_21(619-643)Online publication date: 1-Mar-2018
https://doi.org/10.1007/978-3-319-76581-5_21
Ning ZJinfu Z(2015)Study on Image Compression and Fusion Based on the Wavelet Transform TechnologyInternational Journal on Smart Sensing and Intelligent Systems10.21307/ijssis-2017-7688:1(480-496)Online publication date: 1-Mar-2015
https://doi.org/10.21307/ijssis-2017-768
Malka L(2015)How to Achieve Perfect Simulation and a Complete Problem for Non-interactive Perfect Zero-KnowledgeJournal of Cryptology10.1007/s00145-013-9165-628:3(533-550)Online publication date: 1-Jul-2015
https://dl.acm.org/doi/10.1007/s00145-013-9165-6
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents