Jeudi 28 mars 2019 à 16h30 en salle C49

Matthieu Rambaud (Télécom ParisTech)

Titre : Multiplication friendly lifts of (AG) codes over local rings and applications

Résumé :

Let C be a code over a local ring (R,m), e.g. Z/2^l Z, we say that C is a good lift iff it is free of same dimension than the reduced code C' over the residue field. This is very desirable (the minimum distance and dual distance are then at least as large than those of the reduced code, plus, decoding is linear), and easy to produce (lift arbitrarily a basis of C').
But things are less happy when taking the square. For the (interesting) codes of small square ---which are not generic--- then the square of a good lift can fail to be a good lift. We can interpret this problem in terms of lifting quadrics with many zeros in common, simultaneously with these zeros in common, which we still ignore in which generality this has solutions.
We then show that solutions do exist for every algebraic geometry codes over curves (from divisors of degree larger than 2g+1). This follows from the existence of smooth projective lifts for algebraic curves, Judy Walker's AG codes over rings and Mumford's ``normal generation'' for L(2D). Our numerical examples of multiplication-friendly lifts (from scandalously heavy linear systems) lead us to conjecture an even stronger property for AG codes: it seems that any multiplication-friendly lift C_i of C' over R/m^i, has a multiplication-friendly lift over R (whereas only C' is so far proven to have a multiplication-friendly lift over R).
This has applications to faster secure multiparty computation on secret integers. Work submitted with R. Cramer and C. Xing (available on my webpage), and ongoing with A. Couvreur and M. Abspoel.