Hash functions such as SHA are considered as non-algebraic statements. How can one construct a NIZK proof to show that the output of a hash is computed correctly in an efficient manner.
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
For example, one could rely on ZKBoo, which in turn builds upon the MPC-in-the-Head paradigm by Ishai et al. The authors even provide an implementation, which demonstrates how to prove knowledge of a SHA-1 and SHA-256 preimage, respectively. The proofs are of linear size in the number of AND gates in the circuit. For more compact proofs you could have a look at SNARKs.
The authors discuss $\Sigma$-protocols, which are in fact interactive. However, as shown here or here, one can make those proofs non-interactive using the Fiat-Shamir transform (yielding security in the random oracle model) or the Unruh transform (yielding security in the quantum accessible random oracle model).
-
1$\begingroup$ Thanks for your reply! To prove knowledge of the pre-images in ZKBoo, the non-algebraic statement must be first expressed as a Boolean circuit.(I'm assuming this is not very efficient). What is the difficulty in creating NIZKs for arithmetic circuits? $\endgroup$– zkvroonJun 25, 2018 at 17:25
-
1$\begingroup$ ZKBoo does not only work for binary circuits, but for arithmetic circuits over arbitrary rings. It heavily depends on the circuit which ring fits best. $\endgroup$– dadeJun 25, 2018 at 17:41