Article

Free access

The complexity of perfect zero-knowledge

Author:

L. FortnowAuthors Info & Claims

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

Pages 204 - 209

https://doi.org/10.1145/28395.28418

Published: 01 January 1987 Publication History

PDF eReader

Abstract

A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.

References

[1]

Babai, L., "Trading Group Theory for Randomness'', Proc. 17th STOC, 1985, pp. 421- 429.

Digital Library

Google Scholar

[2]

Boppana, R. and J. Hastad, "Does co-NP Have Short Interactive Proofs?", IPL, to appear.

Digital Library

Google Scholar

[3]

Brassard, G. and C. Cr6peau, "Non- Transitive Transfer of Confidence' A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond", Pvoc. z97th FOCS, 1986, pp. 188-195.

Google Scholar

[4]

Carter, J.L. and M.N. Wegman, "Universal Classes of Hash Functions", JC$$18 2, 1979, pp.143-154.

Google Scholar

[5]

Goldreich, O., S. Micali and A. Wigderson, "Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design", Proc. 27th FOCS, 1986, pp. 174-187.

Digital Library

Google Scholar

[6]

Goldwasser, S., S. Micali and C. Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proc. 17th $TOC, 1985, pp. 291-304.

Digital Library

Google Scholar

[7]

Goldwasser, S. and M. Sipser, "Private Coins versus Public Coins in Interactive Proof Systems'', Proc. 18ih STOC, 1986, pp. 59-68.

Digital Library

Google Scholar

[8]

Sipser, M., "A Complexity Theoretic Approach to Randomness", Proc. 15th STOC, 1983, pp. 330-335.

Digital Library

Google Scholar

Cited By

View all

Campanelli MGanesh CKhoshakhlagh HSiim J(2023)Impossibilities in Succinct Arguments: Black-Box Extraction and MoreProgress in Cryptology - AFRICACRYPT 202310.1007/978-3-031-37679-5_20(465-489)Online publication date: 13-Jul-2023
https://doi.org/10.1007/978-3-031-37679-5_20
E. Jansirani Dr. N. Kowsalya (2022)Using Zero-Knowledge Proof for Secure Data Transmission on Distributed NetworkInternational Journal of Scientific Research in Science and Technology10.32628/IJSRST229211(75-80)Online publication date: 10-Mar-2022
https://doi.org/10.32628/IJSRST229211
Hiroka TMorimae TNishimaki RYamakawa T(2022)Certified Everlasting Zero-Knowledge Proof for QMAAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_9(239-268)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15802-5_9
Show More Cited By

Index Terms

The complexity of perfect zero-knowledge

Recommendations

A study of perfect zero-knowledge proofs
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 ...
Languages with efficient zero-knowledge PCPs are in SZK
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of Cryptography

A Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computing

January 1987

471 pages

ISBN:0897912217

DOI:10.1145/28395

Editor:
Alfred V. Aho

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1987

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC87

Sponsor:

SIGACT

STOC87: 19th Annual ACM Conference on Theory of Computing

New York, New York, USA

Acceptance Rates

STOC '87 Paper Acceptance Rate 50 of 165 submissions, 30%;

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

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

101
Total Citations
View Citations
1,409
Total Downloads

Downloads (Last 12 months)251
Downloads (Last 6 weeks)24

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Campanelli MGanesh CKhoshakhlagh HSiim J(2023)Impossibilities in Succinct Arguments: Black-Box Extraction and MoreProgress in Cryptology - AFRICACRYPT 202310.1007/978-3-031-37679-5_20(465-489)Online publication date: 13-Jul-2023
https://doi.org/10.1007/978-3-031-37679-5_20
E. Jansirani Dr. N. Kowsalya (2022)Using Zero-Knowledge Proof for Secure Data Transmission on Distributed NetworkInternational Journal of Scientific Research in Science and Technology10.32628/IJSRST229211(75-80)Online publication date: 10-Mar-2022
https://doi.org/10.32628/IJSRST229211
Hiroka TMorimae TNishimaki RYamakawa T(2022)Certified Everlasting Zero-Knowledge Proof for QMAAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_9(239-268)Online publication date: 12-Oct-2022
https://doi.org/10.1007/978-3-031-15802-5_9
Ganesh CKhoshakhlagh HKohlweiss MNitulescu AZając M(2022)What Makes Fiat–Shamir zkSNARKs (Updatable SRS) Simulation Extractable?Security and Cryptography for Networks10.1007/978-3-031-14791-3_32(735-760)Online publication date: 5-Sep-2022
https://doi.org/10.1007/978-3-031-14791-3_32
Ganesh CKhoshakhlagh HParisella R(2022)NIWI and New Notions of Extraction for Algebraic LanguagesSecurity and Cryptography for Networks10.1007/978-3-031-14791-3_30(687-710)Online publication date: 5-Sep-2022
https://doi.org/10.1007/978-3-031-14791-3_30
Alikhani PBrunner NCrépeau CDesignolle SHoulmann RShi WYang NZbinden H(2021)Experimental relativistic zero-knowledge proofsNature10.1038/s41586-021-03998-y599:7883(47-50)Online publication date: 3-Nov-2021
https://doi.org/10.1038/s41586-021-03998-y
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
Khurana DMughees M(2020)On Statistical Security in Two-Party ComputationTheory of Cryptography10.1007/978-3-030-64378-2_19(532-561)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64378-2_19
Dixon PGayen SPavan AVinodchandran N(2020)Perfect Zero Knowledge: New Upperbounds and Relativized SeparationsTheory of Cryptography10.1007/978-3-030-64375-1_24(684-704)Online publication date: 9-Dec-2020
https://doi.org/10.1007/978-3-030-64375-1_24
Katzir LShikhelman CYogev E(2020)Interactive Proofs for Social GraphsAdvances in Cryptology – CRYPTO 202010.1007/978-3-030-56877-1_20(574-601)Online publication date: 17-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-56877-1_20
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

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

Cited By

Index Terms

Recommendations

A study of perfect zero-knowledge proofs

On efficient zero-knowledge PCPs

Languages with efficient zero-knowledge PCPs are in SZK