News for hackers. Stuff that matters.

A comment on Zero Knowledge Protocols without Magic. Parent comment

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.

[ Parent | on HN ]
Re:Zero Knowledge Protocols without Magic by fryguy on Friday July 29, 2016 @02:13AM (#12185270)
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.

[ Parent | on HN ]
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.
[ Parent | on HN ]
Re:Zero Knowledge Protocols without Magic by eru on Thursday July 28, 2016 @01:55AM (#12178608)
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.

[ Parent | on HN ]
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.
[ Parent | on HN ]