• Julia Wolf, Ecole Polytechnique – A quadratic Goldreich-Levin theorem

We present a local self-correction procedure for Reed-Muller codes of order 2 for functions at distance 1/2-epsilon from a codeword. This is an algorithmic analogue of Samorodnitsky’s tester for this problem, and to our knowledge, the first instance of a correction procedure beyond the list-decoding radius for any class of codes. It also forms the key ingredient of a « quadratic Goldreich-Levin theorem », which computes with high probability the large quadratic Fourier coefficients of a function in polynomial time.

This is joint work with Madhur Tulsiani.

  • Julia Pieltant, INRIA Saclay Île-de-France – Tours de corps de fonctions algébriques et algorithme de type Chudnovsky pour la détermination de bornes sur la complexité bilinéaire de la multiplication dans les corps finis.

On s’intéresse ici aux algorithmes de multiplication dans les corps finis, et plus précisément à la détermination de bornes sur la complexité bilinéaire de la multiplication dans une extension de degré n de F_q. On distingue en effet deux types d’opérations élémentaires : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire et les opérations bilinéaires (multiplications de deux éléments de F_q dépendants directement des éléments de F_{q^n} dont on effectue le produit) comptabilisées par la complexité bilinéaire. Ce dernier type de complexité est indépendant de la base de F_{q^n} sur F_q choisie et correspond au rang du tenseur de la multiplication dans F_{q^n}.

L’algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire : il a permis d’établir que le rang de tenseur de la multiplication dans F_{q^n} est linéaire en le degré n de l’extension considérée, et en fournit désormais les meilleures bornes connues dans le cas d’extensions de degré grand relativement au cardinal du corps de base.

Au cours de cet exposé, on présentera la dernière version de l’algorithme de type Chudnovsky, ainsi qu’une méthode d’obtention de bornes uniformes en n pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q à partir de tours de corps de fonctions algébriques ayant de bonnes propriétés. En particulier, l’étude des tours de Garcia-Stichtenoth d’extensions d’Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vladut permet d’obtenir les meilleures bornes actuellement connues pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q, pour tout q premier ou puissance d’un premier.

Julia.Pieltant-28-06-2013 (format pdf)

  • Antoine Joux, DGA et Université de Versailles – Logarithmes discrets dans les corps finis. Application en caractéristiques petite et moyenne

Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d’index dans le cas le plus simple: celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet un amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.

  • Gaëtan Leurent, Université catholique de Louvain -« Differential Attacks against ARX Designs »

In this talk, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We describe an efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2^32 2.5-bit constraints.

We have developed a set of tools for this analysis of ARX primitives based on this set of constraints. We show that the new constraints are more precise than what was used in previous works, and n detect several cases of incompatibility. In particular, we show that several published attacks are in fact fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.

Moreover, we are able to build automatically complex non-linear differential characteristics for reduced versions of the hash function Skein. We describe several characteristics for use in various ttack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively. These are some of the first examples of complex differential trails built for pure ARX designs.

Gaetan.Leurent-28-6-2013 (format pdf)