05d-computational-hardness-cdh-ddh.ipynb

Kernel: SageMath 10.5

Notebook 05d: Computational Hardness. CDH and DDH

Module 05. The Discrete Logarithm and Diffie-Hellman

---

Motivating Question. Diffie-Hellman's security requires that Eve cannot compute $g^{ab}$ from $g^a$ and $g^b$. But is this really equivalent to solving the discrete log? Could there be a clever way to compute $g^{ab}$ without finding $a$ or $b$? And could Eve perhaps not even compute $g^{ab}$, but still distinguish it from a random group element? These questions lead to a precise hierarchy of hardness assumptions: DLP, CDH, and DDH.

---

Prerequisites. You should be comfortable with:

• The discrete logarithm problem (notebook 05a)

• Diffie-Hellman key exchange (notebook 05c)

Learning objectives. By the end of this notebook you will be able to:

1. State the CDH (Computational Diffie-Hellman) problem and assumption.

2. State the DDH (Decisional Diffie-Hellman) problem and assumption.

3. Explain the hierarchy: DDH $\Rightarrow$ CDH $\Rightarrow$ DLP.

4. Build an experimental DDH distinguisher game.

5. Understand where DDH fails (e.g., groups with efficient pairings).

1. Three Problems, One Hierarchy

Let $G = \langle g \rangle$ be a cyclic group of prime order $q$. We define three problems of increasing difficulty:

Problem	Given	Task	Intuition
DLP	$g, g^a$	Find $a$	"Invert the exponentiation"
CDH	$g, g^a, g^b$	Compute $g^{ab}$	"Combine two exponentiations"
DDH	$g, g^a, g^b, g^c$	Decide if $c = ab \bmod q$	"Detect a DH tuple"

The hardness hierarchy is: $$\text{DDH hard} \;\Longrightarrow\; \text{CDH hard} \;\Longrightarrow\; \text{DLP hard}$$

Equivalently (contrapositively): $$\text{DLP easy} \;\Longrightarrow\; \text{CDH easy} \;\Longrightarrow\; \text{DDH easy}$$

Each arrow is believed to be strict (not reversible) in general, though proving this remains open.

2. The CDH Problem

Computational Diffie-Hellman (CDH): Given $g, g^a, g^b$, compute $g^{ab}$.

This is exactly what an eavesdropper needs to do to break Diffie-Hellman. If you can solve the DLP (recover $a$ from $g^a$), you can trivially solve CDH: just compute $(g^b)^a$. But maybe you can compute $g^{ab}$ through some other route, without ever learning $a$ or $b$?

No such method is known for well-chosen groups.

# CDH challenge: given g, g^a, g^b, compute g^{ab}
p = next_prime(10^9)
g = Mod(primitive_root(p), p)
a = randint(2, p - 2)
b = randint(2, p - 2)

ga = g^a
gb = g^b
gab = g^(a * b)   # the answer Eve wants

print("=== CDH Challenge ===")
print(f"  g   = {g}")
print(f"  g^a = {ga}")
print(f"  g^b = {gb}")
print(f"  Goal: compute g^(ab) = ???")
print()

# Strategy 1: Solve DLP first, then compute
start = walltime()
a_recovered = discrete_log(ga, g)
gab_via_dlp = gb^a_recovered
t = walltime() - start
print(f"Strategy (DLP then compute): g^(ab) = {gab_via_dlp}")
print(f"  Correct? {gab_via_dlp == gab}")
print(f"  Time: {t*1000:.1f} ms")

Checkpoint 1. Can you think of any algebraic operation on $g^a$ and $g^b$ that would give $g^{ab}$ without knowing $a$ or $b$? For example, does $g^a \cdot g^b$ work? (Answer: $g^a \cdot g^b = g^{a+b} \neq g^{ab}$ in general.)

3. The DDH Problem

Decisional Diffie-Hellman (DDH): Given $(g, g^a, g^b, T)$, decide whether $T = g^{ab}$ or $T$ is a random group element.

DDH is a weaker requirement than CDH: you don't need to compute $g^{ab}$, you just need to recognise it. If DDH is hard, then DH tuple looks indistinguishable from a random tuple, which is exactly what we need for DH-based encryption schemes like ElGamal.

---

