29 lines
2 KiB
Markdown
29 lines
2 KiB
Markdown
# 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
|