Les fonctions booléennes sont utilisées depuis longtemps en cryptographie. Elles interviennent comme primitives cryptographiques, par exemple comme fonctions de combinaison et de filtrage dans les schémas de chiffrement à flots. Elles doivent satisfaire différents critères (degré algébrique, non-linéarité, k-résilience), mais il faut souvent trouver un compromis entre ces propriétés car elles induisent des incompatibilités partielles.
Nous nous intéressons ici au critère d'immunité aux corrélations. Notre objectif est de classifier les fonctions booléennes et de mesurer la représentativité d'une fonction selon ce critère.
Nous verrons une méthode pour coder les fonctions booléennes qui permet de classifier les fonctions selon leur distance aux fonctions sans corrélation d'ordre 1. Ce codage a de bonnes propriétés algorithmiques, nous disposons ainsi des premiers algorithmes efficaces pour énumérer et générer des fonctions 1-résilientes. Nous l'utiliserons également pour améliorer les bornes supérieures et donner les premières bornes inférieures significatives du nombre de fonctions 1-résilientes.

Un automate FCSR (Feedback with Carry Shift Register) est un automate qui calcule le développement 2-adique de p/q, où q est un nombre impair fixé. En octobre 2004, François Arnault et moi-même avons proposé un générateur pseudo-aléatoire en filtrant les états internes de l'automate par un filtre linéaire. Ce générateur est actuellement en cours d'évaluation par le réseau d'excellence Ecrypt dans le cadre de l'appel à propositions de stream ciphers. Le but de cet exposé est de faire le point sur les propriétés de ce générateur, les cryptanalyses connues à ce jour et les modifications à apporter à son design pour rendre ces attaques inopérantes.

Le calcul de polynômes de classe est l'étape principale dans la construction de courbes elliptiques par la méthode de la multiplication complexe. Ces courbes peuvent servir comme base de cryptosystèmes, dans les preuves de primalité ou pour tricher dans la chasse au record de factorisation avec ECM. Je présente un algorithme asymptotiquement optimal, mais pratiquement trop lent pour calculer ces polynômes, ainsi qu'un algorithme asymptotiquement plus lent, mais qui a permis d'établir des records. Finalement, en utilisant une méthode due à Régis Dupont, on peut espérer concilier la théorie de la complexité et la vraie vie.

Nous présentons des résultats de sécurité obtenus sur les protocoles d'échange de clé de la famille MTI et sur MQV. La sécurité de MTI/C0 est ramenée à un problème algorithmique qui est une version "interactive" du problème Diffie-Hellman calculatoire et dont la difficulté dépend du plus petit facteur premier du cardinal du groupe utilisé, ce qui correspond à l'existence d'"attaques à petits sous-groupes" sur le protocole. MQV est quant à lui ramené à un autre problème ad-hoc, HCDH, dont nous étudierons la difficulté. Ces réductions sont effectuées dans le modèle de l'oracle aléatoire. Nous supposons également dans notre analyse de MQV que les valeurs ephémères générées lors de l'exécution du protocole sont hors de portée de l'attaquant. Nous montrons que cette hypothèse est nécessaire pour la sécurité de MQV; on la retrouve dans l'analyse par Krawczyk de la variante HMQV de MQV. Nous présentons un protocole en 4 passes proche de HMQV qui ne nécessite pas de faire cette hypothèse.

La compression est un outil prometteur pour renforcer les générateurs pseudo-aléatoires utilisés en chiffrement à flot. Ainsi, des composants de compression peuvent par exemple rendre impraticables les attaques algébriques visant des systèmes de chiffrement à flot basés sur des registres à décalage. Le Shrinking Generator ainsi que le Self-Shrinking Generator appartiennent à cette classe de composants. Plus récemment, des variations autour du Bit-Search Generator ont remis au goût du jour ces composants, et sont à la source d'une proposition de système de chiffrement à flot en réponse à l'appel du réseau d'excellence européen Ecrypt.

Nous proposons ici un modèle générique pour la compression destinée à renforcer la qualité des suites pseudo-aléatoires. En particulier, nous montrons qu'il existe une unique construction (modulo des permutations conservant la longueur) qui atteint un compromis optimal entre le débit de sortie et la sécurité obtenue contre plusieurs types d'attaques, telles que la reconstruction exhaustive et la reconstruction par obtention d'équations.

(Travail en collaboration avec Aline Gouget)

Un algorithme euclidien est une série de divisions. Son coût total d'exécution est la somme des coûts individuels apportés par chaque division. Nous considérons dans ce travail des coûts individuels d'ordre logarithmique, dépendant uniquement des quotients obtenus à chaque étape, et nous étudions les coûts additifs totaux pour deux algorithmes classiques du domaine: l'algorithme de Gauss et l'algorithme de comparaison par fractions continues de Gosper. Les algorithmes montrent des ressemblances remarquables. En particulier, leur distributions des coûts décroissent géométriquement, avec des taux ayant un rapport simple. Nous prévoyons de survoler les liens de ce travail avec l'algorithme LLL et la cryptologie.

