Institut de Mathématiques de Luminy
SÉMINAIRES 2008
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

jeudi 11 décembre
Sergey Rybakov
(Labo. Poncelet, Moscou)
Zeta functions of genus 3 curves over finite fields

Abstract: We will give some necessary and some sufficient conditions for a function to be a zeta function of genus 3 curve. To prove the result we have to construct an irreducible principal polarisation on an abelian threefold. Mostly we will discuss polarisations on abelian threefolds isogenous to a product of a geometrically simple abelian surface and an ordinary elliptic curve.

jeudi 4 décembre
Patrick Solé
(ESSI, Sophia-Antipolis)
Le critère de Pustel'nikov pour l'hypothèse de Riemann

Résumé : Le critère du titre associe à chaque zéro de la fonction zêta de Riemann dans la bande critique hors de l'axe critique un opérateur avec une valeur propre $-1$. On montre que la partie suffisante de ce critère est fausse par contradiction. L'argument utilise des résultats de Wong et Li sur le comportement asymptotique des solutions des équations aux différences du second ordre. On donne trois critères de remplacement.

jeudi 27 novembre
Gautami Bhowmik
(Univ. Lille 1)
Prolongement méromorphe des séries de Dirichlet

Résumé : Nous nous intéressons aux prolongements analytiques des séries de Dirichlet . On ne connait des résultats précis sur leurs frontières naturelles de méromorphie que dans certains cas (par exemple un théorème célèbre pour les produits eulériens d’une variable dû à Estermann (1928)).
Des applications diverses découlent de cette étude, nous en donnerons quelques exemples récents (fonction de hauteur, nombre de Goldbach, groupes classiques..).

jeudi 20 novembre
Jacques Wolfmann
(GRIM, Toulon)
Nouveaux paramètres pour les fonctions courbes

jeudi 13 novembre
Robert Rolland
(IML)
Le deuxième poids des codes de Reed-Muller généralisés, d'ordre d

jeudi 23 octobre
Alain Couvreur
(IML)
Codes différentiels construits
sur des surfaces algébriques et applications

Résumé : Nous commençerons par rappeler les notions connues sur les codes correcteurs construits à partir de courbes algébriques. En particulier, nous présenterons les deux constructions existantes, la première utilisant des fonctions et la seconde des formes différentielles.
Ensuite partant de la constatation que les généralisations connues en dimension supérieure ne concernent que la construction fonctionnelle, nous présenterons un procédé nouveau de constructions de codes sur des surfaces que l'on peut voir comme une généralisation de la construction différentielle connue dans le cas des courbes. Nous nous intéresserons ensuite aux relations qui lient ces codes aux codes fonctionnels en vue de généralisation de résultats connus dans le cas des courbes.
Le résultat le plus surprenant est que dans le cas des surfaces, l'orthogonal d'un code fonctionnel ne peut en général pas se réaliser comme un code différentiel. C'est là une différence majeure avec le cas des codes sur les courbes. Nous finirons l'exposé par quelques résultats et questions ouvertes sur l'étude des ces "nouveaux codes" que sont les orthogonaux de codes fonctionnels.

jeudi 16 octobre
David Kohel
(IML)
Le logiciel SAGE

jeudi 9 octobre
David Gruenewald
(Univ. Sydney, Australia)
Humbert surfaces

jeudi 26 juin
Frédéric Edoukou
(IML)
Sur les mots de code de petits poids
pour les codes fonctionels C_2(Q),
où Q est une quadrique non singulière
(Travail commun avec A. Hallez, F. Rodier et L. Storme)

jeudi 19 juin
à 11h
Pierre-Louis Cayrel
(XLIM, Univ. Limoges)
Nouveaux résultats en signature basée
sur des codes correcteurs d'erreurs
Cet exposé se base sur une série de trois travaux réalisés avec Philippe
Gaborit et Emmanuel Prouff (pour le premier), Philippe Gaborit, David
Galindo et Marc Girault (pour le deuxième) et Carlos Aguilar Melchor et
Philippe Gaborit (pour le troisième)

Résumé : Je présenterai dans un premier temps la cryptographie basée sur les codes correcteurs d'erreurs (schéma de McEliece, Niederreiter) puis je détaillerai le schéma d'identification et de signature de Stern présenté à CRYPTO en 1993 et le schéma de signature de Courtois-Finiasz-Sendrier (ASIACRYPT 2001).
Je présenterai ensuite 3 travaux récents sur ce sujet :
- une construction sécurisée du schéma de Stern contre les attaques par canaux cachés (DPA)
- un schéma de signature basé sur l'identité, prouvé sûr mêlant le schéma de Stern et le schéma de signature de Courtois-Finiasz-Sendrier.
- un schéma de signature de cercle (de taille n) à seuil (t-out-of-n threshold ring signature scheme) construit comme une généralisation du schéma de Stern et qui donne les meilleurs résultats connus pour ce type de signature.

