article

Free access

Algebraic methods for interactive proof systems

Authors:

Howard Karloff,

Noam NisanAuthors Info & Claims

Journal of the ACM (JACM), Volume 39, Issue 4

Pages 859 - 868

https://doi.org/10.1145/146585.146605

Published: 01 October 1992 Publication History

Abstract

A new algebraic technique for the construction of interactive proof systems is presented. Our technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. This technique played a pivotal role in the recent proofs that IP = PSPACE [28] and that MIP = NEXP [4].

References

[1]

~AIELLO, W., GOLDWASSER, S., AND H~xSTAD, J. On the power of interaction. Combinatorica, ~10, 1 (1992), 3-25.

[2]

~BAUAI, L. Trading group theory for randomness. In Proceedings' of the 17th Annual ACM ~Symposium on the Theory of Computing (Providence, R.I., May 6 8). ACM, New York, 1985, ~pp. 421-429.

[3]

~BABAI, L., AND FORTNOW, L. Arithmetization: a new method in structural complexity theory. ~Computat. Complex. 1 (1991), 41-66.

[4]

~BABAI, L., FORTNOW, L. AND LUND, C. Non-deterministic exponential time has two-prover ~interactive protocols. Comp,tat. Complex. I (1991), 3-40.

[5]

~BABAI, L., AND MORAN, S. Arthur-Merlin games: A randomized proof system, and a ~hierarchy of complexity classes. J. Co,zput. Syst. Sci. 36 2 (1988), 254-276.

[6]

~BEAVER, D. AND FEIGENBAUM, J. Hiding instances in multioracle queries. In Proceedings of ~the 7th Symposium on the Theoretical Aspects of Computer Sctence. Lecture Notes in Computer ~Science, vol. 415. Springer Verlag, New York, 1990, pp. 37-48.

[7]

~BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., H~STAD, J., KILIAN, J., MICAL1, S., AND ~ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Crypto ~88. Lecture notes in Computer Science, vol. 403. Springer-Verlag, New York, 1988, pp. 37-56.

[8]

~BEN-OR, M., GOLDWASSER, S., KILIAN, J., AND WIGDERSON, m. Multi-prover interactive ~proofs: How to remove intractability assumptions. In Proceedings' of the 20th Annual ACM ~Symposium on the Theory of Computing (Chicago, Ill, May 2-4). ACM, New York, 1988, pp. ~113-131.

[9]

~BLUM, M., AND KANNAN, S. Designing programs that check their work. In Proceedings of the ~21th Annual ACM Symposittm on the Theory of Computing (Seattle, Wash., May 15-17). ACM. ~New York, 1989. pp. 86-97.

[10]

~BLUM. m., LUBY, M., AND RUBINFELD, R. Self-testing correcting with applications to numeri- ~cal problems. In Proceedtngs of t/re 22nd Annual A CM Symposium on the Theory of Comt)ttting ~(Baltimore, Md., May 14-16). ACM, New York, 1990, pp. 73-83.

[11]

~BOPPANA, R., H&STAD, J., AND ZACHOS, $. Does co-NP have short interactive proofs? b~f ~Proc. Lett. 25, 2 (1987). 127-132.

[12]

~CAt, J., CONDON, A., AND LIPTON, R.J. PSPACE is provable by two provers in one round. In ~Proceedings of the 6th Annual Conference on Structure in Complexity Theory (Chicago, Ill., June ~30-July 3). IEEE, New York, 1991, pp. 110-115.

[13]

~CHOR, B., GOLDREICH, O., AND H,~STAD, J. The random oracle hypothesis is false. ~Manuscript, Technion, Haifa, Israel, 1990.

[14]

~COOK, S. A. The complexity of theorem-proving procedures. In Proceedzngs of the 3rd ~Annual ACM Sympostum on the Theory of Computing (Shaker Heights, Oh., May 3-5). ACM, ~New York, 1971, pp. 151 158.

[15]

~FELDMAN, P. The optimum prover lives in PSPACE. Manuscript. M.I.T., Cambridge, Mass., ~1986.

[16]

