New answers tagged zero-knowledge-proofs
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