Exposés invités / Tutoriels

Christine Bachoc
Université Bordeaux 1

Applications of semidefinite programming to coding theory

Semidefinite programming is a subfield of convex optimization which contains lienar programming as a special case. Thanks to the so-called interior point methods, semidefinite programs can be solved to a given approximation in polynomial time. Many practical problems in areas as different as combinatorial and polynomial optimization, statistics, control theory, and of course information theory can be modeled or approximated as semidefinite programming problems.
In this talk we will review some of these applications concerned with information theory, namely sensor network localization, maximum likelihood decoding in MIMO communication model, and bounds on performance of binary codes.

Jérémie Detrey
LORIA, Nancy

Accélération FPGA pour les codes et la cryptographie : Applications et limites

Circuits intégrés reconfigurables composés de dizaines (voire centaines) de milliers de cellules logiques très simples reliées entre elles par une interconnexion programmable, les FPGA sont aujourd'hui, de par leur flexibilité et leur parallélisme à grain fin, une cible de choix pour l'accélération de calculs spécifiques, tels que l'on peut en rencontrer en codage ou en cryptographie. Au cours de cet exposé, après une rapide présentation de l'architecture générale de ces FPGA, nous étudierons donc les possibilités d'accélération qu'ils offrent à travers plusieurs exemples, ainsi que leurs limites face aux CPU et GPU.

Marc Joye
Technicolor

Courbes elliptiques de Huff et applications cryptographiques

Dans cet exposé, nous revisitons un modèle pour les courbes elliptiques, introduit par Huff en 1948 dans l'étude d'un problème diophantien. Le modèle de Huff s'applique littéralement aux corps de caractéristique impaire. Toute courbe elliptique sur un tel corps et contenant une copie de Z/4Z x Z/2Z est birationalement équivalente sur le corps d'origine. Nous étendons et généralisons le modèle de Huff pour couvrir davantage de classes d'isomorphismes de courbes elliptiques. Nous adressons également le cas des corps binaires. Les applications cryptographiques sont discutées. Nous présentons des formules explicites rapides pour l'addition et le doublement de points sur les courbes de Huff généralisées. De façon remarquable, certaines formules obtenues présentent des propriétés intéressantes, y compris le fait d'être complètes et l'indépendance par rapport aux paramètres de la courbe.

Vadim Lyubashevsky
ENS Paris

Lattice-Based Cryptography: From Practice to Theory to Practice

Lattice-based cryptography is currently seen as one of the most promising alternatives to cryptography based on number theory. The major advantages of lattice-based protocols is that they are faster than ones based on number theory and they also seem to be resistant against quantum attacks. The origins of lattice-based cryptography, in the mid 90's, can be attributed to the 'practical' NTRU cryptosystem and the 'theoretical' constructions of Ajtai. Initially, these areas developed independently, but work done in the past few years showed surprising connections between the two and there has been a lot of recent success in bridging the gap between the practical and theoretical aspects of lattice-based cryptography. On the one hand, we have used the theoretical ideas to construct new practical, provably-secure schemes, and on the other hand, we have also been able to prove that (with a few modifications) the early practical schemes are actually provably secure. In this talk, I will explain the current hardness assumptions used for constructing efficient lattice-based schemes as well as present some sample constructions.

Sihem Mesnager
LAGA, Université Paris 8 - Université Paris 13

Fonctions courbes et "hyper-courbes" en codes et en cryptographie et liens avec les sommes de Kloosterman et les polynômes de Dickson

Bent functions are maximally nonlinear Boolean functions with an even number of variables. They were introduced by Rothaus in 1976. For their own sake as interesting combinatorial objects, but also because of their relations to coding theory (Reed-Muller codes) and applications in cryptography (design of stream ciphers), they have attracted a lot of research, specially in the last 15 years. The class of bent functions contains a subclass of functions, introduced by Youssef and Gong in 2001, the so-called hyper-bent functions whose properties are still stronger and whose elements are still rarer than bent functions. Bent and hyper-bent functions are not classified. A complete classification of these functions is elusive and looks hopeless. So, it is important to design constructions in order to know as many of (hyper)-bent functions as possible. This talk is devoted to the constructions of bent and hyper-bent Boolean functions in polynomial forms. We survey and present an overview of the constructions discovered recently. We extensively investigate the link between the bentness property of such functions and some exponential sums (Kloosterman smus and cubic sums) involving Dickson polynomials.

François Morain
LIX, École Polytechnique

Équations modulaires, algorithmes et applications

Les équations modulaires ont été introduites il y a fort longtemps, en liaison avec le calcul d'intégrales elliptiques. Au fil du temps, on les as vues comme des modèles des courbes modulaires, typiquement X0(N). Leur intérêt intrinsèque est grand, comme le démontre le théorème de Wiles. Les courbes modulaires ont permis de construire de bons codes géométriques (Tsfasman, Vladut, Zink; plus récemment les tours de Garcia-Stichtenoth expliquées par Elkies). D'un point de vue plus algorithmique, elles sont la clef de voûte de l'algorithme SEA qui calcule la cardinalité d'une courbe elliptique sur un corps fini. Le but de l'exposé est de présenter quelques éléments de base de la théorie, en insistant sur les calculs de ces équations et les applications aux thèmes déjà cités, en y ajoutant quelques liens avec la théorie de la multiplication complexe.

Damien Vergnaud
ENS Paris

Fonctions à trappe à perte d'information et applications

En 2008, C. Peikert et B. Waters ont introduit la notion de fonctions à trappe à perte d'information (lossy trapdoor functions) et ont développé de nouvelles constructions cryptographiques basées sur cette notion (par exemple des fonctions de hachage résistante aux collisions ou des protocoles de chiffrement résistant aux attaques actives). Ils ont également proposé différentes réalisations de cette primitive basées sur des hypothèses algorithmiques variées (comme la difficulté du problème décisionnel Diffie-Hellman ou de problèmes classiques dans les réseaux euclidiens). L'objectif de cet exposé est de présenter plusieurs applications et extensions récentes de ces fonctions en cryptographie asymétrique.