# Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $\log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at least both problems infeasible, e.g. because you want to use $g=2,h=3,p$ as domain parameters for some scheme. How large would $p$ have to be?

Intuitively, the problem of finding $\log_2(3)$ seems similar to the problem of doing the precomputations of Index Calculus, i.e. to find a sequence of exponents ${(k_i)}_{i=0}^n$ such that, for all $i=0..n$, the integer $FE2I(g^{k_i} \pmod p)$ is $B$-smooth (and has prime power factors with exponents that form a vector $v_i$ that cannot be expressed as a linear combination of any other $v_j$, etc).

To make Index Calculus in $\mathbb{Z}_p$ hard, requires choosing a prime $p$, such that, for any smaller prime $B$, there would either be too few $B$-smooth integers, or the number $\pi(B)$ of primes less than $B$ would have to be too great. Given the approximation that the probability of a number less than $p$ being $B$-smooth is approximately $u^{-u}$ where $u = \frac{\ln(p)}{\ln(B)}$, and that $\pi(B) \approx \frac{B}{\ln(B)}$, you e.g. get either a probability of at most $2^{-128}$ that a random element in $\mathbb{Z}_p$ is $B$-smooth, or you have to choose a $B$ that is greater than the $2^ {128}$:th prime, if $p \approx 2^{3645}$.

Consequently, presuming that a 3072-bit prime is generally (more than) sufficient for schemes that require a 128-bit strong DLP scheme, would a 4096-bit prime be sufficient for a scheme that relies on the hardness of computing $\log_g(h)$ for small deterministically selected generators $g$ and $h$?

Edit: Considering that e.g. $p = 2^{4096} - 3^{2225}$ is a prime (implying $\log_2(3) = 4096(2225)^{-1} \bmod (p-1)$) and the main argument in my question only applies to verifiably randomly generated primes, do primes for which $\log_2(3)$ is easily solvable have anything in common? Are all such primes on the form $p = 2^n-3^m$ or some other easily detected form, or is it possible to doctor such a prime in such way that knowledge of $\log_2(3)$ may be kept secret?

Edit 2: Considering that the equation $kp = 2^n - 3^m$ has at least one solution $k \in \mathbb{Z}, n,m \in \mathbb{Z}_{p-1}$ for all primes $p > 3$, could the question regarding doctoring these primes be expressed as: Is there a way to calculate $(2^n - 3^m)/k$ as efficiently in $\mathbb{Z}$, as $2^n - 3^m$ might be calculated in $\mathbb{Z}_p$, for arbitrary $k,n,m$ in a suitable range?.

For instance, would checking $2^i3^{-j} \bmod p \neq 1$ for $0 \lt i,j \le 2^{48}$ be sufficient, or is it possible to calculate $(2^n - 3^m)/k$ for huge $n,m$ e.g. if $k$ is a huge power of another small prime? Are there other short cuts?

Edit 3: Because $kp = 2^n - 3^m$ is equivalent to $1 + kp3^{-m} = 2^n3^{-m}$, we have $n\ln(2) - m\ln(3) = \ln(1 + kp3^{-m})$. If $kp$ is significantly smaller than $3^m$, we would have $|n\ln(2) - m\ln(3)| \lt \epsilon$. This would however require that $\frac{\ln(3)}{\ln(2)} = \frac{n}m + \delta$ with $|\delta| \lt \epsilon$, which is not the case (because $\epsilon$ can be approximated by an exponential function in $-m$ and the fractional expansion of $\frac{\ln(3)}{\ln(2)}$ is not periodic with period dividing $\phi(m)$ in the $\approx m$ most significant positions).

Hence, if $2^{255} \lt n \lt 2^{256}$, there is no solution in the natural numbers to $kp = 2^n - 3^m$ in which $k$ is small enough for $kp$ to be several magnitudes smaller than $2^{2^{255}}$.

