Zero Knowledge Protocols without Magic

Re:Zero Knowledge Protocols without Magic by sulam on Wednesday July 27, 2016 @06:12PM (#12176891)

As someone who knows very little about subject, initially it appeared to me as if they were going to present some method to authenticate users without any shared knowledge, which seemed pretty close to magic to me! In fact the tl;dr is that two parties have a shared secret, but effectively they transmit proofs of possession that, statistically, achieve a high probability of being the same secret without needing to transmit it.

Calling this "zero knowledge" is sort of confusing from that perspective, but makes sense once you know what they're solving for.

[ Parent | on HN ]

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.

[ Parent | on HN ]