The Four Faces of Lifting for the Elliptic Curve Discrete Logarithm Problem

Joseph Silverman
Brown University

Let E be an elliptic curve defined over a (large) finite field
GF(p). For two given points P and Q of E, the "elliptic curve discrete
logarithm problem" (ECDLP) asks for an integer n such that Q=nP. Many
cryptographic constructions that make use of the classical discrete
logarithm problem in GF(p) also work for elliptic curves, and using ECDLP is
often advantageous because the fastest known method for solving ECDLP is
exponential. Various authors have considered the possibility of
solving ECDLP by lifting the curve E and the points P and Q (or some
associated collection of points) from GF(p) to a larger ring or field. In
this talk I will describe how these lifting methods naturally are of four
basic types and will consider the different hard problems that are
associated with each of the four categories of lifting problems.


Back to Contemporary Methods in Cryptography