Annamaria IEZZI | A day on Commutative Algebra and Cryptography

A day on Commutative Algebra and Cryptography

Université Grenoble Alpes & Université de Neuchâtel

We are pleased to invite you to A Day on Commutative Algebra and Cryptography, taking place on Monday November 25th, 2024, at Laboratoire Jean Kuntzmann, Université Grenoble Alpes.

Location of talks: Room 106, Laboratoire Jean Kuntzmann (IMAG building, 1st floor).
Location of lunch: A complimentary buffet will be held in the Espace de Convivialité (IMAG building, ground floor).

If you wish to participate, please contact Annamaria Iezzi.

We look forward to welcoming you for an enriching and convivial day of mathematical discussions!

Organisers:

Annamaria Iezzi (Université Grenoble Alpes)
Elisa Lorenzo García (Université de Neuchâtel)

Programme of the day

9-9:45am: Elisa Gorla, Université de Neuchâtel: Complexity of Groebner basis computations: invariants and applications.

Complexity of Groebner basis computations: invariants and applications

I will introduce and discuss some algebraic invariants that one can use to bound the complexity of computing a Groebner basis, hence the complexity of solving a multivariate polynomial system. The focus will be on the type of systems that are of interest in (multivariate) cryptography. After recalling the basics of linear-algebra-based algorithms for computing Groebner bases, I introduce the solving degree, an invariant which measures their complexity. Since the solving degree is hard to compute, I will discuss other algebraic invariants that one can use in this context, such as the degree of regularity, the last fall degree, and the Castelnuovo-Mumford regularity.
10:15-11am: Lisa Seccia, Université de Neuchâtel: Commutative algebra techniques for grobner bases and ideals of minors.
11:30am-12pm: Elisa Lorenzo García, Université de Neuchâtel: When does a "nice" curve admit a smooth plane model?.

When does a "nice" curve admit a smooth plane model?

In Section 4 of [AAL], we give an algorithm to determine when a smooth curve given by its canonical model admits a smooth plane model and, in such a case, we are sometimes able to compute it. The algorithm is based on the study of the graded Betti numbers of a minimal resolution of the canonical ideal of the curve and in a partial proof of a conjecture of Green by Schreyer. There are still many open questions around this conjecture and its applications to study models of curves. More particularly, I would like to apply these techniques to determine when abelian varieties of dimension $d$ contain curves of given genus $g$, which has applications to the construction of algebraic geometry codes with given parameters, see for example this recent preprint.
12-2pm: Buffet in Espace de Convivialité (Bâtiment IMAG, Ground Floor).
2-2:45pm: Giulia Gaggero, Université de Neuchâtel: Multivariate cryptography and the complexity of solving a random polynomial system.
3:15-4pm: Vanessa Vitse, Université Grenoble Alpes: Boolean polynomial systems.

Boolean polynomial systems

An important problem in cryptography, but also in theoretical computer science, is the existence of $\mathbb F_2$-rational solutions of a multivariate polynomial system over $\mathbb F_2$, a problem known to be NP-complete. This means working in Boolean rings, i.e. in which $f^2=f$ for any polynomial $f$. The algebraic approach to this problem consists of computing a Gröbner basis of the ideal associated to the system. It is then important to estimate the sizes of the Macaulay matrices involved in this calculation, which corresponds to the study of the Hilbert series of a Boolean ideal. We shall see how the use of certain tools of homological algebra, adapted to the Boolean case, sheds light on the complexity of complexity of solving these systems.
4:30-5pm: Annamaria Iezzi, Université Grenoble Alpes: Challenges in generating random supersingular elliptic curves over finite fields of large characteristic.

Challenges in generating random supersingular elliptic curves over finite fields of large characteristic

Constructing supersingular elliptic curves with unknown endomorphism ring over finite fields of large characteristic is an open problem with significant implications for isogeny-based cryptography. In this talk, we will provide an overview of recent attempts to tackle this problem, we will examine their limitations and we will possibly discuss new ideas.

Practical infomation

The IMAG building is located here: MAP.

From the center of Grenoble, you can easily reach it by taking Tram B (direction GIERES Plaine des Sports) or Tram C (direction SAINT-MARTIN-D'HÈRES UNIVESITÉ Condillac). The nearest stop is Gabriel Fauré. Remember to validate your ticket before getting on the tram.