Les volcans d'isogénies sont des graphes dont les noeuds sont des courbes elliptiques et les arêtes sont des l-isogénies entre les courbes. En 1996, Kohel propose l'utilisation du parcours en profondeur de ces graphes dans un algorithme qui calcule l'anneau d'endomorphismes d'une courbe elliptique. Afin d'améliorer l'algorithme de comptage de points d'une courbe elliptique, Fouquet et Morain (2001) ont proposé d'autres algorithmes pour le parcours de ces graphes. Cependant, jusqu`à présent, il n'était pas possible de prédire la direction d'un pas sur le volcan; de fait, un grand nombre de pas successifs était nécessaire avant de déterminer la direction prise. Nous introduisons une méthode qui permet de calculer, pour une courbe elliptique E, les points d'ordre l qui engendrent les noyaux des isogénies descendantes, ascendantes ou horizontales. Notre méthode, basée sur le calcul de quelques couplages, est très efficace et donne, dans beaucoup de cas, des algorithmes plus rapides que les méthodes existantes pour le parcours des volcans d'isogénies.
Travail commun avec Antoine Joux
Side Channel Analysis (SCA) is a cryptanalytic technique where the adversary analyzes the physical leakage produced during the execution of a cryptographic algorithm embedded in a physical device. Indeed, this leakage often statistically depends on the intermediate variables of the computation and key recovery attacks are therefore possible. Until now, almost all SCA involved the linear correlation coefficient as wrong-key distinguisher. This coefficient is actually a sound statistical tool to quantify linear dependencies between univariate variables. However, when those dependencies are non-linear, the correlation coefficient stops being pertinent so that another statistical tool must be investigated.
Recent works showed that the Mutual Information (MI for short) measure is a promising candidate, since it detects any kind of statistical dependency. Substituting it for the correlation coefficient may therefore be considered as a natural extension of the existing attacks. Nevertheless, the first applications published at CHES 2008 have revealed several limitations of the approach and have raised several questions.
In this presentation, we expose the theoretical foundations behind MI-based attacks and we clarify its limitations and assets. We apply it against a flawed countermeasure and we compare its efficiency with the one of correlation-based attacks. We also extend the works recently published at CHES 2008 conference. We argue that in critical contexts (when implementations are protected with masking) MI-based attacks potentially bring improvements compared to existing attacks, because they directly extend to multivariate statistics while, e.g. correlation or Kocher's difference-of-mean generally need to be tweaked to apply to such contexts. Our argumentation will be based on theoretical analyses and on simulations and practical experiments on both hardware and software implementations.
In this talk, we will focus on remote (Internet) voting. We will first introduce a security model for such electronic elections. The emphasis will be on so-called 'coercion-resistance' (a confidentiality property) and 'universal verifiability' (an integrity property). We will then present a practical approach for constructing coercion-resistant and 'universally' verifiable voting systems. Our solution relies on special anonymous signature schemes (a.k.a list signatures or Direct Anonymous Attestations) and is proven secure with respect to our model under the q-Strong Diffie-Hellman and Strong Decision Diffie-Hellman Inversion assumptions. We will conclude our presentation with a discussion of ongoing research in the area of remote voting.
Un schéma de Signature Caméléon est un schéma de signature permettant au signataire d'un message de désigner un délégué qui pourra, par la suite, modifier certaines parties du message signé tout en gardant une signature valide du signataire sur le nouveau message. Nous présenterons d'abord un nouveau schéma de signature caméléon prouvé sûr dans le modèle proposé par Brzuska et al. à PKC 2009. Puis nous nous intéresserons aux limitations qu'un signataire souhaiterait imposer au délégué sur ses futures modifications. En particulier nous regarderons comment le signataire peut limiter les modifications dans un ensemble de valeur autorisées, et comment il peut limiter le nombre de versions que le délégué publiera. Si il reste suffisamment de temps, nous monterons aussi comment le signataire peut fixer une limite k sur le nombre de parties modifiées par le délégué parmi les parties modifiables n (n>k).
Les passeports électroniques sont désormais diffusés dans le monde entier, depuis la première génération de passeports spécifiés par l'ICAO en 2004. Plusieurs problèmes de sécurité ont aussi été identifiés et de nouveaux ensembles de protocoles ont vu le jour, notamment l'ensemble EAC.
Ce type de document possède un circuit intégré contenant des informations biométriques sur le porteur du document (photographie faciale, empreintes digitales) et utilise une technologie sans contact. Les données contenues dans ce document sont donc personnelles, très sensibles et demandent une attention particulière.
Dans cet exposé, nous étudions les trois générations de passeports électroniques, ainsi que les problèmes de sécurité qui sont reliés. On décrit par ailleurs quelques attaques exploitant ces vulnérabilités, ainsi que la thématique de la protection de la vie privée.
Le problème du plus court vecteur (SVP), et aussi celui du plus proche vecteur (CVP) d'un réseau euclidien sont deux problèmes NP-difficiles, et sur lesquels la sécurité de nombreux cryptosystemes se réduit instantanément. Dans cet exposé, nous étudions des methodes probabilistes pour résoudre exactement et en pratique ces problèmes (principalement des algorithmes de crible).
On connait depuis quelques années des algorithmes simplement exponentiels probabilistes en temps et en memoire qui résolvent ces problèmes. Cependant, dans les dimensions qui nous interessent: entre 90 et 150, ces methodes ne sont pas forcément les plus rapides, et sont actuellement difficilement parallélisables.
Dans cet exposé, nous étudions plutot des algorithmes en 2^O(n2) qui s'avèrent en pratique bien plus rapides. Ce sont des variantes de l'algorithme de recherche exhaustive de Schnorr-Euchner, dans lequel l'arbre de recherche exhaustive a été élagué de très près, de sorte qu'il ne reste qu'une partie infinitésimale de l'arbre initial. Nous montrons que la probabilité que le plus court vecteur appartienne toujours à l'arbre élagué diminue bien moins rapidement que la taille de l'arbre, ce qui représente un compromis temps-de-calcul/probabilité de succès plus que favorable. Par ailleurs, nous montrons comment une randomisation des entrées permet de compenser la faible probabilité de succès intrinsèque de l'algorithme sus-mentionné, et de de résoudre le SVP et le CVP dans n'importe quel réseau, et ce en utilisant une approche MIMD ultra-parrallèle.
Travail commun avec Phong Nguyen et Oded Regev
Introduced by Micali, Rabin and Kilian, zero-knowledge sets (ZKS) allow a prover to commit to a secret set S so as to be able to prove statements such as "x belongs to S" or "x does not belong to S". Chase et al. showed that ZKS protocols are underlain by a cryptographic primitive termed mercurial commitment. A (trapdoor) mercurial commitment has two commitment procedures. At committing time, the committer can choose not to commit to any specific message and rather generate a dummy value which it will be able to softly open to any message without being able to completely open it. Hard commitments, on the other hand, can be hardly or softly opened to only one specific message.
At Eurocrypt 2008, Catalano, Fiore and Messina (CFM) introduced an extension called trapdoor q-mercurial commitment (qTMC), which allows committing to a vector of q messages at once. These qTMC schemes are interesting since their openings w.r.t. specific vector positions can be short (ideally, the opening length should not depend on q), which provides zero-knowledge sets with much shorter proofs when such a commitment is combined with a Merkle tree of arity q. The CFM construction notably features short proofs of non-membership as it makes use of a qTMC scheme with short soft openings. A problem left open is that hard openings still have size O(q), which prevents proofs of membership from being as compact as those of non-membership.
In this work, we describe a new qTMC scheme where hard and soft position-wise openings, both, have constant size. We then show how our scheme can be extended to provide independent zero-knowledge sets (i.e., ZKS schemes that prevent adversaries from correlating their set to the sets of honest provers, as defined by Gennaro and Micali). (joint work with M. Yung)
En janvier 2010, la factorisation du challenge rsa-768 a été annoncée, fruit d'une collaboration internationale entre plusieurs équipes, dont les principales sont EPFL/LACAL (Lausanne), INRIA/CACAO (Nancy), NTT (Tokyo). Cette factorisation a été obtenue par le crible algébrique. Nous décrivons comment cette factorisation a été possible, et en quoi ce calcul apporte des éléments nouveaux par rapport aux records précédemment établis.
Finite fields arithmetic is one of the challenges in current computer arithmetic. It occurs, in particular, in cryptography where the needs increase with the evolution of the technologies and also of the attacks. Through our research, we have proposed different systems based on residues representations. Different kinds of finite fields are concerned with. For each of them, some specificities of the representations are exploited to ensure the efficiency, as well as for the performances, than for the robustness to side channel attacks.
In this paper, we deal with three similar approaches: the first one is dedicated to prime field using residue number systems, a seconde one concerns extension finite fields of characteristic two, the last one discusses of medium characteristic finite fields.
The main interest of these systems is their inherent modularity, well suited for circuit implementations.
Les codes géométriques ont été introduits au début des années 80 par le mathématicien et ingénieur Russe V.D. Goppa. Dans les années qui ont suivi ils se sont avérés être un sujet de recherche aussi fructuex que passionnant. Outre les avancées théoriques qu'ils ont permis, on dénombre un certain nombre de domaines de la théorie de l'information où ils sont utilisés (codage, cryptographie, partage de secret etc...)
Dans cet exposé nous commençerons par présenter la théorie des codes géométriques sur des courbes algébriques ainsi que certaines de ses applications. Dans un second temps, nous nous focaliserons sur la théorie des codes sur les surfaces, à la fois moins comprise et nettement moins explorée et présenterons une méthode géométrique d'estimation des paramètres de tels codes puis de leurs duaux.
Un schéma de signature à seuil classique permet aux membres du groupe d'émettre des signatures au nom du groupe, dès qu'un certain nombre d'entre eux participe au processus. Dans ces cas là, l'anonymat est parfait (en tout cas aucune trappe n'est connue) et ainsi personne ne peut savoir qui a aidé à atteindre le seuil.
Dans cet exposé, on va s'intéresser à un anonymat révocable dans les signatures à seuil.
De cette façon, on pourra, si besoin, trouver qui a signé. (On va donc se servir de notions d'anonymat, non-forgeabilité et non frameability similaires à celle des signatures de groupe).
On va plus particulièrement s'interesser à des groupes et seuils dynamiques, mais en gardant une taille optimale pour la signature, ie linéaire en la taille du seuil et ce via une signature ne nécessitant aucune interaction entre les signataires. Dans un premier temps, on s'intéressera à une construction générique à partir des signatures de groupes et de listes.
Puis on montrera une construction efficace, non interactive, avec une signature en taille linéaire en le seuil. Dans le modèle de l'oracle aléatoire la sécurité repose sur le SDH pour la non forgeabilité, et le DLIN/DTDH pour l'anonymat.
Les étiquettes RFID sont des dispositifs à ressources limitées utilisées pour identifier des objets (ou des personnes) à l'aide d'un lecteur. Les communications entre ces entités transitent par les champs électromagnétiques permettant de réaliser ces identifications à distance et sans contact physique ou visuel. Avec le développement massif de ces dispositifs, un consommateur moyen peut se retrouver avec une constellation de telles étiquettes sur lui. Pour assurer le respect de la vie privée de ces personnes, un individu malhonnête ne doit pas être en mesure d'identifier les objets transportés. Toutefois, l'anonymat des produits ne semblent pas suffisant dans ce cas précis.
Le but de cette présentation est de développer les différentes manières de modéliser un tel système afin de pouvoir obtenir le modèle de sécurité le plus fort possible. En analysant l'état de l'art, je présenterai à l'aide d'exemples concrets les différents problèmes de plusieurs solutions. Je terminerai cette présentation en exposant le modèle de sécurité que Sébastien Canard et moi-même avons mis en place qui permet de modéliser une nouvelle propriété de sécurité pour de tels schémas d'identification.
Jacobson, Scheidler et Weimer présentent en 2008 un schéma de chiffrement NICE (New Ideal Coset Encryption) dans le groupe de classes des formes (quadratiques entières binaires) réelles de discriminant N=q^2p avec p et q deux grands nombres premiers impairs différents. Sa sécurité repose sur la difficulté de factoriser N et à l'avantage d'avoir un temps asymptotique de déchiffrement quadratique en la taille de discriminant, au lieu de cubique pour le schéma de chiffrement classique RSA de module N. Le principe de ce schéma est d'utiliser la relation entre les formes de discriminant non fondamental N et les formes de discriminant fondamental p.
En 2009 Castagnos, Joux, Laguillaumie et Nguyen combinent la réduction des formes et une variante de l'algorithme de Coppersmith pour trouver la factorisation de N en temps heuristique polynomial en la taille de N.
Dans cet exposé, nous commencerons par donner quelques rappels sur les formes réelles et nous présenterons un nouvel algorithme de réduction qui nous a permis de passer à la racine carrée les meilleures bornes connues sur la matrice de passage. Dans une deuxième partie nous énoncerons le cryptosystème NICE ainsi que l'attaque heuristique de 2009, et nous prouvons que cette attaque est bien correcte, et fonctionne en temps polynomial.
Travail en commun avec Malika Izabachène et David Pointcheval
La notion d'anonymat pour le chiffrement (à clé publique) assure qu'un adversaire en possession d'un chiffré est incapable d'identifier l'utilisateur auquel il est destiné. Puisque cette propriété peut être utilisée de manière frauduleuse, il semble nécessaire de mettre en place une autorité de traçage capable de lever l'anonymat en cas de comportement illégal. Cependant un protocole de chiffrement peut contenir un canal subliminal qui permettrait à des utilisateurs malhonnêtes de communiquer de manière illégale en utilisant des chiffrés qui traçent vers des utilisateurs honnêtes.
Dans cet exposé, nous étudieront l'existence de canaux subliminaux dans les protocoles de chiffrement anonyme traçable et nous introduirons une nouvelle primitive cryptographique pour déjouer ce type d'attaques. Nous formaliserons les notions de sécurité attendues d'un tel protocole et nous présenterons plusieurs constructions efficaces les atteignant.
Travail commun avec Jean-Charles Faugère et Ludovic Perret
Dans cet exposé, nous étudierons un cadre général permettant de combiner des méthodes statistiques et des attaques algébriques pour la cryptanalyse de chiffrements par blocs. En particulier, nous verrons comment on peut étendre des attaques algébriques contre le DES en y incorporant des éléments de cryptanalyse différentielle.
Pour résoudre les systèmes polynomiaux, nous utiliserons un SAT-Solver efficace : MiniSAT2. L'étude de son comportement vis-à-vis des systèmes polynomiaux creux permettra de choisir une modélisation adaptée des boîtes-S. Pour réduire le nombre de clair-chiffrés, on utilisera différentes caractéristiques différentielles qu'on cherchera à combiner.
Ce mélange entre des techniques de natures très différentes permettra d'obtenir des compromis, notamment entre le nombre de clair-chiffrés nécessaires pour retrouver la clé et le temps de l'attaque. Grâce à cette méthode, on pourra étendre à 8 tours des attaques algébriques contre le DES jusqu'ici limitées à 6 tours.
This paper presents the first study of pairing computation on curves with embedding degree $15$. We compute the Ate and the twisted Ate pairing for a family of curves with parameter $\rho~1.5$ and embedding degree $15$. We use a twist of degree 3 to perform most of the operations in $\F_p$ or $\F_{p^5}$. Furthermore, we present a new arithmetic for extension fields of degree $5$. Our computations show that these curves give very efficient implementations for pairing-based cryptography at the 192 bits security levels.