Misconception alert. "CDH and DDH are the same thing." No! DDH is strictly easier than CDH. If you can compute $g^{ab}$ (CDH), you can certainly decide whether $T = g^{ab}$ (DDH). But being able to distinguish does not mean you can compute. There are groups where DDH is easy but CDH is hard (e.g., groups with bilinear pairings. Module 07).

# DDH distinguishing game
def ddh_challenge(p, g):
    """
    Generate a DDH challenge: with probability 1/2, return a real
    DH tuple (g, g^a, g^b, g^{ab}), and with probability 1/2,
    return a random tuple (g, g^a, g^b, g^c).
    Returns (ga, gb, T, is_real).
    """
    g = Mod(g, p)
    a = randint(2, p - 2)
    b = randint(2, p - 2)
    ga = g^a
    gb = g^b
    
    if randint(0, 1) == 0:
        # Real DH tuple
        T = g^(a * b)
        return ga, gb, T, True
    else:
        # Random tuple
        c = randint(2, p - 2)
        T = g^c
        return ga, gb, T, False

# Play the game: can you tell real from random?
p = next_prime(10^9)
g_val = int(primitive_root(p))

print("=== DDH Distinguishing Game ===")
print(f"p = {p}, g = {g_val}")
print()
for trial in range(5):
    ga, gb, T, is_real = ddh_challenge(p, g_val)
    print(f"Trial {trial+1}: g^a={ga}, g^b={gb}, T={T}")
    print(f"  Real DH tuple? {is_real}")
    print()

Looking at those numbers, can you tell which are real DH tuples and which are random? Without solving the DLP, you cannot, that's exactly the DDH assumption.

4. The Hierarchy: DLP $\leftarrow$ CDH $\leftarrow$ DDH

Let us verify the implications experimentally.

DLP $\Rightarrow$ CDH: If we can solve DLP, we can solve CDH.

CDH $\Rightarrow$ DDH: If we can solve CDH, we can solve DDH (just compute $g^{ab}$ and compare with $T$).

# DLP => CDH: Use DLP solver to solve CDH
p = 1009   # small enough to solve DLP
g = Mod(primitive_root(p), p)
a, b = randint(2, p-2), randint(2, p-2)
ga, gb = g^a, g^b

# Solve CDH via DLP
a_found = discrete_log(ga, g)
cdh_answer = gb^a_found
print("=== DLP => CDH ===")
print(f"Recovered a = {a_found}")
print(f"Computed g^(ab) = {cdh_answer}")
print(f"Correct? {cdh_answer == g^(a*b)}")

# CDH => DDH: Use CDH solver to solve DDH
print("\n=== CDH => DDH ===")
ga, gb, T, is_real = ddh_challenge(p, int(g))

# Solve DDH using CDH: compute g^{ab} and check if T equals it
a_found = discrete_log(ga, g)
gab_computed = gb^a_found
ddh_guess = (T == gab_computed)
print(f"CDH gives g^(ab) = {gab_computed}")
print(f"T = {T}")
print(f"DDH guess (T == g^ab?): {ddh_guess}")
print(f"Actually real? {is_real}")
print(f"Correct guess? {ddh_guess == is_real}")

5. Statistical DDH Test

Let us run many DDH challenges and see if a naive distinguisher (random guessing) can do better than 50%.

# Run many DDH challenges and test a "random guess" strategy
p = next_prime(10^6)   # medium-size: hard enough that naive stats fail
g_val = int(primitive_root(p))
N = 1000

# Strategy: guess randomly (should get ~50%)
correct_random = 0
for _ in range(N):
    ga, gb, T, is_real = ddh_challenge(p, g_val)
    guess = (randint(0, 1) == 0)  # random guess
    if guess == is_real:
        correct_random += 1

print(f"Random guessing: {correct_random}/{N} = {100*correct_random/N:.1f}% correct")
print(f"(Expected: ~50%)")

# Strategy: use DLP oracle (should get 100%)
# Only feasible for small p
p_small = 101
g_small = int(primitive_root(p_small))
correct_dlp = 0
for _ in range(N):
    ga, gb, T, is_real = ddh_challenge(p_small, g_small)
    g_mod = Mod(g_small, p_small)
    a_rec = discrete_log(ga, g_mod)
    gab = gb^a_rec
    guess = (T == gab)
    if guess == is_real:
        correct_dlp += 1

