4
$\begingroup$

For a standard hash function $H$ like SHA-256, one can choose a secret message $M$, compute and publish $h=H(M)$, then prove knowledge of the preimage $M$ in zero knowledge [that is without disclosing anything about $M$ beyond $h=H(M)$ ]. However such proofs are (or at least used to be) large, often interactive, and slow to verify.

What's the sate-of-the art in hash functions with a relatively lightweight Zero Knowledge Proof of a preimage, still having standard hash security attributes [collision-resistance, preimage-resistance at least] ?

Update per comment: we can assume $M$ of public fixed size, e.g. a kilobyte. We want the hash of that to be practically computable, no need that it's especially fast.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ Does just the proof need to be lightweight, or the hash as well? $\endgroup$ Commented Nov 17 at 17:02
  • 2
    $\begingroup$ Also, does the approximate preimage length need to be confidential (or can we assume a reasonable upper bound)? If that length is confidential, with no upper bound, that would appear to be difficult with many reasonable hash functions (which may rely on iterated hash compression or permutation operations) $\endgroup$ Commented Nov 17 at 18:12
  • 2
    $\begingroup$ Will try a proper answer later. But for the time being: in terms of state-of-the art ZK friendly hashes, there's work on reusing existing designs over prime fields. For example, the sponge function could be defined using a permutation over a prime field (See poseidon hash function). Efficiency gains come from using “native” arithmetic rather than embedding binary arithmetic in finite field. This website (linked in comments on another question) has a good list of other such primitives. stap-zoo.com $\endgroup$ Commented Nov 17 at 23:22
  • 2
    $\begingroup$ In SHA256, the current state of general-purpose provers allows for significant efficiency trade-offs. For instance, Google's Longfellow system (ia.cr/2024/2010) achieves a ~16ms proving time per SHA256 compression round. Regarding proof size, a common technique is to wrap the initial proof in a "verification proof," which can be substantially smaller (with some increase in proving time). $\endgroup$ Commented Nov 17 at 23:36
  • 1
    $\begingroup$ perhaps $g^x h^r$ style pedersen commitments, or their elliptic curve counterparts? don't they have pretty straightforward proofs in zero-knowledge? $\endgroup$ Commented Nov 18 at 1:58

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.