Is there Zero Knowledge Proof of Knowledge protocol for Hash function? (If h(v)=w) without revealing v to the anyone can we prove that we know 'v')
1
-
1$\begingroup$ Every function in NP has zkp I think. $\endgroup$– VS.Apr 21, 2020 at 11:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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 $w$ can be represented as a graph where knowing a 3-coloring for that graph is equivalent to knowing a $v$ such that $h(v) = w$.
That isn't the most efficient way to do it; for that you'd want zk-snarks or one of the zillion similar encodings. That approach is similar but you're modeling your hash function as a modular matrix multiplication instead of a graph coloring. But the answer is yes, there is a zero-knowledge protocol for proving you know the preimage of a value for a hash function.
-
$\begingroup$ Can u be more precise that how zk-snarks is useful here? I do not mean internal working. but how the input to the zk-snarks and output to the zk-snarks look like $\endgroup$– VinayJul 21, 2020 at 19:08