Séminaire de Théorie Algorithmique des Nombres

Generally, polynomial systems that arise in algebraic cryptanalysis have extra structure compared to generic systems, which comes from the algebraic modelling of the cryptographic scheme. Sometimes, part of this extra structure can be caught with polynomial rings with non-standard grading. For example, in the Kipnis-Shamir modelling of MinRank one considers the system over a bi-graded polynomial ring instead. This allows for better approximations of the solving degree of such systems when using Gröbner basis algorithms.

In this talk, I will present ongoing work in which this idea is extended to multi-graded polynomial rings. Furthermore, I will show how we can use this grading to tailor existing algorithms to use this structure and speed up computation. 

We will make a tour of related concepts whose motivation lies in

quantum information theory. We consider the detection of entanglement

in unitarily-invariant states, a class of positive (but not completely

positive) multilinear maps, and the construction of tensor polynomial

identities. The results are established through the use of commutative

and noncommutative Positivstellensätze and the representation theory of

the symmetric group.

Gröbner bases lie at the forefront of the algorithmic treatment of polynomial systems and ideals in symbolic computation. They are

defined as special generating sets of polynomial ideals which allow to decide the ideal membership problem via a multivariate version of

polynomial long division. Given a Gröbner basis for a polynomial ideal, a lot of geometric and algebraic information about the

polynomial ideal at hand can be extracted, such as the degree, dimension or Hilbert function.

Notably, Gröbner bases depend on two parameters: The polynomial ideal which they generate and a monomial order, i.e. a certain kind

of total order on the set of monomials of the underlying polynomial ring. Then, the geometric and ideal-theoretic information that can be

extracted from a Gröbner basis depends on the chosen monomial order. In particular, the lexicographic one allows us to solve a polynomial system.

Such a lexicographic Gröbner basis is usually computed through a change of order algorithm, for instance the seminal FGLM algorithm. In this talk,

I will present progress made to change of order algorithms: faster variants in the generic case, complexity estimates for system of critical values, computation

of colon ideals or of generic fibers.

This is based on different joint works with A. Bostan, Ch. Eder, A. Ferguson, R. Mohr, V. Neiger and M. Safey El Din.

Witsenhausen's problem asks for the maximum fraction α_n of the n-dimensional unit sphere that can be covered by a measurable set containing no pairs of orthogonal points. We extended well known optimization hierarchies based on the Lovász theta number, like the Lasserre hierarchy, to Witsenhausen's problem and similar problems. We then showed that these hierarchies converge to α_n, and used them to compute the best upper bounds known for α_n in low dimensions.

We will discuss computable descriptions of isomorphism classes in a fixed isogeny class of both polarised abelian varieties over finite fields (joint work with Bergström-Marseglia) and Drinfeld modules over finite fields (joint work with Katen-Papikian). 

More precisely, in the first part of the talk we will describe all polarisations of all abelian varieties over a finite field in a fixed isogeny class corresponding to a squarefree Weil polynomial, when one variety in the isogeny class admits a canonical lifting to characteristic zero. The computability of the description relies on applying categorical equivalences, due to Deligne and Centeleghe-Stix, between abelian varieties over finite fields and fractional ideals in étale algebras. 

In the second part, we will use an action of fractional ideals, inspired by work of Hayes, to compute isomorphism classes of Drinfeld modules. As a first step and a problem of independent interest, we prove that an isogeny class contains a Drinfeld module whose endomorphism ring is minimal if and only if the class is either ordinary or defined over the prime field. We obtain full descriptions in these cases, that can be compared to the Drinfeld analogues of those of Deligne and Centeleghe-Stix, respectively.

I will present recent joint work with Magnus Carlson, where we provide formulas for 3-fold Massey products in the étale cohomology of the ring of integers of a number field. Using these formulas, we identify the first known examples of imaginary quadratic fields with a class group of p-rank two possessing an infinite p-class field tower, where p is an odd prime. Furthermore, we establish a necessary and sufficient condition, in terms of class groups of p-extensions, for the vanishing of 3-fold Massey products. As a consequence, we offer an elementary and sufficient condition for the infinitude of class field towers of imaginary quadratic fields. Additionally, we disprove McLeman’s (3,3)-conjecture.

SQIsign is an isogeny-based signature scheme in Round 1 of NIST’s recent alternate call for signature schemes. In this talk, we will take a closer look at SQIsign verification and demonstrate that it can be performed completely on Kummer surfaces. In this way, one-dimensional SQIsign verification can be viewed as a two-dimensional isogeny between products of elliptic curves. Curiously, the isogeny is then defined over Fp rather than Fp2. Furthermore, we will introduce new techniques that enable verification for compression signatures using Kummer surfaces, in turn creating a toolbox for isogeny-based cryptography in dimension 2.This is based on joint work with Krijn Reijnders.

We discuss the computational problem of finding pairs of consecutive smooth integers, also known as smooth twins. Such twins have had some relevance in isogeny-based cryptography and reducing the smoothness bound of these twins aids the performance of these cryptosystems. However searching for such twins with a small smoothness bound is the most challenging aspect of this problem especially since the set of smooth twins with a fixed smoothness bound is finite. This talk presents new large smooth twins which have a smaller smoothness bound compared to twins found with prior approaches.

In this talk, we present a new construction of quantum codes that enables the integration of a broader class of classical codes into the mathematical framework of quantum stabilizer codes. Next, we discuss new connections between twisted codes and linear cyclic codes and provide novel bounds for the minimum distance of twisted codes. We demonstrate that classical tools, such as the Hartmann-Tzeng minimum distance bound, are applicable to twisted codes. This has led to the discovery of five new infinite families and many other examples of record-breaking, and sometimes optimal, binary quantum codes. Additionally, we explore the role of the $\gamma$ value on the parameters of twisted codes and present new findings regarding the construction of twisted codes with different $\gamma$ values but identical parameters.

