The GKR Protocol
65610.csail.mit.edu · 2,642 words · saved by 1 readers
N/A
The GKR Protocol Notes by Yael Kalai MIT - 6.5610 Lecture 12 (March 13, 2024) Warning: This document is a rough draft, so it may contain bugs. Please feel free to email me with corrections. Outline • Warmup for the GKR protocol • Low-degree Extension • The GKR protocol Intuition for the GKR protocol Given a circuit C of depth D and size S, an input x ∈ {0, 1}n and an output y, the prover needs to convince the verifier that C ( x ) = y. In other words, the verifier wants to catch the prover if y is incorrect. Here is a simple idea: The verifier will ask the…
related reading
- Zero Knowledge Proofs: An illustrated primer – A Few Thoughts on Cryptographic Engineeringblog.cryptographyengineering.com
- ProofsArgsAndZK.pdfpeople.cs.georgetown.edu
- Lecture 14: Zero knowledge proofsboazbarak.org
- A Gentle Introduction to Yao's Garbled Circuitsweb.mit.edu
- Succinct Non-Interactive Arguments (SNARGs) for NP65610.csail.mit.edu
- 118.pdfeprint.iacr.org
- 1482.pdfeprint.iacr.org
- 370.pdfeprint.iacr.org
- Zero-knowledge proof - Wikipediaen.wikipedia.org
- Collaborative zkSNARKseprint.iacr.org
- lec5.pdfcrypto.stanford.edu
- small-sumcheck.pdfpeople.cs.georgetown.edu