Next, suppose $C$ is the greatest number you are able to represent in arithmetic operations. If $k = \prod_{i=0}^{l}p_i^{e_i}$ with each $p_i^{e_i} \le \frac{C}{p_i}$, there is a non-negligible probability that $kp$ might be factored by performing a CRT reconstruction from $\frac{(2^n-3^m)\prod_{j=0,j\neq i}^{l}p_j^{-e_j} \pmod {p_i^{e_i+1}}}{p_i^{e_i}}$. This would however still entail a bound $k \lt C^{\pi(C)}$, which would still be too small to guarantee that $n$ and $m$ might not be calculated given $p$.

• Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Jan 18 '16 at 22:26

You're looking for two small, deterministically selected generators $g$ and $h$ for the use as domain parameters.

If you drop your your requirement of $h$ being small you might choose $h = next\_group\_element(H(g))$, where H is a full domain hash function into $\mathbb{Z}_p$.

In the Random Oracle Model, calculating $dlog_g(next\_group\_element(H(g)))$ is than as hard as the general discrete log problem in the group.

You can omit $h$ in the discription of your domain parameters. You might even omit $g$, by defining $g$ to be the $smallest\ generator > 1$ of the group. Then the discription only consists of your verifiably generated prime $p$. All the other parameters are deterministically derived.

If you're considered about $g$ having some special property you might pick $g = next\_group\_element(H(p))$.

• The question asks for $g$ and $h$ to be chosen and generate $p$ in dependence of those. If you define $h=f(g)$ with some function $f$, then $h$ is not chosen independently and the answer fails to adress the question. – tylo May 9 '17 at 15:07
• The question askes for the appropriate size of the prime $p$, such that the discrete logarithm problem is hard for specific generators $g$ and $h$ (instead of the general case only). No part of the question asks for $h$ being indepent of $g$. So if you are the downvoter of my answer, I would like you to rethink about the question/answer. – raisyn May 9 '17 at 16:24
• Using 2 and 3 (or any other small, relatively prime numbers) is the whole point of the question. Using a fixed $g$ and a larger, generated $h$ is an already well explored alternative option. – Henrick Hellström May 9 '17 at 19:12

I have recentently considered a similar problem and have run some tests using Sagemath. I've ended up choosing a safe prime $p$. These are also used for Diffie Hellman (see http://www.rfc-base.org/txt/rfc-3526.txt).

When using a safe prime $p$ for the group you get a subgroup $G$ of large order $q = (p-1) / 2$ in which the discrete logorithm problem is hard.

Every element except 1 in $G$ is a generator of the group. You can check if an element $g$ (e.g. $2$ and $3$) is in the group in the following way:

$g \in G \iff g > 1 \ \land \ g ^ q \equiv 1 \pmod{p}$

To my understanding, the described construction results in a group in which the calculation of the discrete logarithm $dlog_2(3)$ is hard, given a suitable size for $p$ (e. g. 3072 bits as stated in the question)

Instead of using a safe prime for the group you might consider Schnorr groups (https://en.wikipedia.org/wiki/Schnorr_group) for better performance.

DISCLAMER: I'm not a cryptographer or mathematician. Maybe the answer is useful anyway. :)

• I don't think this answers the question. – kodlu Apr 27 '17 at 23:13
• I've added an additional paragraph to explain my reasoning further. Do you still think this does not address the question? Can you explain why? – raisyn Apr 27 '17 at 23:50
• The construction does not guarantee that computing $\text{dlog}_2(3)$ is hard; you could do a similar construction with 2 and 4; however, even though the dlog problem is hard in general, we know $\text{dlog}_2(4)$ is easy. Also, you can't use Schnorr groups; 2 and 3 are unlikely to be members of the subgroup. – poncho Apr 28 '17 at 19:39
• Thanks @poncho for the clarification I did not get around to writing, I wasn't on crypto stackexchange for more than 24 hours, a rare occasion. – kodlu Apr 29 '17 at 1:09