Several algorithmic problems on supersingular elliptic curves are

currently under close scrutiny. When analysing algorithms or reductions

in this context, one often runs into the following type of question:

given a supersingular elliptic curve E and an object x attached to E, if

we consider a random large degree isogeny f : E -> E' and carry the

object x along f, how is the resulting f(x) distributed among the

possible objects attached to E'? We propose a general framework to

formulate this type of question precisely, and prove a general

equidistribution theorem under a condition that is easy to check in

practice. The proof goes from elliptic curves to quaternionic

automorphic forms via an augmented Deuring correspondence, and then to

classical modular forms via the Jacquet-Langlands correspondence. This

is joint work with Benjamin Wesolowski.

The classical modular polynomial phi_N parametrizes pairs of elliptic curves connected by an isogeny of degree N. They play an important role in algorithmic number theory, and are used in many applications, for example in the SEA point counting algorithm.

This talk is about a new method for computing modular polynomials. It has the same asymptotic time complexity as the currently best known algorithms, but does not rely on any heuristics. The main ideas of our algorithm are: the embedding of N-isogenies in smooth-degree isogenies in higher dimension, and the computation of deformations of isogenies.

The talk is based on a joint work with Damien Robert.

In a category enriched in a closed symmetric monoidal category, the power

object construction, if it is representable, gives a contravariant monoidal

action. We first survey the construction, due to Serre, of the power object

by (projective) Hermitian modules on abelian varieties. The resulting

action, when applied to a primitively oriented elliptic curve, gives a

contravariant equivalence of category (Jordan, Keeton, Poonen, Rains,

Shepherd-Barron and Tate).

We then give several applications of this module action:

1) We first explain how it allows to describe purely algebraically the

ideal class group action on an elliptic curve or the Shimura class group

action on a CM abelian variety over a finite field, without lifting to

characteristic 0.

2) We then extend the usual algorithms for the ideal action to the case of

modules, and use it to explore isogeny graphs of powers of an elliptic

curve in dimension up to 4. This allows us to find new examples of curves

with many points. (This is a joint work with Kirschmer, Narbonne and

Ritzenthaler)

3) Finally, we give new applications for isogeny based cryptography. We

explain how, via the Weil restriction, the supersingular isogeny path

problem can be recast as a rank 2 module action inversion problem. We also

propose ⊗-MIKE a novel NIKE (non interactive isogeny key exchange) that only

needs to send j-invariants of supersingular curves, and compute a dimension

4 abelian variety as the shared secret.

Isogeny-based cryptography is founded on the assumption that the Isogeny problem—finding an isogeny between two given elliptic curves—is a hard problem, even for quantum computers.

In the security analysis of isogeny-based schemes, various related problems naturally arise, such as computing the endomorphism ring of an elliptic curve or determining a maximal quaternion order isomorphic to it.

These problems have been shown to be equivalent to the Isogeny problem, first under some heuristics and subsequently under the Generalized Riemann Hypothesis.

In this talk, we present ongoing joint work with Benjamin Wesolowski, where we unconditionally prove these equivalences, notably using the new tools provided by isogenies in higher dimensions.

Additionally, we show that these problems are also equivalent to finding the lattice of all isogenies between two elliptic curves.

Finally, we demonstrate that if there exist hard instances of the Isogeny problem then all the previously mentioned problems are hard on average.

A pair elliptic curves E/Q and E’/Q are isogenous if and only if they have the same number of points mod p for every (good) prime p. A conjecture of Frey and Mazur predicts that E and E’ are isogenous if and only if they are N-congruent for any sufficiently large integer N > N_0 (i.e., #E(F_p) = #E’(F_p) mod N for all good p).

Congruences appear quite naturally in applications, for example:

- In isogeny-based cryptography (an abelian surface being (N,N)-split implies that the corresponding pair of elliptic curves are N-congruent).

- In Diophantine problems (e.g., Fermat’s last theorem),

- In descent obstructions (via Mazur’s notion of “visible elements of Sha”).

Despite the Frey—Mazur conjecture, it is not known for which integers there exist non-isogenous N-congruent elliptic curves: what is N_0? I will discuss progress towards refining the Frey—Mazur conjecture by studying the geometry of “Humbert surfaces” which parametrise N-congruences.

The aim of the talk is to explain an unexpected link between a class of molecules composed of carbon and hydrogen atoms, and the theory of elliptic curves over finite fields. The correspondence is of topological nature and doesn't include, so far, any of the crucial geometric features of the cycloalkanes. We will nevertheless explain how modular curves help making this connection, the role of modular polynomials, give details about explicit computations we performed, and give several examples. The talk is based on joint work with Henry Bambury and Francesco Campagna. 

In 2022, Ducas et al. introduced the signature scheme Hawk, based of the presumed hardness of a new problem in lattice-based cryptography: the Lattice Isomorphism Problem for the module-lattice O_L^2, where L is a cyclotomic number field. Last year we presented a polynomial time algorithm solving this problem when L is a totally real number field (thus not affecting the security of Hawk). More recently, we provided a reduction of the same problem when L is now a CM field (thus containing Hawk's instance) to the problem of finding a generator of a principal quaternionic ideal. 

In this talk we give a framework containing both the totally real and the CM case, and we will discuss the differences. This is based on a joint work with C. Chevignard, P-A. Fouque, A. Pellet-Mary, H. Pliatsok and A. Wallet.