Christophe Petit


Elliptic curve cryptography

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].

In a work (together with Kristin Lauter, David Kohel and Jean-Pierre Tignol), we proposed a partial attack on the CGL hash function [CGL07] that precisely consists in computing some large degree isogenies between supersingular elliptic curves, assuming knowledge of their endomorphism rings.

The techniques developed in this work also provide a constructive version to a theorem of Max Deuring from 1941: given a maximal order in the quaternion algebra ramified at only one prime and the infinity, we can construct a supersingular elliptic curve with endomorphism ring isomorphic to this maximal order in probabilistic polynomial time.


Contributions

Here are my papers that are related to elliptic curves. Your questions/comments are welcome!

Traveling in supersingular elliptic curves isogeny graphs
Christophe Petit, Kristin Lauter
In preparation.

On Generalized First Fall Degree Assumptions
Huang Yun-Ju, Christophe Petit, and Tsuyoshi Takagi
Preprint (2014)

Bounding HFE with SRA
Christophe Petit
Preprint (2013)

Finding Roots in GF(p^n) with the Successive Resultant Algorithm
Christophe Petit
LMS Journal of Computation and Mathematics, Volume 17, Issue A, pp 203-217. Special issue for
ANTS, Algorithmic Number Theory Symposium conference.
Preprint. LMS link.

On the quaternion $\ell$-isogeny path problem
LMS Journal of Computation and Mathematics, Volume 17, Issue A, pp 418-432. Special issue for ANTS, Algorithmic Number Theory Symposium conference.
David Kohel, Kristin Lauter, Christophe Petit, Jean-Pierre Tignol
Preprint. LMS link.

Improvement of Faugère et al.'s method to solve ECDLP
Huang Yun-Ju, Christophe Petit, Naoyuki Shinohara, and Tsuyoshi Takagi
IWSEC 2013 - Advances in Information and Computer Security
Paper.

On polynomial systems arising from a Weil descent
Christophe Petit and Jean-Jacques Quisquater
Asiacrypt 2012 - 18th International Conference on the Theory and Application of Cryptology and Information Security
Paper. Extended version.

Improving the complexity of index calculus algorithms in elliptic curves over binary fields
Jean-Charles Faugère, Ludovic Perret, Christophe Petit, Guénaël Renault
Eurocrypt 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques
Paper.