New answers tagged


Sure. ​ For any total relation, Protocol: ​ verifier accepts Simulator: ​ run the adversary is a zero-knowledge proof system, but if it's of knowledge then the search problem is efficiently solvable. There trivially exist easily-checkable total relations whose search problems are hard: For example, consider the relation given by xRy if and only if ​ ...


There are certainly ZK proof systems which are not known to be POK, and for which no knowledge extractor is known. For example, take the Goldreich-Kahan 4-round ZK proof system. However, do we know of a non-trivial proof system that is provably not a proof of knowledge? Not that I know of.

Top 50 recent answers are included