1

 Stephen D. Miller
 Rutgers University

2

 Many cryptographic applications are based on the discrete logarithm.
 Important example: DLOG on elliptic curves.
 Is it always equally hard? Are
there “good curves” and “bad curves”?
 Main result: in some situations curves have equivalent difficulty.
 Mathematical content: proof/techniques use
 Elliptic Curves
 Expander Graphs
 Modular Forms
 Lfunctions
 Generalized Riemann Hypothesis

3

 When Windows or Microsoft office are installed, the user is required to
enter a 25digit alphanumeric antipiracy code.
 This code (“key”) must be short.
 The computer must be able to quickly recognize whether or not this is a
valid key, without giving away any clue as to how to manufacture
additional valid keys.
 Otherwise thieves would copy the software CDs and illegally resell them
with new codes. Key=CA$H.
 Future attacks will be faster.
How can one keep the key short, yet still keep up with the
attackers?
 This requires new methods and cryptosystems. Serious mathematics involved in
design.

4

 Mathematical Methods to hide information.
 Based on the difficulty of some underlying mathematical problem.
 Wellknown problems include:
 Precomputer age: guessing keys, inverting ax+b (mod n).
 Factoring (RSA).
 Discrete Logarithm.
 Braid group conjugacy problem.
 ….. But a good problem is just the start – implementation matters, too!

5

 A good cryptosystem needs more than just a hard problem behind it.
 It’s rare to reduce the cryptosystem directly to the underlying problem,
for example…
 Hypothetically: RSA might be easier than factoring.
 Some desired attributes:
 Speed of encryption and decryption.
 Use of a large state space – without having to store it all.
 Short “keys” (passwords).
 Stability against foreseen attacks.
Leave no trace.

6


7

 Difficult because the values of g^{x} are very scattered (mod p)
as x varies.
 Very important that p1 have a large prime factor
 (otherwise can use Chinese remainder theorem to “bootstrap” from easier
cases).
 Methods exist which are much faster than simply guessing. Some use the structure of Z.
 Possibly harder for more abstract incarnations of the same group. Different representations do not
necessarily have equivalent DLOG problems.
 Example: (Z/pZ)^{*} is abstractly isomorphic to Z/(p1)Z.
 DLOG is very easy on the
cyclic groups Z/mZ :
 can easily solve ax=b (mod m), if a and m are relatively prime.
 … especially when the
generator a is 1 (tautological).

8

 A method for two users to share a common
 password (without revealing it to the public)

9

 Introduced because of subexponential attacks on DLOG over (Z/nZ)^{*}.
 Idea: Find an isomorphic group where the structure of the integers is
not as apparent.
 Also want computation to be efficient, e.g. by polynomial operations
(rules out many abstract choices).
 Elliptic Curves: the set of solutions to an equation of the form
E : y^{2 }= x^{3 }+ a x + b
 over a finite field satisfies
these criteria.

10

 More or less, the solutions to an equation of the form
 E : y^{2 }= x^{3 }+ a x + b

11

 Introduced by V. Miller and N. Koblitz circa 1985.
 Bitforbit gives very strong cryptography, compared to e.g. RSA.
 RSA, EC, etc: backbone of $2 billion/year industry.
 Drawbacks:
 Elliptic curves are not well understood by mathematicians or
cryptographers.
 Perhaps danger of hidden attacks possibly outweighs benefits of use
(?).
 Therefore it is crucial to understand various risks. Many mathematically interesting
challenges remain.

12

 Unlike DLOG on (Z/nZ)^{*}, there can be many elliptic curves
having the same order.
 Elliptic curves over finite fields can be
 “supersingular”: have subexponential attacks.
 “ordinary”: so far, no subexponential attacks.*
 Want E(F_{q}) to be prime, or at least have a large prime
factor. E(F_{q}) should
be a cyclic group.

13

 Widely thought that ordinary curves are superior to supersingular
curves.
 National Institute of Standards and Technology (NIST) – Part of US
Department of Commerce.
 Proposed a family of convenient curves to serve as standards for
Elliptic Curve Cryptography.
 Some users fear these curves are cryptographically weak.
 How can the consumer know they have a good curve or not? Is my neighbor’s stronger?

14

 NIST P192
 Characteristic p =
6277101735386680763835789423207666416083908700390324961279
 Elliptic curve E: y^{2} = x^{3}  3x +
2455155546008943817740293915197451784769108058161191238065 over F_{p}
 Number of points = #E =
6277101735386680763835789423176059013767194773182842284081 (a prime)

15

 An isogeny is a nontrivial algebraic map between two elliptic
curves. It is a group
homomorphism.
Examples:
 Map any E to itself by z ! 2z (called an endomorphism)
 map C/Z[i] ! C/Z[2i] by z ! 2z
 map C/Z[i] ! C/Z[i] by z !
iz (called complex
multiplication “CM”)
 Tate’s Isogeny Theorem: two elliptic curves over F_{q} with the same
number of points are isogenous over F_{q}_{ }(isogenies
exist between them in both directions).
 Related to commensurability.
 Isogenies give an explicit reduction between DLOG on different curves if
