Foundations and Trends® in Theoretical Computer Science > Vol 13 > Issue 3

On Doubly-Efficient Interactive Proof Systems

By Oded Goldreich, Weizmann Institute of Science, Israel, oded.goldreich@weizmann.ac.il

 
Suggested Citation
Oded Goldreich (2018), "On Doubly-Efficient Interactive Proof Systems", Foundations and Trends® in Theoretical Computer Science: Vol. 13: No. 3, pp 158-246. http://dx.doi.org/10.1561/0400000084

Publication Date: 19 Apr 2018
© 2017 O. Goldreich
 
Subjects
Computational complexity,  Randomness in computation
 

Free Preview:

Download extract

Share

Download article
In this article:
1. Introduction
2. Simple doubly-efficient interactive proof systems
3. On the doubly-efficient interactive proof systems of GKR
4. Overview of the doubly-efficient interactive proof systems of RRR
5. Epilogue
A. Defining interactive proofs and arguments
References

Abstract

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear time. Such proof systems, introduced by Goldwasser, Kalai, and Rothblum (JACM, 2015), make the benefits of interactive proof system available to real-life agents who are restricted to polynomial-time computation. We survey some of the known results regarding doubly-efficient interactive proof system. We start by presenting two simple constructions for t-no-CLIQUE (due to Goldreich and Rothblum (ECCC, 2017 and 2018)), where the first construction offers the benefit of being generalized to any “locally characterizable” set, and the second construction offers the benefit of preserving the combinatorial flavor of the problem. We then turn to two more general constructions of doublyefficient interactive proof system: the proof system for sets having (uniform) bounded-depth circuits (due to Goldwasser, Kalai and Rothblum (JACM, 2015)), and the proof system for sets that are recognized in polynomial-time and small space (due to Reingold, Rothblum, and Rothblum (STOC, 2016)). Our presentation of the GKR construction is quite complete (and is somewhat different from the original presentation), but for the RRR construction we only provide an overview.

DOI:10.1561/0400000084
ISBN: 978-1-68083-424-6
106 pp. $75.00
Buy book (pb)
 
ISBN: 978-1-68083-425-3
106 pp. $140.00
Buy E-book (.pdf)
Table of contents:
1. Introduction
2. Simple doubly-efficient interactive proof systems
3. On the doubly-efficient interactive proof systems of GKR
4. Overview of the doubly-efficient interactive proof systems of RRR
5. Epilogue
A. Defining interactive proofs and arguments
References

On Doubly-Efficient Interactive Proof Systems

An interactive proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier’s strategy can be implemented in almost-linear time. Such proof systems make the benefits of interactive proof system available to real-life agents who are restricted to polynomial-time computation.

On Doubly-Efficient Interactive Proof Systems surveys some of the known results regarding doubly-efficient interactive proof systems. It starts by presenting two simple constructions for t-no-CLIQUE, where the first construction offers the benefit of being generalized to any “locally characterizable” set, and the second construction offers the benefit of preserving the combinatorial flavor of the problem. It then turns to two more general constructions of doubly-efficient interactive proof system: the proof system for sets having (uniform) bounded-depth circuits and the proof system for sets that are recognized in polynomial-time and small space. The presentation of the GKR construction is complete and is somewhat different from the original presentation. A brief overview is provided for the RRR construction.

 
TCS-084