print(f"\nDLP-based strategy: {correct_dlp}/{N} = {100*correct_dlp/N:.1f}% correct")
print(f"(Expected: 100%)")

Checkpoint 2. In the DDH game, what if someone proposes the following "distinguisher": compute $g^a \cdot g^b = g^{a+b}$ and check if $T = g^{a+b}$? Does this work? (Answer: No, $g^{ab} \neq g^{a+b}$ in general, so this test has no useful signal.)

6. When DDH Breaks: Quadratic Residues

In $\mathbb{Z}/p\mathbb{Z}^*$ with a safe prime $p = 2q + 1$, the DDH assumption holds in the order-$q$ subgroup (quadratic residues). But in the full group $\mathbb{Z}/p\mathbb{Z}^*$, DDH can be broken using the Legendre symbol.

The key observation: the Legendre symbol $\left(\frac{x}{p}\right)$ tells us whether $x$ is a quadratic residue. Since $g^a$ is a QR iff $a$ is even, and $g^{ab}$ is a QR iff $ab$ is even, we can leak information about the parity of $a \cdot b$ from the Legendre symbols of $g^a, g^b, T$.

# DDH breaks in Z/pZ* using Legendre symbol
p = 23   # safe prime: (23-1)/2 = 11 is prime
g = Mod(primitive_root(p), p)  # generator of full group

print(f"p = {p} (safe prime: q = {(p-1)//2})")
print(f"g = {int(g)} (primitive root, order {p-1})")
print()

# Legendre symbol: kronecker(x, p) = +1 if QR, -1 if QNR
def legendre(x, p):
    return kronecker(int(x), p)

# For a DH tuple (g^a, g^b, g^{ab}):
# legendre(g^a) = (-1)^a, legendre(g^b) = (-1)^b
# legendre(g^{ab}) = (-1)^{ab}
# But (-1)^{ab} = ((-1)^a)^b  ... we can check parity!

print("Legendre-symbol based DDH test:")
for a in [3, 4, 5, 6]:
    for b in [7, 8]:
        La = legendre(g^a, p)
        Lb = legendre(g^b, p)
        Lab = legendre(g^(a*b), p)
        product = La * Lb
        # For a real DH tuple, L(g^{ab}) should be consistent
        # with L(g^a) * L(g^b) when both are -1 => L(g^{ab}) = +1

Notice that $\text{Legendre}(g^{ab}) = \text{Legendre}(g^a) \cdot \text{Legendre}(g^b)$ always holds for real DH tuples. For a random $T$, this relation holds only half the time. This gives a distinguisher with advantage $1/2$. DDH is broken in the full group!

Solution: work in the order-$q$ subgroup (quadratic residues), where the Legendre symbol is always $+1$ and provides no information.

---

Bridge to Module 07. In elliptic curve groups with bilinear pairings, DDH is also easy (the pairing gives a DDH oracle). This is why pairing-based crypto uses different hardness assumptions, but CDH can still be hard in those groups!

# DDH distinguisher using Legendre symbol
def legendre_ddh_distinguisher(p, g_val, ga, gb, T):
    """Guess whether (g, ga, gb, T) is a real DH tuple,
    using the Legendre symbol in Z/pZ*."""
    La = kronecker(int(ga), p)
    Lb = kronecker(int(gb), p)
    LT = kronecker(int(T), p)
    # Real tuple should satisfy LT == La * Lb
    return (LT == La * Lb)

# Test the distinguisher
p = 23
g_val = int(primitive_root(p))
N = 1000
correct = 0
for _ in range(N):
    ga, gb, T, is_real = ddh_challenge(p, g_val)
    guess = legendre_ddh_distinguisher(p, g_val, ga, gb, T)
    if guess == is_real:
        correct += 1

print(f"Legendre distinguisher: {correct}/{N} = {100*correct/N:.1f}% correct")
print(f"Random would give ~50%. The Legendre symbol gives ~75% advantage!")
print(f"(Real tuples always pass; random tuples pass ~50% of the time.)")

Checkpoint 3. The Legendre distinguisher gets about 75% accuracy. Can you explain why it's 75% and not 100%? (Hint: real tuples always pass the test, but random tuples also pass the test half the time by coincidence.)

7. Which Assumption Does What?

Different cryptographic schemes rely on different assumptions:

