GKR protocol

A public-coin interactive proof for any language computable by a log-space-uniform Boolean circuit of depth $d$ on inputs of length $n$, with a prover running in time $\mathrm{poly}(n)$, a verifier running in time $(n+d)\cdot \mathrm{polylog}(n)$ and space $O(\log n)$, and $d\cdot \mathrm{polylog}(n)$ communication — GKR15.

For log-space-uniform $\mathrm{NC}$ the verifier runs in time $n\cdot \mathrm{polylog}(n)$ with $\mathrm{polylog}(n)$ communication, and all of $\mathbf{P}$ has public-coin interactive proofs with log-space, polynomial-time verifiers — GKR15. With the Kalai–Raz transformation from public-coin interactive proofs to 1-round arguments, log-space-uniform $\mathrm{NC}$ has designated-verifier non-interactive arguments in the public-key model with polylogarithmic communication and quasi-linear verification, sound if PIR with polylogarithmic communication exists — GKR15, KR09. Every language decidable in polynomial time and bounded polynomial space has an interactive proof with a polynomial-time prover, an almost-linear-time verifier and a constant number of rounds — RRR16.

TODO: syntax and security definition.

Participates in

Barriers

• No fixed-construction reduction from Fiat-Shamir + GKR to SNARK