Séminaire de Cryptologie

La réduction de réseaux a d'importantes applications dans divers domaines aussi bien en mathématiques qu'en informatique : algèbre computationnelle, cryptologie, théorie algorithmique des nombres, communications, arithmétique des ordinateurs, etc. L'algorithme LLL permet de réduire une base quelconque d'un réseau en une 'bonne' base en temps polynomial. Cependant la qualité de la base obtenue dépend directement d'un paramètre auxiliaire : delta (le facteur 3/4 de l'algorithme original). Comme présenté par LaMacchia dans sa thèse, une technique intéressante de réduction consiste à réduire la base avec un delta petit (de manière à obtenir une réduction aussi rapide que possible), puis à augmenter la valeur de delta afin d'obtenir la qualité maximale atteignable par LLL. Je présenterai ainsi un algorithme qui améliore la qualité d'une base LLL- réduite en augmentant la valeur de delta, dont la complexité, de même exposant global que celle de l'algorithme LLL, est essentiellement indépendante de la taille binaire des coordonnées.

Les applications distribuées sont réparties entre plusieurs ressources et requièrent des mécanismes de sécurité efficaces. Bien que des protocoles d'échange de clés à base de Diffie-Hellman semblent être des mécanismes naturels pour ces applications, les solutions actuelles sont soit limitées par l'utilisation de PKI et le besoin de support sécurisé pour la clé secrète, soit par le nombre de tours nécessaires (linéaires en le nombre de participants).

Pour dépasser les limitations dues à la PKI, certains protocoles utilisent des mots de passe pour l'authentification, mais la sécurité est délicate à définir, ainsi qu'à garantir.

Dans cet exposé, on présentera les notions de sécurité souhaitées pour la cryptographie à base de mots de passe au sein de groupes, en exhibant plusieurs candidats faibles, et les attaques associées. Les évolutions successives convergeront vers un protocole basé sur le Burmester et Desmedt, qui a un nombre constant de tours et qui est prouvé sûr, sous l'hypothèse DDH.

En général, pour récupérer un élément d'une base de données, un utilisateur envoie une requête indiquant quel élément l'intéresse, puis la base lui renvoie l'élément en question. Quel élément de la base de données intéresse un utilisateur peut être une information que celui-ci souhaite garder secrète, même auprès des administrateurs de la base.

Un protocole RIP est un protocole permettant à un utilisateur d'obtenir un élément d'une base de données, sans dévoiler aucune information, même aux gestionnaires de la base, sur quel élément particulier l'intéresse, avec une quantité de données transférées sous linéaire par rapport à la taille de la base.

Je présenterai dans cet exposé un tel protocole basé sur les réseaux et proposé par Philippe Gaborit et moi même à la conférence WEWorC l'an dernier et dont une preuve de sécurité sera publiée cette année à la conférence IEEE ISIT.

Most cryptographic proofs consist of reduction arguments: given query access to a probabilistic polynomial time algorithm A which solves a certain problem P, we build another algorithm B which solves another problem P' which is widely believed to be hard. Often, one of the main difficulties of the proof lies in dealing with the errors of A, an algorithm of which typically we only know the probability of its being correct on uniformly sampled elements. Sometimes, a solution is to query the oracle on independent pairs of points, instead of making completely independent queries.

In this seminar we will study in which cases the probability that the two answers of the algorithm A are correct exceeds the trivial lower bound and discuss some applications.

This is joint work with Paz Morillo.

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.

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).

Dans cet exposé, nous présentons une nouvelle attaque par corrélation sur le modèle de chiffrement classique de LFSRs combinés par une fonction booléenne. Nous commencerons par décrire cette attaque dans un cadre un peu plus général avant de voir précisement comment utiliser la structure des LFSRs à chaque étapes afin d'obtenir une méthode efficace.

The Naccache-Stern (NS) knapsack cryptosystem is a little-known public-key encryption scheme, despite (or because of) its original design. In this scheme, the ciphertext is obtained by multiplying the public-keys indexed by the message bits modulo a prime p. The cleartext is then recovered by factoring the ciphertext raised to a secret power modulo p.

NS encryption requires a multiplication per two plaintext bits on the average, while decryption is roughly as costly as an RSA decryption. However, NS features a bandwidth sublinear in log(p), namely log(p)/log(log(p)).

