Skip to main content
Cryptography

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

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