# 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$$:

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

• '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... – poncho Jun 6 at 21:17
• 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. – Squeamish Ossifrage Jun 7 at 12:02

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