Institut de Mathématiques de Luminy

SÉMINAIRES 2009
Arithmétique et Théorie de l'Information

Responsables: G. Lachaud, F. Rodier
Horaires: Le jeudi à 10h30
Salle: amphi du 1er étage, salle 130-134, I.M.L., Groupe des Laboratoires de Luminy (CNRS).

Planning

Stephanie Dib
jeudi 17 décembre
Stéphanie Dib
(IML, Marseille)
Distribution des fonctions booléennes
selon la non-linéarité et décodage des codes
de Reed-Muller d'ordre 1

Résumé : Dans le contexte de la cryptographie, la non-linéarité des fonctions booléennes est un critère essentiel pour résister aux attaques linéaires. Comme il y a beaucoup plus d'approximations quadratiques que d'approximations linéaires, il est nécessaire aussi de considérer la non-linéarité d'ordre 2.
Dans cet exposé, nous étudions la distribution de la non-linéarité des fonctions booléennes, ainsi que celle d'ordre 2. De plus, comme les codes de Reed-Muller sont liés aux fonctions booléennes, nous étudions la relation entre la non-linéarité et le décodage au delà de la moitié de la distance minimale. Nous trouvons un seuil de décodage au delà duquel il devient impossible de décoder correctement.

jeudi 10 décembre
Jean-Francis Michon
(LIFAR, Rouen)
Constructions de polynomes irréductibles
et logarithme discret sur F2

Page web : http://www.univ-rouen.fr/LIFAR/Membres/Michon.php4

Abstract: Using a natural action of the permutation group S3 on the set of irreducible polynomials, we attach to each subgroup of S3 the family of its invariant polynomials. Enumeration formulas for the trivial subgroup and for one transposition subgroup were given by Gauss and Carlitz (for all finite base fields). Respectively, they allow to enumerate all irreducible and self reciprocal irreducible polynomials. In our context, the last remaining case concerned the alternating subgroup A3. We give here the corresponding enumeration formula restricted to F2 base field. We wish this will give an interesting basis for subsequent developmentsanalogous to those of Meyn and Cohen.

jeudi 26 novembre
Damien Robert
(ENS Paris)
Le calcul des isogénies entres des variétés abéliennes

(joint work with David Lubicz)
Homepage : http://www.normalesup.org/~robert/pro/

Abstract: Isogenies are an essential tool in Elliptic Curves cryptography, where they are used in a wide variety of area: fast point counting, complex multiplication methods... Vélu's formulas give an efficient method for computing such isogenies, but there were no known formulas for computing isogenies for hyperelliptic curves of higher genus, except in particuliar cases. In this talk, we will show how the framework of theta structures, developped by Mumford in 1967, allows us to give a generalization of Vélu's formulas for any abelian variety.

jeudi 19 novembre
Yves Aubry
(IMT Toulon / IML Marseille)
Fonctions booléennes cryptographiquement robustes

Page web : http://yaubry.univ-tln.fr/

jeudi 12 novembre
Dimitrii Nogin
(IITP, Moscou)
Spectral approach to
linear programming bounds of coding theory
(in collaboration with A.Barg)
Homepage : http://www.iitp.ru/en/users/122.htm

Abstract: Estimating the maximum size of the code with a given value of the code distance is one of the main problems of coding theory. A powerful technique to bound the code size from above, which is applicable in a wide class of metric spaces, is Delsarte's linear programming method.
We suggest a new proof method for linear programming upper bounds of coding theory. Our approach, which relies on the analysis of eigenvectors of some finite-dimensional operators related to orthogonal polynomials arguably makes some steps of the proofs conceptually more transparent than those previously known.

jeudi 22 octobre
Stéphane Louboutin
(IML, Marseille)
Unités fondamentales de certains ordres

jeudi 25 juin
Safia Haloui
(IML, Marseille)
Jacobiennes et variétés de Prym sur un corps fini

jeudi 18 juin
Marcos Zarzar
(Univ. of Texas, Austin)
Estimating minimal distance on codes on surfaces

Homepage : http://www.math.utexas.edu/users/zarzar/

jeudi 11 juin
Frédéric Didier
(EPFL, Lausanne)
Décodage rapide pour un code
de Reed-Solomon à effacement

Page web : http://algo.epfl.ch/~didier/

jeudi 28 mai
Gaëtan Bisson
(LORIA, Vandoeuvre)
Calcul des anneaux d'endomorphismes des courbes elliptiques sur les corps finis
(Travail en commun avec Andrew V. Sutherland)

