Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #3 to TR17-018 | 10th September 2017 15:49

#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revision #3
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 10th September 2017 15:49
Keywords:

Abstract:

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)

Changes to previous version:

Various expositional changes (incl switching Sections 4 and 5).

Revision #2 to TR17-018 | 3rd March 2017 10:56

#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revision #2
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 3rd March 2017 10:56
Keywords:

Abstract:

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)

Changes to previous version:

Correcting a typo that made a minor unfavorable comparison (against our own construction).

Revision #1 to TR17-018 | 2nd March 2017 20:01

#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revision #1
Authors: Oded Goldreich, Guy Rothblum
Accepted on: 2nd March 2017 20:01
Keywords:

Abstract:

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)

Changes to previous version:

Added a few references we were not aware of, and a comment asserting that the proof system underlying Thm 1 applies also to verifying the number of violated conditions.

### Paper:

TR17-018 | 6th February 2017 16:44

#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

TR17-018
Authors: Oded Goldreich, Guy Rothblum
Publication: 6th February 2017 16:44
Keywords:

Abstract:

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)

ISSN 1433-8092 | Imprint