Institut de Mathématiques de Luminy

SÉMINAIRES ATI 2002

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


Décembre 2002

19 décembre
P. Gaudry :
Algorithme de Mestre pour le calcul du nombre
de points des courbes de genre 2
.

Résumé : Calculer le cardinal de la Jacobienne d'une courbe de genre 2 sur un corps fini est une tâche importante pour la cryptographie. Mestre a proposé un algorithme basé sur le calcul du relèvement p-adique canonique grâce à l'isogénie de Richelot. Nous expliquerons le fonctionnement de cet algorithme et nous montrerons comment les améliorations qui existent pour l'analogue elliptique peuvent s'étendre au genre 2 et fournissent un algorithme asymptotiquement très rapide.

12 décembre
M. Tsfasman (IML) :
Sur l'amélioration par Xing de la borne de Tsfasman, Vladut et Zink.

5 décembre
A. Canteaut :
Attaques par corrélation des générateurs
pseudo-aléatoires pour le chiffrement à flot
.

Résumé : Dans un algorithme de chiffrement à flot, le chiffré est obtenu en additionnant bit-à-bit le message clair à une suite pseudo-aléatoire, appelée suite chiffrante. Cette suite est produite par un générateur pseudo-aléatoire dont l'initialisation correspond à la clef secrète du système. Dans ce contexte, une attaque à clair connu consiste donc à retrouver cette initialisation à partir de la connaissance de certains bits de la suite chiffrante.
Dans ce type d'applications, le générateur pseudo-aléatoire est généralement composé de registres à décalage à rétroaction linéaire, car il s'agit de composants très rapides et faciles à implémenter en hardware. Ces registres peuvent être combinés de différentes manières (combinaison par une fonction booléenne, utilisation d'une fonction de filtrage, contrôle de l'horloge...). Dans ces systèmes, la clef secrète correspond donc à l'ensemble des initialisations des registres utilisés. Tous ces générateurs sont vulnérables aux attaques par corrélation. Cette technique de cryptanalyse, introduite par Siegenthaler, est de type "diviser pour mieux régner" : elle consiste à retrouver l'initialisation de chacun des registres indépendamment des autres. Pour cela, on exploite l'existence d'une éventuelle corrélation entre la sortie du générateur pseudo-aléatoire et celle d'un des registres utilisés. Meier et Staffelbach ont montré que ce type d'attaques pouvait être vu comme un problème de correction d'erreurs, dans lequel la suite chiffrante est assimilée à une version bruitée de la sortie d'un des registres du système. Dans cet exposé, nous présenterons le principe général de ces attaques ainsi que plusieurs techniques proposées récemment pour résoudre ce problème. Ces méthodes reposent sur l'utilisation de différents types de codes correcteurs et d'algorithmes de décodage. Dans le cas des générateurs par combinaison de registres, nous nous intéresserons également à l'influence de certaines propriétés de la fonction booléenne de combinaison sur les performances des attaques par corrélation.


Novembre 2002

28 novembre
G. Lachaud (IML) :
Zéros des fonctions L et formes toriques.

21 novembre
S. David :
Amélioration du papier d'Agrawal et al. sur les nombres premiers.

7 novembre
M. Laurent (IML) :
Approximations simultanées et dualité.


Octobre 2002

