2021/2022
- 2022-07-12Michael Monagan (Simon Fraser University)Computing with polynomials over algebraic number fields
Let $K = \mathbb{Q}(\alpha_1,\dots,\alpha_k)$ be an algebraic number field. We are interested in computing polynomial GCDs in $K[x]$ and $K[x_1,\dots,x_n]$. Of course we also want to multiply, divide and factor polynomials over $K$. In $K[x]$ we have the Euclidean algorithm but it “blows up”; there is a growth in the size of the rational numbers in the remainders. It is faster to compute the GCD modulo one or more primes and use the Chinese remainder theorem and rational number reconstruction. This leads to computing a GCD in $R[x]$ where $R = K \bmod p$ is usually not be a field – it is a finite ring.
How do Computer Algebra Systems represent elements of $K$? How do Computer Algebra Systems compute GCDs in $K[x]$? What is the best way to do arithmetic in $R$? How can we compute a polynomial GCD in $K[x_1,\dots,x_n]$? In the talk we will try to answer these questions and we will present some timing benchmarks comparing our own C library for computing GCDs in $R[x]$ with Maple and Magma. - 2022-06-28Andreas Enge (Inria/IMB)Implementing fastECPP in CM
FastECPP is currently the fastest approach to prove the primality of general numbers, and has the additional benefit of creating certificates that can be checked independently and with a lower complexity. It crucially relies on the explicit construction of elliptic curves with complex multiplication.
I will take you on a leisurely stroll through the different phases of the ECPP and fastECPP algorithms, with explanations of their complexity. We will then see the algorithmic choices I have made when integrating a parallelised implementation of fastECPP into my CM software, which has recently been used to prove the primality of a number of record size 50000 digits. - 2022-06-14Antoine Leudière (Université de Lorraine)An explicit CRS-like action with Drinfeld modules
L’une des pierres angulaires de la cryptographie des isogénies est l’action (dite CRS), simplement transitive, du groupe des classes d’un ordre d’un corps quadratique imaginaire, sur un certain ensemble de classes d’isomorphismes de courbes elliptiques ordinaires.
L’échange de clé non-interactif basé sur cette action (espace homogène difficile) est relativement lent (de Feo, Kieffer, Smith, 2019) ; la structure du groupe (Beullens, Kleinjung, Vercauteren, 2019) est difficile à calculer. Pour palier à cela, nous décrivons une action, simplement transitive, de la jacobienne d’une courbe hyperelliptique imaginaire, sur un certain ensemble de classes d’isomorphismes de modules de Drinfeld.
Après avoir motivé l’utilisation des modules de Drinfeld en lieu et place des courbes elliptiques, nous décrirons un algorithme efficace de calcul de l’action, ainsi que la récente attaque de Benjamin Wesolowski sur l’échange de clé donné par l’action. - 2022-05-31Philippe Elbaz-Vincent (Institut Fourier / Inria / IMB)Sur quelques points, plus ou moins effectifs, de cohomologie des groupes arithmétiques
Nous donnerons un panorama de certaines techniques et résultats pour le calcul de la cohomologie des groupes arithmétiques de rang $\ge 4$ pour des anneaux d’entiers algébriques, ainsi que leurs applications arithmétiques et K-théoriques. Nous ferons ensuite un focus sur les méthodes utilisant le modèle de Voronoi (euclidien ou hermitien), ainsi que plusieurs améliorations algorithmiques. Nous préciserons certains résultats relatifs aux complexes de Voronoi et leurs cellules (pour $\mathrm{GL}_N$ avec $N<12$), ainsi qu’un travail en cours avec B. Allombert et R. Coulangeon sur les formes parfaites de rang $N$ sur $\mathcal{O}_K$ et la cohomologie de $\mathrm{GL}_N(\mathcal{O}_K)$ pour certains anneaux d’entiers avec $N=4,5,6$. Nous mentionnerons aussi plusieurs problèmes ouverts relatifs à ces modèles.
- 2022-05-24Alice Pellet-Mary (CNRS/IMB)Rigorous computation of class group and unit group
Computing the class group and the unit group of a number field is a famous problem of algorithmic number theory. Recently, it has also become an important problem in cryptography, since it is used in multiple algorithms related to algebraic lattices.
Subexponential time algorithms are known to solve this problem in any number fields, but they heavily rely on heuristics. The only non-heuristic (but still under ERH) known algorithm, due to Hafner and McCurley, is restricted to imaginary quadratic number fields.
In this talk, we will see a rigorous subexponential time algorithm computing units and class group (and more generally S-units) in any number field, assuming the extended Riemann hypothesis.
This is a joint work with Koen de Boer and Benjamin Wesolowski. - 2022-05-18Wessel van Woerden (CWI Amsterdam)On the Lattice Isomorphism Problem, Quadratic Forms, Remarkable Lattices, and Cryptography
A natural and recurring idea in the knapsack/lattice cryptography literature is to start from a lattice with remarkable decoding capability as your private key, and hide it somehow to make a public key. This is also how the code-based encryption scheme of McEliece (1978) proceeds.
This idea has never worked out very well for lattices: ad-hoc approaches have been proposed, but they have been subject to ad-hoc attacks, using tricks beyond lattice reduction algorithms. On the other hand the framework offered by the Short Integer Solution (SIS) and Learning With Errors (LWE) problems, while convenient and well founded, remains frustrating from a coding perspective: the underlying decoding algorithms are rather trivial, with poor decoding performance.
In this work, we provide generic realisations of this natural idea (independently of the chosen remarkable lattice) by basing cryptography on the Lattice Isomorphism Problem (LIP). More specifically, we provide:
- a worst-case to average-case reduction for search-LIP and distinguish-LIP within an isomorphism class, by extending techniques of Haviv and Regev (SODA 2014).
- a zero-knowledge proof of knowledge (ZKPoK) of an isomorphism. This implies an identification scheme based on search-LIP.
- a key encapsulation mechanism (KEM) scheme and a hash-then-sign signature scheme, both based on distinguish-LIP.
The purpose of this approach is for remarkable lattices to improve the security and performance of lattice-based cryptography. For example, decoding within poly-logarithmic factor from Minkowski’s bound in a remarkable lattice would lead to a KEM resisting lattice attacks down to a poly-logarithmic approximation factor, provided that the dual lattice is also close to Minkowski’s bound. Recent works have indeed reached such decoders for certain lattices (Chor-Rivest, Barnes-Sloan), but these do not perfectly fit our need as their duals have poor minimal distance. - 2022-05-17Daniel Fiorilli (Université Paris Saclay)Résultats de type oméga pour les comptages de corps cubiques
Il s’agit d’un travail en collaboration avec P. Cho, Y. Lee et A. Södergren. Depuis les travaux de Davenport-Heilbronn, beaucoup d’articles ont été ecrits donnant des estimations de plus en plus précises sur le comptage du nombre de corps cubiques de discriminant au plus X. Mentionnons par exemple les travaux de Belabas, Belabas-Bhargava-Pomerance, Bhargava-Shankar-Tsimerman, Taniguchi-Thorne et Bhargava-Taniguchi-Thorne. Dans cet exposé je parlerai d’un résultat négatif, qui montre que l’hypothèse de Riemann implique une limitation sur la plus petite taille possible du terme d’erreur dans ces estimations. Nous approchons la questions à partir de la théorie des petits zéros de fonctions $L$, en particulier la philosophie de Katz-Sarnak et les articles subséquents pour la famille des fonctions zeta de Dedekind de corps cubiques. Je présenterai aussi des résultats numériques obtenus avec pari/gp et le programme «cubic» de Belabas qui indiquent que notre résultat pourrait être optimal.
- 2022-05-03Sergey Yurkevich (University of Vienna, Inria)The generating function of the Yang-Zagier Numbers is algebraic
In a recent paper Don Zagier mentions a mysterious integer sequence $(a_n) _{n \geq 0}$ which arises from a solution of a topological ODE discovered by Marco Bertola, Boris Dubrovin and Di Yang. In my talk I show how to conjecture, prove and even quantify that $(a_n) _{n \geq 0}$ actually admits an algebraic generating function which is therefore a very particular period. The methods are based on experimental mathematics and algorithmic ideas in differential Galois theory, which I will show in the interactive part of the talk. The presentation is based on joint work with A. Bostan and J.-A. Weil.
- 2022-04-26Lassina Dembélé (King's College London)Correspondance de Langlands inertielle explicite pour ${\rm GL}_2$ et quelques applications arithmétiques
Dans cet exposé nous allons décrire une approche explicite qui permet de calculer les types automorphes inertiels pour ${\rm GL}_2$. Nous donnerons ensuite quelques applications de cet algorithme à des problèmes diophantiens ou de nature arithmétique.
- 2022-04-12Josué Tonelli-Cueto (Inria Paris, IMJ-PRG)A p-adic Descartes solver: the Strassman solve
Solving polynomials is a fundamental computational problem in mathematics. In the real setting, we can use Descartes’ rule of signs to efficiently isolate the real roots of a square-free real polynomial. In this talk, we show how to translate this method into the p-adic worlds. We show how the p-adic analog of Descartes’ rule of signs, Strassman’s theorem, leads to an algorithm to isolate the p-adic roots of a square-free p-adic polynomial and provide some complexity estimates adapting the condition-based complexity framework from real/complex numerical algebraic geometry to the p-adic case.
- 2022-04-05Damien Robert (IMB)Towards computing the canonical lift of an ordinary elliptic curve in medium characteristic
$\newcommand{\F}{\mathbb{F}}$Satoh’s algorithm for counting the number of points of an elliptic curve $E/\F_q$ with $q=p^n$ is the fastest known algorithm when $p$ is fixed: it computes the invertible eigenvalue $λ$ of the Frobenius to $p$-adic precision $m$ in time $\tilde{O}(p^2 n m)$. Since by Hasse’s bound, recovering $\chi_{\pi}$ requires working at precision $m=O(n)$, the point counting complexity is of $\tilde{O}(p^2 n^2)$, quasi-quadratic in the degree $n$.
Unfortunately, the term $p^2$ in the complexity makes Satoh’s algorithm suitable only for smaller $p$. For medium sized $p$, one can use Kedlaya’s algorithm which cost $\tilde{O}(p n^2 m)$ or a variant by Harvey’s which cost $\tilde{O}(p^{1/2} n^{5/2} m + n^4 m)$, which have a better complexity on $p$ but a worse one on $n$. For large $p$, the SEA algorithm costs $\tilde{O}(\log^4 q)$.
In this talk, we improve the dependency on $p$ of Satoh’s algorithm while retaining the dependency on $n$ to bridge the gap towards medium characteristic. We develop a new algorithm with a complexity of $\tilde{O}(p n m)$. In the particular case where we are furthermore provided with a rational point of $p$-torsion, we even improve this complexity to $\tilde{O}(p^{1/2} n m)$.
This is a joint work with Abdoulaye Maiga. - 2022-03-29Andreas Pieper (Universität Ulm)Constructing all genus 2 curves with supersingular Jacobian
F. Oort showed that the moduli space of principally polarized supersingular abelian surfaces is a union of rational curves. This is proven by showing that every principally polarized supersingular abelian surface is the Jacobian of a fibre of one of the families of genus 2 curves $\pi: \mathcal{C}\rightarrow \mathbb{P}^1$ constructed by L. Moret-Bailly. We present an algorithm that makes this construction effective: Given a point $x\in \mathbb{P}^1$ we compute a hyperelliptic model of the fibre $\pi^{-1}(x)$. The algorithm uses Mumford’s theory of theta groups to compute quotients by the group scheme $\alpha_p$.
- 2022-03-22Jean Kieffer (Harvard University)
Les fonctions thêta permettent de relier les points de vue algébrique et analytique dans l’étude des variétés abéliennes: ce sont des formes modulaires de Siegel qui fournissent des coordonnées sur ces variétés et leurs espaces de modules. Rendre ce lien effectif nécessite un algorithme efficace d’évaluation de ces fonctions thêta en un point. Dupont, dans sa thèse (2006), a décrit un algorithme heuristique basé sur la moyenne arithmético-géométrique (AGM) et un schéma de Newton pour évaluer certaines fonctions thêta en genre 1 et 2 en temps quasi-linéaire en la précision. Le but de cet exposé est de montrer que l’on peut en fait obtenir un algorithme certifié dont la complexité est uniforme. Je discuterai également des obstacles restants pour généraliser ce résultat en dimension supérieure.
- 2022-03-15Pierrick Dartois (Corps des mines, Rennes 1)Cryptanalyse du protocole OSIDH
Oriented Supersingular Isogeny Diffie-Hellman (OSIDH) est un échange de clé post-quantique proposé par Leonardo Colò et David Kohel en 2019. La construction repose sur l’action du groupe de classe d’un ordre quadratique imaginaire sur un espace de courbes elliptiques supersingulières et peut donc être vue comme une généralisation du célèbre échange de clé à base d’isogénies CSIDH. Cependant, OSIDH est très différent de CSIDH d’un point de vue algorithmique parce qu’OSIDH utilise des groupes de classe plus structurés que CSIDH. Comme l’ont reconnu Colò et Kohel eux-mêmes, cela rend OSIDH plus vulnérable aux attaques. Pour contourner cette faiblesse, ils ont proposé une façon ingénieuse d’effectuer l’échange de clé en échangeant de l’information sur l’action du groupe de classe au voisinage des courbes publiques, et ont conjecturé que cette information additionnelle n’impacterait pas la sécurité.
Dans cet exposé, on réévaluera la sécurité d’OSIDH en proposant une nouvelle attaque, inspirée des travaux précédents d’Onuki. Notre attaque est exponentielle mais parvient à casser les paramètres choisi par Colò et Kohel, contrairement à l’attaque d’Onuki. On verra aussi des contremesures possibles à cette attaque, dont on analysera l’impact sur OSIDH d’un point de vue de l’efficacité et de la fonctionnalité. - 2022-03-08Elena Berardini (Télécom Paris)Calcul d'espaces de Riemann-Roch pour les codes géométriques
Les codes de Reed-Solomon sont largement utilisés pour représenter des données sous forme de vecteurs, de sorte que les données peuvent être récupérées même si certaines coordonnées des vecteurs sont corrompues. Ces codes ont de nombreuses propriétés. Leurs paramètres sont optimaux. Ils permettent de reconstruire des coordonnées qui ont été effacées. Ils sont compatibles avec l’addition et la multiplication de données. Néanmoins, ils souffrent de certaines limitations. Notamment, la taille de stockage des coordonnées des vecteurs augmente de manière logarithmique avec le nombre de coordonnées. Les codes dits géométriques généralisent les codes de Reed-Solomon en bénéficiant des mêmes propriétés, tout en étant libres de ces limitations. Par conséquent, l’utilisation de codes géométriques apporte des gains de complexité, et s’avère utile dans plusieurs applications telles que le calcul distribué sur les secrets et les preuves zero-knowledge. Les codes géométriques sont construits en évaluant des familles de fonctions, appelées espaces de Riemann-Roch, en les points rationnels d’une courbe. Il s’ensuit que le calcul de ces espaces est crucial pour la mise en œuvre des codes géométriques. Dans cet exposé, je présenterai un travail récent en collaboration avec S. Abelard, A. Couvreur et G. Lecerf sur le calcul effectif des bases des espaces de Riemann-Roch de courbes. Après avoir révisé l’état de l’art sur le sujet, je discuterai des idées à la base de notre algorithme, en particulier la théorie de Brill-Noether et l’utilisation des expansions de Puiseux. Les courbes utilisées dans la construction des codes géométriques sont pour la plupart limitées à celles pour lesquelles les bases de Riemann-Roch sont déjà connues. Ce nouveau travail et ceux qui suivront, permettront la construction de codes géométriques à partir de courbes plus générales.
- 2022-02-08Elisa Lorenzo Garcia (Université de Neuchâtel)Reduction type of hyperelliptic curves in terms of the valuations of their invariants.
In this talk we will first review the classical criteria to determine the (stable) reduction type of elliptic curves (Tate) and of genus 2 curves (Liu) in terms of the valuations of some particular combinations of their invariants. We will also revisit the theory of cluster pictures to determine the reduction type of hyperelliptic curves (Dokchitser’s et al.). Via Mumford theta constants and Takase and Tomae’s formulas we will be able to read the cluster picture information by looking at the valuations of some (à la Tsuyumine) invariants in the genus 3 case. We will also discuss the possible generalization of this strategy for any genus and some related open questions.
- 2022-01-25Céline Maistret (University of Bristol)Parity of ranks of abelian surfaces
Let $K$ be a number field and $A/K$ an abelian surface. By the Mordell-Weil theorem, the group of $K$-rational points on $A$ is finitely generated and as for elliptic curves, its rank is predicted by the Birch and Swinnerton-Dyer conjecture. A basic consequence of this conjecture is the parity conjecture: the sign of the functional equation of the $L$-series determines the parity of the rank of $A/K$.
Assuming finiteness of the Shafarevich-Tate group, we prove the parity conjecture for principally polarized abelian surfaces under suitable local constraints. Using a similar approach we show that for two elliptic curves $E_1$ and $E_2$ over $K$ with isomorphic $2$-torsion, the parity conjecture is true for $E_1$ if and only if it is true for $E_2$. In both cases, we prove analogous unconditional results for Selmer groups. - 2022-01-04Guillaume Moroz (Inria, LORIA)New data structure for univariate polynomial approximation and applications to root isolation, numerical multipoint evaluation, and other problems
We present a new data structure to approximate accurately and efficiently a polynomial $f$ of degree $d$ given as a list of coefficients. Its properties allow us to improve the state-of-the-art bounds on the bit complexity for the problems of root isolation and approximate multipoint evaluation. This data structure also leads to a new geometric criterion to detect ill-conditioned polynomials, implying notably that the standard condition number of the zeros of a polynomial is at least exponential in the number of roots of modulus less than $\frac{1}{2}$ or greater than $2$.
- 2021-12-14Xavier Goaoc (Université de Lorraine, LORIA)
Le type d’ordre d’une séquence de points du plan est une généralisation de la permutation associée à une séquence de nombres réels. Cette structure combinatoire encode de nombreuses propriétés géométriques de la séquence de points, par exemple le treillis des faces de son enveloppe convexe, ou encore les triangulations qu’elle supporte.
Cet exposé commencera par une rapide introduction à ces objets. Je discuterai ensuite d’un phénomène de concentration qui apparaît lorsque l’on lit les types d’ordres de séquences de points aléatoires, pour divers modèles naturels. Cette concentration rend difficile une bonne exploration aléatoire de ces structures.
Ceci est un travail conjoint avec Emo Welzl (article ici et ici). - 2021-12-07Olivier Bernard (IRISA EMSEC, Rennes)
The Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé in 2019, was introduced in 2020. The authors performed experiments for prime conductors cyclotomic fields of degrees at most 70, reporting exact approximation factors reached in practice. The main obstacle for these experiments is the computation of a log-S-unit lattice, which requires classical subexponential time.
In this work, we extend these experiments to 210 cyclotomic fields of any conductor m and of degree up to 210. Building upon new results from Bernard and Kucera on the Stickelberger ideal, we construct a maximal set of independent S-units lifted from the maximal real subfield using explicit Stickelberger generators obtained via Jacobi sums. Hence, we obtain full-rank log-S-unit sublattices fulfilling the role of approximating the full Twisted-PHS lattice. Notably, our obtained approximation factors match those from the Twisted-PHS team in small dimensions, when it is feasible to compute the original log-S-unit lattice.
As a side result, we use the knowledge of these explicit Stickelberger elements to remove almost all quantum steps in the CDW algorithm, by Cramer, Ducas and Wesolowski in 2021, under the mild restriction that the plus part of the class number verifies $h_{m}^{+}\leq O(\sqrt{m})$.
The full paper is available on ePrint:2021/1384. This is joint work with Andrea Lesavourey, Tuong-Huy Nguyen and Adeline Roux-Langlois. - 2021-11-30Katharina Boudgoust (IRISA EMSEC, Rennes)
This work contributes in the field of lattice-based cryptography, a research domain of public key cryptography that was initiated at the end of the 1990s by two different branches. On the one had, there have been proposals benefiting from strong theoretical connections to presumed hard worst-case lattice problems, leading to the development of public key cryptography based on the SIS (Short Integer Solution) and LWE (Learning With Errors) problems. On the other hand, very efficient schemes basing their security on average-case structured lattice problems have been introduced, the most popular among them is the NTRU encryption scheme.
Following the latter approach, Hoffstein and Silverman introduced in 2015 a public key encryption scheme called PASS Encrypt. It is very efficient and fulfills additive and multiplicative homomorphic properties. Unfortunately, a main problem with PASS Encrypt to date is that its security is not well understood, no proof of security was given with respect to the hardness of explicit computational problems, and the scheme is deterministic and hence cannot satisfy the standard notion of IND-CPA security.
In the presented work, we make progress towards understanding the hardness assumptions needed to prove the security of PASS Encrypt. We study the Partial Vandermonde Knapsack problem (PV-Knap) and emphasize its connection to (average-case) ideal lattices. We enlarge the landscape of problems that use the partial Vandermonde matrix by defining a new variant of LWE, called Partial Vandermonde Learning With Errors (PV-LWE). Later, we show the equivalence of PV-Knap and PV-LWE by exploiting the same duality connection as we have for standard Knapsack problems and LWE. In order to provide a security proof for PASS Encrypt, we need to define a variant of PV-Knap, that we call the PASS problem. This problem serves (together with the decision version of PV-Knap) as the underlying hardness assumption for (a slightly modified version of) PASS Encrypt. Furthermore, we present the scheme together with the security proof. We conclude the presentation with some interesting open questions regarding problems using the partial Vandermonde transform.
This is joint work with Amin Sakzad and Ron Steinfeld, currently under submission. - 2021-11-23Aurel Page (IMB)Norm relations and class group computations
When $L/K$ is a Galois extension of number fields with Galois group $G$, some invariants of $L$ can be related to those of its proper subfields. I will present some old and some new such relations, and an application to the computation of class groups of some large number fields. This is joint work with Jean-François Biasse, Claus Fieker and Tommy Hofmann.
- 2021-11-16Benjamin Wesolowski (CNRS, IMB)
We will present the signature scheme SQISign, (for Short Quaternion and Isogeny Signature) exploiting isogeny graphs of supersingular elliptic curves. The signature and public key sizes combined are an order of magnitude smaller than all other post-quantum signature schemes. Its efficient implementation and security analysis open new research challenges.
- 2021-11-09Koen de Boer (CWI Amsterdam)
We show a method to sample an element alpha from a given ideal I, such that their quotient ideal (alpha)/I is a (possibly large) prime times a smooth number (‘near-prime’) with reasonable probability. This method consists of ‘randomizing’ the ideal I by multiplying it with small primes (yielding J) and consequently sampling the element alpha from this randomized ideal J intersected with a large box. The probability that the quotient (alpha)/J is prime (i.e., that the quotient (alpha)/I is a near-prime) is tightly related to density results on prime ideals (prime ideal theorem). As an application we show an efficient way to compute power residue symbols for varying degree number fields.
- 2021-10-12Damien Robert (IMB)Revisiter l'algorithme de Satoh de comptage de points en petite caractéristique par relèvement canonique
L’algorithme de Satoh de comptage de points sur les courbes elliptiques permet d’obtenir (après des améliorations de Harvey) une complexité quasi-quadratique en le degré pour une (petite) caractéristique fixée $p$. Dans cet exposé je passerai en revue plusieurs variantes de cet algorithme et ses extensions aux variétés abéliennes. J’expliquerai ensuite comment on peut grandement simplifier l’implémentation de cet algorithme. L’implémentation dans Pari/GP du nouvel algorithme produit un gain d’un facteur 30 à la fois de temps de calcul et de consommation mémoire.
- 2021-10-05Henri Cohen (IMB)Algebraic values of the hypergeometric function
In this talk, I will study the general problem of when the value of the hypergeometric function $F(a,b;c;z)$ is algebraic, assuming $a$,$b$,$c$, and $z$ rational. The results involve modular forms and functions, complex multiplication, Shimura curves, and computer searches.