Mardi 3 octobre 2006 : Guilhem Castagnos
Soutenance de thèse : Quelques schémas de cryptographie asymétrique probabiliste

Dans cette thèse, on construit de manière générique plusieurs familles de fonctions trappe probabilistes : une famille de fonctions trappe homomorphiques généralisant, entre autres, le cryptosystème de Paillier, et deux autres familles de fonctions trappe, à partir de fonctions trappe déterministes.

Pour utiliser ces fonctions trappe, on étudie plusieurs groupes finis : les quotients de Z, les courbes elliptiques définies sur Z/nZ, où n est un entier impair, pour lesquelles on donne un système complet de formules d'additions, et un autre groupe fini peu utilisé en cryptographie, celui des éléments de norme 1 d'un corps quadratique modulo n.

On expose plusieurs cryptosystèmes avec une analyse de leur sécurité et de leur complexité, en utilisant les familles de fonctions trappe dans ces groupes. Dans les quotients de Z et dans les courbes elliptiques, on retrouve de nombreux cryptosystèmes décrits ces dernières années. Dans les quotients de corps quadratiques, on propose plusieurs nouveaux systèmes probabilistes très performants.

Mardi 10 octobre 2006 : Thierry Berger (DMI – XLIM)
Comment diminuer la taille et masquer la structure des codes utilisés dans les cryptosystèmes à clé publique fondés sur les codes

Les codes utilisés dans les cryptosystèmes doivent être résistants à 2 types d'attaques : les attaques structurelles qui consistent à retrouver la structure algébrique masquée permettant leur décodage et les attaques de type décodage de codes aléatoires. Dans cet exposé, nous allons présenter quelques méthodes pour construire des codes résistants à ces attaques tout en essayant de minimiser la taille de la clé publique correspondante.

Mardi 14 novembre 2006 : Raphael Overbeck (Technische Universität Darmstadt)
Attaquer des cryptosystèmes de type GPT

Nous présentons une cryptanalyse de la version Gabidulin du cryptosystème à clé publique de McEliece (GPT) qui a été présentée en 1991 à Eurocrypt. Les attaques précédentes qui ont été proposées pour des cryptosystèmes de type GPT n'arrivent pas à casser toutes les variantes proposées. Résultat : il semble que l'on puisse utiliser des clés publiques moins longues pour certains d'entre eux que pour le système McEliece.

Néanmoins, nous sommes capables d'utiliser la structure des codes pour développer une attaque en temps cubique qui peut être utilisée pour toutes les variantes proposées. En conséquence, nous allons démontrer que les codes de Gabidulin ne peuvent pas être utilisés pour des applications cryptographiques.

Mardi 12 décembre 2006 : Olivier Orciere
Utilisation des groupes de classes en cryptographie

Suite aux travaux de Bhargava sur la généralisation de la loi de Gauss sur le groupes de classes des formes quadratiques binaires, on présentera les quatre formalismes des formes quadratiques binaires utilisés et connus jusqu'à présent :

On montrera que ces quatre formalismes sont tous équivalents. On présentera quelques conséquences des travaux de Bhargava du point de vue cryptologique. En particulier on présente de nouvelles formules de la loi de Gauss grâce à la représentation de Bhargava.

On conclura en présentant une « nouvelle » loi de groupe sur les classes de formes cubiques binaires qui découle directement du formalisme de Bhargava.

Mardi 16 janvier 2007 : David Galindo
On the Generic Construction of Identity-Based Signatures with Additional Properties

In a work recently appeared at Asiacrypt'06, we show how identity-based signature schemes with some additional properties can be securely constructed, starting from a standard (PKI-based) digital signature scheme and a PKI-based signature scheme with the same property. In this talk we will explain the simple idea behind these generic constructions, and we will list which additional properties can be achieved in this way. In particular, our work implies the existence of identity-based signatures with additional properties that are provably secure in the standard model, do not need bilinear pairings, or can be based on general assumptions. Then we will consider in more detail the case of blind signatures: we will give the basic definitions, the construction, and a sketch of the security proofs.

Joint work with Javier Herranz and Eike Kiltz.

Mardi 23 janvier 2007 : Roger Oyono
Addition rapide sur les Jacobiennes des courbes non hyperelliptiques de genre 3

Dans cet exposé je présenterai un algorithme de calcul efficace de la loi de groupe sur les Jacobiennes des courbes de genre 3 non hyperelliptiques. Cet algorithme admet non seulement une interprétation géométrique similaire à celle du « corde-tangente » sur les courbes elliptiques, mais elle admet aussi une implantation optimisée (formules explicites).

Mardi 13 février 2007 : Andrea Röck
Entropy Approximation for FCSRs
Mardi 20 février 2007 : Jean Creignou
Programmation linéaire & codes sphériques

L'exposé sera une introduction à la méthode de la programmation linéaire en prenant le cas particulier des codes sphériques. Les principes généraux et les méthodes seront illustrés sur cet exemple (en évitant autant que possible la théorie des représentations). Si le temps le permet seront abordés : la généralisation aux autres codes, les précisions et la dualité.

Mardi 6 mars 2007 : Gregor Leander
On the Equivalence of RSA and Factoring Regarding Generic Ring Algorithms

To prove or disprove the computational equivalence of solving the RSA problem and factoring integers is a longstanding open problem in cryptography. This paper provides some evidence towards the validity of this equivalence. We show that any efficient generic ring algorithm which solves the (flexible) low-exponent RSA problem can be converted into an efficient factoring algorithm. Thus, the low-exponent RSA problem is intractable w.r.t. generic ring algorithms provided that factoring is hard.

