Proof of work scheme with one and only one correct answer I need a problem that has one and only one solution, such that the solution is hard to find but easy to verify. I need to be able to generate the problem deterministically from a random seed.

So essentially, I want to be able to do this:


A random value is produced.
One can then search for the "correct answer" to the random value.
There is one and only one "correct answer".
That a particular answer is correct can easily be verified.


Ideally, the amount of work required would be tunable. The problem with most proof of work systems is either that they don't ensure that there is one and only one correct answer or they require some entity to generate the problem and withhold the solution.

For example, I could require someone to produce something that HMACs with the random value to a very low result. But then there wouldn't be one and only one correct answer. I could multiply two primes together and the lowest factor could be the correct answer. But I have no agent that can do that multiplication. Steps one and two are set in stone, though I can adjust the size of the random number.

Update: It must not be possible to do all of the work before the random number is generated. Ideally, there would be no significant benefit to any precomputation. The random number being revealed must enable you to do the work.
One obvious approach would be look at a discrete log problem.  That is, you pick an appropriate group of order $n$ (where $n$ is prime) and a generator $G$; for a challenge, you pick a random element $H$, and you ask for the value $0 \le k &lt; n$ such that $H = kG$.

This meets your requirements (1) the value produced is effectively random, requirement (2) one can search for the answer in $O(\sqrt n)$ time, (3) if $G$ is a generator, then there is exactly one such value, and (4) the answer can be verified in $O(\log n)$ time. In addition, the amount of work is tunable (by selecting groups of various sizes).  

For this to work, we need to select a group where we can't find discrete logs faster than $O(\sqrt n)$ time; I believe an appropriately sized random Elliptic Curve meets this requirement.

However, the chief difficulty with this suggestion is finding an Elliptic Curve group of the appropriate size; that's nontrivial, and all the precomputed Elliptic Curve groups I know are scaled to make the discrete log problem "infeasible", not "difficult".

Another group that would appear to be suitable is a small subgroup of a larger multiplicative group.  That is, we pick a large prime $p$ and a small prime $q$ where $q | p-1$.  We will then work in the multiplicative subgroup of size $q$ of the group $\mathbb{Z}^*_p$.  To create a random element of this subgroup, we select a random number $1 &lt; x &lt; p$, and compute $H = x^{(p-1)/q}$.  The order of the subgroup is, of course, $q$, and so if the work target is about $2^{32}$ operations, we may select a 1024 bit $p$ and a 64 bit $q$.  The chief advantage of this proposal over the Elliptic Curve idea is that it is much easier to devise a $p$ and $q$ of the appropriate sizes, rather than trying to define an Elliptic Curve.