Constructing and using fast, twist-secure elliptic curves

03/14/2014
Speaker(s) : Benjamin SMITH ( Équipe-Projet GRACE, INRIA Saclay–Île-de-France, Laboratoire d'informatique (LIX),
When we're implementing elliptic curve cryptosystems, we generally want to use a curve with (1) a very strong group structure, and (2) fast cryptographic operations, (3) defined over a fast finite field.
The classic Gallant--Lambert--Vanstone technique uses efficient endomorphisms to offer (2), but generally this comes at the cost of a choice between (1) and (3). The newer Galbraith--Lin--Scott technique offers (2) and (3), but with a compromised (1): GLS curves can never have secure twists. In this talk we describe a new technique, based on some middlebrow theory of modular curves, that allows us to construct curves that have all three properties at the same time. We also discuss a fast software implementation of these curves (developed with Craig Costello and Huseyin Hisil) targeting Diffie--Hellman key exchange at the 128-bit security level.