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; a smart contract pays the miners for finding 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 such as SHA, how hard is it to decide how many preimages a given image $y$ has, when we can trivially learn that $y$ 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')$.

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

I have been considering an approach to incentivize cryptocurrency mining rigs to verify claims of quantum computational advantage. Briefly, miners find collisions $f(x_1)=f(x_2)=y$ of some known $f:m+1\mapsto m$-bit hash function $f$; the quantum computer (an honest prover) had previously committed to $y$ along with an $m+1$-bit string $d$ such that $d\cdot(x_1\oplus x_2)=0$.

The function $f$ is, in this case, not 2-to-1. Indeed I envision instantiating $f$ by looking at the last $m$ bits of a hash such as SHA256.

I think, generically, the number of collisions is distributed according to the Poisson distribution, and there would often be many $y$ that only have a single preimage.

A cheating prover could try to use a birthday attack to find pairs $(x_1,x_2)$ that both hash on to the same $y$ - but the scheme may be secure against this birthday attack, because the prover needs to often broadcast enough $y$ that only have a single preimage.

But, the security of the scheme may be contingent on whether a cheating prover could find an $(x,f(x))$ pair that she knows only has one preimage, in which case she would commit to $f(x)$ and some random $d$.

Thus to the question:

> For some generic hash such as SHA, how hard is it to decide how many preimages a given image $y$ has, knowing that $y$ 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')$.

Is there a search-to-decision reduction for something like this?

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; a smart contract pays the miners for finding 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 such as SHA, how hard is it to decide how many preimages a given image $y$ has, when we can trivially learn that $y$ 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')$.