Mardi 20 mars 2007 : Benoît Chevallier-Mames
A Practical and Tightly Secure Signature Scheme Without Hash Function

In 1999, two signature schemes based on the flexible RSA problem (a.k.a. strong RSA problem) were independently introduced: the Gennaro-Halevi-Rabin (GHR) signature scheme and the Cramer-Shoup (CS) signature scheme. Remarkably, these schemes meet the highest security notion in the standard model. They however differ in their implementation. The CS scheme and its subsequent variants and extensions proposed so far feature a loose security reduction, which, in turn, implies larger security parameters. The security of the GHR scheme and of its twinning-based variant are shown to be tightly based on the flexible RSA problem but additionally (i) either assumes the existence of division-intractable hash functions, or (ii) requires an injective mapping into the prime numbers in both the signing and verification algorithms.

In this paper, we revisit the GHR signature scheme and completely remove the extra assumption made on the hash functions without relying on injective prime mappings. As a result, we obtain a practical signature scheme (and an on-line/off-line variant thereof) whose security is solely and tightly related to the strong RSA assumption.

This is a joint work with Marc Joye (Thomson R&D), which has been published at CT-RSA 07.

Mardi 27 mars 2007 : Émeline Hufschmitt
Les signatures aveugles révocables revisitées

Les signatures aveugles, introduites en 1982 par Chaum, sont très largement utilisées en cryptographie, notamment dans des schémas de vote ou de paiement électronique. Ces signatures permettent à un utilisateur d'obtenir une signature d'un signataire sans que celui-ci ait connaissance du message qu'il signe. Une fois la signature émise, il est impossible pour quiconque de tracer une signature ou un utilisateur. Dans certaines applications (comme le paiement ou les enchères en ligne) il est nécessaire de garder cette propriété de blindness, mais aussi de permettre à une autorité de révocation de lever l'anonymat en cas de fraude ou d'abus. C'est dans ce but que les fair blind signatures ont été introduites par Stadler et al. en 1995. Ces schémas comportent une autorité et un juge capables de tracer un utilisateur à partir de sa signature mais aussi de retrouver une signature à partir d'une vue du protocole de signature, tout en apportant la preuve que leur révocation est correcte. De nombreux schémas ont été proposés depuis, mais aucun n'est à la fois efficace et sûr. De plus, le modèle de sécurité proposé par Abe et Ohkubo en 2001 ne couvre pas toutes les propriétés voulues et certaines définitions sont incomplètes.

Dans cet exposé, nous verrons tout d'abord une faille dans la construction de la plupart des schémas de signatures aveugles. Nous présenterons ensuite un nouveau modèle de sécurité pour les fair blind signatures ainsi qu'un nouveau schéma reposant sur les applications bilinéaires. La sécurité de ce schéma sera étudiée dans ce nouveau modèle.

Mardi 10 avril 2007 : Pierre-Louis Cayrel
Nouveaux résultats autour de la signature avec des codes

Après avoir décrit les principaux systèmes de signature basés sur les codes, je propose deux variations autour de ces schémas : un nouveau schéma d'identification (et de signature) basé sur l'identité et un schéma de one time signature.

Le schéma d'identification est le premier schéma basé sur l'identité n'utilisant pas de problème lié à la théorie des nombres. Il combine deux schémas basés sur les codes bien connus : le schéma de Courtois, Finiasz et Sendrier et le schéma d'authentification sans divulgation de connaissance de Stern (qui peut aussi être utilisé en signature). Il peut aussi fonctionner en signature mais donne des signatures de grande taille (1Mo).

En ce qui concerne le schéma de one time signature je présente une analyse de sécurité ainsi qu'une réduction de la taille des paramètres.

Mardi 29 mai 2007 : Aka Bilé Frédéric Edoukou
Distribution des poids des codes hermitiens en dimension supérieure

En 1985 R. Tobias thésard de I. Chakravati à l'UNC-CH en Caroline du Nord présenta l'étude des codes construits sur des surfaces hermitiennes sur le corps fini à quatre éléments grâce à un traitement à l'ordinateur. Son travail fut achévé en 1986 par P. Spurr à l'UNC-CH qui par un traitement informatique détermina la distance minimale ainsi que la distribution des poids ce code.

En 1991 Sørensen dans sa thèse de doctorat à Århus en s'affranchissant de l'outil informatique, donna une approche plus générale et plus géométrique de l'étude ce code construit sur la surface hermitienne. Il formula une conjecture sur sa distance minimale qui suscita plusieurs tentatives de résolutions quelques années plus tard.

Dans cet exposé nous allons répondre à cette conjecture. En utilisant des résultats de géométrie finie nous donnerons la distribution des poids et proposerons une généralisation de nos résultats aux codes hermitiens en dimension supérieure.

Mardi 5 juin 2007 : Vivien Dubois
Cryptanalyse du schéma de signature SFLASH

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.

Mardi 19 juin 2007 : Christophe Clavier
Attaques par analyse de canaux cachés et de fautes. Application aux algorithmes à spécifications

Les attaques par analyse de canaux cachés (analyse de temps, de consommation de courant,…) sont apparues il y a une dizaine d'années environ. Elles peuvent menacer la sécurité des cartes à puces en permettant par exemple la révélation de clés cryptographiques bien plus efficacement que ne le permet la cryptanalyse classique. Nous introduirons ces attaques et en donnerons quelques exemples classiques. Nous étudierons ensuite la possibilité de les appliquer au cas où la fonction cryptographique attaquée est partiellement inconnue. Dans ce contexte, nous exhiberons des possibilités de retrouver malgré tout la clé utilisée, et/ou d'obtenir par retro-conception de l'information nouvelle sur la spécification de l'algorithme.