~FORTNOW, L., AND LUND, C. Interactive proof systems and alternating time-space complex- ~ity. In Proceedings' of the 8th Symposium on Theoretzcal Aspects of Computer Science Lecture ~Notes in Computer Science, vol. 480, Sprmger-Verlag, New York, 1991, pp. 263 274.

[17]

~FORTNOW, L., ROMPEL, J., AND SIPSER, M. On the power of multi-prover interactwe ~protocols. In Proceedings of the 3rd Con}erence on Structure zn Complexity Theory (Washington, ~D.C., June 14-17). IEEE, New York, 1988, pp. 156 161.

[18]

~FORTNOW, L., AND SIPSER, M. Are there interactive protocols for co-NP languages? inf. ~Proc. Lett. 28 (1988), 249-251.

[19]

~FURER, M., GOLDREICH, O., MANSOUR, Y., SIPSER, M., AND ZACHOS, S. On completeness ~and soundness in interactive proof systems. In S. Micali, ed. Randomness and Computation, ~(volume 5 of Advances m Compzmng Research). JAI Press, Greenwich, Conn. 1989, pp. ~429-442.

[20]

~GOLDREICH, O., MICALI, S., AND WiGDERSON, A. Proofs that yield nothing but their validity ~and a methodology of cryptographic protocol design. In Proceedings of the 27th IEEE ~Symposium on Foundations of Computer Science. IEEE, New York, 1986, pp. 174 187.

[21]

~GOLDWASSER, S., MICAL1, S., AND RACKOFF, C. The knowledge complexity of interactive ~proof-systems. SIAMJ. Comput. 18, 1 (1989), 186-208.

[22]

~GOLDWASSER, S. AND SIPSER, M. Private coins versus public coins in interactive proof ~systems. In S. Micali, ed. Randomness and Compzttatzon, (volume 5 of AdL,ances bz Computing ~Research). JAI Press, Greenwich, Conn. 1989, pp. 73-90.

[23]

~IMPAGLIAZZO, R., AND YUNG, M. Direct minimum-knowledge computation. In Proceeding3 ~of Crypto 87. Lecture Notes in Computer Science, vol. 293, Springer-Verlag, New York, 1987, ~pp. 40-51.

[24]

~KARP, R., AND LIPTON, R. Some connection between nonuniform and uniform complexity ~classes. In Proceedings of the 12th Annual ACM Synzposzum on the Theory of Computzng (Los ~Angeles, Calif., Apr. 28-30). ACM, New York, 1980, pp. 302 309.

[25]

~LIPTON, R. New directions in testing. In J. Feigenbaum and M. Merntt, eds. Dtstributed ~Computing and Cr37~tography (volume 2 of DIMACS Se~es in Dtscrete Mathematics and ~Theoretical Computer Science). American Mathematical Society, Providence, R.I., 1991, pp. ~191-202.

[26]

~NIVEN, I., AND ZUCKERMAN, H. S. An tntroductzon to the theory of numbers 4th ed., Wiley, ~New York, 1980, pp. 224-225.

[27]

~PRATt, V. Every prime has a succinct certificate. SIAMJ. Comput. 4 (1975), 214-220.

[28]

~SHAMIR, h. IP - PSPACE. J. ACM 39, 4 (Oct. 1992), 869-877.

[29]

~SHEN, A. IP PSPACE: Simplified proof. J ACM 39, 4 (Oct. 1992), 878-880.

[30]

~StMOr% J. On some central problems in computational complexity. PhD thesis, Cornell ~University, Computer Science, 1975. Tech Report TR 75-224.

[31]

~SOLOVAY, R., AND STRASSEN, V. h fast Monte-Carlo test for primality. SIAM Jr. Conzput. 6 ~(1977), 84-85. See also erratum 7 (1978), I18.

[32]

~TODA, S. On the computational power of PP and ~ P. In Proceedings of the 30th iEEE ~Symposntm on Foundatzons of Computer Science. IEEE, New York, 1989, pp. 514-519.

[33]

~VALIANT, L. The complexity of computing the permanent. Theoret. Conzput. Scz 8 (1979), ~189-201.

