28
$\begingroup$

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

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

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – tylo May 9 '17 at 15:07
  • $\begingroup$ 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. $\endgroup$ – raisyn May 9 '17 at 16:24
  • 2
    $\begingroup$ 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. $\endgroup$ – Henrick Hellström May 9 '17 at 19:12
-2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I don't think this answers the question. $\endgroup$ – kodlu Apr 27 '17 at 23:13
  • $\begingroup$ 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? $\endgroup$ – raisyn Apr 27 '17 at 23:50
  • 2
    $\begingroup$ 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. $\endgroup$ – poncho Apr 28 '17 at 19:39
  • $\begingroup$ 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. $\endgroup$ – kodlu Apr 29 '17 at 1:09

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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