4 ms·
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
by 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 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.