they each have the same number of prime points. (Identical cyclic groups.)
 So because of Tate’s theorem, the selection problem can be
reinterpreted: is isogeny class a fine enough invariant for curve
selection? Or is more needed?

16

 Given an elliptic curve E over F_{q}, let End(E) denote the
endomorphisms of E
 ( = isogenies + trivial, zero
map)
 which are defined over the algebraic closure of F_{q}_{.}
 For an ordinary elliptic curve, End(E) is an order in some imaginary
quadratic number field K = Q(pd).
 This field K is an invariant of the isogeny class
(called the “Complex Multiplication
Field”)
 Orders are always of the form O_{D} = Z+cO_{K}, where O_{K}
is the ring of algebraic integers in K (solutions to monic integral
polynomials).
 The discriminant of the order O_{D} is related to the
discriminant d of K by D=c^{2}d. Curves for a given constant value of c
form levels.
 Isogenies can therefore be of two forms:
 They can preserve D (“horizontal”).
 Or they can change D (“vertical”).
 Supersingular curves all lie on the same level (by definition), so this
is really an issue pertaining to ordinary curves.

17

 Jao, M, Venkatesan (2004): Assuming the Generalized Riemann Hypothesis
(GRH), the DLOG problem on isogeneous elliptic curves is “random
reducible” in the following sense:

18

 All NIST and IPSec international standards elliptic curves have c_{max}
= 1
 (except NIST P256 which has c_{max} = 3)
 (and the NIST K family of Koblitz curves, which a priori have large c_{max
})

19

 Low degree isogenies between elliptic curves provide explicit polynomial
time reductions between the curves they connect.
 An “isogeny graph” is a graph whose vertices represent all the elliptic
curves on a given level, and whose edges represent low degree isogenies
(of degree (log q)^{2+}^{e}^{, } e > 0).
 Mixing Hypothesis: suppose that the random walk on this graph mixes
rapidly (i.e. after polylog(q) steps one reaches any vertex with uniform
probability up to a small error).
This is proven using GRH.
 Then by computing random low degree isogenies, DLOG can be explicitly
reduced between any two curves on that level.
 Therefore DLOG has uniform difficulty on this level (assuming the Mixing
Hypothesis).

20

 These applications of GRH and expander graphs are used in estimating the
security of the upcoming Windows Longhorn product key algorithm (2006).
 Also, solidifies earlier heuristic cryptographic arguments which relied
upon rapid mixing of the random walk (Kohel, Galbraith et al).

21

 Definitions: A graph G is a
collection of vertices V, and (undirected) edges E connecting the vertices.
 A kregular graph has exactly k edges meeting at each vertex.
 Adjacency operator A on L^{2}(V) averages the function over its neighbors
 The constant functions on V are eigenfunctions with the trivial eigenvalue
l = k.

22

 Graphs for which the random walk mixes rapidly (=uniformly distributed
up to small error). Assume degree
k is relatively small compared to the size of the graph V  e.g. k = (logV)^{power}.
 If all nontrivial eigenvalues of A satisfy
 for some r, then the random
walk mixes in (log k)^{r+1} steps. Can serve as definition of “expander”.
 “Optimal” bound is l <
2(k1)^{1/2}, known as the Ramanujan bound.
 Isogeny graphs are close to being “Ramanujan graphs”
 Can have l =
O(k^{1/2+}^{e}).

23

 Originally shown to exist by counting methods
 Pinsker: There are far more graphs than there are
 nonexpander graphs.
 Margulis (70s, 80s), LubotzkyPhillipsSarnak (1986) give first
constructions.
 LPS “Ramanujan graphs” use the (known) Ramanujan conjectures in their
proof. The Ramanujan conjectures
in number theory are a statement about optimal cancellation in random
sums.
 Other constructions: ReingoldVadhanWigderson “ZigZag”, algebraic
geometry. Have algebraic flavor.

24

 Supersingular case: essentially already observed by Ihara, Mestre, and
Pizer. Relies on (known) Ramanujan
conjectures as well, properties of Brandt matrices.
 Ordinary case (JMV): construction of isogeny graphs is a new method of
constructing expanders with small degree k = (logV)^{power}. Relies conditionally on the (unproven)
Generalized Riemann Hypothesis “GRH”.

25

 Let Q be a large integer.
 Let S = { primes p < (log Q)^{B} , p  Q } , for B > 2.
 Define the graph G to have
 vertices V=(Z/QZ)^{*}.
 edges connecting v to pv, for
each v 2 V and p 2 S.
 (G is the Cayley graph of the group (Z/QZ)^{*} with
respect to the generating set S).
 Theorem – Assuming GRH, G is an expander: its nontrivial
eigenvalues satisfy the bound
 l = O(k^{1/2+1/B}).

26

 DLOG has roughly equivalent difficulty on elliptic curves over F_{q}
whose endomorphism rings are “comparable” in size.
 There is a random polynomial time reduction (equivalence) between the
DLOG problems on such elliptic curves.
 NIST and IPSec international standards curves were not chosen as to
foist cryptographically weak curves upon an unsuspecting public.
 Method gives a new elementary construction of expander graphs.
