Re:Zero Knowledge Protocols without Magic
by Ar-Curunir on Wednesday July 27, 2016 @08:11PM
(#12177501)
A rigorous definition of a zero knowledge proof would be as follows.
Given some problem P (say proving that two graphs are isomorphic), you want to create a protocol such that the view of the verifier can be simulated without access to the witness (the graph isomorphism).
By "simulated" we mean that there exists some polynomial time simulator that produces a "fake" protocol transcript that is nonetheless indistinguishable from an actual protocol execution.
The existence of such a simulator implies that whatever the verifier could have learned from an interaction with the prover, it could also have learnt by interacting with the simulator.
Given some problem P (say proving that two graphs are isomorphic), you want to create a protocol such that the view of the verifier can be simulated without access to the witness (the graph isomorphism).
By "simulated" we mean that there exists some polynomial time simulator that produces a "fake" protocol transcript that is nonetheless indistinguishable from an actual protocol execution.
The existence of such a simulator implies that whatever the verifier could have learned from an interaction with the prover, it could also have learnt by interacting with the simulator.