Cryptography
hash zero-knowledge-proofs hash-signature
Updated Sat, 17 Sep 2022 14:04:47 GMT

Zk Proof to Prove that I know the secret x of y = HASH(x)


Lets say I know a secret value x.

The hash of x, y = H(x) is public.

Is there any zk way to prove to a verifier that I know x without revealing x and only revealing y?




Solution

There are many protocols that can do this. I'm listing a few that do not require computational assumption (like pairing or DH) since I'm more familiar with these. They're based on either MPC in the Head or Reed-Solomon IOP.

The first three has sub-linear proof size in the size of the circuit but potentially longer prover time. The last one (Limbo) has fast prover time but linear proof size. The abstract of Limbo gives you a feel of its efficiency for SHA-256:

The new system creates proofs of SHA-256 pre-images of 43KB in 53ms with 16 MPC parties, or 23KB in 188ms for 128 parties.

If you want to use computational assumption, there are more efficient protocols such as bulletproofs (https://eprint.iacr.org/2017/1066.pdf).





Comments (1)

  • +0 – Thank you. It was really nice explanation. — Aug 18, 2022 at 07:32