# Tag Info

### Complexity classes for proofs of knowledge

This is not an actual answer; I'm just sharing some results (which do not fit in one comment). Goldreich, Micali and Wigderson (J. ACM, 1991) proved that every language in NP has a zero-knowledge ...
• 16.4k
Accepted

### Minimum communication cost for zero knowledge proofs of three colorability

So here is the right paper for my purposes: Joe Kilian, "A note on efficient zero-knowledge proofs and arguments." http://people.csail.mit.edu/vinodv/6892-Fall2013/efficientargs.pdf To get the ...
• 3,221
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
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,190
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

### Minimum communication cost for zero knowledge proofs of three colorability

Update: This answer is obsoleted by my other answer, with fully polylogarithmic bounds from appropriate references. On second thought, there's no need to reveal the Merkle tree gradually, so the ...
• 3,221