Exercise 11.12. Let p be a prime, q a prime that divides p ’ 1, γ ∈ Z— an

p

— of order q, and ± ∈ G. For δ ∈ G,

element that generates a subgroup G of Zp

a representation of δ with respect to γ and ± is a pair of integers (r, s),

with 0 ¤ r < q and 0 ¤ s < q, such that γ r ±s = δ.

(a) Show that for any δ ∈ G, there are precisely q representations (r, s)

of δ with respect to γ and ±, and among these, there is precisely one

with s = 0.

(b) Show that given a representation (r, s) of 1 with respect to γ and ±

such that s = 0, we can e¬ciently compute logγ ±.

(c) Show that given any δ ∈ G, along with any two distinct representa-

tions of δ with respect to γ and ±, we can e¬ciently compute logγ ±.

(d) Suppose we are given access to an “oracle” that, when presented with

any δ ∈ G, tells us some representation of δ with respect to γ and ±.

Show how to use this oracle to e¬ciently compute logγ ±.

11.3 The Di¬e“Hellman key establishment protocol 279

The following two exercises examine the danger of the use of “short”

exponents in discrete logarithm based cryptographic schemes that do not

work with a group of prime order.

e e

Exercise 11.13. Let p be a prime and let p ’ 1 = q11 · · · qr r be the prime

factorization of p ’ 1. Let γ be a generator for Z— . Let X, Y be positive

p

e

numbers. Let Q be the product of all the prime powers qi i with qi ¤ Y .

Suppose you are given p, the primes qi dividing p ’ 1 with qi ¤ Y , along

with γ and an element ± of Z— . Assuming that x := logγ ± < X, show how

p

to compute x in time

(Y 1/2 + (X/Q)1/2 ) · len(p)O(1) .

Exercise 11.14. Continuing with the previous exercise, let Q be the prod-

uct of all the primes qi dividing p ’ 1 with qi ¤ Y . Note that Q | Q. The

goal of this exercise is to heuristically estimate the expected value of log Q ,

assuming p is a large, random prime. The heuristic part is this: we shall

assume that for any prime q ¤ Y , the probability that q divides p ’ 1 for

a randomly chosen “large” prime p is ∼ 1/q. Under this assumption, show

that

E[log Q ] ∼ log Y.

The results of the previous two exercises caution against the use of “short”

exponents in cryptographic schemes based on the discrete logarithm problem

for Z— . Indeed, suppose that p is a random 1024-bit prime, and that for

p

reasons of e¬ciency, one chooses X ≈ 2160 , thinking that a method such

as the baby step/giant step method would require ≈ 280 steps to recover x.

However, if we choose Y ≈ 280 , then we have reason to expect Q to be at

least about 280 , in which case X/Q is at most about 280 , and so we can in

fact recover x in roughly 240 steps, which may be a feasible number of steps,

whereas 280 steps may not be. Of course, none of these issues arise if one

works in a subgroup of Z— of large prime order, which is the recommended

p

practice.

An interesting fact about the Di¬e“Hellman problem is that there is no

known e¬cient algorithm to recognize a solution to the problem. Some cryp-

tographic protocols actually rely on the apparent di¬culty of this decision

problem, which is called the decisional Di¬e“Hellman problem. The

following three exercises develop a random self-reducibility property for this

decision problem.

Exercise 11.15. Let p be a prime, q a prime dividing p ’ 1, and γ an

Finding generators and discrete logarithms in Z—

280 p

element of Z— that generates a subgroup G of order q. Let ± ∈ G, and let H

p

be the subgroup of G—G generated by (γ, ±). Let γ , ± be arbitrary elements

˜˜

of G, and de¬ne the map

Zq — Zq ’ G — G

ρ:

([r]q , [s]q ) ’ (γ r γ s , ±r ±s ).

˜ ˜

Show that the de¬nition of ρ is unambiguous, that ρ is a group homomor-

phism, and that

• if (˜ , ±) ∈ H, then img(ρ) = H, and

