ECCC-Report TR17-018https://eccc.weizmann.ac.il/report/2017/018Comments and Revisions published for TR17-018en-usSun, 10 Sep 2017 15:49:24 +0300
Revision 3
| Simple doubly-efficient interactive proof systems for locally-characterizable sets |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/018#revision3A 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.
We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)Sun, 10 Sep 2017 15:49:24 +0300https://eccc.weizmann.ac.il/report/2017/018#revision3
Revision 2
| Simple doubly-efficient interactive proof systems for locally-characterizable sets |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/018#revision2A 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.
We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)Fri, 03 Mar 2017 10:56:22 +0200https://eccc.weizmann.ac.il/report/2017/018#revision2
Revision 1
| Simple doubly-efficient interactive proof systems for locally-characterizable sets |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/018#revision1A 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.
We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)Thu, 02 Mar 2017 20:01:26 +0200https://eccc.weizmann.ac.il/report/2017/018#revision1
Paper TR17-018
| Simple doubly-efficient interactive proof systems for locally-characterizable sets |
Oded Goldreich,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2017/018
A 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.
We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such constructions are presented for $t$-CLIQUE and $t$-SUM.
In addition, we present a generic construction of such proof systems for a natural class that contains both problems and is in NC (and also in SC).
The proof systems presented by us are
significantly simpler than the proof systems presented by Goldwasser, Kalai and Rothblum (JACM, 2015), let alone those presented by Reingold, Rothblum, and Rothblum (STOC, 2016)Mon, 06 Feb 2017 16:44:43 +0200https://eccc.weizmann.ac.il/report/2017/018