This presentation presents new NS variants allowing to reach bandwidths linear in log(p). The price to pay for reaching a linear bandwidth is a public-key of size log3(p)/log(log(p)). Beyond their mathematical interest, these modifications can possibly make the NS knapsack cryptosystem more practical and attractive.

The presentation will be held in French, and will be self-included as much as possible. This is a joint work with David Naccache (U. Paris II, ENS) and Jacques Stern (ENS).

In 1998, Blaze, Bleumer and Strauss proposed a cryptographic primitive called proxy re-encryption, in which a proxy transforms -- without seeing the corresponding plaintext -- a ciphertext computed under Alice's public key into one that can be opened using Bob's secret key. Recently, an appropriate definition of chosen-ciphertext security and a construction fitting this model were put forth by Canetti and Hohenberger. Their system is bidirectional: the information released to divert ciphertexts from Alice to Bob can also be used to translate ciphertexts in the opposite direction. In this work, we present the first construction of unidirectional proxy re-encryption scheme with chosen-ciphertext security in the standard model (i.e. without relying on the random oracle idealization). Our construction is efficient and requires a reasonable complexity assumption in bilinear map groups. Like the Canetti-Hohenberger scheme, it ensures security according to a relaxed definition of chosen-ciphertext security introduced by Canetti, Krawczyk and Nielsen.

(joint work with D. Vergnaud)

We propose to cryptanalysis a McEliece cryptosystem that is based on the use of Quasi-Cyclic Low Density Parity Check codes. We show a structural attack by exploiting some weakness in the particular choice of the linear transformations that mask the generator matrix of the code. This cryptanalysis adopts a polynomial-oriented approach and consists in searching for two polynomials of low weight such that their product is a public polynomial. Our analysis shows that with high probability a parity check matrix of the secret code can be recovered with time complexity $O\left( n^3 \right)$ where $n$ is the length of the considered code. An implementation of the attack extracts the secret key in about $140$ seconds on a PC.

Joint work with Jean-Pierre Tillich and Léonard Dallot

Le chaos est un phénomène observé depuis longtemps, mais étudié seulement depuis les années 1960. Depuis la découverte par Edward Lorenz du fameux « effet papillon », les systèmes chaotiques et autres attracteurs étranges n'en finissent pas de fasciner. On découvre que le chaos est présent partout : en biologie, en physique, en optique...

En 1990 il a été démontré que deux systèmes chaotiques ont, sous certaines conditions, la capacité de se synchroniser. Ce problème a ensuite été étendu à un problème classique en automatique, à savoir la synthèse d'observateurs non linéaires. Ces travaux ont ouvert la voie à de nombreuses applications, parmi lesquelles l'utilisation du chaos pour élaborer de nouvelles techniques de chiffrement. Les systèmes chaotiques, bien que parfaitement déterministes, génèrent des trajectoires qui ressemblent à du bruit. Cet aspect aléatoire permet de cacher une information dans un signal chaotique. La propriété de synchronisation est essentielle, c'est elle qui permet le déchiffrement. Dans mon exposé, je présenterai les différentes étapes de la conception d'un cryptosystème reposant sur la modulation de la phase d'un système hyperchaotique.

Il existe aujourd'hui des algorithmes de factorisation de polynômes dont la complexité est polynômiale en le degré et la taille des coefficients du polynôme à factoriser. Dans le cas où celui-ci est lacunaire (i.e. possède peu de coefficients non nuls), ces algorithmes ne sont plus efficaces en raison de la grande taille éventuelle du degré du polynôme. On s'est alors demandé s'il était possible de déterminer les racines rationelles d'un tel polynôme. Nous décrirons dans cet exposé l'algorithme donné en 1999 par H.W. Lenstra qui a fait l'objet de mon mémoire de Master II. Celui-ci permet de déterminer les racines rationelles et même les facteurs de petit degré d'un polynôme lacunaire à coefficients dans un corps de nombre.

En 1996, Coppersmith introduit deux techniques basées sur la réduction de réseaux permettant de retrouver de petites racines d'équations polynomiales. Une de ces techiques s'applique au cas d'équations modulaires en une variable, l'autre concerne les équations entières à deux variables. Depuis, ces méthodes ont été utilisées dans de nombreuses applications cryptographiques. Pour certaines de ces applications, qui font intervenir plus de deux variables, des extensions des méthodes de Coppersmith ont été proposées. Malheureusement, ces méthodes sont heuristiques et ne permettent pas toujours de retrouver les racines recherchées quand le nombre de variables est supérieur à deux.

