Conference in honour of the 25th birthday of the LLL algorithm.

This paper presents an off-line divisible e-cash scheme where a user can withdraw a divisible coin of monetary value 2^L that he can parceled and spend anonymously and unlinkably. Divisible e-cash allows to withdraw or spend several coins more efficiently than repeating several times a single withdrawal or spending protocol. We present the construction of a security tag that allows to protect the anonymity of honest users and to revoke anonymity only in case of cheat for protocols based on a binary tree structure without using a trusted third party. The paper presents the first divisible e-cash scheme that provides both full unlinkability and anonymity without requiring a trusted third party.

Joint work with A. Gouget

Un sytème de chiffrement broadcast (broadcast encryption) permet à un diffuseur de chiffrer des messages destinés à un ensemble quelconque d'utilisateurs (parmis l'ensemble des utilisateurs du système). Dans un tel système, tout utilisateur appartenant à l'ensemble visé doit pouvoir déchiffrer les messages, et aucune coalition d'utilisateurs non visés ne doit aboutir au déchiffrement des messages. De nombreux schémas de chiffrement broadcast sont apparus depuis 1993 (article de Fiat et Naor). Dans cet exposé, nous verrons de quoi est constitué un système de chiffrement broadcast, et quelles sont les propriétés de sécurité à satisfaire. Nous nous intéresserons ensuite aux récentes avancées dans le domaine, en décrivant certaines solutions basées sur les couplages, proposées entre 2005 et 2006. Nous verrons également comment ces techniques peuvent être utilisées afin de tracer les traîtres.

Je présenterai l'algorithme de Sudan, puis de Guruswami-Sudan, qui permettent de décoder les codes ultra classiques que sont les codes de Reed-Solomon bien au delà de la capacité de correction usuelle. Je rappellerai aussi comment Jakobsen a utilisé cet algorithme pour cryptanalyser le cryptosystème de Knudsen et Nyberg. Ensuite je poserai le problème de la généralisation multivariée de ces algorithmes, et je dirai les capacités de correction que l'on peut obtenir.

In this talk, we address some particular drawbacks of usual electronic vote systems and show that recent works give serious hope to overcome them -or, on the contrary, annihilate such a hope. In particular, we briefly present methods such as "Punchscan" or "Prêt à Voter", initiated by Chaum, which allow to detect when vote machines (or softwares) are misbehaving. By using them, it is possible to achieve the "What You See Is What You Vote for" property without performing a complex and costful security evaluation of these machines (or softwares). Afterwards we present the Juels et al. solution to the coercion problem (how to ensure that a vote is free, i.e. not constrained) in case of on-line voting. Finally, we also give evidence that the "perfect system" cannot exist, by mentioning some impossibility results from Pointcheval et al. In particular, perfect ballot secrecy and universal verifiability cannot be satisfied at the same time.

Work with Jacques Traoré

Dans cet exposé apres avoir presenté rapidement une partie de mon travail sur l'interpolation multivariée et ses applications en codage et en cryptographie ainsi que des travaux sur les schemas PIR (Private Information Retrieval), je presenterai une serie de travaux recents avec divers coauteurs sur les codes binaires doublements circulants qui peuvent faire mieux que la borne de Gilbert-Varshamov, le lien avec la borne de Minkoswki pour les reseaux, ainsi que des applications en cryptographie pour obtenir des tailles de clé beaucoup plus courtes pour des schemas basés sur les codes: authentification, generateur aleatoires et fonctions de hachage. On considerera aussi certaines applications pour le schema NTRU.

Depuis quelques années, la recherche sur l'application des couplages aux constructions de schéma cryptographique a débouché sur de nombreux résultats importants tels que les constructions de chiffrement basé sur l'Identité, les signatures du groupe sans oracle aléatoire... Dans cet exposé, nous présentons l'application des Couplages au problème de Traçage de traîtres, ainsi qu'une nouvelle primitive dite Traçage de traîtres basé sur l'Identité.

In many Western countries information is being censored or plans are being made. In Australia, the Australian Communications Minister Helen Coonan has suggested to censor the internet TV program Big Brother. Moreover two books are censored. In Belgium the Information Minister Peter Vanvelthoven is looking into "censoring websites with illegal content or with illegal services" (translated from the official Belgian memorandum) or at least to "inform customers that they entered a black listed site". Critics remember that before 1966 it was hard in small Belgian villages to buy books that were on the Vatican "Index Librorum Prohibitorum" blacklist. Other examples of censorship in the West include the censorship: by the church of ``non-traditional'' gospels, Hitler's ``Mein Kampf'' in countries as France and Germany, and the Rolling Stones performance during the 2006 superbowl on 5 February 2006 in the US. Texts describing in details the construction of atomic bombs, or other classified information, are also censored.

