Conference - Effective moduli spaces and applications to cryptography

###The following speakers have accepted to give a lecture:

Jeff Achter (Colorado), Gaetan Bisson (Polynésie), Gavril Farkas (Berlin), Samuel Grushevsky (New York), Ghaith Hiary (Ohio), Boris Kolev (Marseille), Marc Olive (Marseille), Giorgio Ottaviani (Firenze), Mihaela Popoviciu (Basel), Rachel Pries (Colorado), Gwénaël Renault (Paris 6), Damien Robert (Bordeaux), Riccardo Salvati Manni ( Roma), Nick Shepherd-Barron (Cambridge), Pierre-Jean Spaenlehauer (Nancy), Marco Streng (Leiden)

Ghaith Hiary

Detecting squarefree numbers

Let $d = l^2 \Delta$, where $\Delta$ is square-free, and $\Delta$ and $l$ are unknown to us. A method to obtain a lower bound on $\Delta$ without attempting to factor $d$ is presented. If $d$ happens to be square-free, then the method might yield a sufficiently good lower bound on $\Delta$ so that the square-freeness of $d$ can be certified fast. The running time of the method is heuristically sub-exponential in the lower bound over a relatively wide initial range, and perhaps further. The method is based on the explicit formula for the Dirichlet $L$-function associated with a suitably chosen real character, and assuming the generalized Riemann hypothesis for that $L$-function. This is joint work with Andy Booker and Jon Keating.

Nick Shepherd-Barron

Tropes and the Torelli theorem.

We describe another way of recovering a genus 3 curve from the configuration formed by the singularities of its theta divisor (its bitangents).

Samuel Grushevsky

Relations among theta constants, the Schottky problem, and the cosmological constant

We will discuss the ideal of relations among theta constants associated to abelian varieties, the relations among theta constants of the Jacobians, and how this relates to string perturbation theory. This is to say we will review the classical Schottky-Jung approach to the Schottky problem, Igusa's results and our work with Salvati Manni in genus 5.

Giorgio Ottaviani

The bitangents of a plane quartic and the White-Miller quartic fourfold.

The general plane quartic has 28 bitangents, corresponding to 28 odd theta characteristics. We review a classical construction by White and Miller, who identify the bitangents with the 28 singular points of a covariant quartic fourfold, defined in the space of conics. Starting from a general Lueroth quartic, the White-Miller fourfold exhibits a 29th singular point, corresponding to the "pentalateral" theta. This gives a computational tool to detect if a plane quartic is Lueroth.

Damien Robert

Isogenies between abelian varieties

In this talk we give a brief panorama of the effective computation of isogenies between principally polarized abelian varieties and of modular equations.

Guenael Renault

On polynomial systems with structures related to the ECDLP.

The index calculus algorithm successively introduced by Semaev, Gaudry and Diem for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) relies on polynomial systems solving. Depending on the properties of the underlying curve (model, characteristic), these systems inherit of different kind of structures (symmetries, homogeneity). In this talk, I will present recent results on the use of these structures in order to gain up to an exponential factor in n for solving the ECDLP defined over a non-prime finite field of degree $n$.

Gaetan Bisson

On Polarized Class Groups of Orders in Quartic CM-Fields

Many recent advances in theoretical and computational aspects of abelian varieties as well as their applications to cryptography intensely exploit complex multiplication theory. This theory describes the structure of the endomorphism rings of those varieties and of their class groups.

We will first introduce these notions in the case of elliptic curves, show how well-understood they are, and present some of their major applications.

Much less is known for general abelian varieties. We will consider the problem of characterizing when two endomorphism rings have the same class group, and give a partial answer to it for abelian surfaces. We will then derive two applications: one to the classification of abelian surfaces with complex multiplication over the rationals, the other to the computation of endomorphism rings of abelian surfaces over finite fields.

This is joint work with Marco Streng.

Mihaela Popoviciu

Let $V_n$ be the set of binary forms (homogeneous polynomials in two variables) of degree $n$. If $V$ is a rational finite-dimensional $SL_2(\mathbb{C})$-module, then there exist $n_1,\ldots,n_p\in \mathbb{N}$ such that $V\cong V_{n_1}\oplus \ldots \oplus V_{n_p}$ as $SL_2(\mathbb{C})$-modules, and the algebra $R := \mathcal{O}(V)^{SL_2(\mathbb{C})}$ of polynomial functions on $V$ invariant under the action of $SL_2(\mathbb{C})$ can be identified with the algebra of joint invariants of $p$ binary forms of degrees $n_1,\ldots,n_p$.

In 1893 Hilbert proved that the algebra $R$ is finitely generated, i.e., there exist a finite number of invariants $j_1,\ldots, j_r$ of $V$ such that $R=\mathbb{C}[j_1,\ldots,j_r]$. Finding a set of generators of $R$ is, in general, a difficult problem. For example, the structure of $\mathcal{O}(V_n)^{SL_2(\mathbb{C})}$ was well known for $n\leq 6$, from the nineteenth century, but for big $n$ the problem is still open. In the past 25 years some progress was made and sets of generating invariants of $V_n$ were found in the cases $n=7,9,10$ by Dixmier&Lazard and by Brouwer&Popoviciu. The difficulty of this problem is reflected by the large homological dimensions of the algebras of invariants.

