2022/2023

• 2023-06-27
  Agathe Houzelot (Labri)
  White-Box Implementations of ECDSA

  Cryptographic algorithms are primarily designed to be secure in the black-box model, where an attacker can only observe their input/output behavior. However in practice, algorithms are rarely executed in a completely isolated environment and additional information is often leaked. In the context of mobile applications or connected objects, devices often lack secure storage to protect secret keys, and their generally open execution environment exposes a large attack surface. This hostile environment is captured by the white-box attack model.
  While many white-box implementation of block ciphers have been published since 2002, asymmetric cryptosystems have been very little studied. In my PhD thesis, we got interested in white-box implementations of ECDSA. This led us to participate in the WhibOx Contest that was organized as part of the TCHES workshops in 2021. During three months, developpers were invited to submit ECDSA white-box implementations and attackers to try to break them. In this talk, I will introduce the white-box model before explaining the specificities of the ECDSA algorithm in this context. I will then present the different attacks that we used to break almost all the challenges of the WhibOx Contest.

• 2023-06-20
  Canari team
  Meeting Canari team and Inria Bordeaux head team

  A recurrent meeting between the team members and the administrative direction.

• 2023-06-13
  Mahshid Riahinia (ENS de Lyon)
  Constrained Pseudorandom Functions from Homomorphic Secret Sharing

  A Constrained pseudorandom function (CPRF) is a pseudorandom function that provides fine-grained access to the evaluation of the function. In other words, for a (possibly super-polynomial) subset of inputs, a constrained pseudorandom function allows us to derive a constrained key that enables evaluating the function on that subset of inputs while learning nothing beyond. We propose and analyze a simple strategy for constructing 1-key constrained pseudorandom functions from homomorphic secret sharing (HSS) protocols. This relation, in particular, leads to instantiations of CPRFs for various constraints and from various assumptions. In this talk, I present this strategy and briefly go over one of the instantiations.

