Authors
Oded Goldreich, Guy N Rothblum
Publication date
2018
Conference
9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Publisher
Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik
Description
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 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), and can be implemented using a smaller number of rounds.
Total citations
20172018201920202021202220236833222
Scholar articles
O Goldreich, GN Rothblum - 9th Innovations in Theoretical Computer Science …, 2018