Zero Knowledge Protocols without Magic
cossacklabs.com
Zero Knowledge Protocols without Magic
1–10 of 20 posts
Re: Zero Knowledge Protocols without Magic
#2So basically, it's magic.
Re: Zero Knowledge Protocols without Magic
#3As 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.
Re: Zero Knowledge Protocols without Magic
#4It's kind of sad that even in an article about zero-knowledge proofs doesn't understand the difference between a zero-knowledge proof, and a proof of knowledge (without the zero-knowledge part). The ladder are usually much simpler than the former, and typically the zero-knowledge part is not necessary.
Re: Zero Knowledge Protocols without Magic
#5Good description of the intuition behind zero knowledge proofs is the following: http://pages.cs.wisc.edu/~mkowalcz/628.pdf
Re: Zero Knowledge Protocols without Magic
#6Does anyone have a feel for what the performance overhead of zkp authentication would be? Presumably the main cost is having to do lots of round trips?
Re: Zero Knowledge Protocols without Magic
#7As 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 tr…
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.
Re: Zero Knowledge Protocols without Magic
#8It's kind of sad that even in an article about zero-knowledge proofs doesn't understand the difference between a zero-knowledge proof, and a proof of knowledge (without the zero-knowledge part). The ladder are usually much simpler than the former, and typically the zero-knowledge part is not necessary.
In this situation, both the ZK and the PoK properties are essential; indeed I would say that for most useful applications of ZK proofs, the PoK property is necessary.
Re: Zero Knowledge Protocols without Magic
#9It's kind of sad that even in an article about zero-knowledge proofs doesn't understand the difference between a zero-knowledge proof, and a proof of knowledge (without the zero-knowledge part). The ladder are usually much simpler than the former, and typically the zero-knowledge part is not necessary.
* latter
Re: Zero Knowledge Protocols without Magic
#10It's kind of sad that even in an article about zero-knowledge proofs doesn't understand the difference between a zero-knowledge proof, and a proof of knowledge (without the zero-knowledge part). The ladder are usually much simpler than the former, and typically the zero-knowledge part is not necessary.
In this situation, both the ZK and the PoK properties are essential; indeed I would say that for most useful applications of ZK proofs, the PoK property is necessary.
The ZK property absolutely doesn't matter. Imagine that instead of passwords the client stored a private key, and transmitted the associated public key to the server. Then when logging in the server sent a challenge and the client signed the challenge with their private key. The server then validated the signature against the public key for the user. This is absolutely not a zero-knowledge proof, but is a definite proof-of-knowledge since you've proved you know the private key.
Zero-knowledge proof (soundness, completeness, zero-knowledge) is a subset of proof-of-knowledge (soundness, completeness), so your last statement is true by definition.