Demi-journée de théorie analytique des nombres
jeudi 19 juin
à 14h30
Eric Saias
(Univ. Paris 6)
Questions autour de l'hypothèse de Riemann généralisée
à 16h
Hugh L. Montgomery
(Univ. du Michigan, Ann Arbor)
Titre à préciser

jeudi 12 juin
Guilhem Castagnos
(Greyc, Univ. Caen)
A NICE Alternative to Paillier's Encryption
(Travail en commun avec Fabien Laguillaumie)

Résumé : Je présenterai un nouveau schéma de chiffrement à clef publique homomorphe additif (dont la fonction de déchiffrement est un morphisme) basé sur l'arithmétique des ordres quadratiques imaginaires. Ce schéma peut-être vu comme une transposition du schéma de Paillier dans les corps quadratiques, et bénéficie donc d'un algorithme de déchiffrement
au coût quadratique hérité des schémas utilisant cette structure, comme le schéma NICE proposé par Paulus et Takagi.
De plus, ce schéma est sémantiquement sûr face à des attaques à clairs choisis sous l'hypothèse d'un problème classique d'appartenance à un sous-groupe.
Essentiellement, le déchiffrement consiste à calculer de manière efficace la surjection du groupe de classe d'un ordre de discriminant $-p^4q^2r$ dans le groupe de classe d'un ordre de discriminant $-p^4r$, où $p$, $q$ et $r$ sont trois grands nombres premiers. Contrairement au
cryptosystème NICE, notre schéma ne nécessite pas un codage complexe d'un message en un élément du groupe de classe.

jeudi 5 juin
Kristin Lauter
(Microsoft Research, USA)
Improved bounds on the number of points
on curves over finite fields
(Joint work with Everett Howe)

Abstract: We give new arguments that improve the known upper bounds on the maximal number N_q(g) of rational points of a curve of genus g over a finite field F_q, for a number of pairs (q,g). Given a pair (q,g) and an integer N, we determine the possible zeta functions of genus-g curves over F_q with N points, and then deduce properties of the curves from their zeta functions. In many cases we can show that a genus-g curve over F_q with N points must have a low-degree map to another curve over F_q, and often this is enough to give us a contradiction.

jeudi 29 mai
Kristin Lauter
(Microsoft Research, USA)
Applications of Ramanujan graphs in cryptography
(Joint work with Denis Charles and Eyal Goren)

Abstract: This talk will explain a new construction of secure cryptographic hash functions from Ramanujan graphs. First we will explain cryptographic hash functions and the importance of the collision-resistance property. After a brief overview of expander graphs, we will give a construction of provable collision resistant hash functions from expander graphs in which finding cycles is hard.
As an example, we give a family of optimal expander graphs for provable collision resistant hash function constructions: the family of Ramanujan graphs constructed by Pizer. Pizer described a family of Ramanujan graphs, where the nodes of the graph are isomorphism classes of supersingular elliptic curves over F_p^2, and the edges are n-isogenies, n a prime different from p. When the hash function is constructed from one of Pizer's Ramanujan graphs, then collision resistance follows from hardness of computing isogenies between supersingular elliptic curves.

jeudi 15 mai
à 11h
François Rodier
(IML)
Applications de la géométrie algébrique
à la cryptographie symétrique

Résumé : Nyberg a défini la notion de la non-linéarité presque parfaite (APN) pour caractériser les fonctions booléennes qui ont la meilleure résistance aux attaques différentielles. Nous montrons ici que pour beaucoup de fonctions booléennes APN, le nombre de ses variables est borné par une expression dépendant du degré de cette fonction. Nous utilisons pour cela des résultats de Lang-Weil et de P. Deligne (ou plus exactement des améliorations, due à Ghorpade et Lachaud) sur les conjectures de Weil.

à 14h30
Sudhir Ghorpade
(IIT Bombay)
Recent progress on the weight hierarchy of Grassmann and Schubert codes

jeudi 24 avril
Gilles Lachaud ou Christophe Ritzenthaler
(IML)
Courbes de genre 3

jeudi 10 avril
Le Duc-Phong
(ESIL)
Multisignature Schemes with tight reduction
in the plain public-key model

jeudi 3 avril
Magali Rocher
(IMB-A2X, Univ. Bordeaux)
Courbes algébriques lisses en caractéristique p>0
munies d'un gros p-groupe d'automorphismes

