Séminaire de Cryptologie

In some situations, a user wants to sign a message in such a way that only a designated verifier is convinced of the validity of the signature, whereas other users cannot distinguish whether the signer has signed this message at all. In some cases, the signer may want to preserve this level of privacy forever, which means that the initial verifier should not be able to convince anyone else of the fact that the signer signed the message. In some other cases, the signer may want to give the initial verifier the possibility to transfer his conviction to someone else (maybe to everybody), when/if desired.

In this paper we review this notion of private signatures, focusing on the level of transferability desired by the signer. We first consider the two extreme cases (non-transferability and complete transferability) which can be generically and efficiently solved by using very basic cryptographic primitives, as we show in this paper. Then we consider a case with partial transferability, for which we propose a generic solution based on the primitive of distributed ring signatures.

Un grand nombre des cryptosystèmes à base de codes proposés à ce jour réduisent leur sécurité au problème de Syndrome Decoding : le problème du décodage dans un code aléatoire. En plus d'être NP-complet se problème présente un avantage net par rapport à beaucoup d'autres problèmes : il a été étudié en détails pour la théorie des codes et les meilleurs algorithmes pour le résoudre sont bien identifiés. En pratique, deux familles d'algorithmes existent : les algorithmes basés sur Information Set Decoding et ceux basés sur le Generalized Birthday Algorithm.

Cependant, calculer les complexités exactes de ces algorithmes n'est pas toujours chose simple. Dans cet exposé nous proposons de donner des bornes inférieurs, simples à calculer, pour la sécurité des problèmes du type Syndrome Decoding. Le but principal de ces bornes est de simplifier le choix des paramètres lors de la conception de nouveaux algorithmes cryptographiques à base de codes. Au passage, nous en profitons pour recenser certaines variantes d'attaque récentes adaptées à certains problèmes particuliers.

(Travail commun avec L. Chaussade et F. Ulmer)

En utilisant les propriétés de l'anneau non commutatif des polynômes tordus, on est en mesure de construire des codes correcteurs de la même manière que l'on construit les codes cycliques en utilisant la famille des polynômes classiques. Dans cet exposé, nous montrerons comment construire des codes de distance minimale prescrite ou bien de distance rang minimale prescrite à partir de cet anneau non-commutatif. On montrera également comment ont été trouvés des codes ayant une bonne distance de Hamming minimale.

Dans cette exposé, un nouveau algorithme de chiffrement à clé publique et de nouveaux schémas de signatures sont proposés. Ces derniers apparaissent comme étant une modification des variantes des cryptosystèmes "à la El Gamal" déjà connus. Pour ces cryptosystèmes, il est possible de ne pas publier le générateur utilisé directement ainsi que son ordre. Comme El Gamal, le chiffrement est basé sur le problème de décision de Diffie-Hellman. Ces nouveaux cryptosystèmes ont à peu près la même efficience que ceux d'El Gamal à part l'algorithme de génération de clés qui lui est moins efficient.

(joint work with Jonathan Katz and Eric Levieil and David Naccache)

In classical t-out-of-n secret sharing, a "dealer" distributes shares of a secret among n parties so that any group of at least t parties can reconstruct the secret, whereas any group of size less than t has no information about the secret.

This implicitly assumes that parties are either honest or corrupt. A game-theoretic approach is to assume that instead parties are "rational" in that they act in their own interest. Since in this scenario standard secret-sharing schemes completely fail, starting with Halpern and Teague in 2004, a series of works focused on designing protocols so that it is rational to follow them.

We propose a new methodology for rational secret sharing leading to various instantiations that are simple and efficient in terms of computation, share size, and round complexity. Our protocols do not require physical assumptions or simultaneous channels, and can even be run over asynchronous, point-to-point networks.

Alors que les cryptosystèmes à clé publique les plus utilisés reposent sur la difficulté de la factorisation ou du logarithme discret, il est intéressant d'étudier d'autres alternatives reposant sur des problèmes plus difficiles, et potentiellement résistants aux ordinateurs quantiques. La sécurité de certains cryptosystèmes, comme NTRU, LWE ou GPV reposent sur des problèmes issus de la géométrie des nombres, et notamment les problèmes de plus court vecteur ou de plus proche vecteur dans des réseaux euclidiens.

