2022/2023
- 2023-01-24Razvan Barbulescu (CNRS/IMB)
The computation of unit and class groups in arbitrary degree number field is done in polynomial time in a simmilar fashion to the Shor’s factoring algorithm. Contrary to the fixed degree case which was solved in 2001 by Hallgren and a follow-up paper of Schmidt and Vollmer (2005), the arbitrary degree case requires errors estimations and is solved by the conjunction of two papers, Eisenträger et al. (2014) and de Boer et al. (2020).
In the particular case of cyclotomic fields we propose a version of the algorithm which makes use of cyclotomic units. Indeed, the Shor-like procedure of Eisenträger et al.’s algorithm produces random approximations of vectors in the dual of the lattice of units. In order to guarantee the correction of the algorithm, they have to do the computations in high precision and hence require a large amount of qubits. Thanks to the lattice of cyclotomic units, one can do the computations in smaller precision and reduce the number of qubits. - 2022-09-13Damien Robert (Inria/IMB)Breaking SIDH in polynomial time
SIDH/SIKE was a post quantum key exchange mechanism based on isogenies between supersingular elliptic curves which was recently selected in July 5 2022 by NIST to advance to the fourth round of the PQC competition. It was soon after broken during the summer in a series of three papers by Castryck-Decru, Maino-Martindale and myself.
The attacks all use the extra information on the torsion points used for the key exchange. We first review Petit’s dimension 1 torsion point attack from 2017 which could only apply to unbalanced parameters. Then we explain how the dimension 2 attacks of Maino-Martindale and especially Castryck-Decru could break in heuristic (but in practice very effective) polynomial time some parameters, including the NIST submission where the starting curve $E: y^2=x^3+x$ has explicit endomorphism $i$.
Finally we explain how by going to dimension 8, we could break in proven quasi-linear time all parameters for SIKE.
We will explain how the SIDH protocol worked at the beginning of the talk. We will see that the attack ultimately relies on a very simple 2x2 matrix computation! There will also be (hopefully) fun memes during the talk! - 2022-09-20Fredrik Johansson (Inria/IMB)Faster computation of elementary functions
Over a decade ago, Arnold Schönhage proposed a method to compute elementary functions (exp, log, sin, arctan, etc.) efficiently in “medium precision” (up to about 1000 digits) by reducing the argument using linear combinations of pairs of logarithms of primes or Gaussian primes. We generalize this approach to an arbitrary number of primes (which in practice may be 10-20 or more), using an efficient algorithm to solve the associated Diophantine approximation problem. Although theoretically slower than the arithmetic-geometric mean (AGM) by a logarithmic factor, this is now the fastest algorithm in practice to compute elementary functions from about 1000 digits up to millions of digits, giving roughly a factor-two speedup over previous methods. We also discuss the use of optimized Machin-like formulas for simultaneous computation of several logarithms or arctangents of rational numbers, which is required for precomputations.
- 2022-10-04Pierrick Dartois, Fabrice Etienne et Nicolas SarkisPrésentation des nouveaux doctorants de l'équipe LFANT
- 2022-10-11Rémy Oudompheng (Paribas)
The method found by W. Castryck and T. Decru to break SIDH requires computing (2^n,2^n)-isogenies from a product of elliptic curves to another abelian surface (which is also a product), which are realized as degree 2 correspondences between curves.
Transposing the attack to the other side of the SIDH exchange involves degree (3,3) isogenies that can be evaluated using either theta functions, or divisors on genus 2 curves. Methods for the curve approach exist for the Jacobian case, but the case of a product of elliptic curves (Bröker, Howe, Lauter, Stevenhagen 2014) can be difficult to implement for cryptographically relevant field sizes due to various limitations in CAS such as SageMath/Singular.
I will explain how traditional algebraic geometry can be called to the rescue to give a simple construction of the curve correspondence associated to the quotient of E_1 x E_2 by an isotropic (3,3) kernel. This leads to a rather fast computation method relying only on elementary field operations and 2 square roots. The journey will bring back some memories of 19th century projective geometry. Theta function experts might recognize familiar objects in the geometric construction. - 2022-10-18Èrell GachonSome Easy Instances of Ideal-SVP and Implications on the Partial Vandermonde Knapsack Problem
In our article, we generalize the works of Pan et al. (Eurocrypt’21) and Porter et al. (ArXiv’21) and provide a simple condition under which an ideal lattice defines an easy instance of the shortest vector problem. Namely, we show that the more automorphisms stabilize the ideal, the easier it is to find a short vector in it. This observation was already made for prime ideals in Galois fields, and we generalize it to any ideal (whose prime factors are not ramified) of any number field. We then provide a cryptographic application of this result by showing that particular instances of the partial Vandermonde knapsack problem, also known as partial Fourier recovery problem, can be solved classically in polynomial time.
- 2022-10-25Damien Robert (Inria/IMB)Evaluating isogenies in polylogarithmic time
We explain how the « embedding lemma » used in the recents attacks against SIDH can be used constructively. Namely we show that every $N$-isogeny between abelian varieties over a finite field admits an efficient representation allowing for its evaluation in time polylogarithmic in $N$. Furthermore, using Vélu’s formula for elliptic curves, or isogenies in the theta model for dimension $g>1$, this representation can be computed in time quasi-linear in $N^g$.
- 2022-11-08Anne-Edgar Wilke (IMB)Énumération des corps de nombres quartiques
Fixons un entier $n \geq 2$, et, pour $X \geq 0$, soit $C_n(X)$ l’ensemble des classes d’isomorphisme de corps de nombres de degré $n$ et de discriminant inférieur à $X$ en valeur absolue. La méthode de Hunter-Pohst permet d’énumérer $C_n(X)$ en temps $O(X^{\frac{n + 2}{4} + \epsilon})$. Pour $n \geq 3$, on s’attend à ce que cette complexité ne soit pas optimale : en effet, une conjecture classique, démontrée pour $n \leq 5$, prévoit qu’il existe une constante $c_n > 0$ telle que le cardinal de $C_n(X)$ soit équivalent à $c_n X$. En utilisant une paramétrisation des corps cubiques due à Davenport et Heilbronn, Belabas a mis au point un algorithme énumérant $C_3(X)$ en temps optimal $O(X^{1 + \epsilon})$. Je montrerai comment une paramétrisation des corps quartiques due à Bhargava permet de manière similaire d’énumérer $C_4(X)$ en temps $O(X^{\frac{5}{4} + \epsilon})$. Je présenterai ensuite des résultats numériques, ainsi que des perspectives d’amélioration et de généralisation en degré supérieur.
- 2022-11-15Henri Cohen (IMB)
I will describe with numerous examples a new Pari/GP package for infinite continued fractions which can in particular compute numerically the limit, the exact asymptotic speed of convergence (almost never given in the literature), accelerate continued fractions, and especially apply the powerful Apéry acceleration technique to almost all continued fractions, leading to hundreds of new ones.
- 2022-11-22Sulamithe Tsakou (Université de Picardie)
The security of many existing cryptographic systems relies on the difficulty of solving the discrete logarithm problem (DLP) in a group. For a generic group, we can solve this problem with many algorithms such as the baby-step-giant-step, the Pollard-rho or the Pohlig-Hellman algorithm. For a group with known structure, we use the index calculus algorithm to solve the discrete logarithm problem. Then, the DLP on the Jacobian of a hyperelliptic curve defined over a finite field $\mathbb{F}_{q^n}$ with $n>1$ are subject to index calculus attacks. After having chosen a convenient factor basis, the index calculus algorithm has three steps - the decomposition step in which we decompose a random point in the factor basis, the linear algebra step where we solve a matricial equation and the descent phase in which the discrete logarithm is deduced. The complexity of the algorithm crucially depends on the size of the factor basis, since this determines the probability for a point to be decomposed over the base and also the cost of the linear algebra step. Faugère et al (EC 2014) exploit the $2$-torsion point of the curve to reduce the size of the factor basis and then improve the complexity of the index calculus algorithm. In a similar manner, we exploit the endomorphism of the Jacobian to reduce the size of the factor base for certain families of ordinary elliptic curves and genus $2$ hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but our benchmarks show that reducing the size of the factor base allows to have a gain on the total complexity of index calculus algorithm with respect to the generic attacks.
- 2022-11-29Elie Bouscatié (Orange)
Outsourcing IT services has become very common worldwide for multiple reasons ranging from costs reduction to improved services. Whatever the actual reason is, the concrete consequence for the company that delegates such services is that a third party ends up with its data in clear because of the well-known limitations of standard encryption.
Ideally, this third party should only learn the minimal information necessary for performing the requested processing, which has motivated the design of countless encryption schemes compatible with specific processing. Such schemes belong to the realm of functional encryption, where the third party recovers a function f(x) from an encryption of x without learning anything else about x, with minimal interaction. Of course, the function f, and hence the encryption scheme, strongly depends on the considered application, which explains the profusion of papers related to this topic. We will focus on the possibility to allow a third party to search the presence of chosen substrings of different lengths (and more !) at any position in the encryption of a stream of data. After an introduction to this problematic and to the associated security notion, we will take a look at the proof of security of one specific construction. - 2022-12-06Léo Poyeton (IMB)Admissibility of filtered $(\varphi,N)$-modules
Filtered $(\varphi,N)$-modules over a $p$-adic field $K$ are semi-linear objects which are easy to define and can be implemented on a computer. The modules $D_{st}(V)$ defined by $p$-adic Hodge theory, where $V$ is a $p$-adic representation of the absolute Galois group of $K$, provide examples of filtered $(\varphi,N)$-modules. When $V$ is nice enough (semi-stable), the data of $D_{st}(V)$ is sufficient to recover $V$. A necessary and sufficient condition for a filtered $(\varphi,N)$-module $D$ to be written as $D_{st}(V)$ for some semi-stable representation $V$ is the condition of ``admissibility’’ which imposes conditions on the way the different structures of the $(\varphi,N)$-module interact with each other.
In a joint work with Xavier Caruso, we try to provide an algorithm which takes a filtered $(\varphi,N)$-module as an input and outputs whether it is admissible or not. I will explain how we can implement filtered $(\varphi,N)$-modules on a computer and why this question is well posed. I will then present an algorithm which answers the question if the $(\varphi,N)$-module is nice enough and explain the difficulties we are facing both in this nice case and in the general case. - 2022-12-13Samuel Le Fourn (Université Grenoble Alpes)Points de torsion d'une variété abélienne dans des extensions d'un corps fixé
Pour une variété abélienne A sur un corps de nombres K, on sait que pour toute extension finie L/K, le nombre c(L) de points de torsion de A(L) est fini par le théorème de Mordell-Weil.
En fait, un résultat de Masser prédit que c(L) est polynomial en [L:K] (si on fixe A et K) avec un exposant g=dim A, et une conjecture de Hindry et Ratazzi de 2012 donne l’exposant optimal (plus petit que g en général) en fonction d’une certaine structure de la variété abélienne (liée à son groupe dit de Mumford-Tate)
Dans cet exposé, je parlerai d’un travail commun avec Lombardo et Zywina dans lequel nous démontrons une forme inconditionnelle de cette conjecture (et cette conjecture en admettant la conjecture de Mumford-Tate), en insistant sur les résultats intermédiaires qui peuvent être d’intérêt indépendant pour la compréhension des représentations galoisiennes associées à des variétés abéliennes. - 2023-01-17Wouter Castryck (KU Leuven)Radical isogeny formulas
In several applications one is interested in a fast computation of the codomain curve of a long chain of cyclic N-isogenies emanating from an elliptic curve E over a finite field Fq, where N = 2, 3, … is some small fixed integer coprime to q. The standard approach proceeds by finding a generator of the kernel of the first N-isogeny, computing its codomain via Vélu’s formulas, then finding a generator of the kernel of the second N-isogeny, and so on. Finding these kernel generators is often the main bottleneck.
In this talk I will explain a new approach to this problem, which was studied in joint work with Thomas Decru, Marc Houben and Frederik Vercauteren. We argue that Vélu’s formulas can be augmented with explicit formulas for the coordinates of a generator of the kernel of an N-isogeny cyclically extending the previous isogeny. These formulas involve the extraction of an N-th root, therefore we call them “radical isogeny formulas”. By varying which N-th root was chosen (i.e., by scaling the radical with different N-th roots of unity) one obtains the kernels of all possible such extensions. Asymptotically, in our main cases of interest this gives a speed-up by a factor 6 or 7 over previous methods.
I will explain the existence of radical isogeny formulas, discuss methods to find them (the formulas become increasingly complicated for larger N), and pose some open questions.