Dans cette présentation, nous proposons une nouvelle variante de l'algorithme de Coppersmith dans le cas d'équations entières faisant intervenir trois variables et nous étudions son applicabilité. Nous nous intéressons notamment à des attaques sur RSA dans le cas d'exposants petits. Cette méthode utilise non seulement la réduction de réseaux mais également le calcul de bases de Gröbner. En principe, elle peut être généralisée dans le cas de quatre variables ou plus.

La sécurité prouvée (ou sécurité réductioniste) a été introduite en 1984 par S. Goldwasser et S. Micali. La sécurité d'un protocole cryptographique repose sur la difficulté de résoudre un ou plusieurs problèmes algorithmiques. Dans cette approche, la sécurité du schéma est alors prouvée en utilisant un adversaire potentiel pour résoudre le ou les problèmes sous-jacents. Si ce problème est reconnu comme calculatoirement difficile, il s'ensuit que l'existence d'un tel adversaire est impossible. Les travaux de M. Bellare et P. Rogaway ont mis en évidence l'importance de la qualité de cette réduction pour une utilisation pratique des schémas ainsi prouvés.

N. Courtois, M. Finiasz & N. Sendrier ont proposé en 2001 le premier schéma de signature basé sur la théorie des codes. Il est basé sur le schéma de chiffrement proposé par H. Niederreiter en 1986 utilisant les codes de Goppa. Sa sécurité repose sur deux hypothèses algorithmiques : la difficulté du décodage borné paramétré pour les codes de Goppa (Goppa Parametrized Bounded Decoding ou GPBD) et l'indistinguabilité des codes de Goppa (Goppa Code Distinguishing ou GD).

Dans cet exposé, nous présenterons une légère modification du schéma original nous permettant d'établir une preuve de sécurité dans le modèle de l'oracle aléatoire et d'obtenir une évaluation de la qualité de la réduction. Cette preuve couvre à la fois la résistance du schéma à une attaque par décodage (usuellement liée à la difficulté du décodage borné) et à une attaque par recouvrement de la clef secrète (liée à l'indistinguabilité des codes de Goppa).

We show that computing $e$-th roots modulo $n$ is easier than factoring $n$ with currently known methods, given subexponential access to an oracle outputting the roots of numbers of the form $x_i + c$.

Here $c$ is fixed and $x_i$ denotes small integers of the attacker's choosing.

Several variants of the attack are presented, with varying assumptions on the oracle, and goals ranging from selective to universal forgeries. The computational complexity of the attack is $L_n(\frac{1}{3}, \sqrt[3]{\frac{32}{9}})$ in most significant situations, which matches the {\sl special} number field sieve's ({\sc snfs}) complexity.

This sheds additional light on {\sc rsa}'s malleability in general and on {\sc rsa}'s resistance to affine forgeries in particular -- a problem known to be polynomial for $x_i > \sqrt[3]{n}$, but for which no algorithm faster than factoring was known before this work.

