2 KiB
2 KiB
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