# Zero-Knowledge Proof

- [[cryptography]]
- back in the 80s
  - people were studying [[interactive-proofs]]
  - if you know the proof of a claim, you can show that you know the proof in much less cost than the whole proof
  - original interest was not ZK but rather communication cost
  - original ZKP paper was rejected a lot for being confusing, but all 3 authors received Turing awards for it
- zero-knowledge
  - prove 3-colorable without disclosing coloring
  - prove graph isomorphism without disclosing vertex mapping
  - in general: prove something with minimum communication
- bad definition: prove something without giving extra information
  - what does it mean for a computer to know something
- computer "knows" something if, given data on computer, the something can be computed in polytime
  - claim: graph is 3-colorable
  - public parameter: graph
  - private parameter: graph coloring
  - if challenger can learn anything about the private parameter from the proof, it is not ZKP
- bad definition: a ZKP lets A convice B of a fact without helping compute things that weren't computable before
  - learning is represented via a transcript (qv [[simulation]])
  - any knowledge learned by a "conversation" is equivalent to the knowledge learned by that conversation's transcript
  - we say that B can "imagine" a transcript, and then learning from that imaginary transcript is equivalent to a real conversation
- okay definition: a zero-knowledge interaction between A and B is ZK if B can produce "valid-looking" transcripts without ever talking to A
  - the transcripts generated from a real run of the protocol should be from the same distribution from the imagined transcripts for this to be true
  - this means A cannot distinguish real transcripts from fake transcripts!
  - how can you also allow everyone to make perfect forgeries while at the same time rejecting counterfeits?
  - specific proof is important to challenger: not 3rd party
  - transcript after-the-fact is useless, generation in order is the only thing that can be used for proving