Why are elliptic curves so important? A subexponential algorithm for ECDLP in small characteristics Traveling in supersingular isogeny graphs Related papers and talks
Why are elliptic curves so important?
Since their introduction in cryptography in 1985, independtly by Koblitz [K87] and Miller [M85], elliptic curves have become increasingly popular. The reason is that the elliptic curve discrete logarithm problem (ECDLP) is believed to be much harder to solve than its counterpart over finite fields (DLP) or the integer factorization problem (FP), the two main alternatives for public key cryptography. ''Harder to solve'' implies shorter keys needed: 160-bit elliptic curve keys are commonly believed to be as secure as 1024-bit factorization or discrete logarithm keys. (See keylength.com for currently recommended key sizes.) The main reason why ECDLP is "more trusted" than DLP or FP is because DLP and FP can be solved in subexponential time with index calculus algorithms. Until recently, no similar result had been obtained for ECDLP: except for exceptional curves and somewhat non natural families of parameters, the time required to solve was believed to be exponential in the size of the parameters.ECDLP can be solved in (heuristic) subexponential time for binary curves
In fact, we recently showed that an algorithm of Claus Diem [D11] does achieve a subexponential complexity, under a common assumption in algebraic cryptanalysis. This algorithm applies to elliptic curves over binary fields, a very relevant case in practice since 10 out of the 15 curves recommended by NIST for digital signatures are binary curves. [NIST]. Diem's algorithm reduces ECDLP to the resolution of a particular system of polynomial equations. We observed that this system (and a larger class of systems as well) has a very particular structure, which typically helps the resolution. In particular, the system has a block structure and its corresponding ideal contains an abnormally high number of low degree polynomials that can be explicitely written as algebraic combinations of the initial polynomials. Under a common assumption in algebraic cryptanalysis, supported in our case by experimental results, these low degree equations provide very good complexity estimates for the polynomial system resolution with Gröbner basis algorithms. Our analysis suggests that ECDLP over F(2^n) can be solved in time roughly 2^(cn^(2/3)log(n)) for some constant c<2, while the problem was previously thought to be exponential. However, the result is mainly of theoretical interest so far. According to our estimations, generic algorithms will be beaten for parameters n larger than 2000, far beyond the 160 bits security currently recommended for ECC.Traveling in supersingular isogeny graphs
Isogenies are homomorphisms between elliptic curves with the same number of points. Their potential utility for the discrete logarithm problem has long been identified, for example by Galbraith [G]. Large degree isogenies are also believed to be hard to compute in general. This has led to a few proposals for building cryptographic schemes based on potentially hard isogeny problems [CGL07,JS11].