March 19th, 2018, Chitchanok Chuengsatiansup (EPI ARIC, Inria Lyon): Optimizing multiplications with vector instructions

In this talk, I will explain techniques to achieve fast and secure implementations.

I will introduce a vector unit which is a part of a CPU and ways to utilize it. I will also briefly emphasize the importance of and ways to prevent software side-channel attacks. Then, I will explain how to optimize scalar multiplication in Curve41417 and polynomial multiplication Streamlined NTRU Prime $9829^{739}$.

Karatsuba’s method play an important role in the former case, while combinations of Karatsuba’s method and Toom–Cook’s method are crucial in the latter case. Both implementations utilize the CPU’s vector unit.

3 octobre 2016, Aurore Guillevic: Key-size updates for pairing-friendly elliptic curves

The building-bloc function in bilinear pairing-based cryptography is a Weil or Tate pairing over an elliptic (or hyperelliptic) curve, defined over a finite field, and of small embedding degree. The security relies on the hardness of a discrete logarithm computation in an elliptic curve and in a finite field: the target group of a cryptographic bilinear pairing is a finite field GF(p^n) where usually the embedding degree n is small: 1 ≤= n ≤= 24 and most of the time, n=12. (Small characteristic finite fields are now avoided: there exists a quasi-polynomial-time algorithm to compute DL). Until 2014 is was assumed that computing a discrete logarithm in a large characteristic field GF(p^n) was at least as hard as in a prime field GF(q) where log q = log p^n (i.e. of same total size). This is not true anymore: the Number Field Sieve algorithm now has better variants for such finite fields. To obtain the same security, finite fields should be enlarged. The asymptotic complexity of the NFS algorithm is not tight enough to obtain tight intervals for key-sizes according to a given security level. We propose to study the ingredient in NFS that determines the complexity: the size of the elements involved in the relation collection. Graphs of these sizes will be presented for 2 ≤ n ≤ 12, with quite interesting results in some cases. The norms were computed experimentally.