Résumé : Nous considérerons les courbes elliptiques ordinaires définies sur les corps finis et nous intéresserons au calcul de leurs anneaux d'endomorphismes. Ces objets interviennent notamment dans la méthode CM
qui permet de construire des courbes d'ordre prescrit ; il est donc important de savoir les calculer.
Dans sa thèse, Kohel étudie la structure du graphe d'isogénies et l'exploite afin d'obtenir un algorithme déterministe pour cette tâche.
Ici, nous présenterons un algorithme probabiliste mais plus rapide (de complexité sous-exponentielle en log(q)) qui se base sur les résultats de Kohel ainsi que sur l'action du groupe de classe de l'anneau d'endomorphismes sur le graphe d'isogénies. L'idée est de comparer certaines « relations » que l'on calculera indépendamment dans le groupe de classe et dans le graphe d'isogénies.
Nous montrerons aussi comment cette démarche permet de certifier l'anneau d'endomorphismes d'une courbe.

jeudi 7 mai
Didier Alquié
(Rennes)
Nombre de branchements d'un automate linéaire et codes convolutifs récursifs systématiques
(Travail en commun avec Franck Landelle)

Résumé : Nous proposons un nouveau cadre pour évaluer la biais linéaire d'un générateur pseudo aléatoire. Nous définissons le nombre de branchements ("branch number") d'un automate intermédiaire défini sur un corps fini GF(q) comme le nombre de boîtes actives reliées aux entrées et sorties. Cette valeur est utile pour évaluer le biais global linéaire chaîné du générateur. Nous montrons comment il peut être relié à la distance libre d'un code convolutif sur GF(q) convenablement défini, et que les codes optimaux par rapport à la distance libre conduisent à une borne - fine - sur le branch number. En conséquence, l'utilisation de ces registres spécifiques dans une conception peut aider à fournir une borne supérieure "prouvable" du biais global.

jeudi 16 avril
Claude Carlet
(Univ. Paris 8)
Une classe infinie de fonctions équilibrées d'immunité
algébrique optimale, de bonne immunité contre les
attaques algébriques rapides, et de bonne non-linéarité
(Travail en commun avec Keqin Feng, Tsinghua University, Pékin)

Résumé: After the improvement by Courtois and Meier of the algebraic attacks on stream ciphers and the introduction of the related notion of algebraic immunity, several constructions of infinite classes of Boolean functions with optimum algebraic immunity have been proposed. All of them gave functions whose algebraic degrees are high enough for resisting the Berlekamp Massey attack and the recent Ronjom-Helleseth attack, but whose nonlinearities either achieve the worst possible value (given by Lobanov's bound) or are slightly superior to it. Hence, these functions do not allow resistance to fast correlation attacks. Moreover, they do not behave well with respect to fast algebraic attacks.
In this paper, we study an infinite class of functions which achieve an optimum algebraic immunity. We prove that they have an optimum algebraic degree and a much better nonlinearity than all the previously obtained infinite classes of functions. We study the complexity of computing their output.
We check that, at least for small values of the number of variables, the functions of this class have in fact a very good nonlinearity and also a good behavior against fast algebraic attacks. The question of more efficiently lower bounding their nonlinearity is related to open questions in sequence theory.

jeudi 9 avril
Antonella Perucca
(EPFL, Suisse)
On the order of the reductions of points
on products of abelian varieties and tori, I

jeudi 12 mars
salle séminaires
à 10h30

Fabien Pazuki
(IMJ, Paris)
Fonctions thêta et surfaces abéliennes

Résumé : On étudiera dans cet exposé le rôle que les fonctions thêta jouent dans l'étude des hauteurs de Néron-Tate et de Faltings pour les variétés abéliennes de dimension 2 sur un corps de nombres

à 14h30
Gary McGuire
(UCD, Ireland)
Recent Results on APN Functions
and their Fourier Transforms

jeudi 19 février
David Lubicz
(Univ. Rennes 1)
Calcul de correspondances modulaires
entre variétés abéliennes
(travail commun avec Jean-Charles Faugère et Damien Robert)

Résumé : L'objet de cet exposé est de donner un équivalent en dimension plus grande que un des classiques polynômes modulaires. Nous utilisons pour cela la description de l'espace des modulaires des variétés abéliennes donnée par les thêta constantes.

jeudi 12 février
Eric Nart
(Univ. Barcelone)
Newton polygons of higher order
in algebraic number theory

Abstract: We develop a theory of arithmetic Newton polygons of higher order, that provides the factorization of a separable polynomial over a p-adic field, together with relevant arithmetic information about the fields generated by the irreducible factors. As an application, we obtain fast algorithms to compute discriminants, prime ideal decomposition and integral bases of number fields.

jeudi 5 février
Christophe Ritzenthaler
(IML, Marseille)
Calcul de l'obstruction de Serre pour les courbes de genre 3 et application aux courbes optimales

jeudi 22 janvier
Stéphane Ballet
(IML, Marseille)
Existence de diviseurs non-spéciaux de degré g-1 dans des corps de fonctions algébriques définis sur F_q

jeudi 15 janvier
Michel Balazard
(IML, Marseille)
Sur les zéros des sommes partielles de la fonction zêta

 

EL, le 7 décembre 2009