γ˜

• if (˜ , ±) ∈ H, then img(ρ) = G — G.

γ˜ /

Exercise 11.16. For p, q, γ as in the previous exercise, let Dp,q,γ consist

of all triples of the form (γ x , γ y , γ xy ), and let Rp,q,γ consist of all triples of

the form (γ x , γ y , γ z ). Using the result from the previous exercise, design a

probabilistic algorithm that runs in expected polynomial time, and that on

input p, q, γ, along with a triple “ ∈ Rp,q,γ , outputs a triple “— ∈ Rp,q,γ such

that

• if “ ∈ Dp,q,γ , then “— is uniformly distributed over Dp,q,γ , and

• if “ ∈ Dp,q,γ , then “— is uniformly distributed over Rp,q,γ .

/

Exercise 11.17. Suppose that A is a probabilistic algorithm that takes

as input p, q, γ as in the previous exercise, along a triple “— ∈ Rp,q,γ , and

outputs either 0 or 1. Furthermore, assume that A runs in strict polynomial

time. De¬ne two random variables, Xp,q,γ and Yp,q,γ , as follows:

• Xp,q,γ is de¬ned to be the output of A on input p, q, γ, and “— , where

“— is uniformly distributed over Dp,q,γ , and

• Yp,q,γ is de¬ned to be the output of A on input p, q, γ, and “— , where

“— is uniformly distributed over Rp,q,γ .

In both cases, the value of the random variable is determined by the random

choice of “— , as well as the random choices made by the algorithm. De¬ne

(p, q, γ) := P[Xp,q,γ = 1] ’ P[Yp,q,γ = 1] .

Using the result of the previous exercise, show how to use A to design a

probabilistic, expected polynomial-time algorithm that takes as input p, q, γ

as above, along with “ ∈ Rp,q,γ , and outputs either “yes” or “no,” so that

if (p, q, γ) ≥ 0.001, then for all “ ∈ Rp,q,γ , the probability

that A correctly determines whether “ ∈ Dp,q,γ is at least

0.999.

11.4 Notes 281

Hint: use the Cherno¬ bound.

The following exercise demonstrates that distinguishing “Di¬e“Hellman

triples” from “random triples” is hard only if the order of the underlying

group is not divisible by any small primes, which is another reason we have

chosen to work with groups of large prime order.

Exercise 11.18. Assume the notation of the previous exercise, but let us

drop the restriction that q is prime. Design and analyze a deterministic

algorithm A that takes inputs p, q, γ and “— ∈ Rp,q,γ , that outputs 0 or 1,

and that satis¬es the following property: if t is the smallest prime dividing

q, then A runs in time (t + len(p))O(1) , and the “distinguishing advantage”

(p, q, γ) for A on inputs p, q, γ is at least 1/t.

11.4 Notes

The probabilistic algorithm in §11.1 for ¬nding a generator for Z— can be

p

made deterministic under a generalization of the Riemann hypothesis. In-

deed, as discussed in §10.7, under such a hypothesis, Bach™s result [10] im-

plies that for each prime q | (p ’ 1), the least positive integer a such that

[a]p ∈ Z— \ (Z— )q is at most 2 log p.

p p

Related to the problem of constructing a generator for Z— is the question

p

of how big is the smallest positive integer g such that [g]p is a generator

for Z— ; that is, how big is the smallest (positive) primitive root modulo p.

p

The best bounds on the least primitive root are also obtained using the

same generalization of the Riemann hypothesis mentioned above. Under

this hypothesis, Wang [98] showed that the least primitive root modulo p is

O(r6 len(p)2 ), where r is the number of distinct prime divisors of p’1. Shoup

[90] improved Wang™s bound to O(r4 len(r)4 len(p)2 ) by adapting a result of

Iwaniec [48, 49] and applying it to Wang™s proof. The best unconditional

bound on the smallest primitive root modulo p is p1/4+o(1) (this bound is

also in Wang [98]). Of course, just because there exists a small primitive