So my question is as follows: We know that we can prove in zero-knowledge equality of discrete logs, for example to prove equality of committed values we can prove in ZK for $g^xh^y$ and $g^{x'}h^{y'}$ that $x = x'$ using a Sigma protocol.

Is there a way to prove equality when one committed value is the output of a hash function? This means prove in ZK for $g^xh^y$ and $H(x')$ that $x = x'$. (the tricky part here is that the Hash function doesn't necessarily have homomorphic properties as the commitment does)


1 Answer 1


This paper (here also in case of a academic barrier) solves exactly the problem you have; just instantiate the garbling scheme with the hash function.

To prove the relation of the hash, they use a garbling scheme with the garbler being the verifier and the evaluator being the prover. Since the garbler has no inputs to provide into the garbled circuit, the verifier can 'open' the complete circuit to the prover after the prover has commited to the output key, which makes the performance comparable to garbing schemes secure against semi-honest adversaries (which is a lot faster than security against malicious adversaries) This paper (here also in case of a academic barrier) describes that in detail. The paper cited above now only combines that idea with 'common' commitment schemes.


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.