Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR17-101 | 30th January 2018 18:58

On the doubly-efficient interactive proof systems of GKR

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 30th January 2018 18:58
Downloads: 640
Keywords: 


Abstract:

We 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.



Changes to previous version:

See Footnote 5, outlining a possible simplification (which will appear in a forthcoming survey).


Paper:

TR17-101 | 8th June 2017 18:54

On the doubly-efficient interactive proof systems of GKR





TR17-101
Authors: Oded Goldreich
Publication: 8th June 2017 18:55
Downloads: 1189
Keywords: 


Abstract:

We 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.



ISSN 1433-8092 | Imprint