ECCC-Report TR17-101https://eccc.weizmann.ac.il/report/2017/101Comments and Revisions published for TR17-101en-usTue, 30 Jan 2018 18:58:15 +0200
Revision 1
| On the doubly-efficient interactive proof systems of GKR |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2017/101#revision1We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).
Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in the proof system is linearly related to the depth of the circuit).
Our simplification is in the handling of the log-space uniformity condition. Rather than having the prover provide the verifier with bits of the encoding of the circuit and establish their correctness, we employ the proof system to a highly regular universal circuit that constructs and evaluates the log-space uniform circuit in question.Tue, 30 Jan 2018 18:58:15 +0200https://eccc.weizmann.ac.il/report/2017/101#revision1
Paper TR17-101
| On the doubly-efficient interactive proof systems of GKR |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2017/101We present a somewhat simpler variant of the doubly-efficient interactive proof systems of Goldwasser, Kalai, and Rothblum (JACM, 2015).
Recall that these proof systems apply to log-space uniform sets in NC (or, more generally, to inputs that are acceptable by log-space uniform bounded-depth circuits, where the number of rounds in the proof system is linearly related to the depth of the circuit).
Our simplification is in the handling of the log-space uniformity condition. Rather than having the prover provide the verifier with bits of the encoding of the circuit and establish their correctness, we employ the proof system to a highly regular universal circuit that constructs and evaluates the log-space uniform circuit in question.Thu, 08 Jun 2017 18:55:20 +0300https://eccc.weizmann.ac.il/report/2017/101