Re:Zero Knowledge Protocols without Magic
by giantahead on Thursday July 28, 2016 @03:55AM
(#12178941)
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
by Ar-Curunir on Wednesday July 27, 2016 @11:29PM
(#12178151)
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
by Ar-Curunir on Sunday July 31, 2016 @02:42PM
(#12198229)
No, being zero knowledge does not imply being proof of knowledge.
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
by Ar-Curunir on Thursday July 28, 2016 @02:01PM
(#12181917)
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.
Zero-knowledge proof (soundness, completeness, zero-knowledge) is a subset of proof-of-knowledge (soundness, completeness), so your last statement is true by definition.