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.