Séminaires CRYPTO 2011-2012

webmaster Archives des séminaires CRYPTO (PRISM) Pas de commentaires
  • 27 juin 2012 – Jacques Patarin (PRiSM) : Génération quantique de bits pseudo-aléatoires et random walks.
Résumé : Il y a quelque mois le professeur Chris Calude (univeristé d’Auckland) a fait un exposé dans ce séminaire où il signalait un résultat fort étonnant : il était capable de distinguer des bits générés par des procédés quantiques (et vendus par des sociétés) de bits générés par des fonctions cryptographiques usuelles (type AES par exemple). Je suis allé en Nouvelle-Zélande en février et une bonne partie du mystère a été résolu, comme nous le verrons.
De plus ce sera une bonne occasion de présenter quelques propriétés fascinantes des marches aléatoires (random walks) en effet ces tests sont parfois utilisés.
  • 20 juin 2012 – Double séance : Luca De Feo et Jérôme Plût (PRiSM) : Fun with isogenies and trees.
Résumé : Il est bien connu que certains graphes de courbes elliptiques isogènes ont une structure de graphe de Ramanujan, ce qui garantit des bonnes propriétés de mixage pour les marches aléatoires. Cette observation a été utilisée à plusieurs reprises pour construire des cryptosystèmes basés sur la difficulté supposée de calculer une isogénie entre deux courbes elliptiques données.
Parmi ces protocoles, nous nous intéressons particulièrement à l’échange de clef de Rostovstev et Sotlbunov: il s’agit essentiellement d’un protocole de Diffie-Helman basé sur l’action du groupe des classes sur un graphe d’isogénies ordinaires. Ce protocole est peu efficace et présente un intérêt purement théorique; les auteurs ont suggéré qu’il pourrait être utilisée dans un contexte post-quantique, cependant Childs, Jao et Soukharev ont montré qu’il est attaquable en temps sous-exponentiel quantique à cause de sa structure abélienne.
Dans ce travail, en commun avec David Jao, nous proposons un noveau protocole à la Diffie-Helman basé sur des marches dans des graphes d’isogénies supersingulières. La similitude avec le protocole de Rostovstev et Stolbunov est seulement superficielle: dans notre cas il n’y a pas de structure abélienne agissant sur le graphe, ce qui nous oblige à passer de l’information supplémentaire pour réaliser l’échange. Cependant il n’e semble pas y avoir de moyen d’utiliser cette information supplémentaire pour attaquer le protocole, et l’absence de la structure abélienne défie toute attaque quantique. La séparation la plus significative entre notre construction et les échanges de Diffie-Helman est réalisée par un protocole Zero-Knowledge que nous construisons au dessus de nos primitives, et dont l’équivalent abélien est trivialement cassé.
Notre protocole, déjà dans une implantation naïve en Magma, est sensiblement plus performant que celui de Rostovstev et Stolbunov. Son optimisation est aussi intéressante que le protocole lui même; en effet une étude fine de la combinatoire du calcul d’isogénies se réduit naturellement à des problèmes d’optimisation pour des arbres binaires (infinis) avec poids. En combinant cette étude avec des techniques classiques en arithmétique des courbes elliptiques, nous obtenons une implantation mixte en Sage/Cython/C 1000 fois plus rapide que le protocole de Rostovstev et Stolbunov et avec des performances comparables à celles de nombreux protocoles à base de couplages.
  • 13 juin 2012 – Léo Ducas (École Normale Supérieure) : Learning A Zonotope and More : Cryptanalysis of NTRUsign countermeasures.
