Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Zero Knowledge Protocols without Magic

cossacklabs.com

Post reply on HN
Print view View original

11–20 of 20 posts

Re: Zero Knowledge Protocols without Magic

#11

Post by Ar-Curunir »

fryguy wrote: post #10
Ar-Curunir wrote: post #8

Earlier quoted context omitted.

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 pr…

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.

Re: Zero Knowledge Protocols without Magic

#13

Post by eru »

Ar-Curunir wrote: post #11
fryguy wrote: post #10

Earlier quoted context omitted.

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 pr…

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.

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.

Re: Zero Knowledge Protocols without Magic

#14

Post by giantahead »

fryguy wrote: post #10
Ar-Curunir wrote: post #8

Earlier quoted context omitted.

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 pr…

Your case is a case of established trust relationship (remote party has your private key it trusts), which is somewhat different from what folks in the article suggest, hence the zero knowledge part. so, for them ZK property matters a lot, to my understanding.

Re: Zero Knowledge Protocols without Magic

#15

Post by giantahead »

anonymousDan wrote: post #6

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?

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.

Re: Zero Knowledge Protocols without Magic

#16

Post by rhyzomatic »

anonymousDan wrote: post #6

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?

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.

Re: Zero Knowledge Protocols without Magic

#17

Post by Ar-Curunir »

eru wrote: post #13
Ar-Curunir wrote: post #11

Earlier quoted context omitted.

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.

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.

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.

Re: Zero Knowledge Protocols without Magic

#18

Post by fryguy »

giantahead wrote: post #14
fryguy wrote: post #10

Earlier quoted context omitted.

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 pr…

Your case is a case of established trust relationship (remote party has your private key it trusts), which is somewhat different from what folks in the article suggest, hence the zero knowledge part. so, for them ZK property matters a lot, to my understanding.

The server doesn't have the private key, only the client.

Re: Zero Knowledge Protocols without Magic

#19

Post by fryguy »

Ar-Curunir wrote: post #11
fryguy wrote: post #10

Earlier quoted context omitted.

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 pr…

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.

Because it's got a zero-knowledge proof means it's got a proof-of-knowledge. Quicksort is O(n^2) so that means it's in NP. It also means it's in P. Same with GNI being in ZKP, and also in PoK.

What's missing is the cheating verifier that can generate a transcript of a valid interaction without actually knowing the secret.

Re: Zero Knowledge Protocols without Magic

#20

Post by Ar-Curunir »

fryguy wrote: post #19
Ar-Curunir wrote: post #11

Earlier quoted context omitted.

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.

Because it's got a zero-knowledge proof means it's got a proof-of-knowledge. Quicksort is O(n^2) so that means it's in NP. It also means it's in P. Same with GNI being in ZKP, and also in PoK. What's missing is the cheating verifier that can generate a transcript of a valid interaction without actually knowing the secret.

No, being zero knowledge does not imply being proof of knowledge.
Post reply on HN