Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.
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 ...
user avatar
  • 16.3k
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 ...
user avatar
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....
user avatar
  • 46
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 $...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 401

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