Résumé : Les réseaux euclidiens suscitent de plus en plus d’intérêt pour la construction de primitives de cryptographie asymétrique, à la fois pour leurs qualités algorithmiques (calculs simples, parallélisables) et pour leur vertus théoriques (confiance en la difficulté des problèmes sous-jacents).
Dès 1995, un schéma de signature basé sur les réseaux est construit par Goldreich Goldwasser et Halevi, et en 2001, une instanciation efficace, NTRUsign, est proposé. Sa sécurité est rapidement mise en doute: la distribution des signatures révèle l’information lié a la clé secrète. En 2005, Nguyen et Regev formalisent ce problème comme « l’apprentissage d’un parallélépipède »; ils montrent que le lieux des minima des moments d’ordre 4 sont exactement les vecteurs de la clé secrètes, et que ces minima peuvent être trouvés par une descente de gradient étant donné seulement 400 paires messages-signature pour NTRUsign.
Des contremesures heuristiques ont été proposées, et nos travaux s’intéressent à la cryptanalyse de ces contremesures. La contremesure principale, dite méthode de perturbation a été proposées pour la standardisation de NTRUsign, et sa cryptanalyse passe par l’apprentissage d’un « zonotope » (convolution de plusieurs parallélépipèdes). Une analyse locale prouve l’existence de minima proches des vecteurs recherchés. En pratique, nous ajoutons un algorithme spécialisé de « Bounded Distance Decoding » pour corriger l’erreur, nous permettant de retrouver les clé secrète de NTRUsign avec 5000 signatures.
Pour la seconde contremesure, dite technique de déformation, nous montrons que les minima contiennent toujours de l’information sur la clé secrète, bien qu’elle soit différemment utilisable: de façon surprenante, retrouver la clé a partir de ces minima peut se ramener a un problème d’énumération d’isomorphisme de Graphe, énumération qui s’avère facile pour les instances considérées.
Nos travaux démontrent ainsi l’importance d’utiliser des techniques prouvablement sûres pour éviter toute fuite d’information, tel le « Gaussian Sampling » (proposé par GPV en 2008), malgré un impact significative sur l’efficacité des cryptosystèmes construits.
  • 6 juin 2012 – Marc Kaplan (Télécom Paristech) : Puzzle de Merkle dans le monde quantique.
Résumé : En 1974, Ralph Merkle a proposé un schéma pour communiquer de façon sécurisée à travers un canal non-sécurisé. La sécurité de son protocole repose sur le fait suivant: les participants fournissent un effort calculatoire de l’ordre de N mais un espion ne peut pas apprendre leur communication sans fournir un effort de l’ordre de N2. La sécurité du protocole de Merkle n’est plus valable face à un espion ayant accès à un ordinateur quantique. Brassard et Salvail ont montré que si les participants légitimes ont également accès à des ressources quantiques, alors il est possible de restaurer en partie la sécurité. Leur protocole nécessite un effort de l’ordre de N3/2 pour être brisé. Nous présenterons deux nouveaux protocoles pour communiquer de manière sécurisée à travers un canal non sécurisé. Dans le premier, les participants légitimes ont accès à des ressources quantiques et un espion a besoin de fournir un effort de N5/3. Le second protocole est entièrement classique et offre une sécurité de l’ordre de N7/6 contre un adversaire qui a accès à des ressources quantiques. Cet exposé ne suppose pas de notion préalable de calcul quantique.
  • 2 mai 2012 – Gaëtan Bisson (Macquarie University) : Un algorithme à la Pollard pour le problème du sac à dos.
