3 votes
Accepted

3-coloring graph zero-knowledge proof

Yes, it would still be zero knowledge. However, it wouldn't be a proof of anything, since whether the colors matched or not, you still know nothing about whether the graph is actually 3-colored or not....
David's user avatar
  • 46
2 votes
Accepted

Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

The $NP$-problem here is not the problem of finding y,z,n, but rather the following problem: "Given a mathematical statement $A$ that can be encoded in $n$ bits, does there exist a proof of $A$ ...
Or Meir's user avatar
  • 5,460
2 votes
Accepted

Zero Knowledge proofs of knowledge

Yes. The simplest way to understand this is to understand the zero-knowledge proof that you know a 3-coloring of a graph. 3-coloring is NP-complete, so an arbitrary hash function $h$ and target value $...
lacker's user avatar
  • 256

Only top scored, non community-wiki answers of a minimum length are eligible