Scheme	Assumption Needed	Why
DH key exchange	CDH	Eve must not be able to compute $g^{ab}$
ElGamal encryption	DDH	Ciphertext $(g^r, m \cdot h^r)$ must be indistinguishable from random
Schnorr signatures	DLP	Forger must not be able to recover the secret key
Pedersen commitments	DLP	Opener must not be able to find two different openings

---

Crypto foreshadowing. In Module 09 (Sigma protocols), Schnorr signatures rely on DLP hardness. In Module 07 (Pairings), the pairing operation breaks DDH but preserves CDH, enabling constructions like BLS signatures and identity-based encryption.

8. Exercises

Exercise 1 (Worked): CDH from DLP

Problem. Given $p = 43, g = 3, g^a = 25, g^b = 34$, solve CDH by first solving the DLP.

Solution.

1. Solve $3^a \equiv 25 \pmod{43}$: try $a = 8$ since $3^8 = 6561 \equiv 25 \pmod{43}$.

2. Compute $g^{ab} = (g^b)^a = 34^8 \bmod 43$.

# Exercise 1, verification
p = 43; g = Mod(3, p)
ga = Mod(25, p); gb = Mod(34, p)

a_found = discrete_log(ga, g)
print(f"DLP: a = {a_found}")
print(f"Check: g^a = {int(g^a_found)}")

gab = gb^a_found
print(f"CDH: g^(ab) = (g^b)^a = {int(gab)}")

Exercise 2 (Guided): DDH Experiment

Problem. Run the DDH distinguishing game 500 times with $p = 10007$ and a primitive root $g$.

1. Use the Legendre-symbol distinguisher.

2. Record the accuracy.

3. Now repeat, but generate challenges in the order-$q$ subgroup (use $g^2$ as the base). Does the Legendre distinguisher still work?

Hint: In the QR subgroup, every element has Legendre symbol $+1$, so the test always returns "real".

# Exercise 2, fill in the TODOs
p = 10007

# TODO 1: Test Legendre distinguisher in full group
# g = primitive_root(p)
# correct = 0
# for _ in range(500):
#     ga, gb, T, is_real = ddh_challenge(p, g)
#     guess = legendre_ddh_distinguisher(p, g, ga, gb, T)
#     if guess == is_real:
#         correct += 1
# print(f"Full group: {correct}/500 = {100*correct/500:.1f}%")

# TODO 2: Test in QR subgroup (use g^2 as base)
# g_qr = int(Mod(g, p)^2)
# correct_qr = 0
# for _ in range(500):
#     ga, gb, T, is_real = ddh_challenge(p, g_qr)
#     guess = legendre_ddh_distinguisher(p, g_qr, ga, gb, T)
#     if guess == is_real:
#         correct_qr += 1
# print(f"QR subgroup: {correct_qr}/500 = {100*correct_qr/500:.1f}%")
# print("(Should be ~50%. Legendre gives no info in QR subgroup)")

Exercise 3 (Independent): Is CDH Strictly Harder Than DDH?

Problem. We showed that solving CDH lets you solve DDH. But is the converse true?

1. Explain why a DDH oracle (which only gives yes/no) cannot directly compute $g^{ab}$.

2. However, show that a DDH oracle can recover $g^{ab}$ one bit at a time. (Hint: consider $g^{ab} \cdot g^{-r}$ for known $r$ values and use the DDH oracle to check.)

3. Research: in which groups is the gap between CDH and DDH known to be strict?

# Exercise 3, write your solution here

Summary

Concept	Key Fact
DLP	Given $g, g^a$, find $a$
CDH	Given $g, g^a, g^b$, compute $g^{ab}$
DDH	Given $(g, g^a, g^b, T)$, decide if $T = g^{ab}$
Hierarchy	DDH hard $\Rightarrow$ CDH hard $\Rightarrow$ DLP hard
DDH breaks	Legendre symbol breaks DDH in full $\mathbb{Z}/p\mathbb{Z}^*$; work in QR subgroup instead
Applications	DH needs CDH; ElGamal needs DDH; signatures need DLP

We now understand the theoretical hardness that protects Diffie-Hellman. But how fast can an attacker actually solve the DLP? The next two notebooks study concrete algorithms: baby-step giant-step (a generic $O(\sqrt{n})$ attack) and Pohlig-Hellman (exploiting smooth group orders).

---

Next: 05e. Baby-Step Giant-Step