Résumé : Soit S une suite finie d’éléments d’un groupe fini G noté multiplicativement ; le problème du sac à dos consiste à trouver une sous-suite de S dont le produit vaut un élément donné z de G. Pour certains groupes particuliers comme G=Z/nZ, on connait des méthodes très efficaces pour le résoudre ; cependant, aucun algorithme générique ne peut résoudre ce problème en moins de O(sqrt(#G)) opérations.
Une approche de type « pas de bébé, pas de géant » atteint cette complexité en temps mais requiert un espace mémoire de taille comparable. La première partie de cet exposé présentera une adaptation d’idées de Pollard à ce contexte afin d’obtenir un algorithme similaire mais au coût mémoire négligeable. Ensuite, j’en présenterai certaines applications, notamment au calcul d’isogénies entre deux courbes elliptiques.
Ces travaux sont conjoints avec Andrew V. Sutherland.
  • 2 avril 2012 – Maike Massierer – Elisa Gorla (Universität Basel) : Trace zero varieties in cryptography.
Abstract : Elliptic curves defined over finite fields are one of the most important types of groups used in cryptography today. Trace zero varieties arise from certain subgroups of such elliptic curves, namely those points of trace zero. They are interesting from a constructive point of view, because they allow fast arithmetic, and also from a cryptanalytic point of view, since the security of some cryptographic protocols is directly linked to the properties of these varieties. We discuss the geometric construction that leads to the trace zero variety. We also study the hardness of the discrete logarithm problem by considering an index calculus type attack on trace zero varieties.
  • 26 mars 2012 – María Naya Plasencia (PRiSM) : How to Improve Rebound Attacks (and New Applications).
Résumé : Rebound attacks are a state-of-the-art method for the analysis of hash functions.Such attacks are based on a well chosen differential path and have been applied to several hash functions from the SHA-3 competition, providing the best known analysis in these cases. In this talk, we will describe the main idea of rebound attacks, and we will show how can we improve most of them. This is done by identifying a common family of problems at the bottleneck of these attacks: « merging large lists with respect to a relation t ». Theses problems can be studied out of the rebound-attack context, and we provide several algorithms that efficiently solve some subcases, which are directly applicable to several practical instances.
Recently, we proposed new applications of this approach — recognizing an instance of the list-merging problem and applying the ad-hoc algorithm that solves it — which provide the best known analysis against the hash functions ECHO, JH (SHA-3 finalist) and the multipurpose primitive ARMADILLO2. We will describe the intuition behind these latest applications.
  • 19 mars 2012- Jean-François Biasse (University of Calgary) : Les idéaux d’un corps de nombres en cryptologie.
Résumé: Dans cet exposé, nous nous intéresserons aux usages possibles des idéaux d’un corps de nombres en cryptologie.
Nous ferons appel à des calculs dans le groupe de classes d’idéaux. Leur intérêt dans le cadre de la théorie des nombres est notamment relié au calcul du groupe des unités et à la résolution d’équations Diophantiennes.
Une des raisons motivant l’étude de ces objets d’un point de vue cryptologique est que le groupe de classes d’idéaux est un groupe fini dont la difficulté des instances du problème du logarithme discret (DLP) permet de définir des cryptosystèmes. Nous étudieront les optimisations pratiques aux algorithmes sous-exponentiel de résolution du DLP et leur impact sur la sécurité des cryptosystèmes correspondants.
Nous envisagerons aussi l’utilisation des méthodes optimisées pour la résolution du DLP dans le groupe de classes d’idéaux d’un corps de nombres dans le context du calcul d’isogénies et du calcul de l’anneau d’endomorphismes d’une courbe elliptique par la théorie de la multiplication complexe.
  • 12 mars 2012 – Nicolas Gama (PRiSM) et Malika Izabachène (LSV) : Worst case to average case reduction revisited.
  • 5 mars 2012 – Emmanuel Volte (PRiSM/Université de Cergy-Pontoise) : ZK with Rubik’s Cubes.
Abstract : Since the invention of the Rubik’s cube by Ernö Rubik in 1974, similar puzzles have been produced, with various number of faces or stickers. We can use these toys to define several problems in computer science, such as go from one state of the puzzle to another one. In this talk, we will classify some of these problems based on the classic Rubik’s cube or on generalized Rubik’s Cube. And we will see how we can use them in Zero Knowledge Authentication with a public key in order to achieve a given complexity against the best known attacks (for example 280 computations). The efficiency of these schemes, and their possible connection with NP-complete problems will also be discussed.
  • 6 février 2012 – Guillaume Quintin (Doctorant LIX) : On Generalized Reed-Solomon Codes Over Commutative and Noncommutative Rings.
Abstract : In this talk we will study generalized Reed-Solomon codes over commutative, non commutative rings and show that the classical Welch-Berlekamp and Guruswami-Sudan decoding algorithms still hold in this context and we investigate their complexities. Under some hypothesis, the study of noncommutative Reed-Solomon codes over finite rings leads to the fact that GRS code over commutative rings have better parameters than their noncommutative counterparts. Also GRS codes over finite fields have better parameters than their commutative rings counterparts. But we will also show that given a unique decoding algorithm for a GRS code over a finite field, there exists a unique decoding algorithm for a GRS code over a Galois ring with a better asymptotic complexity. Moreover we will introduce new unique- and list-decoding algorithms designed to work when the base ring is for example a Galois ring or the ring of square matrices over a Galois ring.
  • 7 décembre 2011 – Cécile Gonçalves (Doctorante LIX) : Un algorithme à la Kedlaya pour compter les points de revêtements cycliques de la droite projective.
Résumé : Le comptage de points de la jacobienne d’une courbe est un problème intervenant naturellement en théorie des nombres et en cryptographie. L’algorithme proposé par Kedlaya en 2001 est l’un des premiers à être pratiquable en genre supérieur à 2 : c’est un algorithme qui permet de compter les points d’une courbe hyperelliptique et qui est polynomial en le genre. Dans cet exposé, nous présenterons un algorithme à la Kedlaya de comptage de points d’un revêtement cyclique de la droite projective, qui résulte en fait d’une extension de l’algorithme proposé par P. Gaudry et N. Gürel pour les courbes superelliptiques.
  • 30 novembre 2011 – Aurore Guillevic (Doctorante Thalès – ENS) : Familles de courbes hyperelliptiques de genre 2, calcul de l’ordre de la jacobienne et constructions pour les couplages.
Résumé : L’utilisation des courbes elliptiques et hyperelliptiques en cryptographie nécessite de pouvoir calculer en un temps raisonnable l’ordre de la courbe elliptique et dans le cas hyperelliptique, de la jacobienne de la courbe. T. Satoh proposa à Eurocrypt 2009 un algorithme polynomial pour vérifier si l’ordre de la jacobienne d’une courbe hyperelliptique de la forme Y^2 = X^5 + aX^3 + bX définie sur un corps fini Fq admet un grand facteur premier. Son approche consiste à obtenir différents candidats pour la fonction zeta de la jacobienne sur Fq en partant de l’expression de la fonction zeta sur une extension où la jacobienne se départage en deux courbes elliptiques. L’approche de T. Satoh se généralise pour obtenir l’expression exacte de la fonction zeta de la jacobienne de courbes hyperelliptiques de genre 2 de la forme ci-dessus et de la forme Y^2 = X^6 + aX^3 + b. Nous avons obtenus les coefficients exacts des fonctions zeta par des calculs successifs (un peu techniques) de résolution d’équations de degré 2.
Les systèmes à bases de couplages utilisent des courbes elliptiques particulières présentant un petit degré de plongement par rapport à un grand sous-groupe d’ordre premier. Les formules explicites d’ordre des jacobiennes des deux familles de courbes hyperelliptiques ci-dessus permettent de construire des jacobiennes ayant les propriétés voulues pour une utilisation en cryptographie à base de couplages. Pour cela nous avons étendu les méthodes existantes dans le cas elliptique, à savoir la méthode de Cocks-Pinch et la méthode cyclotomique (ou de Brezing-Weng). Pour illustrer la faisabilité de notre méthode nous donnons quelques exemples pour un degré de plongement entre 5 et 35. La mesure de l’efficacité rho = 2 log p / log r est comprise entre 2.25 et 4.
Travail en collaboration avec Damien Vergnaud.
  • 23 novembre 2011 – Nicolas Estibals (Doctorant équipe CARAMEL – INRIA Nancy Grand-Est) : Implémentation matérielle de l’arithmétique de corps de caractéristique 2 et 3.
Résumé : La cryptographie sur courbes elliptiques et hyperelliptiques, et plus spécialement celle reposant sur les couplages, demande d’effectuer des calculs dans des corps finis de petites caractéristiques. Dès lors, développer des opérateurs matériels pour effectuer les opérations arithmétiques sur ces corps est un problème intéressant, que ce soit dans un but de performances (ces opérations sont mal supportées par les processeurs généralistes) ou pour obtenir des accélérateurs spécifiques pour les calculs cryptographiques.
Durant cet exposé, nous examinerons la représentation des éléments de corps finis de petites caractéristiques et la réalisation d’opérations sur ceux-ci afin de décrire un coprocesseur arithmétique pour corps finis. Parmi ces opérations, la plus coûteuse est la multiplication. C’est pourquoi nous montrerons différents algorithmes pour effectuer le produit et discuterons des différents compromis performance/consommation de ressources obtenus lors de l’implémentation matérielle de ceux-ci.
Travail en collaboration avec Jean-Luc Beuchat (LCIS, Université de Tsukuba, Japon) et Jérémie Detrey (Équipe-projet CARAMEL, INRIA Nancy Grand-Est).
  • 16 novembre 2011 – Cristian Calude (University of Auckland) : Is quantum randomness pseudo-randomness?
Abstract: This talk will present recent theoretical and experimental results contrasting quantum randomness with software-generated randomness.
  • 9 novembre 2011 – Louise Huot (doctorante LIP6) : Utilisation des symétries pour la résolution du problème de décomposition de points.
Résumé : Pour résoudre le DLP sur les courbes elliptiques définies sur un corps fini non premier K : extension de degré n de k, P. Gaudry a introduit un nouvel algorithme reposant sur le principe général du calcul d’indice. Une étape cruciale de cet algorithme nécessite de décomposer des points de la courbe E(K) selon une base de facteurs. C’est à dire, étant donné un point fixé R de E(K) trouver n points Pi, 1 ≤ i ≤ n, de la base de facteurs F ⊂ E(K) tels que R = P1 ⊕ … ⊕ Pn (1). Une méthode de résolution algébrique de ce problème consiste à modéliser l’équation (1) sous forme d’un système polynomial et de le résoudre. À cette fin, Semaev introduit les polynômes de sommation qui projettent le problème de décomposition de points sur l’axe des abscisses. L’application d’une restriction de Weil de K à k sur un tel polynôme de sommation engendre un système à coefficients dans k à n équations et n inconnues, dont la résolution est équivalente à celle du problème de décomposition de point. Le coût de la résolution de ces systèmes est exponentiel en n et elle devient rapidement impossible. Il est donc nécessaire d’optimiser la résolution de ces systèmes. Un moyen est d’utiliser les symétries du problème de décomposition de points. Une symétrie naturelle de ce problème, lié à la commutativité de la loi de groupe sur les points de la courbe, est l’action du groupe symétrique Sn. Dans cet exposé, nous mettrons en évidence des symétries supplémentaires. Nous étudierons en particulier deux représentations de courbes − les courbes d’Edwards et les intersections de Jacobi − dont les symétries se propagent sur les polynômes de sommation. Pour ces représentations, nous verrons également comment elles permettent de simplifier les systèmes polynomiaux à résoudre. Finalement nous présenterons quelques résultats pratiques montrant le gain apporté par l’utilisation des symétries.

Travail en collaboration avec Jean-Charles Faugère, Pierrick Gaudry et Guénaël Renault.
  • 12 octobre 2011 et 2 novembre 2011 – Jacques Patarin : Quelques généralisations transfinies du Théorème d’incomplétude de Gödel
Résumé : Que se passe-t-il dans les théorèmes d’incomplétude si l’on dispose d’ordinateurs « transfinis » c’est-à-dire capables de faire une infinité de calculs en 1 seconde ? Par infinité de calculs on désigne ici une quantité de calculs inférieure ou égale à alpha, et avec une mémoire inférieure ou égale à alpha, où alpha est un cardinal infini fixé, par exemple alpha égal aleph zero (le dénombrable) ou bien alpha égal le continu (le cardinal de l’ensemble des nombres réels). Ceci sera le sujet de notre exposé, où nous verrons qu’en fait à peu près tous les célèbres théorèmes d’incomplétude ou de limitation se généralisent dans ce cadre.
– Mercredi 12 octobre : présentation du théorème classique de Gödel et de résultats classiques de limitation sur les ordinateurs standards.
– Mercredi 2 novembre : généralisation au transfini, et, si on a le temps, discussion sur ce qui se passe sur les classes (au lieu des ensembles).
  • 6 octobre 2011 – Dimitar Jechtev (Post-doctoral LACAL -EPFL) : Hardness of Computing Individual Bits for Pairing-based One-way Functions
Abstract: We prove that if one can predict any of the bits of the input to a classical pairing-based one-way function with non-negligible advantage over a random guess then one can efficiently invert this function and thus, solve the Fixed Argument Pairing Inversion problem (FAPI-1/FAPI-2). The latter has implications for the security of various pairing-based schemes such as the identity-based encryption scheme of Boneh–Franklin, Hess’ identity-based signature scheme, as well as Joux’s three-party one-round key agreement protocol. Moreover, if one can solve FAPI-1 and FAPI-2 in polynomial time then one can solve the Computational Diffie–Hellman problem (CDH) in polynomial time. Our result implies that all the bits of the pairing-based one-way function are hard–to–compute, assuming that CDH is hard. Our argument uses a list-decoding technique via discrete Fourier transforms due to Akavia–Goldwasser–Safra.

This is joint work with Alexandre Duc.
  • 28 septembre 2011 – Jérôme Plût (Post-doctorant CRYPTO- UVSQ) : Modularité de familles de courbes elliptiques.
Résumé : Je présenterai des extensions du modèle quartique de Jacobi représentant des familles plus larges de courbes elliptiques, au prix de surcoûts dans les opérations d’addition. Ces formules d’additions sont unifiées sur un grand sous-groupe des points de ces courbes. Je donnerai également une caractérisation de ces familles de courbes par l’action du Frobenius sur les points de torsion, ce qui permet d’en obtenir un comptage asymptotique de façon particulièrement directe. Enfin, je montrerai comment cette caractérisation est une conséquence de la modularité de certaines familles de courbes elliptiques.
Séminaires CRYPTO 2011-2012