I will present in my talk the way we obtained the generating invariants of $V_9$ and of $V_{10}$. I will also give a classification of the $SL_2(\mathbb{C})$-module with homological dimensions $\leq 15$, extending a result of Popov.

Marco Streng

Families of class invariants in genus two

The theory of complex multiplication allows one to construct elliptic curves with a given number of points. The idea is to construct a curve over a finite field by starting with a special curve E in characteristic 0, and taking the reduction of E modulo a prime number. Instead of writing down equations for the curve E, one only needs the minimal polynomial of its j-invariant, called a Hilbert class polynomial. The coefficients of these polynomials tend to be very large, so in practice, one replaces the j-invariant by alternative modular functions that yield smaller polynomials. Schertz gave a systematic way of creating class invariants using modular functions for the group Gamma_0(N). The theory of complex multiplication has been generalized to higher-dimensional abelian varieties. I will show how to generalize Schertz's method to modular functions on higher-dimensional moduli spaces. This is joint work with Andreas Enge.

Boris Kolev / Marc Olive

Moduli spaces in elasticity

I will present some applications of invariant theory in elasticity, where effective moduli spaces are as important as in cryptography. I will also discuss the algorithms we used to compute invariants. This is a joint work with N. Auffray, M. Olive and M. Petitot.

Rachel Pries

Irreducibility of the p-rank stratification of the moduli space of curves - results and questions

An elliptic curve defined over a finite field of characteristic p can be ordinary or supersingular. This distinction can be generalized for curves of higher genus in terms of the p-rank, which measures the number of p-torsion points on the Jacobian or the number of roots of the L-polynomial with p-adic absolute value 1. I will discuss results, both theoretical and computational, about the geometry of the p-rank stratification of various moduli spaces of curves in positive characteristic, some of which are joint with Achter, Ozman, Weir and Zhu. I will end with some open questions on this topic which can be studied computationally.

Pierre-Jean Spaenlehauer

Algorithms and complexity bounds for computing Gröbner bases of determinantal and sparse multivariate systems.

Many polynomial systems arising in Cryptology inherit structural properties from the objects they model. In this context, we will present recent works whose goal is to exploit specific algebraic structures in Gröbner bases algorithms in order to provide dedicated solving methods and sharp complexity estimates.

In the first part of the talk, we will focus on the complexity of computing Gröbner bases of determinantal systems and their applications in Cryptology: explicit formulas for the Hilbert series of determinantal rings and the Thom-Porteous-Giambelli formula allow us to derive asymptotic complexity estimates of the computational effort required to compute low-rank matrices in linear subspaces of matrices. In the second part, we will present how the F5 and FGLM algorithms can be extended to semigroup algebras and polytopal algebras via connections with toric geometry and Ehrhart theory: this provides new directions for Gröbner-based methods for solving sparse systems of multivariate polynomials.

The first part is a joint work with Jean-Charles Faugère and Mohab Safey El Din. The second part is a joint work with Jean-Charles Faugère and Jules Svartz.

Gavril Farkas

Natural resolutions and the level $p$ modular variety over the moduli space of curves.

In joint work with Chiodo, Eisenbud and Schreyer, we formulate, and in some cases prove, three statements concerning the naturalness of the resolution of various rings one can attach to a generic curve of genus g and a torsion point of order p in its Jacobian. These statements can be viewed as analogues of Green's Conjecture and we verify them computationally for bounded genus. This we the use to derive results about the birational geometry of the moduli space R_{g,p} of such objects. I will finally discuss the surprising failure of the Prym-Green Conjecture for p=2 and genus 8 and 16, which we prove with heavy use of computers.

Jeff Achter

Local heuristics and exact formulas for abelian varieties over finite fields

An isogeny class of elliptic curves over a finite field is determined by a quadratic Weil polynomial. Gekeler has given a beautiful product formula, purely in terms of congruence considerations involving that polynomial, for the size of such an isogeny class.

I'll describe joint projects with Cassie Williams and Julia Gordon which, respectively, generalize and explain this phenomenon.

Riccardo Salvati Manni

Coble quartic and the universal Kummer varieties

The Kummer surface can be represented as a quartic in $\mathbb{P}^3$ whose coefficients are polynomials of degree 12 in the second order theta constants. Such a polynomial of (bi)degree (12,4) is an equation for the universal Kummer surface. Using several recent results, we intend to explain how one can extend this method to higher genera. In particular we will discuss Coble's hypersurface in genus 3 .

Tuesday 10 June Wednesday 11 June Thursday 12 June Friday 13 June
9h-9h30 Registration 9h-9h50 Shepherd-Barron 9h30-10h20 Ottaviani 9h30-10h20 Achter
9h30-10h30 Grushevsky 10h-10h30 Coffee break 10h30-11h Coffee break 10h30-11h Coffee break
10h30-11h Coffee break 10h30-11h20 Salvati Manni 11h-11h50 Popoviciu 11h-11h50 Hiary
11h-11h50 Farkas G. 11h30-12h20 Pries 12h-14h Lunch break 12h-13h30 Lunch break
12h-14h Lunch break 12h30 Lunch 14h-14h50 Kolev/Olive
14h-14h50 Robert Free afternoon 15h-15h30 Coffee break
15h-15h30 Coffee break 15h30-16h20 Bisson
15h30-16h20 Streng 16h30-17h20 Spaenlehauer
16h30-17h20 Renault Conference Dinner