Les fonctions booléennes symétriques sont les fonctions dont la valeur ne dépend que du poids du vecteur d'entrée. Ces fonctions peuvent être représentées plus simplement, que ce soit par leur forme algébrique normale ou leur vecteur des valeurs, que des fonctions booléennes générales --- vecteurs de taille (n+1) contre des vecteurs de taille 2^{n} en général. En outre, ces fonctions ont une complexité en nombre de portes qui est linéaire en le nombre de variables d'entrées [Muller_Preparata75]. Ces qualités en font par exemple, des candidates potentielles comme fonctions de filtrage dans un chiffrement à flot. C'est pourquoi une étude systématique des propriétés cryptographiques de ces fonctions est nécessaire. Des résultats concernant la non-linéarité maximale des fonctions booléennes symétriques sont connus [Savicky 1994, Maitra-Sarkar 2002], ainsi que des familles infinies de fonctions symétriques sans correlation et résilientes [Gopalakrishnan-Hoffman-Stinson 1993, von zur Gathen-Roche 1997, Maitra-Sarkar 2003]. L'étude que nous présentons (travaux en commun avec Anne Canteaut) se fonde sur un théorème qui établit un lien entre le degré algébrique des fonctions symétriques et la périodicité de leur vecteur des valeurs simplifié (vecteur des valeurs prises pour les différents poids des vecteurs d'entrée). Ce théorème nous a permis d'explorer de manière systématique différentes propriétés cryptographiques (non-linéarité, résilience, critère de propagation) et d'établir plusieurs nouveaux résultats pour ces fonctions. Par ailleurs, le calcul explicite du spectre de Walsh des fonctions booléennes symétriques de degré 2 et 3 a été réalisé, ainsi que la détermination de toutes les fonctions symétriques équilibrées de degré inférieur ou égal à 7, indépendamment du nombre de variables.

Le principe de la diffusion de données chiffrées est que seuls les abonnés, disposant d'un décodeur légitime, peuvent déchiffrer les données transmises par un centre. Le souci du centre est d'empêcher ses abonnés de fabriquer de nouveaux décodeurs, dits décodeurs pirates.
Nous étudions le problème du traçage de traîtres (les abonnés qui participent à la fabrication des décodeurs pirates) : « Comment le centre peut-il, à partir d'un décodeur pirate, retrouver les traîtres ? ».

Dans un premier temps, nous introduisons une nouvelle fonctionnalité au traçage de traîtres : la traçabilité publique. Grâce à cette propriété, toute personne - disposant d'une clef publique prédéfinie - peut faire du traçage de traîtres. Le centre peut donc déléguer cette tâche à plusieurs autres personnes. Nous proposons d'abord un schéma de base (à deux usagers) avec cette propriété, nous le généralisons ensuite au cas à plusieurs usagers. Utilisant des codes résistants aux coalitions, ce dernier atteint, toutefois, la traçabilité publique seulement dans la phase d'interactivité avec le décodeur pirate.

Dans un deuxième temps, nous proposons un schéma qui atteindrait pleinement la traçabilité publique. Le schéma de base de $c$ usagers est construit à partir du framework Tag-KEM/DEM. Ce schéma est ensuite généralisé par l'utilisation des codes $c$-IPP.

Travaux communs avec Hervé Chabanne et David Pointcheval (première partie) et avec Rei-Safavi Naini et Tovu Dongnien (deuxième partie)

It is well-known that RSA-based signature schemes such as FDH-RSA and PSS-RSA are as secure as RSA is hard to invert in the random oracle model. Such proofs, however, were never discovered in the standard model. This paper provides an explanation to this gap by pointing out a strong impossibility of equivalence between inverting RSA and any form of unforgeability. Apart from showing that virtually any RSA-based signature scheme separates the random oracle model from the standard model, our work leaves the real-life security of well-known signatures in a state of uncertainty. No weakness or attack on RSA can be derived from this work.

Cet exposé porte sur la sécurité du protocole d'authentification GQ2. Comme tout protocole interactif à 3 passes à divulgation nulle de connaissance, sa sécurité réside dans la vérification des 3 propriétés suivantes : completeness, soundness et zero-knowledge.
En particulier, on étudie la propriété soundness qui permet de déterminer le seuil de sécurité du protocole. On recherche les conditions suffisantes pour s'assurer que s'authentifier avec une probabilité supérieure à ce seuil de sécurité de manière non négligeable revient à connaître la factorisation du module.
Dans un premier temps, on vérifie que ce seuil est minoré par $1/2^{km}$, où $k$ est le paramètre de sécurité et $m$ le nombre de nombres de base. Ensuite, la généralisation du forking lemma permet de caractériser ce seuil par la probabilité de générer des triplets entrelacés qui dévoilent la factorisation du module. En conclusion, on définit les conditions d'optimalité de la sécurité du protocole GQ2 lorsque ce seuil est égal à $1/2^{km}$.
Application : on démontre, à partir d'un raisonnement basé sur les symboles de Legendre, que dans le cas de facteurs congrus à 3 modulo 4, le seuil de sécurité de $1/2$ est obtenu. Puis on généralise le raisonnement à des facteurs quelconques, à partir d'une représentation du graphe de la fonction carrée dans les groupes induits par les facteurs du module. Dans certains cas particuliers, validés par simulation, on constate un seuil optimal de sécurité de $1/2^b$ où $b$ est le paramètre d'adaptation.

Formal methods have been extensively applied to the certification of cryptographic protocols. However, most of these works make the perfect cryptography assumption, i.e. the hypothesis that there is no way to obtain knowledge about the plaintext pertaining to a ciphertext without knowing the key. A model that does not require the perfect cryptography assumption is the generic model and the random oracle model. These models provide non-standard computational models in which one may reason about the computational cost of breaking a cryptographic scheme. Using the machine-checked account of the Generic Model and the Random Oracle Model formalized in Coq, we prove the safety of cryptosystems that depend on a cyclic group (like ElGamal cryptosystem), against interactive generic attacks and we prove the security of blind signatures against interactive attacks. To prove the last step, we use a generic parallel attack to create a forgery signature.

Dans cet exposé, nous présenterons des arguments montrant que la résistance aux contrefaçons de certains protocoles de signature numérique fondés sur le problème du logarithme discret n'est pas équivalente à la résolution de ce problème, dans le modèle standard. Ces résultats sont en opposition avec les preuves de sécurité bien connues dans le modèle de l'oracle aléatoire ou dans le modèle générique. Nos résultats s'appliquent à de nombreux protocoles tels que ceux de Schnorr et El Gamal, DSA, ECDSA, KCDSA et même à certains protocoles basés sur RSA comme GQ.
Les réductions montrant la résistance aux contrefaçons des protocoles de signature dérivés de l'heuristique de Fiat-Shamir, dans le modèle de l'oracle aléatoire, perdent toutes un facteur de l'ordre du nombre d'appels à l'oracle q_h, dans le temps d'exécution ou la probabilité de succès. Il n'existe pas de preuve que cette perte est nécessaire, mais nous montrerons cependant que pour le protocole de Schnorr, une telle réduction doit perdre au moins un facteur de l'ordre de la racine carrée de q_h. (Travail en collaboration avec Pascal Paillier)

Dans cet exposé, je présenterai un cryptosystème asymétrique probabiliste, le système de Paillier utilisant un quotient de Z/(n^2)Z, où n est un entier RSA. Je présenterai également une variante de ce système proposée par Catalano, Gennaro et al. , permettant d'obtenir un système proche d'un RSA probabiliste, très performant, mais au prix d'une perte de structure. Ces deux systèmes ont donné lieu à de multiples développements dont un portage dans les courbes elliptiques.
J'explorerai un autre champ d'investigation pour adapter ces systèmes : celui de certains groupes quotients issus des corps quadratiques. Ces groupes n'ont été que timidement utilisés en cryptographie, cependant, ils permettent comme nous le verrons, de construire des systèmes très performants, notamment grâce à un algorithme d'exponentiation basé sur les suites de Lucas.

Lors d'un protocole de mise en accord de clé (comme Diffie-Hellman) basé sur un groupe générique G, les protagonistes aboutissent à un élément commun K_{AB} de G qui est indistinguable d'un autre élément de G mais pas d'une suite de bits aléatoire de même taille. Nous présenterons deux nouvelles méthodes pour extraire des bits de K_{AB} lorsque G est une courbe elliptique définie sur une extension quadratique d'un corps fini puis sur un corps premier.

A Eurocrypt'03, Goh et Jarecki ont montré que, contrairement aux autres schémas basé sur le logarithme discret, the schéma de signature appelé EDL avait une réduction fine, plus précisement au problème Diffie-Hellman calculatoire (CDH), dans le modèle de l'oracle aléatoire. Ces auteurs ont également remarqué qu'EDL pouvait être transformé en un schéma de signature avec précalcul, en utilisant la technique de Shamir et Tauman basée sur les fonctions de hachage caméleon.
Dans ce papier, nous proposons un nouveau schéma de signature qui possède également une réduction fine au CDH, mais dont les signatures sont plus petites que les signatures EDL. De plus, comme pour le schéma de signature de Schnorr (mais contrairement à EDL), notre schéma est naturellement efficace avec précalcul: aucune astuce supplémentaire n'est nécessaire pour pouvoir effectuer ces précalculs, et l'étape de vérification est inchangée.
Par exemple, dans le cas des courbes elliptiques, notre schéma améliore de 25% l'état de l'art des schémas basés sur le logarithme discret, avec la même sécurité. Notre proposition de schéma de signature représente actuellement la plus efficace des solutions basées sur le logarithme discret avec une réduction fine.