Whether censorship is a benefit to mankind or not, is a non-scientific topic, and therefore not the focus of the presentation. In this talk we discuss methods that can be used to censor networks. A problem with a straightforward solution is that censorship techniques might be used by terrorist or hackers who want to perform a denial of service attack. We therefore analyze how telecommunication providers can guarantee privacy on how to censor (i.e. protecting against hackers with limited resources using it to perform a denial of service) while at the same time being able to demonstrate to the authorities the capability to censor. Above is impossible when using traditional models to describe network reliability. We discuss an alternative model in which it can be achieved. We propose a zero-knowledge interactive proof for this problem.

No background information is required to be able to understand most of the lecture. This presentation is based on joint work with Yongge Wang and Mike Burmester and presented at the First International Workshop on Critical Information Infrastructures Security.

Dans cet exposé, on présentera une nouvelle attaque pour retrouver une clé secrète RSA quand on a des bits non forcément consécutifs de la clé secrète randomisée. On montrera que ces bits peuvent être obtenus par une attaque en consommation de puissance. Ces résultats étendent les résultats classiques de Boneh et al. qui retrouvent la clé secrète RSA en ayant accès à quelques bits consécutifs. Ces derniers résultats utilisent des techniques de réseau et utilisent le fait que les bits sont consécutifs. Quand les bits ne sont pas consécutifs, c'est un problème difficile de remonter à la clé. La nouvelle attaque décrite est extrêmement efficace et n'utilise pas les réseaux.

Ce travail a été présenté à CHES 2006 et c'est un travail effectué avec S. Kunz-Jacques, G. Martinet, F. Muller et F. Valette.

We examine Feedback with Carry Shift Registers (FCSR) where the initial state is chosen uniformly. In this case, it is possible to determine the probability of each value of the FCSR and thus, the entropy of the register, after k iterations. We consider two different problems. In the first place, we estimate the entropy of the register after one feedback. If the FCSR consists of a main register of length n and l carry bits we can show that we loose already l/2 bits after one step. Subsequently we examine the final entropy of the FCSR. As soon as we reach the circle in the functional graph of the register, the FCSR behaves like a permutation and the entropy stays constant. We present an algorithm to determine this entropy for a given FCSR. The exact calculation has a complexity O(2^l) which is unpractical for large l. However we are able to give an upper bound, a lower bound and an approximation which works in O(2^l).

Kabastianskii, Krouk and Smeets proposed in 1997 a digital signature scheme based on random error-correcting codes. In this talk we investigate the security and the efficiency of their proposal. We show that a passive attacker who may intercept just a few signatures can recover the private key. We give precisely the number of signatures required to achieve this goal. This enables us to prove that all the schemes given in the original paper can be broken with at most 5 signatures. We improve the efficiency of these schemes by firstly providing parameters that enable to sign about 40 messages, and secondly, by describing a way to extend these few-times signatures into classical multi-time signatures.

Joint work with P.L. Cayrel et D. Vergnaud

Intrusion-resilient signatures are key-evolving protocols that extend the concepts of forward-secure and key-insulated signatures. As in the latter schemes, time is divided into distinct periods where private keys are periodically updated while public keys remain fixed. Private keys are stored in both a user and a base; signature operations are performed by the user while the base is involved in periodic updates. Such a system remains secure after arbitrarily many compromises of both modules as long as break-ins are not simultaneous. Besides, when they simultaneously occur within some time period, past periods remain safe. In this work, we propose the first intrusion-resilient signature in the standard model (i.e. without random oracles) which provides both constant-size (short) signatures and at most log-squared private storage in the number of time periods.

Dans le cas du genre 1, le polynôme de classes de Hilbert joue un rôle particulier. Étant donné un corps quadratique $K$, il regroupe les $j$-invariants de courbes elliptiques ayant multiplication complexe par son anneau des entiers $\cO_K$. Dans le cas du genre 2, les polynômes de classes jouent un rôle identique mais sont au nombre de trois. Ils sont le moyen le plus efficace de générer des courbes hyperelliptiques de genre 2 définies sur un corps premier de grande caractéristique, dont on connaît le cardinal de la Jacobienne et par conséquent de construire de des cryptosystèmes hyperelliptiques. Néanmoins les moyens algorithmiques pour obtenir ces polynômes sont nettement moins avancés que dans le cas du genre 1.

Auparavant cantonnés à une sous-classe des corps CM quartiques, les algorithmes de calcul des polynômes de classes en genre 2 ne pouvaient guère dépasser un nombre de classes d'une dizaine. Nous présenterons différents algorithmes, travaux communs avec R. Dupont, P. Gaudry, D. Kohel, C. Ritzenthaler et A. Weng qui repoussent ces limites en terme de nombre de classes et étendent également le calcul des polynômes de classes à la classe entière des corps CM quartiques.

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

