# 2016/2017

- 2017-05-23Christophe Petit (Oxford)We review existing cryptographic schemes based on the hardness of computing isogenies between supersingular isogenies, and present some attacks against them. In particular, we present new techniques to accelerate the resolution of isogeny problems when the action of the isogeny on a large torsion subgroup is known, and we discuss the impact of these techniques on the supersingular key exchange protocol of Jao-de Feo.
- 2017-03-14Cécile Pierrot (Centrum Wiskunde & Informatica, Amsterdam)Nearly sparse linear algebraLinear algebra is a widely used tool both in mathematics and computer science, and cryptography is no exception to this rule. Yet, it introduces some particularities, such as dealing with linear systems that are often sparse, or, in other words, linear systems inside which a lot of coefficients are equal to zero. We propose to enlarge this notion to nearly sparse matrices, characterized by the concatenation of a sparse matrix and some dense columns, and to design an algorithm to solve this kind of problems. Motivated by discrete logarithms computations on medium and high characteristic finite fields, the Nearly Sparse Linear Algebra bridges the gap between classical dense linear algebra problems and sparse linear algebra ones, for which specific methods have already been established. Our algorithm particularly applies on one of the three phases of NFS (Number Field Sieve) which precisely consists in finding a non trivial element of the kernel of a nearly sparse matrix.
This is a joint work with Antoine Joux.

- 2017-01-17Damien Stehlé (ENS Lyon)Tuple lattice sievingLattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075n+o(n)}$, where n is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887n+o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661n+o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812n+o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration. Joint work with Shi Bai, Thijs Laarhoven
- 2016-11-22Razvan BarbulescuPairings are a relatively new cryptographic tool which have been the object of many arithmetic works. In the last few years some of the pairings have become obsolete because of the progress on the underlying problem of discrete logarithm in finite fields. We propose ourselves to make a list of pairings constructions, to explain their advantages but also their weaknesses. The sporadic curves are vulnerable to the Logjam attack and have never been a popular choice. The small characteristic curves allow a very good arithmetic but are the target of a quasi-polynomial algorithm. The pairings where the characteristic has a low Hamming weight, which eliminate the cost of modular reductions, have been the object of special attacks. When the embedding degree is composite the one can use the tower field arithmetic but there are also tower field attacks.
- 2016-11-08Aurélien FocquéAlgorithmes BMSS et Lercier Sirvent pour SEA dans PARI
- 2016-10-18Gregor Seiler (ETH Zurich)Computing ray class fields of imaginary quadratic fields
- 2016-10-11Enea Milio (Inria Nancy Grand Est)Une implantation en genre 2 de "Computing functions on Jacobians and their quotients" de Jean-Marc Couveignes et Tony EzomeCet article explique comment définir et évaluer des fonctions sur des Jacobiennes de courbes de genre $g$ et sur des quotients de telles Jacobiennes par des sous-groupes isotropes maximaux de la $\ell$-torsion, pour $\ell>2$ premier. Pour le cas spécifique du genre 2, il est bien connu qu’à partir d’une courbe hyperelliptique $C$ et d’un sous-groupe isotrope maximal $V$, le quotient $\mathrm{Jac}(C)/V$ est la Jacobienne d’une courbe hyperelliptique $C’$, $(\ell,\ell)$-isogène à $C$. L’application de $C$ vers $\mathrm{Jac}(D)$ peut être décrite avec des fractions rationnelles de degré en $O(\ell)$. L’article donne une méthode pour calculer $C’$ et ces fractions. Pour notre exposé, nous nous proposons d’exposer le contenu de ce papier et de parler de l’implantation que nous avons faite en genre 2.