2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ It's much simpler to do this with asymmetric crypto. Is there scope for changing your protocol to achieve the same goal via different means? $\endgroup$
    – knaccc
    Aug 17 at 22:26

1 Answer 1

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you. It was really nice explanation. $\endgroup$
    – Zubayr
    Aug 18 at 7:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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