5 ms·

Zero Knowledge Protocols without Magic

65 points by cossacklabs 10y ago

makomk 10y ago
So basically, it's magic.
sulam 10y ago
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.
- Ar-Curunir 10y ago
  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.
fryguy 10y ago
It'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.
- Ar-Curunir 10y ago
  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.
  - fryguy 10y ago
    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.
    - Ar-Curunir 10y ago
      Languages that have Zero knowledge proof are not necessarily a subset of languages that have a PoK, for example Graph Non-Isomorphism is a CoNP problem, and so unlikely to have short witnesses. The classical protocol for GNI is not PoK, I believe. PoK is a stronger condition than soundness.
      - eru 10y ago
        I thought graph isomorphism is in P now? Isn't non-isomorphism in co-P then (and that's equal to P)? I'm probably mixing things up.
        Ar-Curunir 10y ago
        GI is in quasi-P, but you could consider another languzge like Quadratic non-residuosity which also is in CoNP but has zero knowledge proofs.
      - 10y ago
anonymousDan 10y ago
Good description of the intuition behind zero knowledge proofs is the following: http://pages.cs.wisc.edu/~mkowalcz/628.pdf http://pages.cs.wisc.edu/~mkowalcz/628.pdf
anonymousDan 10y ago
Does 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?
- Ar-Curunir 10y ago
  You have NIZKs that can do this efficiently.
- giantahead 10y ago
  Yes, exactly, lots of round trips, quite expensive to calculate each. SMP, the ZKP protocol they're using, is quite expensive itself, but promises even better security and nifty set of additional features, based info from presentation linked in the article. However, I think that ZKP is not what you want for regular authentication: just for specific cases, where ZKP properties shine the most.
- rhyzomatic 10y ago
  As Ar-Curunir mentioned, you can use a technique called non-interactive zero knowledge proofs (NIZKs). Usually in ZKPs the prover will go through a part of the proof, send it to the verifier, the verifier will then send back a challenge, and the prover will reply with the final part of the proof based on the challenge. The basic flavor of NIZK I've seen is that instead of getting a challenge from the verifier, the prover simply does hash(prover id | first part of proof) and uses the result as the challenge. The `prover id` part is there such that they don't have complete control over the input to the hash. Doing it this way allows the prover to do the entire proof on their own and then send the whole thing to the verifier who can check the proof without any further interaction, saving network costs in exchange for a single hash.

65 points by cossacklabs 10y ago

So basically, it's magic.

sulam 10y ago

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.

Ar-Curunir 10y ago
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.

fryguy 10y ago

It'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.

Ar-Curunir 10y ago
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.
- fryguy 10y ago
  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.
  - Ar-Curunir 10y ago
    Languages that have Zero knowledge proof are not necessarily a subset of languages that have a PoK, for example Graph Non-Isomorphism is a CoNP problem, and so unlikely to have short witnesses. The classical protocol for GNI is not PoK, I believe. PoK is a stronger condition than soundness.
    - eru 10y ago
      I thought graph isomorphism is in P now? Isn't non-isomorphism in co-P then (and that's equal to P)? I'm probably mixing things up.
      - Ar-Curunir 10y ago
        GI is in quasi-P, but you could consider another languzge like Quadratic non-residuosity which also is in CoNP but has zero knowledge proofs.
    - 10y ago

anonymousDan 10y ago

Good description of the intuition behind zero knowledge proofs is the following: http://pages.cs.wisc.edu/~mkowalcz/628.pdf http://pages.cs.wisc.edu/~mkowalcz/628.pdf

anonymousDan 10y ago

Does 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?

Ar-Curunir 10y ago
You have NIZKs that can do this efficiently.
giantahead 10y ago
Yes, exactly, lots of round trips, quite expensive to calculate each. SMP, the ZKP protocol they're using, is quite expensive itself, but promises even better security and nifty set of additional features, based info from presentation linked in the article. However, I think that ZKP is not what you want for regular authentication: just for specific cases, where ZKP properties shine the most.
rhyzomatic 10y ago
As Ar-Curunir mentioned, you can use a technique called non-interactive zero knowledge proofs (NIZKs). Usually in ZKPs the prover will go through a part of the proof, send it to the verifier, the verifier will then send back a challenge, and the prover will reply with the final part of the proof based on the challenge. The basic flavor of NIZK I've seen is that instead of getting a challenge from the verifier, the prover simply does hash(prover id | first part of proof) and uses the result as the challenge. The `prover id` part is there such that they don't have complete control over the input to the hash. Doing it this way allows the prover to do the entire proof on their own and then send the whole thing to the verifier who can check the proof without any further interaction, saving network costs in exchange for a single hash.