Revision #3 Authors: Oded Goldreich, Guy Rothblum

Accepted on: 10th September 2017 15:49

Downloads: 794

Keywords:

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)

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

Revision #2 Authors: Oded Goldreich, Guy Rothblum

Accepted on: 3rd March 2017 10:56

Downloads: 754

Keywords:

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)

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

Revision #1 Authors: Oded Goldreich, Guy Rothblum

Accepted on: 2nd March 2017 20:01

Downloads: 731

Keywords:

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)

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.

TR17-018 Authors: Oded Goldreich, Guy Rothblum

Publication: 6th February 2017 16:44

Downloads: 968

Keywords:

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.

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)