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

Goel A(2025)Multiplication Is Hard: A Review Of Techniques Aiming To Parallelize Matrix Operations To Accelerate Crypto-ML Frameworks SSRN Electronic Journal10.2139/ssrn.5017963Online publication date: 2025
https://doi.org/10.2139/ssrn.5017963
Sun HBai TLi JZhang H(2025)zkDL: Efficient Zero-Knowledge Proofs of Deep Learning TrainingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.352086320(914-927)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TIFS.2024.3520863
Badakhshan MLuo GJandhyala TGong G(2025)Ursa Minor: The Implementation Framework for PolarisArithmetic of Finite Fields10.1007/978-3-031-81824-0_16(258-273)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-3-031-81824-0_16
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

483
Total Citations
View Citations
4,329
Total Downloads

Downloads (Last 12 months)1,400
Downloads (Last 6 weeks)113

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Goel A(2025)Multiplication Is Hard: A Review Of Techniques Aiming To Parallelize Matrix Operations To Accelerate Crypto-ML Frameworks SSRN Electronic Journal10.2139/ssrn.5017963Online publication date: 2025
https://doi.org/10.2139/ssrn.5017963
Sun HBai TLi JZhang H(2025)zkDL: Efficient Zero-Knowledge Proofs of Deep Learning TrainingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.352086320(914-927)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1109/TIFS.2024.3520863
Badakhshan MLuo GJandhyala TGong G(2025)Ursa Minor: The Implementation Framework for PolarisArithmetic of Finite Fields10.1007/978-3-031-81824-0_16(258-273)Online publication date: 28-Feb-2025
https://doi.org/10.1007/978-3-031-81824-0_16
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
Sun HLi JZhang HLuo BLiao XXu JKirda ELie D(2024)zkLLM: Zero Knowledge Proofs for Large Language ModelsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670334(4405-4419)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670334
Abbaszadeh KPappas CKatz JPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Zero-Knowledge Proofs of Training for Deep Neural NetworksProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670316(4316-4330)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670316
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: 1-Nov-2024
https://dl.acm.org/doi/10.1109/TDSC.2024.3372848
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

Figures

Tables

Media

View Issue’s Table of Contents