2
$\begingroup$

Preliminaries

Let $p$ be a safe prime number. Let $\mathbb{Z}_p^*$ be the multiplicative group of integers modulo $p$. We have $\mathbb{Z}_p = \{\,a \in \mathbb{Z} \mid 1 \le a \lt p\,\}$ .

Let $g \in \mathbb{Z}_p$ be a primitive element of $\mathbb{Z}_p$ . Let $h$ be an element of $\mathbb{Z}_p$ .

We define the Discrete Logarithm Problem for a group of integers modulo a Safe prime (DLPS) as:

DLPS: Find the integer $k$ such that $\;\;1 \le k \lt p\;\;$ and $\;\;g^k \equiv h \pmod p$ .

We assume that the best algorithm to solve DLPS is the Number Field Sieve for Discrete Logarithms, which has an expected running time of $$L_p\left[1/3, \sqrt[3]{64/9}\right] \,=\; e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln p\big)^{1/3}\big(\ln \ln p\big)^{2/3}}$$

Questions

If we choose $p$ to be a 2048-bit safe prime, which is at least equal to $2^{2047}$, then the expected number of arithmetic operations needed to solve DLPS is approximately equal to:

$$e^{\textstyle \left(\sqrt[3]{64/9}+o(1)\right)\big(\ln 2^{2047}\big)^{1/3}\big(\ln \ln 2^{2047}\big)^{2/3}} \\ \approx \, e^{\textstyle \big(1.923\big)\big(1419\big)^{1/3}\big(7.258\big)^{2/3}} \\ \approx \, e^{\textstyle \big(1.923\big)\big(11.24\big)\big(3.749\big)} \\ \approx \, e^{\textstyle \big(81.00\big)} \\ \approx \, 2^{116.9}$$

Is it correct?

Should I make sure that $(p+1)$ has a large prime factor? (to make $p$ a strong prime)

If I am not mistaken, this is the graph showing the security level of DLPS in function of the size of $p$:

Graph of security level in function of length of modulus


Edit 7th June 2019: Here is the context in which I will use this discrete logarithm problem:

Context

I am creating an online massively multiplayer video game. In this game, the player moves around a character and performs actions in a persistent virtual world. I use the discrete logarithm problem as an in-game currency. Every action performed by a character (move around, buy an item, throw a projectile, etc.) has to be paid by the player with CPU time. This way, I don't have to spend my time monitoring players to detect cheaters (multiple accounts, farming bots, etc), because what cheaters usually do is explicitly allowed in my game.

Here is how it works: to earn the right to perform an action in the virtual world, the player requests a discrete logarithm challenge to the game server. Then, the server generates random values for the generator $g$ and the exponent $k$, computes the result $h \equiv g^k \pmod p$, and send the values of $g$ and $h$ to the player. Then the player's client computes the value of the exponent $k$ and send it back to the server to receive credits.

The value of $p$ will never change, and the values of $g$ and $k$ will be different for each challenge. The player can choose the difficulty of the challenge by setting an upper bound on the bit-length of the value of the exponent $k$ (the amount of credits earned is proportional to the amount of CPU time spent).

$\endgroup$
  • 1
    $\begingroup$ 'Is it correct?' Well, at one point, you assume that the $o(1)$ term is neglible, and so can be ignored; I don't believe that is necessarily a correct assumption... $\endgroup$ – poncho Jun 6 at 21:17
  • $\begingroup$ With the additional context that this is a proof-of-work scheme, my general answer about choices for security is not longer particularly applicable. Relying on precise turning of the NFS is going to be hard—as poncho notes, you'll have to worry about the $o(1)$, which is maybe fine for estimating a lower bound on attack costs but not for tuning them; also the discrete log computation factors into an expensive precomputation for a group, determined by the choice of prime, followed by a relatively cheap computation for any particular instance in that group. $\endgroup$ – Squeamish Ossifrage Jun 7 at 12:02
2
$\begingroup$

For a proof of work scheme, you're probably better off making $p$ large enough that you don't have to worry about NFS (e.g. 2048 bits or more), or alternatively, using an elliptic curve group (e.g. P256 or Curve25519).

Instead, you'd tune things so that the generic attacks (e.g. Big-Step-Little-Step) are the optimal attacks, and use that to select the difficultly (range of $k$); if the solver knows that $0 < k \le M$, then these generic searches will take circa $\sqrt{M}$ group operations (modular multiplications, elliptic curve additions), and that's the best the searcher can do (assuming that he doesn't have any further insight into the group structure - that's what we're trying to ensure by making NFS infeasible).

Now, while this would work as a 'proof-of-total-work', I'm not sure if it really meets your requirements, because someone with significant amount of parallelism (e.g a botnet farm) may be able to accelerate this computation significantly.

A better approach might be to have the serve publish integer $g$, $k$ and a composite $n$, and ask the client to compute $g^{2^k} \bmod n$; this type of operation isn't greatly parallizable (because each squaring operation must be done sequentially), and the server (who knows the factorization of $n = pq$) can verify this by checking a claimed answer $A$ by the relation $A \equiv g^{2^k \bmod p-1} \pmod p$

$\endgroup$
  • $\begingroup$ The sequential squaring is a nice trick, but I am OK with the possibility of parallelization. If I propose only serial challenges, a player can request 1000 challenges at the same time, and solve them in parallel anyway (and receive the same amount of credits than for solving a challenge 1000 times harder). This would only increase the workload of my server. BTW, do you know if switching to elliptic curves would decrease significantly the work done by the server to propose a challenge? $\endgroup$ – RalphS Jun 7 at 16:01
  • 2
    $\begingroup$ @RalphS: elliptic curves should decrease the workload on the server somewhat (as an elliptic curve addition on a 256 bit curve is cheaper than a modular multiplication over a 2048 bit modulus) - the exception is if the server just happens to have (and use) an "RSA accelerator" (which speeds up the 2048 bit modulus operations) but not an "ECC accelerator" $\endgroup$ – poncho Jun 7 at 17:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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