At first glance, DL seems clearly stronger than CDH. If you can solve discrete logs, you can obviously solve CDH: given $g^x$ and $g^y$, you recover $x$ and $y$, and then compute $g^{xy}$. The reverse implication is where the mystery begins. Suppose you had access to a machine — an oracle — that, given $(g^x,g^y)$, instantly returns $g^{xy}$. Could you then use this ability to compute discrete logarithms efficiently?
This question is not just an idle theoretical curiosity. It is deeply tied to the security of widely deployed protocols and cryptosystems. Many constructions are proven secure under the assumption that CDH is hard, while others rely on the hardness of DL. In practice we often treat them as “morally similar,” but in theory, their exact equivalence is still an open problem in many standard settings. Cryptographers have spent decades building reductions, finding special cases, and understanding under which group structures CDH hardness truly implies DL hardness.
And yet, despite being open in general, we are surprisingly close in some settings. For a short recap, here the definition of the two contestants:
█ Approaches. Let $\mathcal{O}_{\text{CDH}}$ be the Oracle that given the input $(g^x,g^y)$ returns $g^{xy}$. In the approaches from the literature, e.g. [1],[2],[3], the oracle is actually misused. That means, we do not care that the Oracle returns $g^{xy}$ and therewith breaks the Diffie-Hellman key exchange protocol, but that it can be used to do exponentiation in the unknown exponent. If you only have $g^x$, for unknown $x$, the step to $g^{x^2}$ is assumed to be hard. But with the help of $\mathcal{O}_{\text{CDH}}$ we can do the following:
\begin{align*}
&\mathcal{O}_{\text{CDH}}(g^e,g^e) \rightarrow g^{e^2} \\
&\mathcal{O}_{\text{CDH}}(g^{e^2},g^{e^2}) \rightarrow g^{e^4} \\
&\mathcal{O}_{\text{CDH}}(g^{e^4},g^{e}) \rightarrow g^{e^5}
\end{align*} So the Oracle lets you compute $g^{e^x}$ for an arbitrary integer $x$ using the usual square and multiply algorithm efficiently.
So instead of having access only to $\mathbb{Z}^+_{\varphi(p)}$ we have access to $\mathbb{Z}^*_{\varphi(p)}$ This is why the integer $\varphi(\varphi(p))$ comes into play, where $\varphi(\cdot)$ is as usual Euler's Totient Function. Recall that the size of each subgroup of $\mathbb{F}^*_p$ depends on $\varphi(p) = p-1$. Roughly speaking, the exponents $e$ from $g^e$ are reduced modulo $p-1$. If $p-1$ is smooth itself [i.e. only contains small prime factors] we can solve discrete logarithm efficiently by using the Pohlig-Hellman Algorithm. No need for an Oracle at all.
However the exponents $e^x$ from $g^{e^x}$, which we compute indirectly with the help of our Oracle are reduced modulo $\varphi(\varphi(p)) = \varphi(p-1)$. And if $\varphi(p-1)$ happens to be smooth [Note: $\varphi(p-1)$ can be smooth, albeit $\varphi(p)$ is not] we have another working attack vector and this can be used in a similar manner as the Pohlig-Hellman Algorithm. And this is mostly used for the proofs in the literature to show that in some cases these two problems are equivalent.
Intuition: “The oracle gives us enough algebraic leverage to simulate exponentiation, so the group order seen by the exponent arithmetic becomes $\varphi(p-1)$, not $\varphi(p)$.
So we have, if:
- $\varphi(p)$ is smooth $\rightarrow$ DLP can be solved efficiently
- $\varphi(\varphi(p))$ is smooth and access to $\mathcal{O}_{\text{CDH}}\rightarrow$ DLP can be solved efficiently
Or if you dont want to rely on smoothness, you could replace the smoothness requirement, like in done [2], with an Factorization Oracle as well as an All-Primes-But-P Oracle, which yields
- Access to $\mathcal{O}_{\text{CDH}}$, $\mathcal{O}_{\text{IFP}}$ and $\mathcal{O}_{\text{AbP}} \rightarrow$ DLP can be solved efficiently
Given a fixed in integer (here $\varphi(\varphi(p))$ the probability that it is B-smooth [contains no prime factors larger than B] is negligible, especially for large integers of cryptographic size. However, giving up smoothness comes at the cost of two further Oracles.
But there is help. It would be possible to do slightly better if the probability of finding something smooth could be increased. Here, we can use "auxiliary groups", as stated in [3]. For example you could create an Elliptic Curve $y^2 = x^3+Ax+B$ that "lives in the exponent of $g$". Assume that $p = 2q +1$, so $p$ is a Safe-Prime, which is a good choice for $p$ and well excepted to create secure protocols. So we have to find an Elliptic Curve that is defined modulo $q$ (the factor 2 can be negelected), which can be done efficiently. The advantage is, that the number of points an Elliptic Curve $E(\mathbb{F}^*_q)$, depends not only on $q$ but also on the parameters $A$ and $B$. It is well known that for the number of points $\#E(\mathbb{F}^*_q)$ it holds
$$ p+1-2\sqrt{q} < \#E(\mathbb{F}^*_q) < p+1+2\sqrt{q}$$
$\#E(\mathbb{F}^*_q)$ it can be computed efficiently (at least for curves of the form $x^3+Ax+B$). You can vary the parameters $A$ and $B$ and test for $B$-smoothness [Note: This is exactly the idea of the ECM-Algorithm, that tries to find Elliptic Curves over $\mathbb{Z}^*_N$ with smooth order to factorizes $N$]
At first, this does not seem very promising, since achieving $B$-smoothness is a challenging goal and is often sufficient to break certain protocols. [The Discrete-Calculus Algorithm to break Discrete Logarithms is actually more or less completely based on the ability to generate smooth numbers]
However, discrete logarithms not only appear in cyclic finite fields, but in modern times they are mostly utilised on elliptic curves. Elliptic curves have the advantage that the involved bit sizes are much smaller (256-bit primes are often sufficient), but efficient algorithms such as the aforementioned discrete calculus approach cannot be applied.
However, in the reduction case, the reduced bit size is actually a drawback in terms of security, much like in the case of quantum algorithms, which are more dangerous to elliptic curves in the near future because a smaller bit size requires fewer Qbits. The smaller the bit size, the more likely it is that auxiliary curves with a smooth order will be found. Surprisingly, this is possible for known standard curves. In [4], the authors found auxiliary curves for almost all the standard curves used in elliptic curve cryptography today, e.g. NIST P-256, BrainpoolP256t1 and Curve25519. They therefore showed that the equivalence between CDH and DL for these curves actually holds.
So far, all reductions sought smoothness. But what if we abandon smoothness entirely and try to extract bits of the discrete log instead?
---
The Hidden Shift-Oracle. All the approaches above seek a way to find something smooth, i.e. to control the primes factors of $\varphi(p)$ or $\varphi(\varphi(p))$. What you always can guarantee is, that $2$ is a factor of these numbers.
Can the smallest of all prime number $2$ already be enough to determine the discrete logarithm?
Theoretically, yes. Let $p$ again be a safe prime $p=2q+1$. Given the element $g^x$, you could simply create the set $$S = \{g^x, g^{x+1},\ldots,g^{x+d}\},$$ for $d \approx \log q$. And for all these elements in $S$ you could compute $$g^{(x+i)^{(q-1)/2}} = g^{v_i}$$, using the CDH-Oracle. That means you could compute the Legendre symbols $\binom{e+i}{q}$. Collecting around $\log(q)$ such symbols, heuristically, this should uniquely determine the integer $e$. That means, only one $x$ should satisfy the following equation:
$$ \frac{1}{2^d}\sum^{q-1}_{x=1} \prod^d_{i=0} \left( \binom{x+i}{q}+v_i\right) = (-1)^{\prod^d_{i=0} v_i} $$ However, this is an notorious difficult problem and is known as the Hidden Shift Problem. So, we have
- Access to $\mathcal{O}_{\text{CDH}}$ and $\mathcal{O}_{\text{Hidden Shift}}$ oracles $\rightarrow$ DLP can be solved efficiently
---
Unrelated but interesting. To show how powerful the $\mathcal{O}_{\text{CDH}}$ oracle acutally is, there is a reduction that uses the CDH-Oracle to factorize integers (Ideas come from [2]) and it is acutally not that complicated:
1. Sample a random $v \in \mathbb{Z}^*_N$.
2. Compute $v^2 = g \Leftrightarrow v = g^{1/2}$ Note: $g$ is a quadratic-residue
3. Compute $g^2 = u \Leftrightarrow g = u^{1/2}$ Note: $u$ is a quadratic-residue
Compute (using the CDH-Oracle that uses base $u$)
$$\mathcal{O}_{\text{CDH}}(g,g) = \mathcal{O}_{\text{CDH}}(u^{1/2},u^{1/2}) = w = u^{1/4} = g^{1/2}$$ So we have two square roots of $g$:
$$v^2 = g\;\text{and}\;w^2 = u^{1/2} = g$$.
Since we sampled $v$ randomly, but $u$ is a quadratic residue in $\mathbb{Z}^*_N$ (hence not random). This means or each $v$ we have the probability
$$\text{Pr}[\text{gcd}(v-w,N) > 1] \approx \frac{1}{2}$$ I implemented this reduction in Sage (see Appendix) and it works perfectly.
[1] U. Maurer and S. Wolf, "Diffie-Hellman, decision Diffie-Hellman, and discrete logarithms," Proceedings. 1998 IEEE International Symposium on Information Theory (Cat. No.98CH36252), Cambridge, MA, USA, 1998, pp. 327-, doi: 10.1109/ISIT.1998.708932.
[2] Koblitz, Neal & Menezes, Alfred & Shparlinski, Igor. (2010). Discrete Logarithms, Diffie-Hellman, and Reductions.. IACR Cryptology ePrint Archive. 2010. 577.
[3] Ueli Maurer and Stefan Wolf, The Relationship Between Breaking the Diffie-Hellman Protocol and Computing Discrete Logarithms, SIAM Journal on Computing, 1689--1721, Number 5, Volume 28, Year 1999, Month 4
[4] Alexander May, Dlog is Practically as Hard (or Easy) as DH – Solving Dlogs via DH Oracles on EC Standards, TChess 2023
Appendix A
###############################################
# Discrete Log (Slow) – Linear Search
###############################################
def DLOG(g, r, N):
"""
Naive discrete log: find x such that g^x = r mod N.
WARNING: exponential time.
"""
m = Mod(g, N).multiplicative_order()
t = g
for x in range(1, m):
if t == r:
return x
t = (t * g) % N
return -1
###############################################
# CDH Oracle: returns g^(log_g(a) * log_g(b))
###############################################
def CDHORACLE(g, a, b, N):
e1 = DLOG(g, a, N)
e2 = DLOG(g, b, N)
return Integer(power_mod(g, e1 * e2, N))
###############################################
# Find next prime p ≡ r (mod m)
###############################################
def nextPrimeModk(p, r, m):
p = next_prime(p)
while p % m != r:
p = next_prime(p)
return p
###############################################
# Example experiment
###############################################
# Choose primes p,q ≡ 3 (mod 4)
p = nextPrimeModk(1000, 3, 4) # Change to create other primes
q = nextPrimeModk(800, 3, 4) # Change to create other primes
N = p * q
print(f"p = {p}, q = {q}, N = {N}")
# 1. Sample random v coprime to N
v = randint(1, N)
while gcd(v, N) > 1:
v = randint(1, N)
print(f"v = {v}")
# 2.
g = Integer(power_mod(v, 2, N))
print(f"g = {g}")
# Compute u = g^2
u = Integer(power_mod(g, 2, N))
print(f"u = {u}")
# Use CDH oracle: u2 = u^(1/4) ≡ g^(1/2)
u2 = CDHORACLE(u, g, g, N)
# Verification: u2^2 ≡ g^2 ≡ v^2
print(f"u2^2 mod N = {Mod(u2^2, N)}")
print(f"v^2 mod N = {Mod(v^2, N)}")
# Check if gcd reveals a factor
print(f"gcd(u2 - v, N) = {gcd(u2 - v, N)}")
No comments:
Post a Comment