How easy is it to know how many preimages an image might have, given that there's at least one (preimage, image) pair?

Question

I have been considering an approach to incentivize cryptocurrency miners to verify claims of quantum computational supremacy. Briefly, miners find collisions $f(x_1)=f(x_2)=y$ of some known $f:m+1\mapsto m$-bit hash function $f$. I envision that a quantum computer broadcasts and commits to $y$ and to another sting $d$ related to the preimages $(x_1\oplus x_2)$, and then miners hunt for both preimages. The quantum computing company can draft a smart contract that pays the miners upon finding and broadcasting the preimages. An honest quantum computer might not find both preimages separately but rather can hold both preimages in superposition.

But, the hash function is not designed to be 2-to-1, and can instead be instantiated with something like SHA256. I think, generically, the number of collisions for a random hash function is distributed according to the Poisson distribution, and there would often be many $y$ that only have a single preimage.

Quickly to the question:

> For some generic hash function $f$ such as SHA, how hard is it to decide how many preimages a given image $y$ has, when we can trivially choose a random $x$ and know that $y=f(x)$ has at least one preimage?

I'd be satisfied to know whether a cheating prover who can find an $(x,f(x))$ pair at will has no easy way to determine whether there's another preimage $x'$ with $f(x)=f(x')$.

Answer 1

A common classical model for an ideal hash function is a random oracle. That's an hypothetical device accepting an input $x$ (here a $m+1$-bit bitstring) and then producing an output $y$ (here a $m$-bit bitstring). The device maintains a table of $(x_i,y_i)$ pairs where $x_i$ is a previous input and $y_i$ the output then given; and a counter $n$ of entries in the table, initially $0$. When an $x$ is submitted, the $n$ entries in the table are scanned for a matching $x_i$. If one is found, the device outputs $y:=y_i$. Otherwise, the device draws a uniformly random $y$ that it outputs, adds a new entry $(x_n,y_n):=(x,y)$ to the table, and increments $n$. It follows that at all times there are no duplicates among the $x_i$, and $0\le n\le2^{m+1}$.

In order to know with certainty how many preimages a given $m$-bit bitstring has per a random oracle, it's necessary to make $2^{m+1}$ queries covering all the values of $x$, because how many preimages have been found so far can be incremented at the last of these queries.

If we model "some generic hash function" as a classical random oracle, for

how hard is it to decide how many preimages a given image $y$ has

the answer under a classical computing model and an ideal hash is thus

• if we initially know an $x$ with $f(x)=y\,$: $\ 2^{m+1}-1$ hashes (the $-1$ term is because we do not need to test the known $x$).
• otherwise, $2^{m+1}$ hashes, or $2^{m+1}-1$ in the rare case that none of the first $2^{m+1}-1$ hashes returned $y$, which allows us to conclude that the number of preimages is $1$ without testing the last $x$.

For practical hashes (e.g. SHA-256 truncated to $m$ bits and input consisting of some fixed constant bitstring followed by $m+1$ bits), we know no much better method. However, it's possible to tackle many different problems differing only by the $y$ input, at cost marginally higher than for one problem.

---

I do not hazard to guess how that translates for an hypothetical quantum computer. But whatever $m$ and the complexity of the (classical) hash considered, quantum computers as we have them are of no practical help† on such problem. I'm not sure humanity will reach that stage.

---

† Tentative definition: the problem can't be solved with high probability in 1 second by a standard laptop, AND the combination of QC and classical computing/circuitry needed as support is 10% faster than classical computing/circuitry optimized for the task, at equal resources (gates, power) for the classical computing/circuitry.