Malgré les preuves de NP-difficulté et les réductions du pire-cas au cas moyen, qui ne sont valables que pour des réseaux gigantesques, il est possible d'obtenir de très bonnes approximations aux problèmes de réduction de réseau en pratique. Dans cet exposé, nous étudions ces algorithmes qui permettent de réduction de réseau qui fonctionnent en temps polynomial, ou plus généralement en temps raisonnable. Nous analysons le fonctionnement de ces algorithmes d'un point de vue théorique, en montrant notamment que pour l'instant, tous les algorithmes efficaces découlent de la même construction, alliant de coûteuses recherches exhaustives en dimension fixée avec une mesure de qualité globale pour limiter leur nombre. Nous expliquerons la construction du meilleur algorithme prouvé, au sens de sa complexité et de la qualité de son résultat, ainsi que ses limites théoriques et pratiques.

Les chiffrements homomorphes peuvent servir de primitive pour réaliser des protocoles "PIR" (Private Information Retrieval). Ces protocoles permettent à un utilisateur de télécharger un élément d'une base de données sans révéler à la base quel est l'élément en question.

Une problématique voisine du PIR est le "Private Searching", permettant de filtrer dans un flux de documents ceux correspondant à un ensemble de mots-clefs, tout en gardant les mots-clefs secrets (sous la forme d'une requête PIR) même auprès d'un attaquant analysant le programme de filtrage.

Je montrerai comment utiliser le protocole PIR à base de réseaux proposé par Philippe Gaborit et Carlos Aguilar à WEWorC 2007 pour obtenir un protocole de Private Searching. En adaptant le logiciel développé par Bethencourt et al, des meilleures performances en terme de temps de calcul et taille des requêtes sont attendus.

Algebraic cryptanalysis can be described as a general framework that permits to asses the security of a wide range of cryptographic schemes. The recent proposal and development of algebraic cryptanalysis is now widely considered an important breakthrough in the analysis of cryptographic primitives. It is a powerful technique that applies potentially to a wide range of cryptosystems.

The basic principle of such cryptanalysis is to model a cryptographic primitive by a set of algebraic equations. The system of equations is constructed in such a way as to have a correspondence between the solutions of this system, and a secret information of the cryptographic primitive (for instance, the secret key of a block cipher).

The most efficient method for solving algebraic equations over a finite field is to compute a Gröbner basis. In the first part of this talk, we will give the definition/properties of such bases, and briefly recall the principle of efficient algorithms, i.e. F4/F4, for computing these bases.

In the second part of the talk, we will present two applications of algebraic cryptanalysis. The first application is an attack of MinRank (MR) which is an important problem in multivariate cryptography (joint work with F. Levy-dit-Vehel and J.-C. Faugère). The starting point is the Kipnis-Shamir attack. The second application is the algebraic cryptanalysis of the Flurry and Curry block ciphers (joint work with J.-C. Faugère). We will present a new approach which is based on the use of several well chosen correlated message/ciphertext pairs. This has permitted to establish an interesting connection between algebraic attacks and high order differential cryptanalysis.

Since the very beginnings of cryptography many centuries ago, key management has been one of the main challenges in cryptographic research. In case of a group of players wanting to share a common key, many schemes exist in the literature, managing groups where all players are equal or proposing solutions where the group is structured as a hierarchy. This paper presents the ¯rst key management scheme suitable for a hierarchy where no central authority is needed and permitting to manage a graph representing the hierarchical group with possibly several roots. This is achieved by using symmetric cryptography (namely a MAC scheme) and a non- hierarchical group key agreement scheme in an intricate manner and introducing the notion of virtual node.

In this talk we will present symbolic (in the sense of Dolev and Yao) models and techniques for proving whether a password-based protocol resists against (offline) guessing attacks.

We model protocols using a language close to the applied pi calculus. Resistance against guessing attacks is modeled using static equivalence, a formal indistinguishability relation on sequences of terms. We will present compositionality results: if two password protocols do separately resist against guessing attacks, does their parallel composition resist against guessing attacks (even when the same password is used)? If time permits we will also shortly present methods for automatically deciding resistance against guessing attacks.

Les schémas de Feistel ont été conçus pour construire des permutations de [1,2^(2n)], à partir d'applications (fonctions internes) de [1,2^n]. On s'intéresse ici aux attaques génériques sur les schémas de Feistel, dans le cas où les fonctions internes sont des permutations, au lieu de fonctions. Les attaques sont génériques dans le sens où les permutations internes sont supposées aléatoires. Malgré l'utilisation de tels schémas dans la conception d'algorithmes à clé secrète (ex: Twofish, Camelia, DEAL), ils n'ont pas été le sujet de nombreuses études. Nous allons voir que leur comportement est souvent différent de celui des schémas de Feistel classiques (avec fonctions internes). Plus précisément, nous allons voir que les attaques sont souvent moins efficaces, par exemple sur 3, 6 ou 9 tours de schémas de Feistel. Pour une taille d'entrée de 2n bits, les attaques trouvées nécessitent strictement moins de 2^(2n) messages quand le nombre de tours est inférieur ou égal à 5. Pour un nombre de tours plus grand, des attaques permettant de distinguer un générateur de permutations de Feistel (avec permutations internes) d'un générateur de permutations aléatoires seront également exposées.

Les fonctions éponges sont un nouveau type de primitives cryptographiques introduites par Bertoni et al. et utilisées pour la construction de fonctions de hachage. Elles représentent une solution de remplacement intéressante à l'algorithme d'extension de domaine classique de Merkle-Damgard et leur sécurité fut récemment prouvée dans le modèle de l'indifférentiabilité en supposant la fonction interne comme idéale.

Nous étudierons dans cet exposé la cryptanalyse d'une généralisation des fonctions éponges, tout d'abord d'un point de vue assez général avec les attaques par glissement. Ensuite, nous traiterons deux cas particuliers avec l'analyse de sécurité de Grindahl et de RadioGatun, deux fonctions de hachage récemment publiées et appartenant à la famille des fonctions éponges généralisées.

Travail commun avec David Naccache et Jean-Jacques Quisquater

Multiset hash functions are functions that map multisets (or sets) of arbitrary finite size to strings of fixed length. In this talk, I will introduce a new multiset hash function based on RSA. Its collision resistance is proven under the assumption that deterministic-padding RSA signatures cannot be forged.

Les cryptosystèmes classiques utilisant des codes correcteurs sont pénalisés par la taille importante de leur clé publique. Les codes géométriques semblaient résoudre ce problème. Cependant, on est en mesure de conduire des attaques structurelles efficaces contre de tels codes. Les mécanismes de ces attaques seront exposés ici.

En cryptographie symétrique, de nombreuses attaques sur les chiffrements par bloc peuvent être regroupées au sein d'une même famille : les attaques statistiques. Citons par exemple les cryptanalyses linéaires et différentielles pour les plus connues.

Le cryptanalyste a possibilité de chiffrer (voire déchiffrer) un certains nombre de messages (de façon adaptative ou non) avec une boîte noire. Celle-ci est un chiffrement donné utilisant une certaine clef que le cryptanalyste souhaite retrouver. De l'observation de certains phénomènes dans les échantillons disponibles (messages), on peut tirer de l'information sur la clef afin de restreindre l'espace de recherche.

Le but de cet exposé est de montrer l'importance de la quantification de ces informations pour l'estimation de la complexité d'une attaque ainsi que de donner un aperçu des méthodes utilisées pour estimer cette information après avoir, dans un premier temps, expliqué le fonctionnement des cryptanalyses statistiques.

We describe the use of explicit isogenies to translate instances of the Discrete Logarithm Problem from Jacobians of hyperelliptic genus 3 curves to non-hyperelliptic Jacobians, where they are vulnerable to faster index calculus algorithms. We give explicit formulae for $(2,2,2)$-isogenies for any hyperelliptic curve defined over a finite field of characteristic $p > 3$. Subject to reasonable assumptions, we show that we can construct such an isogeny over the ground field for at least 18.57\% of all hyperelliptic genus 3 curves over a given finite field.