2016/2017

• 2017-06-13
  Bernhard Schmidt (Nanyang Technological University, Singapore)
  The Anti-Field-Descent Method
  A circulant Hadamard matrix of order $v$ is a matrix of the form \[H=\begin{pmatrix} a_1 & a_2 & \cdots & a_v \\ a_v & a_1 & \cdots & a_{v-1} \\ \cdots & \cdots & \cdots &\cdots \\ a_2 & a_3 & \cdots & a_1 \\ \end{pmatrix}\] with $a_i=\pm 1$ such that any two rows of $H$ are orthogonal with respect to the standard inner product. It is conjectured that there is no circulant Hadamard matrix of order larger than $4$.

  One way to study circulant Hadamard matrices is the so-called ``field-descent method’’. The essential fact behind this method is that certain cyclotomic integers necessarily are contained in relatively small fields and thus must have relatively small complex modulus. In this talk, I will present a method which reveals a complementary phenomenon: certain cyclotomic integers cannot be contained in relatively small fields and thus must have relatively large complex modulus. This method provides new necessary conditions for the existence of circulant Hadamard matrices.

  This is joint work with K. H. Leung.

• 2017-06-06
  Guilhem Castagnos (imb)
  Encryption Switching Protocols Revisited: Switching modulo p
  Last year, Couteau, Peters and Pointcheval introduced a new primitive called encryption switching protocols, allowing to switch ciphertexts between two encryption schemes. If such an ESP is built with two schemes that are respectively additively and multiplicatively homomorphic, it naturally gives rise to a secure 2-party computation protocol. It is thus perfectly suited for evaluating functions, such as multivariate polynomials, given as arithmetic circuits. Couteau et al. built an ESP to switch between Elgamal and Paillier encryptions which do n ot naturally fit well together. Consequently, they had to design a clever variant of Elgamal over Z/nZ with a costly shared decryption. In this talk, we first present a conceptually simple generic construction for encryption switching protocols. We then give an efficient instantiation of our generic approach that uses two well-suited protocols, namely a variant of Elgamal in Z/pZ and the Castagnos-Laguillaumie encryption defined over class groups of quadrat ic fields which is additively homomorphic over Z/pZ. Among other advantages, this allows to perform all computations modulo a prime p instead of an RSA modulus. Overall, our solution leads to significant reductions in the number of rounds as well as the number of bits exchanged by the parties during the interactive protocols. We also show how to extend its security to the malici ous setting.

  Joint work with Laurent Imbert and Fabien Laguillaumie.

• 2017-05-30
  Benjamin Wesolowski (EPFL)
  Isogeny graphs of ordinary abelian varieties
  Fix a prime number $\ell$. Graphs of isogenies of degree a power of $\ell$ are well-understood for elliptic curves, but not for higher-dimensional abelian varieties. We study the case of absolutely simple ordinary abelian varieties over a finite field. We analyse graphs of so-called $\mathfrak l$-isogenies, resolving that, in arbitrary dimension, their structure is similar, but not identical, to the ``volcanoes’’ occurring as graphs of isogenies of elliptic curves. Specializing to the case of principally polarizable abelian surfaces, we then exploit this structure to describe graphs of a particular class of isogenies known as $(\ell, \ell)$-isogenies. These results lead to new, provable algorithms to navigate in isogeny graphs, with consequences for the CM-method in genus 2, for computing explicit isogenies, and for the random self-reducibility of the discrete logarithm problem in genus 2 cryptography.
• 2017-05-23
  Christophe Petit (Oxford)
  Post-quantum cryptography from supersingular isogeny problems?
  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-14
  Cécile Pierrot (Centrum Wiskunde & Informatica, Amsterdam)
  Nearly sparse linear algebra
  Linear 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-17
  Damien Stehlé (ENS Lyon)
  Tuple lattice sieving
  Lattice 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-22
  Razvan Barbulescu
  A brief history of pairings
  Pairings 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-08
  Aurélien Focqué
  Algorithmes BMSS et Lercier Sirvent pour SEA dans PARI
• 2016-10-18
  Gregor Seiler (ETH Zurich)
  Computing ray class fields of imaginary quadratic fields
• 2016-10-11
  Enea Milio (Inria Nancy Grand Est)
  Une implantation en genre 2 de "Computing functions on Jacobians and their quotients" de Jean-Marc Couveignes et Tony Ezome
  Cet 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.