11 votes

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
3 votes
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 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,190
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
2 votes

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 ...
2 votes

Zero knowledge proof for value of a hash function

There is an elegant and rather efficient zero-knowledge protocol for these kinds of NP statements given in this paper: Marek Jawurek, Florian Kerschbaum, Claudio Orlandi: Zero-Knowledge Using Garbled ...
  • 2,789
1 vote

Minimum communication cost for zero knowledge proofs of three colorability

There is a recent surge in activity in succinct non-interactive zero knowledge arguments. It is known how for example construct an NIZK argument for Circuit-SAT where the argument length is a very ...
  • 401

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