• 2023-06-06
  Daan van Gent (University of Leiden, Netherlands)
  The Closest Vector Problem for the lattice of algebraic integers

  Any number field comes with a natural inner product as in the theory of the geometry of numbers, so that any order becomes a lattice. We extend the definition of the inner product to $\overline{\mathbb{Q}}$, the algebraic closure of the rationals, and consider its maximal order $\overline{\mathbb{Z}}$, which has infinite rank, as an intrinsically interesting `lattice’. We will compute several lattice invariants and attempt to solve the Closest Vector Problem through proofs inspired by capacity theory. Adjacent to CVP is the problem of finding the Voronoi-relevant vectors, and we pose the challenge to compute all such vectors of degree 3.

• 2023-05-30
  Sarah Arpin (University of Leiden, Netherlands)
  Adding Level Structure to Supersingular Elliptic Curve Isogeny Graphs

  The classical Deuring correspondence provides a roadmap between supersingular elliptic curves and the maximal orders which are isomorphic to their endomorphism rings. Building on this idea, we add the information of a cyclic subgroup of prime order N to supersingular elliptic curves, and prove a generalisation of the Deuring correspondence for these objects. We also study the resulting ell-isogeny graphs supersingular elliptic curve with level-N structure, and the corresponding graphs in the realm of quaternion algebras. The structure of the supersingular elliptic curve ell-isogeny graph underlies the security of a new zero-knowledge proof of isogeny knowledge [Basso-Codogni-Connolly-De Feo-Fouotsa-Lido-Morrison-Panny-Patranabis-Wesolowski 2022].

• 2023-05-23
  Boris Fouotsa (EPFL, Switzerland)
  Beyond the SIDH Countermeasures

  During summer 2022, a series of three cryptanalysis papers lead to a polynomial time attack on SIKE, which was in the fourth round of the NIST standardisation process. In a recent work, we explored countermeasures avenue to the SIDH attacks, M-SIDH and MD-SIDH. These countermeasures, despite being slow and less compact (when compared to SIDH and other post-quantum schemes), come with new insights that may be of independent interest. In this talk, we will discuss an on-going work in which we use M-SIDH together with the SIDH attacks to design a trapdoor one way function. This trapdoor one way function can be leveraged to obtain a public key encryption scheme, most importantly, it can be used to design an Identity Based Encryption scheme. The main drawback is that the design is purely theoretical at the moment, since inverting the one way function requires computing isogenies in higher dimension of prime degree up to 5000 or even higher.

• 2023-05-16
  Wessel van Woerden (IMB)
  Perfect Quadratic Forms -- an Upper Bound and Challenges in Enumeration

  In 1908 Voronoi introduced an algorithm that solves the lattice packing problem in any dimension in finite time. Voronoi showed that any lattice with optimal packing density must correspond to a so- called perfect (quadratic) form and his algorithm enumerates the finitely many perfect forms up to similarity in a fixed dimension. However, the number of non-similar perfect forms and the comlexity of the algorithm grows quickly in the dimension and as a result Voronoi’s algorithm has only been completely executed up to dimension 8. We discuss an upper bound on the number of perfect forms and the challenges that arise for completing Voronoi’s algorithm in dimension 9.

• 2023-05-16
  Matthieu Lequesne (CWI, Netherlands)
  TBA
• 2023-05-09
  Sabrina Kunzweiler (IMB)
  Isogeny-based PAKE protocols

  The passwords that we use in our everyday life are often chosen to be easily memorable which evidently makes them vulnerable to attacks. This problem is addressed by password-authenticated key exchange (PAKE). The general idea of such a protocol is to enable two parties who share the same (potentially weak) password to establish a strong session key.
  Most PAKE protocols used today are based on Diffie-Hellman key exchange in prime order groups, hence they are not secure against quantum attackers. A promising candidate for replacing Diffie-Hellman key exchange in a post-quantum world is the Commutative-Supersingular-Isogeny-Diffie-Hellman (CSIDH) key exchange. In this talk, we introduce two novel PAKE protocols based on CSIDH.

• 2023-05-02
  Sorina Ionica (Université de Picardie)
  Computing bad reduction for genus 3 curves with complex multiplication

  Goren and Lauter studied genus 2 curves whose Jacobians are absolutely simple and have complex multiplication (CM) by the ring of integers of a quartic CM-field, and showed that if such a curve has bad reduction to characteristic p then there is a solution to a certain embedding problem. An analogous formulation of the embedding problem for genus 3 does not suffice for explicitly computing all primes of bad reduction. We introduce a new problem called the Isogenous Embedding Problem (IEP), which we relate to the existence of primes of bad reduction. We propose an algorithm which computes effective solutions for this problem and exhibits a list of primes of bad reduction for genus 3 curves with CM. We ran this algorithm through different families of curves and were able to prove the reduction type of some particular curves at certain primes that were open cases in the literature.

• 2023-04-25
  Alessandro Languasco (University of Padova, Italy)
  Computing $L'(1,\chi)/L(1,\chi)$ using special functions, their reflection formulae and the Fast Fourier Transform

  We will show how to combine the Fast Fourier Transform algorithm with the reflection formulae of the special functions involved in the computation of the values of $L(1,\chi)$ and $L’(1,\chi)$, where $\chi$ runs over the Dirichlet characters modulo an odd prime number $q$. In this way, we will be able to reduce the memory requirements and to improve the computational cost of the whole procedure.
  Several applications to number-theoretic problems will be mentioned, like the study of the distribution of the Euler-Kronecker constants for the cyclotomic field and its subfields, the behaviour of $\min_{\chi\ne \chi_0} | L’(1,\chi)/L(1,\chi) |$, the study of the Kummer ratio for the first factor of the class number of the cyclotomic field and the ``Landau vs. Ramanujan’’ problem for divisor sums and coefficients of cusp forms.
  Towards the end of the seminar we will tackle open problems both of theoretical and implementative nature.

• 2023-04-11
  Henry Bambury (ENS Ulm)
  An inverse problem for isogeny volcanoes

  Supersingular isogeny graphs are very complicated and intricate, and are used extensively by cryptographers. On the other side of things, the structure of ordinary isogeny graphs is well understood connected components look like volcanoes. Throughout this talk we will explore the ordinary $\ell$-isogeny graph over $\mathbb{F}_p$ for various prime numbers $\ell$ and $p$, and answer the following question, given a volcano-shaped graph, can we always find an isogeny graph in which our volcano lives as a connected component?

• 2023-04-04
  Jean Gillibert (Université de Toulouse 2)
  Finite subgroups of $\mathrm{PGL}_2(\mathbb{Q})$ and number fields with large class groups

  For each finite subgroup $G$ of $\mathrm{PGL}_2(\mathbb{Q})$, and for each integer $n$ coprime to $6$, we construct explicitly infinitely many Galois extensions of $\mathbb{Q}$ with group $G$ and whose ideal class group has $n$-rank at least $\#G-1$. This gives new $n$-rank records for class groups of number fields.

• 2023-03-28
  Shane Gibbons (CWI, Netherlands)
  Hull attacks on the Lattice Isomorphism Problem

  The lattice isomorphism problem (LIP) asks one to find an isometry between two lattices. It has recently been proposed as a foundation for cryptography in independent works. This problem is the lattice variant of the code equivalence problem, on which the notion of the hull of a code can lead to devastating attacks. In this talk I will present the cryptanalytic role of an adaptation of the hull to the lattice setting, which we call the s-hull. Specifically, we show that the hull can be helpful for geometric attacks, for certain lattices the minimal distance of the hull is relatively smaller than that of the original lattice, and this can be exploited. The attack cost remains exponential, but the constant in the exponent is halved.
  Our results suggests that one should be very considerate about the geometry of hulls when instantiating LIP for cryptography. They also point to unimodular lattices as attractive options, as they are equal to their own hulls. Remarkably, this is already the case in proposed instantiations, namely the trivial lattice $\mathbb{Z}^n$ and the Barnes-Wall lattices.

• 2023-03-21
  Mathieu Dutour (Institute Rudjer Boskovic, Croatia)
  High dimensional computation of fundamental domains

  We have developed open-source software in C++ for computing with polyhedra, lattices, and related algebraic structures. We will shortly explain its design. Then we will explain how it was used for computing the dual structure of the $W(H_4)$ polytope.
  Then we will consider another application to finding the fundamental domain of cocompact subgroups $G$ of $\mathrm{SL}_n(\mathbb{R})$. The approach defines a cone associated with the group and a point $x\in \mathbb{R}^n$. It is a generalization of Venkov reduction theory for $\mathrm{GL}_n(\mathbb{Z})$. We recall the Poincaré Polyhedron Theorem which underlies these constructions.
  We give an iterative algorithm that allows computing a fundamental domain. The algorithm is based on linear programming, the Shortest Group Element (SGE) problem and combinatorics. We apply it to the Witte cocompact subgroup of $\mathrm{SL}_3(\mathbb{R})$ defined by Witte for the cubic ring of discriminant $49$.

• 2023-03-14
  Leonardo Colô (Université Aix-Marseille)
  Oriented Supersingular Elliptic Curves and Class Group Actions

  We recently defined an OSIDH protocol with Kohel (OSIDH)— for oriented supersingular isogeny Diffie-Hellman — by imposing the data of an orientation by an imaginary quadratic ring $\mathcal{O}$ on the category of supersingular elliptic curves. Starting with an elliptic curve $E_0$ oriented by a CM order $\mathcal{O}_K$ of class number one, we push forward the class group action along an $\ell$-isogeny chains, on which the class group of an order $\mathcal{O}$ of large index $\ell^n$ in $\mathcal{O}_K$ acts. The map from $\ell$-isogeny chains to its terminus forgets the structure of the orientation, and the original base curve $E_0$. For a sufficiently long random $\ell$-isogeny chain, the terminal curve represents a generic supersingular elliptic curve.
  One of the advantages of working in this general framework is that the group action by $\mathrm{Cl}(\mathcal{O})$ can be carried out effectively solely on the sequence of moduli points (such as $j$-invariants) on a modular curve, thereby avoiding expensive generic isogeny computations or the requirement of rational torsion points.
  The proposed attacks of Onuki (2021) and Dartois-De Feo (2021) and their analyses motivate the idea of enlarging the class group without touching the key space using \textit{ clouds}. In this talk we propose two approaches to augments $\mathrm{Cl}(\mathcal{O}_n(M))$ in a way that no effective data is transmitted for a third party to compute cycle relations. In both cases, it comes down to an extension of the initial chain by the two parties separately. In particular, while the original OSIDH protocol made exclusive use of the class group action at split primes in $\mathcal{O}$, we extend the protocol to include descent in the eddies at non-split primes (inert or ramified) or at large primes which are not cost-effective for use for longer isogeny walks.

• 2023-03-08
  Ross Paterson (University of Bristol)
  Elliptic Curves over Galois Number Fields

  As E varies among elliptic curves defined over the rational numbers, a theorem of Bhargava and Shankar shows that the average rank of the Mordell–Weil group E(Q) is bounded. If we now fix a Galois number field K, how does the Mordell–Weil group E(K) behave on average as a Galois module? We will report on progress on this question, which is obtained by instead studying the associated p-Selmer groups of E/K as Galois modules.
  We construct some novel Selmer groups which describe certain invariants of these modules, and go on to study the behaviour of these new Selmer groups. This in turn allows us to give bounds for certain behaviour for the Mordell–Weil groups.

• 2023-02-21
  Floris Vermeulen (KU Leuven)
  Arithmetic equivalence and successive minima

  Two number fields are said to be arithmetically equivalent if they have the same Dedekind zeta function. The central question about arithmetic equivalence is to determine how “similar” arithmetically equivalent number fields are. That is, we would like to determine which arithmetic invariants, such as the degree, discriminant, signature, units, class number, etc., are the same, and which ones can differ. A key result about arithmetic equivalence is Gassmann’s theorem, which allows one to answer such questions using Galois theory and representation theory.
  I will give a general introduction to arithmetic equivalence, discussing some of the main results such as Gassmann’s theorem and giving examples. I will then introduce the successive minima of a number field, and show that arithmetically equivalent number fields have approximately the same successive minima.

• 2023-02-14
  Maxime Plançon (IBM Zürich)
  Exploiting algebraic structure in probing security

  The so-called $\omega$-encoding, introduced by Goudarzi, Joux and Rivain (Asiacrypt 2018), generalizes the commonly used arithmetic encoding. By using the additionnal structure of this encoding, they proposed a masked multiplication gadget (GJR) with quasilinear (randomness and operations) complexity. A second contribution by Goudarzi, Prest, Rivain and Vergnaud in this line of research appeared in TCHES 2021. The authors revisited the aforementioned multiplication gadget (GPRV), and brought the IOS security notion for refresh gadgets to allow secure composition between probing secure gadgets.

  In this paper, we propose a follow up on GPRV. Our contribution stems from a single Lemma, linking algebra and probing security for a wide class of circuits, further exploiting the algebraic structure of $\omega$-encoding. On the theoretical side, we weaken the IOS notion into the KIOS notion, and we weaken the usual $t$-probing security into the RTIK security. The composition Theorem that we obtain by plugging together KIOS, RTIK still achieves region-probing security for composition of circuits.
  To substantiate our weaker definitions, we also provide examples of competitively efficient gadgets verifying our weaker security notions. Explicitly, we give 1) a refresh gadget that uses $d-1$ random field elements to refresh a length $d$ encoding that is KIOS but not IOS, and 2) multiplication gadgets asymptotically subquadratic in both randomness and complexity. While our algorithms outperform the ISW masked compiler asymptotically, their security proofs require a bounded number of shares for a fixed base field.

• 2023-02-07
  Andrea Lesavourey (Irisa)
  Calcul de racines de polynômes dans un corps de nombres

  Computing roots of elements is an important step when solving various tasks in computational number theory. It arises for example during the final step of the General Number Field Sieve~(Lenstra et al. 1993). This problem also intervenes during saturation processes while computing the class group or $S$-units of a number field (Biasse and Fieker).
  It is known from the seminal paper introducing the LLL algorithm that one can recover elements of a given number field $K$ given approximations of one of their complex embeddings. This can be used to compute roots of polynomials. In the first part of this presentation, I will describe an extension of this approach that take advantage of a potential subfield $k$, which replace the decoding of one element of $K$ by the decoding $[K:k]$ elements of $k$, to the cost of search in a set of cardinality $d^{[K:k]}$ where $d$ is the degree of the targetted polynomial equation. We will also describe heuristic observations that are useful to speed-up computations.
  In the second part of the presentation, we will describe methods to compute $e$-th roots specifically. When $K$ and $e$ are such that there are infinitely many prime integers $p$ such that $\forall \mathfrak{p} \mid p, p^{f(\mathfrak{p}\mid p)}\not\equiv1\bmod e$, we reconstruct $x$ from $ x \pmod {p_1}, \dots, x \pmod {p_r} $ using a generalisation of Thomé’s work on square-roots in the context of the NFS~(Thomé). When this good condition on $K$ and $n$ is not satisfied, one can adapt Couveignes’ approach for square roots~(Couveignes) to relative extensions of number fields $K/k$ provided $[K:k]$ is coprime to $e$ and infinitely many prime integers $p$ are such that each prime ideal $\mathfrak{p}$ of $\mathcal{O}_k$ above $p$ is inert in $K$.

• 2023-01-31
  Wessel van Woerden (IMB)
  An Algorithmic Reduction Theory for Binary Codes, LLL and more

  We will discuss an adaptation of the algorithmic reduction theory of lattices to binary codes. This includes the celebrated LLL algorithm (Lenstra, Lenstra, Lovasz, 1982), as well as adaptations of associated algorithms such as the Nearest Plane Algorithm of Babai (1986). Interestingly, the adaptation of LLL to binary codes can be interpreted as an algorithmic version of the bound of Griesmer (1960) on the minimal distance of a code.

• 2023-01-24
  Razvan Barbulescu (CNRS/IMB)
  The particular case of cyclotomic fields when computing unit groups by quantum algorithms

  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.

• 2023-01-17
  Wouter 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.

• 2023-01-10
  Damien Robert (Inria/IMB)
  Some applications of higher dimensional isogenies to elliptic curves

  We survey some recent applications of isogenies between dimension $g>1$ abelian varieties to algorithms on elliptic curves: the endomorphism ring computation of an ordinary curve, canonical lifting and point counting, lifting isogenies, and modular polynomials. In particular some of the speed ups we obtain allow to replace a subexponential time complexity by a polynomial one.

• 2022-12-13
  Samuel 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.

• 2022-12-06
  Lé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-11-29
  Elie Bouscatié (Orange)
  Searching substrings inside an encrypted stream of data ... without decrypting !

  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-11-22
  Sulamithe Tsakou (Université de Picardie)
  Index calculus attacks on hyperelliptic curves with efficient endomorphism

  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-15
  Henri Cohen (IMB)
  A Pari/GP package for continued fractions

  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-08
  Anne-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-10-25
  Damien 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-10-18
  Èrell Gachon
  Some 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-11
  Rémy Oudompheng (Paribas)
  Computation of (3,3)-isogenies from a product of elliptic curves, in the style of 19th century geometry

  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-04
  Pierrick Dartois, Fabrice Etienne et Nicolas Sarkis
  Présentation des nouveaux doctorants de l'équipe LFANT
• 2022-09-20
  Fredrik 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-09-13
  Damien 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!