Cited By

Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Bitansky NKamath CPaneth ORothblum RVasudevan PMohar BShinkar IO'Donnell R(2024)Batch Proofs Are Statistically HidingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649775(435-443)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649775
Gur TO'Connor JSpooner NMohar BShinkar IO'Donnell R(2024)Perfect Zero-Knowledge PCPs for #PProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649698(1724-1730)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649698
Show More Cited By

Index Terms

Algebraic methods for interactive proof systems
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
    2. Complexity theory and logic
  2. Models of computation
    1. Interactive computation
    2. Probabilistic computation

Recommendations

Polylogarithmic-round interactive proofs for coNP collapse the exponential hierarchy

If every language in coNP has a constant-round interactive proof system, then the polynomial-time hierarchy collapses [R.B. Boppana, J. Håstad, S. Zachos, Does co-NP have short interactive proofs? Information Processing Letters 25 (2) (1987) 127-132]. ...
Algebraic methods for interactive proof systems
SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science

An algebraic technique for the construction of interactive proof systems is proposed. The technique is used to prove that every language in the polynomial-time hierarchy has an interactive proof system. For the proof, a method is developed for reducing ...
Quantum multi-prover interactive proof systems with limited prior entanglement

This paper gives the first formal treatment of a quantum analogue of multi-prover interactive proof systems. It is proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in NEXP, under the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 39, Issue 4

Oct. 1992

242 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/146585

Issue’s Table of Contents

Copyright © 1992 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1992

Published in JACM Volume 39, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tag

interactive proof systems

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

472
Total Citations
View Citations
4,073
Total Downloads

Downloads (Last 12 months)1,436
Downloads (Last 6 weeks)166

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ron-Zewi NRothblum R(2024)Local Proofs Approaching the Witness LengthJournal of the ACM10.1145/366148371:3(1-42)Online publication date: 25-Apr-2024
https://dl.acm.org/doi/10.1145/3661483
Bitansky NKamath CPaneth ORothblum RVasudevan PMohar BShinkar IO'Donnell R(2024)Batch Proofs Are Statistically HidingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649775(435-443)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649775
Gur TO'Connor JSpooner NMohar BShinkar IO'Donnell R(2024)Perfect Zero-Knowledge PCPs for #PProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649698(1724-1730)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649698
Chen LHirahara SRen HMohar BShinkar IO'Donnell R(2024)Symmetric Exponential Time Requires Near-Maximum Circuit SizeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649624(1990-1999)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649624
Avizheh SNabi MSafavi-Naini R(2024)Refereed Delegation of Computation Using Smart ContractsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.337284821:6(5208-5227)Online publication date: Nov-2024
https://doi.org/10.1109/TDSC.2024.3372848
Duan HPeng ZXiang LHu YLi B(2024)A Verifiable and Privacy-Preserving Federated Learning Training FrameworkIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2024.336965821:5(5046-5058)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3369658
Drusinsky D(2024)From P Versus NP to Probabilistic and Zero Knowledge Proof SystemsComputer10.1109/MC.2024.335892857:4(119-130)Online publication date: 3-Apr-2024
https://dl.acm.org/doi/10.1109/MC.2024.3358928
Zhang HWu JLin XBashir AAl-Otaibi Y(2024)Integrating Blockchain and Deep Learning Into Extremely Resource-Constrained IoT: An Energy-Saving Zero-Knowledge PoL ApproachIEEE Internet of Things Journal10.1109/JIOT.2023.328006911:3(3881-3895)Online publication date: 1-Feb-2024
https://doi.org/10.1109/JIOT.2023.3280069
Ahmadi MNourmohammadi R(2024)zkFDL: An efficient and privacy-preserving decentralized federated learning with zero knowledge proof2024 IEEE 3rd International Conference on AI in Cybersecurity (ICAIC)10.1109/ICAIC60265.2024.10433831(1-10)Online publication date: 7-Feb-2024
https://doi.org/10.1109/ICAIC60265.2024.10433831
Bosshard ABootle JSprenger C(2024)Formal Verification of the Sumcheck Protocol2024 IEEE 37th Computer Security Foundations Symposium (CSF)10.1109/CSF61375.2024.00014(605-619)Online publication date: 8-Jul-2024
https://doi.org/10.1109/CSF61375.2024.00014
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Article

Media

Figures

Other

Tables

View Issue’s Table of Contents