24 octobre
S. Vladut (IML) :
Une nouvelle constuction des codes à partir des courbes
(d'après Elkies)
.

10 octobre
R. Rolland (IML):
Généralisation de l'algorithme de multiplication
de D.V. et G.V. Chudnovski
Voir preprint: http://iml.univ-mrs.fr/editions/preprint2002/preprint2002.html


Septembre 2002

24 septembre
de 10 h à 16 h
P. Véron
(GRIM Toulon):
AzurCrypt.


Juin 2002

27 juin
S. Ghorpade :
Codes associated to Schubert varieties and flag varieties.

Résumé : I will first report on some recent progress on the conjecture for the minimum distance of the codes associated to Schubert varieties in Grassmannians. Next, we will consider the codes associated to the variety of partial flags, which have recently been studied by Rodier. A partial generalization of Rodier's results will be described.

20 juin
R. Samet :
Sur la maximalité des anneaux d'endomorphismes des modules de Drinfeld sur les corps finis.

13 juin
R. Rolland :
Généralisation de l'algorithme de multiplication
de D.V. et G.V. Chudnovski.
Voir preprint : http://iml.univ-mrs.fr/editions/preprint2002/preprint2002.html

6 juin
Pas d'exposé
en raison du colloque YACC à Porquerolle.


Mai 2002

30 mai
Ben Lichtin :
Majorations des sommes exponentielles en plusieurs variables et la
théorie d'Igusa.

23 mai
M. Ciet :
Elliptic Curve Scalar Multiplication using Efficient Endomorphisms.

Résumé : After recalling classical exponentiation algorithms, we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphism Phi with minimal polynomial X^2+rX+s to compute any multiple kP of a point P of order n lying on an elliptic curve.
This method constructs the following decomposition: kP = k_1P + k_2\Phi(P), \quad\text{with} \max\{|k_1|,|k_2|\}\leq A\sqrt n.
The problem is that until recently no value for A was known and indeed it was conjectured that A\leq 1. In February 2002, Park, Jeong, Kim, and Lim (PKC 2002) gave the first bounds, although they did not manage to prove this conjecture.
In this talk we will produce another value for A, based on the original GLV paper. Then we will derive a careful analysis of (PKC 2002) to find the optimal value of A, thus proving the conjecture in the known examples but disproving it in general.
One consequence of this work is that the GLV method is not effective for a generic elliptic curve.
If time permits, we provide the first explicit bounds for the GLV method generalised to hyperelliptic curves as described in Park, Jeong and Lim (EUROCRYPT 2002).

16 mai
R. Okazaki :
Power residue symbols and class numbers of CM-fields.


Avril 2002

25 avril
D. Nogin :
Titre non précisé.

18 avril
M. Planat :
Physique des nombres et du temps, et hypothèse de Riemann.

Résumé : Je défends la thèse que la théorie des nombres est naturellement présente dans plusieurs domaines issus de la physique expérimentale. Et qu'en retour, il y aurait après la physique du continu du XIXème siècle et la physique quantique du XXème siècle, une physique arithmétique pour le XXième siècle. A l'appui de cette thèse je pose quelques jalons issus
1) d'expériences fines de métrologie des fréquences,
2) de considérations sur la physique statistique des gaz parfaits,
3) d'une adaptation de la transformée de Fourier discrète par les sommes de Ramanujan,
4) de considérations sur la nature arithmétique du temps.
Dans tous les cas on trouve pour pivot la fonction zêta de Riemann (ou les objets construits autour) et la complexité provient du comportement sur la droite critique. De 1) on trouve l'archétype du bruit hyperbolique (en 1/f) en relation avec les fractions continues et l'hypothèse de Riemann généralisée, de 2), on voit que la fonction zêta de Riemann complétée n'est pas autre chose (à transformée de Mellin près) que la fonction de partition du gaz classique, de 3) on tire un nouveau traitement du signal adapté à la présence des résonances, et avec 4) il y aurait une véritable physique arithmétique à temps discret, qui va bien au delà des recettes chaotiques à la mode il y a quelques années.


Mars 2002

28 mars
F. Rodier :
Sur la non linéarité des fonctions booléennes.

21 mars
S. Vladut :
Sur le zéro de hauteur minimale de la fonction zêta de Dedekind.

7 mars
T. Schmidt :
Courbes elliptiques d'un point de vue appliqué.


Février 2002

28 février
J-F. Burnole :

Sur Fourier et Dzêta(s).

21 février
H. Randriambololona :
Hauteurs de matrices d'interpolation


Janvier 2002

31 janvier
P. Solé :
Formes de Jacobi.

24 janvier
exceptionnement à 14 h

Phong Nguyen :
Les deux visages des réseaux en cryptologie.

17 janvier
Pas d'exposé en raison de la rencontre "Théorie des nombres et applications" qui se tiendra au CIRM.

EL, le 26 novembre 2002