Résumé:
Soit k un corps algébriquement clos de caractéristique p>0. Soit C/k une courbe algébrique lisse de genre g>1, munie d'un p-groupe d'automorphismes tel que |G| > (2p/p-1)*g. Alors, C ---> C/G est un revêtement étale de la droite affine Spec k[X], complètement ramifié à l'infini. Après avoir précisé certaine propriétés du second groupe de ramification de G à l'infini: G_2, on donnera des exemples de telles actions avec G_2 abélien d'exposant quelconque. Ces exemples illustreront le lien avec les courbes algébriques sur un corps fini possédant beaucoup de points rationnels. On se concentrera ensuite plus particulièrement sur le cas où G_2 est p-abélien élémentaire. Dans cette situation, on obtiendra un théorème de structure en considérant une filtration de k[X] liée au polynômes additifs.

jeudi 27 mars
Nicolas Meloni
(GRIM, Univ. Toulon)
Chaînes d'additions différentielles et multiplication de points sur les courbes elliptiques

Résumé:
Depuis leur introduction au milieu des années 80, les courbes elliptiques sont devenues l'un des principaux outils de la cryptographie moderne. La principale opération (en termes de temps de calcul) de tout protocole utilisant les courbes elliptiques est la multiplication de point par un scalaire: le calcul de k*P=P+...+P, où k est un entier et P un point de la courbe. Afin d'effectuer cette opération de la manière la plus efficace possible, de nombreuses méthodes ont été proposées. Elles reposent, en général, sur l'algorithme dit "double-and-add" consistant à effectuer des séries de doublements entrecoupées d'additions, en fonction de la représentation binaire du scalaire k.
Dans cet exposé nous allons sortir des sentiers battus en nous intéressant à des méthodes de multiplication de point basées sur les chaînes d'additions différentielles. Celles-ci ont la particularités d'être principalement composées d'additions (au lieu de doublements), entrainant un plus grand nombre d'étapes de calcul, compensé par le fait qu'il est possible d'obtenir, sous certaines conditions, une addition plus efficace qu'un doublement. Nous verrons que cette approche apparait comme très prometteuse de prime abord, mais que certains problèmes (concernant la taille des chaînes notamment) restent à résoudre afin d'envisager une utilisation concrête.

jeudi 20 mars
Harald Niederreiter
(Univ. Singapore)
La théorie asymptotique des codes

jeudi 13 mars
Gregor Leander
(CITS, Ruhr-Univ. Bochum)
Construction of Bent functions from near-Bent functions

Abstract: We give a construction of bent functions in dimension 2m from near-bent functions in dimension 2m-1. In particular, we give the first ever examples of non weakly-normal bent functions in dimensions 10 and 12, which demonstrates the significance of our construction.

jeudi 6 mars
(salle des séminaires)
Michel Laurent
(IML)
Formes linéaires en deux logarithmes
et quelques nouvelles applications

jeudi 28 février
Frédéric Edoukou
(IML)
Les codes sur une quadrique de grande dimension
(travaux communs avec L. Storme)

jeudi 7 février
David Kohel
(IML)
Variétés abéliennes, espaces de modules
et points à multiplication complexe

jeudi 31 janvier
Gabor Wiese
(Univ. Duisburg-Essen)
Sur les coefficients de formes modulaires

jeudi 24 janvier
Xavier Xarles
(Univ. Barcelone)
Squares in arithmetic progression

jeudi 17 janvier
Andreas Enge
(LIX, Palaiseau)
Un algorithme en $L(1/3+\epsilon)$ pour le problème du logarithme discret dans certaines courbes
(travail commun avec P. Gaudry)

Résumé : Depuis les travaux d'Adleman, DeMarrais et Huang il y a plus d'une décennie, il est bien connu que le problème du logarithme discret dans une courbe de grand genre sur un corps fini est plus simple à résoudre que dans une courbe elliptique de la même taille. Si $L(\alpha, c) = e^{(c + o (1)) (g \log q)^{\alpha} (\log (g \log q))^{1 - \alpha}}$ désigne la fonction sous-exponentielle par rapport au genre $g$ de la courbe et au cardinal $q$ de son corps de définition, les algorithmes de logarithme discret pour les courbes de grand genre ont une complexité de $L(1/2, c)$. Ceci est à comparer aux courbes elliptiques d'un côté, pour lesquelles seulement des algorithmes exponentiels existent sauf dans quelques cas particuliers; et au cas des corps finis, pour lesquels le crible des corps de nombres ou des corps de fonctions mène à un algorithme plus rapide en $L(1/3, c)$.
Je présente le premier algorithme sous-exponentiel avec un exposant $\alpha < 1/2$ pour attaquer le problème du logarithme discret dans une certaine classe de courbes algébriques. Ces courbes sont caractérisées par un degré relativement bas par rapport à leur genre. Dans le meilleur des cas, l'algorithme atteint une complexité de $L(1/3, c)$ pour calculer la structure du groupe jacobien et $L(1/3 + epsilon, o(1))$ pour le logarithme proprement dit.

EL, le 2 décembre 2008