Nous présentons une méthode générique (et efficace !) pour construire, à partir d'une PRP (permutation pseudo-aléatoire) définie sur {0,1}^n, de nouveaux modes opératoires de chiffrement permettant d'aller au delà du seuil du paradoxe des anniversaires (i.e. chiffrer plus de 2^(n/2) messages. Ce résultat a été présenté à la conférence SAC 2007 cet été.

Cette construction est principalement une nouvelle contribution au problème consistant à transformer une PRP en PRF (fonction pseudo-aléatoire). Nous verrons que cette solution repose sur l'utilisation d'une matrice génératrice d'un code binaire de distance minimale d. La sécurité de la PRF obtenue est alors de l'ordre de 2^(dn/(d+1)). En utilisant cette PRF dans un pseudo-mode compteur, nous verrons qu'il est alors possible d'obtenir un mode de chiffrement avec une sécurité de l'ordre de 2^(dn/(d+1)) (supérieure à 2^(n/2) pour tout d>1). Nous verrons également que cette méthode générique permet de généraliser le mode compteur, l'algorithme CENC présenté à FSE 2006, et une construction de PRF présentée à Eurocrypt 2000. Nous présenterons enfin une application numérique basée sur l'utilisation d'un code de distance minimale 4 (qui permet donc de chiffrer autour de 2^(4n/5) messages) avec un surplus calculatoire de l'ordre 4% par rapport à un simple mode compteur.

SFLASH est un schéma de signature appartenant à la famille des schémas dits quadratiques multivariés. Il est basé sur un design introduit par Patarin, Goubin et Courtois en 1998, et est recommandé par le Consortium Européen NESSIE depuis 2003. Dans cet exposé, nous présenterons une nouvelle approche cryptanalytique permettant d'attaquer le design général proposé par Patarin, Goubin et Courtois. Cette approche repose sur de simples considérations d'algèbre linéaire et fonctionne très efficacement sur un vaste choix de paramètres, permettant de forger des signatures SFLASH en 3 minutes environ pour les paramètres recommandés.

Les questions d'anonymat surgissent à de nombreuses occasions, dans le contexte d'Internet et plus particulièrement celui des transactions électroniques. Il est souvent souhaitable de protéger l'identité des participants afin d'éviter la constitution de bases de données de renseignements commerciaux, ou l'établissement de profils de consommateurs. De nombreuses solutions cryptographiques ont été apportées afin de renforcer la confiance des utilisateurs dans ces transactions. Une nouvelle approche dans l'élaboration de mécanismes d'anonymat sûrs et performants consiste à s'appuyer sur des applications bilinéaires (couplages de Weil et de Tate sur les courbes elliptiques).

Dans cette thèse, nous présentons tout d'abord un état de l'art des différentes signatures utilisées pour l'anonymat en cryptographie, en particulier les signatures de groupe, les signatures aveugles et les signatures d'anneau. À l'issue de cette présentation, nous décrivons un nouveau protocole d'authentification et montrons comment il peut être converti en signature d'anneau. Notre étude porte ensuite sur les signatures aveugles à anonymat révocable. Il s'agit de signatures aveugles dont l'anonymat et l'intraçabilité peuvent être révoqués par une autorité. Nous proposons le premier véritable modèle de sécurité pour de telles signatures, ainsi qu'une nouvelle construction basée sur les couplages dont nous prouvons la sécurité dans ce modèle. Nos derniers travaux portent sur les systèmes de multi-coupons et de monnaie électroniques. L'utilisation des couplages nous permet d'introduire de nouvelles propriétés destinées à faciliter leur usage. Pour chacun de ces systèmes nous proposons un modèle de sécurité, puis décrivons un schéma dont nous prouvons la sécurité dans ce modèle.

Nous présentons deux attaques du type « key-recovery » dans le cadre de la nouvelle proposition de B. M. Gammel, R. Gottfert, et O. Kniffler (SASC07). Dans cette proposition, la suite chiffrante produite avec le même couple (clé, valeur initiale) est limitée à 2^52 bits pour Achterbah-80 (respectivement à 2^56 pour Achterbahn-128). Notre attaque a une complexité de 2^64.85 (respectivement 2^104) et nécessite moins de 2^52 bits (respectivement moins de 2^56 bits) de suite chiffrante pour Achterbahn-80 (respectivement pour Achterbahn-128). Ces attaques sont basées sur les attaques précédentes, donc sur des attaques par corrélation qui utilisent la décimation et un algorithme pour réduire la complexité en temps de la recherche exhaustive, qui profit de l'indépendance des registres. De plus, s'agissant d'Achterbahn-80 nous proposons une méthode originale qui nous permet de réduire la longueur de suite chiffrante nécessaire.

(travail commun avec P. Gaudry)

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.

Since 1985 and their introduction by Goldwasser, Micali and Rackoff, followed in 1988 by Feige, Fiat and Shamir, zero-knowledge proofs of knowledge have become a central tool in modern cryptography. Many articles use them as building blocks to construct more complex protocols, for which security is often hard to prove. The aim of this paper is to simplify analysis of many of these protocols, by providing the cryptographers with a theorem which will save them from stating explicit security proofs. Kiayias, Tsiounis and Yung made a first step in this direction at Eurocrypt'04, but they only addressed the case of so-called "triangular set of discrete-log relations". By generalizing their result to any set of discrete-log relations, we greatly extend the range of protocols it can be applied to.