4
$\begingroup$

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:

  1. A random value is produced.

  2. One can then search for the "correct answer" to the random value.

  3. There is one and only one "correct answer".

  4. 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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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 < 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 < x < 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.

$\endgroup$
8
  • $\begingroup$ Would it work to simply choose some larger elliptic curve (e.g. one of the NIST curves), and then select a range such that solving the discrete logarithm problem over this range takes the wanted amount of time? Then a random element in this range is chosen, and used as the value to multiply the base point with, and finally the range is published together with the result. Now the attacker "only" has to try values in this range, which we can control the difficulty to do. $\endgroup$ Jun 5, 2012 at 14:23
  • 2
    $\begingroup$ @MartinSuecia: no, that doesn't work (at least, with the parameters that David gave). Selecting a random number in the range means that you have a dealer selecting the challenge response; David didn't want such a dealer (see the "I have no agent that can do that..." of his question). $\endgroup$
    – poncho
    Jun 5, 2012 at 14:32
  • $\begingroup$ I don't see how this can work. Someone can just build a look up table prior to the random number being released and thus the amount of work would be a single lookup. Making it harder to build a lookup table would require making it harder to get the answer at all. This is what the "one can then search" in step 2 means. I've updated the question to clarify this. $\endgroup$ Jun 5, 2012 at 22:01
  • $\begingroup$ @DavidSchwartz: if we have a 64 bit subgroup (and hence a target work effort of $2^{32}$), a lookup table would be $2^{64}$ entries; that is of questionable feasibility. $\endgroup$
    – poncho
    Jun 5, 2012 at 22:14
  • $\begingroup$ What algorithm solves the problem in O(sqrt(n)) time? Pollard's rho? $\endgroup$ Jun 5, 2012 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.