34
$\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$
5
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – e-sushi
    Jan 18, 2016 at 22:26
  • $\begingroup$ Title: What are ´mutual´ logarithms? logarithms ´of´ generators? The example suggests g as base of logarithm. $\endgroup$ Feb 7 at 17:59
  • $\begingroup$ @SamGinrich Do you have a better word in mind? What is to be captured by the term, is the hard problem of finding a prime p (with restrictions?) and an element x (with restrictions?), such that $\log_2(x)$ and $\log_3(x)$ are both known in $\mathbb{Z}_p$. Is this a hard problem, even if we don't put any significant restrictions on the choice of p and/or x? $\endgroup$ Feb 19 at 14:23
  • $\begingroup$ Not yet clear: What does mutual refer to, 2,3 or p,x ? $\endgroup$ Feb 19 at 15:39
  • $\begingroup$ It refers to the discrete logarithms $\log_2(x)$ and $\log_3(x)$ in $\mathbb{Z}_p$, being known simultaneously (sharing the property of being known). Which I assume would require the prime p to be doctored in such way. Hence the mutuality. $\endgroup$ Feb 19 at 16:10

2 Answers 2

0
$\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$
3
  • 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, 2017 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, 2017 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$ May 9, 2017 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$
4
  • $\begingroup$ I don't think this answers the question. $\endgroup$
    – kodlu
    Apr 27, 2017 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, 2017 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, 2017 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, 2017 at 1:09

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.