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....
- 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$ ...
- 5,350
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 $...
- 256
Only top scored, non community-wiki answers of a minimum length are eligible