3 ms·
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
by 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 agoIn 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 agoThe 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 agoLanguages 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 agoI 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 agoGI is in quasi-P, but you could consider another languzge like Quadratic non-residuosity which also is in CoNP but has zero knowledge proofs.
- fryguy 10y agoBecause 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.
- Ar-Curunir 10y agoNo, being zero knowledge does not imply being proof of knowledge.
- giantahead 10y agoYour 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.
- fryguy 10y agoThe server doesn't have the private key, only the client.
- mhluongo 10y ago* latter