2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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).

$\endgroup$
2
  • 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$
    – zkvroon
    Commented Jun 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$
    – dade
    Commented Jun 25, 2018 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.