Les boîtes-S des procédés de chiffrement (à clef secrète) par blocs itéré sont notamment conçues pour résister aux attaques différentielle et linéaire. Ces cryptanalyses reposent sur la manière de combiner le texte clair et la clef. L'opération de combinaison traditionnellement employée est l'addition bit-à-bit de vecteurs binaires. Il existe d'autres façons de mélanger le clair et la clef, aussi dans cet exposé on se propose de remplacer l'addition par une action de groupe plus générale. On étudie alors l'attaque différentielle adaptée à cette nouvelle opération de combinaison ainsi que les boîtes-S qui lui opposent la meilleure résistance possible. On montre en particulier que l'on peut construire des fonctions robustes dans des cas où leurs homologues classiques (i.e. lorsque l'opération de combinaison est une addition binaire) n'existent pas.

In the ''provable security'' paradigm one has confidence on the security of a cryptographic protocol by exhibiting a reduction from a conjectured intractable mathematical problem to a successful attack on the protocol. The concrete security (aka exact security) approach explicitly captures the quantitative aspects of security, by means of an concrete treatment of the security reductions. This enables to obtain practical measurements such as the conjectured number of cycles of adversary computation the scheme can withstand or how long a security parameter must be. In this talk we discuss the state of the art on this topic.

On aborde ici le problème de la reconstruction des composants d'un système de transmission à partir de l'interception d'une communication bruitée. Les deux grandes parties de ce travail s'intéressent successivement aux deux maillons principaux de la chaîne : le brasseur et le code correcteur d'erreur, dans l'ordre où ils doivent être traités par l'attaquant, c'est-à-dire dans l'ordre inverse de leur apparition dans la chaîne de transmission.

La première partie traite donc du problème de la reconstruction d'un code linéaire binaire à partir de la connaissance de mots de code bruités. Dans un premier temps, nous présentons et analysons une méthode suggérée par A.Valembois dans sa thèse. Cette analyse nous amène à présenter un nouveau test statistique permettant de trouver des mots susceptibles d'appartenir au dual du code utilisé lors de la transmission. Puis nous présentons un nouvel algorithme de décodage fondé sur les techniques classiques de décodage itératif. Cet algorithme nous permet de corriger des erreurs même si certaines des équations de parité trouvées par le test statistique ne sont pas valides. Nous décrivons alors un nouvel algorithme de reconstruction utilisant cet algorithme de décodage.

La seconde partie traite du problème de la reconstruction d'un brasseur linéaire. Dans un premier temps, nous supposons que l'attaquant dispose de la sortie exacte du brasseur. Nous présentons alors différentes techniques permettant de reconstruire un brasseur synchrone ou auto-synchronisant en fonction des hypothèses envisagées sur l'entrée du brasseur. Ensuite, nous nous intéressons au cas général et nous présentons alors une technique algébrique permettant de reconstruire un brasseur synchrone quand l'attaquant connaît simplement l'image de sa sortie par une transformation linéaire par bloc et une partie de la suite en entrée.

Les schémas de chiffrement asymétriques authentifiés, utilisés pour envoyer un message à un destinataire, sont particulièrement intéressants dans un contexte de messagerie électronique lorsqu'un expéditeur souhaite utiliser conjointement un service de confidentialité et un service d'authentification. Nous examinons ici le cas des schémas, notés 1->n, qui permettent de chiffrer efficacement dans un contexte clé publique un message pour n destinataires de manière authentifiée. Nous proposons des définitions formelles de sécurité pour de tels schémas qui, pour n=1, sont plus fortes et/ou plus générales que celles actuellement proposées. Nous présentons ensuite un mode d'opérations qui transforme tout schéma 1->1 prenant en entrée des message courts, en un schéma 1->n prenant en entrée des messages longs. Ce mode permet ainsi de déduire la sécurité du schéma 1->n obtenu, de celle, plus simple à étudier, du schéma 1->1 sous-jacent.

La forme de Montgomery pour les courbes elliptiques est une forme particulière de l'équation qui permet une multiplication scalaire rapide utilisant les chaînes de Lucas. Cette forme est utilisée dans l'algorithme de factorisation ECM et pour obtenir des cryptosystèmes à clef public très rapide. Partant d'idées de Chudnovsky et Chudnovsky, nous avons utilisé la théorie des fonctions Theta pour concevoir des formules ayant des propriétés similaires en genre 2. Dans cet exposé nous expliquerons cette construction. Nous discuterons aussi d'une construction analogue pour les courbes de genre 1 qui n'est pas exactement la même que celle de Montgomery. Pour finir, nous montrerons que nos formules peuvent être adaptées à la caractéristique 2.

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 paiment é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.

Cette thèse comporte deux parties indépendantes.

La première partie est consacrée à l'étude de propriétés d'approximation diophantienne quantitative de nombres liés aux courbes elliptiques qui apparaissent comme valeurs spéciales des fonctions elliptiques de Weierstrass, de formes modulaires et de fonctions hypergéométriques. L'objectif du premier chapitre est d'utiliser le lien entre les approches elliptique, modulaire et hypergéométrique pour étudier les propriétés arithmétiques de ces nombres. En utilisant des ingrédients modulaires et hypergéométriques, deux nouvelles démonstrations de résultats obtenus initialement par la voie elliptique sont présentées. Dans le chapitre deux, un résultat d'indépendance linéaire de nombres liés aux courbes elliptiques est démontré. Le résultat est explicite et une mesure d'indépendance linéaire précise est donnée pour ces nombres.

La deuxième partie est consacrée à la construction, en cryptographie asymétrique, de protocoles d'authentification de messages à vérification contrôlée et à l'étude de leur sécurité. L'approche adoptée est à la fois théorique et pratique, puisque les définitions et les résultats sont précisés dans le cadre formel de la sécurité réductionniste, avec l'objectif de concevoir des protocoles parmi les plus efficaces connus. Le chapitre trois présente une taxinomie des problèmes de type Diffie-Hellman et une nouvelle analyse des propriétés de sécurité du protocole de signature de Schnorr. Le chapitre quatre est consacré à l'étude de protocoles de signature désignable dans un environnement classique et dans un environnement multi-agents. Enfin, dans le chapitre cinq, plusieurs schémas de signature non-transférable sont présentés.

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 talk, 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.

(Joint work with B. Chevallier-Mames)

Joint work with David Pointcheval.

We present the first automatic technique for proving protocols and primitives in the exact security computational model. Automatic proofs of cryptographic protocols were up to now reserved to the Dolev-Yao model, which however makes quite strong assumptions on the primitives. On the other hand, with the proofs by reductions, in the complexity theoretic framework, more subtle security assumptions can be considered, but security analyses are manual. A process calculus is thus defined in order to take into account the probabilistic semantics of the computational model. It is already rich enough to describe all the usual security notions of both symmetric and asymmetric cryptography, as well as the basic computational assumptions. As an example, we illustrate the use of the new tool with the proof of a quite famous asymmetric primitive: unforgeability under chosen-message attacks (UF-CMA) of the Full-Domain Hash signature scheme under the (trapdoor)-one-wayness of some permutations.

Les signatures digitales classiques ont la propriété, parfois indésirable, d'être universellement vérifiables par toute personne possédant la clé publique du signataire. D. Chaum et H. van Antwerpen ont introduit, en 1989, le concept de signature non-transférable (undeniable signature, en anglais) dont la vérification ne peut s'effectuer sans interaction avec le signataire. C. H. Lim et P. J. Lee ont proposé le concept de signature non-transférable dirigée qui garantit la possibilité de vérifier une signature, même si le signataire ne peut pas (ou ne souhaite pas) le faire.

Dans cet exposé, nous présenterons un protocole de signature non-transférable et un protocole de signature non-transférable dirigée dont la sécurité repose sur le problème Diffie-Hellman calculatoire dans le modèle standard de sécurité. Ils offrent au signataire la possibilité additionnelle de convertir (individuellement ou universellement) des signatures non-transférables en des signatures universellement vérifiables. Ces schémas, basés sur les couplages, sont performants et produisent des signatures courtes.

A multi-signature scheme enables a group of signers to produce a compact, joint signature on a common document. However, existing schemes impose key setup or PKI requirements that make them impractical, such as requiring a dedicated, distributed key generation protocol amongst potential signers, or assuming strong, concurrent zero-knowledge proofs of knowledge of secret keys done to the CA at key registration.

We provide new schemes that are proved secure in the plain public-key model, meaning requires nothing more than that each signer has a (certified) public key. The important simplification in key management achieved is not at the cost of efficiency or assurance: our schemes match or surpass known ones in terms of signing time, verification time and signature size, and are proved secure in the random-oracle model under standard (not bilinear map related) assumptions. One of the proofs is based on a simplified and generalized Forking Lemma that may be of independent interest.

We also present an identity-based multi-signature scheme based on RSA. The identity-based paradigm is particularly appealing for the case of multi-signatures, because the need to transmit the public keys of all signers partially defeats the purpose of using multi-signatures.