Séminaires 2014 - 2015

Nous organisons régulièrement un séminaire dédié à la cryptographie et à la sécurité informatique. Ce séminaire, ouvert à tous, a généralement lieu le mercredi matin de 11h à 12h en salle 301 du bâtiment Descartes. 

Pour intervenir dans celui-ci, en présentant vos recherches ou vos développements industriels, veuillez contacter Luca De Feo. Pour être tenu au courant des séances, veuillez vous inscrire à la liste de diffusion en visitant cette page, ou en envoyant un mail à  Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser..

2014-2015

  • 11 février 2015 - Alberto Battistiello (Oberthur, UVSQ). Common Points on Elliptic Curves: The Achille's heel of fault attack countermeasures.

    Elliptic curve cryptosystems offer many advantages over RSA-like cryptography, such as speed and memory saving. Nonetheless the advent of side-channel and fault-injection attacks mined the security of such implementations. Several countermeasures have been devised to thwart these threats, so that simple attacks on state-of-the-art secured implementations seem unlikely. We took up the challenge and show that a simple fault attack using a very relaxed fault model can defeat well known countermeasures. After introducing the notion of common points, we exhibit a new fault-injection attack that breaks state-of-the-art secured implementations. Our new attack is particularly dangerous since no control on the injected error is required and only one fault is sufficient to retrieve the secret.

  • 17 décembre 2014 - Alban Quadrat (INRIA). Une introduction à la théorie algébrique des systèmes et à l'automatique [transparents].

    Les systèmes interconnectés jouent un rôle de plus en plus important dans nos vies quotidiennes. La théorie mathématique des systèmes a pour but l'étude générale des systèmes (physiques, biologiques, économiques, …), de leurs interconnections et de leur contrôle. Dans cet exposé, nous donnerons une courte introduction à cette théorie pour les systèmes dynamiques définis par des équations différentielles ou de récurrence linéaires. En particulier, nous montrerons comment la théorie des modules permet de caractériser les propriétés importantes des systèmes de contrôle (contrôlabilité, observabilité, platitude, …) et de développer des lois de commande pour ces systèmes. Pour cela, nous serons amenés à étudier des aspects constructifs de la théorie des modules pour des anneaux d'opérateurs (opérateurs différentiels, opérateurs de décalage, opérateurs de retard). Ces résultats sont implémentables dans des systèmes de calcul formel tels que Maple ou Mathematica.

  • 10 décembre 2014 - Journée CLIC 2014 (Codes, Lattices, Ideals, Cryptograpy). Site web: idealcodes.github.io/clic-2014

  • 3 décembre 2014 - Henri Gilbert (ANSSI, UVSQ). Une représentation simplifiée de l'AES

    Je décrirai une représentation équivalente très simple de l'AES, dans laquelle deux tours consécutifs sont remplacés par la composée d'une transformation non-linéaire des colonnes et d'une transformation affine des lignes de la matrice 4×4 constituant le bloc courant.

    Afin d'illustrer l'utilité de cette représentation pour analyser certaines propriétés structurelles de l'AES, je montrerai que dans le cas d'AES-128, qui comporte 10 tours, la connaissance d'une clé aléatoire permet de construire des ensembles de 264 clairs "anormalement corrélés" aux chiffrés correspondants. La corrélation mise en évidence est non dépendante de la clé, mais très ténue.

    Ce résultat repose sur une amélioration du distingueur à clé connue contre 7 tours de l'AES publié par Knudsen et Rijmen en 2007. Il n'affecte en rien la sécurité de l'AES lorsque l'algorithme est paramétré par une clé secrète et employé à des fins de chiffrement ou d'authentification de message.

  • 26 novembre 2014 - Sonia Belaïd (Thales, ENS). Side-Channel Analysis of Multiplications in GF(2128): Application to AES-GCM. [transparents]

    In this paper, we study the side-channel security of the field multiplication in GF(2n). We particularly focus on GF(2128) multiplication which is the one used in the authentication part of AES-GCM but the proposed attack also applies to other binary extensions. In a hardware implementation using a 128-bit multiplier, the full 128-bit secret is manipulated at once. In this context, classical DPA attacks based on the divide and conquer strategy cannot be applied. In this work, the algebraic structure of the multiplication is leveraged to recover bits of information about the secret multiplicand without having to perform any key-guess. To do so, the leakage corresponding to the writing of the multiplication output into a register is considered. It is assumed to follow a Hamming weight/distance leakage model. Under these particular, yet easily met, assumptions we exhibit a nice connection between the key recovery problem and some classical coding and Learning Parities with Noise problems with certain instance parameters. In our case, the noise is very high, but the length of the secret is rather short. In this work we investigate different solving techniques corresponding to different attacker models and eventually refine the attack when considering particular implementations of the multiplication.

  • 19 novembre 2014 - Christophe Petit (University College London). On the quaternion ℓ-isogeny path problem.

    Let O be a maximal order in a definite quaternion algebra over ℚ of prime discriminant p, and a small prime. We describe a probabilistic algorithm, which for a given left O-ideal, computes a representative in its left ideal class of -power norm. In practice the algorithm is efficient, and subject to heuristics on expected distributions of primes, runs in expected polynomial time. This breaks the underlying problem for a quaternion analog of the Charles-Goren-Lauter hash function, and has security implications for the original CGL construction in terms of supersingular elliptic curves.

    The talk will be based on our ANTS 2014 paper, joint work with D Kohel, K Lauter and JP Tignol.

  • 12 novembre 2014 - Charles Bouillaguet (ULille 1). Systèmes de chiffrement par bloc minimalistes, obfuscation et implémentations en "boite blanche" [transparents]

    La plupart du temps, la sécurité des systèmes de chiffrement est évaluée en supposant que les adversaires interagissent avec le dispositif à travers une "interface", mais qu'ils n'ont pas le système de chiffrement sous la main pour étudier les détails de son fonctionnement interne. En effet, le fonctionnement de tels systèmes repose largement sur le fait qu'ils contiennent des informations secrètes (comme des clefs de chiffrement). Cette hypothèse est réaliste dans certains cas, par exemple si on communique avec un serveur web qui contient un mécanisme de chiffrement.

    Cependant, dans bon nombre de situations, on a sous la main une implémentation soit matérielle soit logicielle du dispositif cryptographique, dont on peut donc observer le fonctionnement... et tenter d'extraire les secrets. On s'intéresse ici à cette deuxième situation. Est-il possible de concevoir des mécanismes cryptographiques contenant des secrets, mais dont le code source serait publiquement distribuable ? C'est en principe l'objet de la cryptographie à clef publique, mais on s'intéresse ici plus particulièrement à des constructions à clef secrète.

    Le problème qui consiste à dissimuler des secrets cryptographiques dans du code source est un cas particulier du problème de l'obfuscation de programme, qui consiste à rendre incompréhensible et impossible à analyser le code de programmes arbitraires. Nous survolerons cette problématique dans l'exposé. Nous présenterons ensuite plusieurs systèmes de chiffrement par blocs, susceptibles de telles implémentations en boite-blanche. Ce sont pour certains des héritiers du système "2R" conçu par J. Patarin en 1997.

    Cet exposé est dérivé de l'article "Cryptographic Schemes Based on the ASASA Structure: Black-box, White-box, and Public-key", disponible à l'adresse : http://eprint.iacr.org/2014/474.pdf.

 Imprimer  E-mail

Séminaires 2013 -2014

Nous organisons régulièrement un séminaire dédié à la cryptographie et à la sécurité informatique. Ce séminaire, ouvert à tous, a généralement lieu le mercredi matin de 11h à 12h en salle 301 du bâtiment Descartes. 

Pour intervenir dans celui-ci, en présentant vos recherches ou vos développements industriels, veuillez contacter Luca De Feo. Pour être tenu au courant des séances, veuillez vous inscrire à la liste de diffusion en visitant cette page, ou en envoyant un mail à Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser..

2013-2014

  • 21 mai 2014 - Chrysanthi Mavromati (Sogeti, UVSQ). Attacks in the multi-users setting : applications to Even-Mansour and PRINCE

    The multi-user setting is a very interesting practical scenario, which is sometimes overlooked in cryptography. Indeed, cryptosystems are designed to be used by many users, and usually cryptographers prove the security of their schemes in a single-user model (except in some cases such as key exchange, public-key encryption and signatures). In this setting, the adversary tries to recover keys of many users in parallel more efficiently than with classical attacks, i.e., the number of recovered keys multiplied by the time complexity to find a single key, by amortizing the cost among several users.

    In this presentation, we will first show that in the multi-user Even-Mansour scheme, all keys of L=N1/3 users can be found with N1/3+ε queries for each user (where N is the domain size). We will also consider the PRINCE block cipher (with 128-bit keys and 64-bit blocks) and we will present an attack which finds the keys of 2 users among a set of 232 in time 265. Finally, we will also describe a new generic attack in the classical model for PRINCE.

    Joint work with Pierre-Alain Fouque and Antoine Joux.

  • 30 avril 2014 - Frédéric de Portzamparc (Gemalto, UPMC). Algebraic Cryptanalysis of McEliece-like cryptosystems with compact keys.

    Introduced in 1978, the McEliece cryptosystem is the first code-based cryptosystem and one of the oldest public-key cryptosystem. One of its drawbacks is the tremendous size of its public key. To overcome this difficulty, a trend in code-based cryptography was to find Goppa and alternant codes whose generator matrix admits symmetries so as to reduce the storage cost for the associated McEliece cryptosystems. Faugère, Otmani, Perret and Tillich showed at Eurocrypt'10 that the private key is the solution of an algebraic system. When the public matrix has symmetries, they proved that the corresponding algebraic system can be drastically simplified, so that its resolution may become feasible by computing Gröbner bases. For many instances of symmetric schemes, the system could be solved with the algorithm F5 in up to a few hours. However, none of the systems derived from binary codes could be solved in practice.

    We extend this work to all the symmetric parameters proposed so far. To do so, we introduce a completely new way of exploiting the symmetries in the algebraic attack. The idea is roughly to reverse the symmetrization process. It reduces the key-recovery to attacking a code of much smaller parameters. We also improve the algebraic modelization of the private key and the elimination technique used in the resolution. We show results of practical attacks for encryption schemes and signature schemes, both over binary and non-binary fields. For almost all parameters, the private key could be recovered in times between a few seconds and a few hours by using the Magma software. For instance, we were able to recover the private key of a signature scheme using a binary public code of length 215 and Goppa degree equal to 12 in only 5.4 seconds. For an encryption scheme defined over F7, with length 1813 and Goppa degree 49, the key recovery took 60 seconds.

    By this work, we challenge the very idea of using Goppa codes with symmetry for cryptographic use.

    Joint work with J.-C. Faugère, A. Otmani, L. Perret and J.-P. Tillich.

  • 22 janvier 2013 - Francisco Vial-Prado (UVSQ). Gentry's blueprint for fully homomorphic encryption schemes.

    We review Gentry's ideas that led to the first fully homomorphic encryption scheme in 2009. First, we describe this scheme based on ideal lattices, and its implementation. We propose new chosen ciphertext attacks that may be adapted to other primitives using lattices. Finally, we describe the state of art of FHE and the latest improvements.
  • 15 janvier 2013 - Jérôme Plût (ANSSI). New Insight into the Isomorphism of Polynomial Problem IP1S and its Use in Cryptography.

    Travail commun avec Gilles Macario-Rat (Orange) et Henri Gilbert (ANSSI).

    Le problème d'isomorphisme de polynômes IP1S est le suivant : étant données deux familles de polynômes (a_1,…,a_m) et (b_1,…,b_m) en n variables, calculer (s'il existe) un changement de variables linéaire transformant une famille en l'autre. Des instances difficiles de ce problème permettraient notamment de construire un schéma d'identification efficace.

    Dans ce travail, nous étudions la structure mathématique sous-jacente au cas de familles de deux polynômes homogènes de degré 2 et nous en déduisons un algorithme polynomial de résolution de la plupart des instances de IP1S. Nous utilisons pour cela des techniques légèrement différentes selon que le corps sous-jacent est de caractéristique impaire ou binaire.

  • 8 janvier 2013 - Rodolphe Lampe (UVSQ). Indifférentiabilité du schéma d'Even-Mansour Itéré.

    Le schéma d'Even-Mansour Itéré est un blockcipher qui alterne des XOR de clés aléatoires et l'application de permutations aléatoires publiques. Par exemple, pour 1 tour: E(x)k1P1(xk0) avec k0, k1 aléatoires et P1 aléatoire publique. Ce schéma reprend la structure de la majorité des blockciphers actuels (par exemple l'AES), il est donc intéressant d'étudier sa sécurité structurelle. Depuis quelques mois, de nombreux résultats sur son indistinguabilité (i.e. le caractère aléatoire des sorties) ont été découverts, ainsi que récemment un résultat d'indifférentiabilité (le caractère aléatoire des sorties en autorisant l'attaquant à choisir les clés) pour certains key-schedules. Dans cet exposé, je présenterai une preuve d'indifférentiabilité pour 12 tours avec des conditions plus acceptables sur le key-schedule.

  • 18 décembre 2013 - Benoît Cogliati (UVSQ). L'indistinguabilité du XOR de plusieurs bijections

    Étant donné k bijections pseudoaléatoires f1, …, fk sur {0,1}n, il est naturel de définir une fonction pseudoaléatoire en les XORant. S. Lucks a étudié la sécurité de cette fonction pseudoaléatoire. Nous améliorons les bornes de sécurité de son article en utilisant deux techniques de preuve : celle des coefficients H classique et la technique des coefficients Hsigma.

     

  • 11 décembre 2013 - Luca De Feo (UVSQ). Algorithms for F_p-bar

    Realizing in software the algebraic closure of a finite field F_p is equivalent to construct so called "compatible lattices of finite fields", i.e. a collection of finite extensions of F_p together with embeddings F_p^m ⊂ F_p^n whenever m | n.

    There are known algorithms to construct compatible lattices in deterministic polynomial time, but the status of the most practically efficient algorithms is still unclear. This talk will review the classical tools available, then present some new ideas towards the efficient construction of compatible lattices, possibly in quasi-optimal time.

  • 27 novembre 2013 - Jérémy Jean (ENS). Structural Evaluation of AES and Chosen-Key Distinguisher of 9-round AES-128.[transparents]

    While the symmetric-key cryptography community has now a good experience on how to build a secure and efficient fixed permutation, it remains an open problem how to design a key-schedule for block ciphers, as shown by the numerous candidates broken in the related-key model or in a hash function setting. Provable security against differential and linear cryptanalysis in the related-key scenario is an important step towards a better understanding of its construction.

    Using a structural analysis, we show that the full AES-128 cannot be proven secure unless the exact coefficients of the MDS matrix and the S-Box differential properties are taken into account since its structure is vulnerable to a related-key differential attack. We then exhibit a chosen-key distinguisher for AES-128 reduced to 9 rounds, which solves an open problem of the symmetric community. We obtain these results by revisiting algorithmic theory and graph-based ideas to compute all the best differential characteristics in SPN ciphers, with a special focus on AES-like ciphers subject to related-keys. We use a variant of Dijkstra's algorithm to efficiently find the most efficient related-key attacks on SPN ciphers with an algorithm linear in the number of rounds.

    The content of this talk is a joint work with Pierre-Alain Fouque and Thomas Peyrin, and appeared in a CRYPTO 2013 paper.

  • 23 octobre 2013 - Virginie Lallemand (INRIA). Amélioration des attaques différentielles sur KLEIN.

    L'apparition récente du besoin de sécuriser des supports de plus en plus miniaturisés tels que les cartes à puces et les puces RFID a amené la communauté cryptographique à concevoir des algorithmes spécifiques à bas coût.

    Ces nouveaux algorithmes doivent répondre à des contraintes spécifiques en matière de consommation d'énergie, de taille et de rapidité. KLEIN est une famille d'algorithmes proposée en 2011 par Gong, Nikova et Law pour répondre à ces besoins. La procédures de chiffrement est de type SPN et est basée sur 4 opérations de tour assez similaires à celles de l'AES, la grande différence résidant dans la taille des états et des boîtes S.

    Nous verrons dans cet exposé comment cette spécificité induit des faiblesses permettant de construire une cryptanalyse différentielle efficace et ainsi de casser KLEIN-64, la version à 64 bits de clef de KLEIN.

  • 16 octobre 2013 - Cécile Pierrot (UPMC). Crible spécial de corps de nombres dans les corps finis et application aux courbes elliptiques bien couplées.[transparents]

    Cet exposé porte sur un des deux problèmes de théorie des nombres sur lesquels reposent un grand nombre de protocoles cryptographiques actuels : le problème du logarithme discret. Nous nous intéressons ici à la résolution de ce problème dans les corps finis.

    L’objet de cet exposé est d’apporter un rapide aperçu des algorithmes actuels puis d'étendre le crible spécial de corps de nombres (SNFS), qui ne portait, jusqu’ici, que sur des corps de cardinal premier. Notre SNFS s’étend sur tout le domaine d’exécution du crible de corps de nombres général (NFS), et en améliore la complexité asymptotique. Il permet le calcul de logarithmes discrets dans des corps finis dont la caractéristique admet une représentation creuse adéquate, ce qui autorise son application sur des corps finis issus de procédés de couplage.

  • 9 octobre 2013 - Christina Boura (UVSQ). Revisiting Impossible Differential Attacks.[transparents]

    Impossible differential attacks are among the most powerful forms of cryptanalysis against block ciphers. These attacks have been extensively applied, however, due to the fact that they are highly technical, many points still remain unclear. The aim of this work is to formalize the complexity evaluation of such attacks, and propose improvements for many of the most crucial steps. We concentrate in particular on certain points of the complexity analysis that seem to be not so well understood and propose a general framework to clarify and improve them. In parallel, we develop and implement a tool for mounting impossible differential attacks on Feistel constructions. We describe this tool and present applications on two recent lightweight ciphers, LBlock and Simon. By applying our methods, we obtain the best current attacks on both of these ciphers.

    This is a joint-work Marine Minier, María Naya-Plasencia and Valentin Suder.

 

 Imprimer  E-mail

Séminaires 2015 -2016

Nous organisons régulièrement un séminaire dédié à la cryptographie et à la sécurité informatique. Ce séminaire, ouvert à tous, a généralement lieu le jeudi matin de 11h à 12h en salle 301 du bâtiment Descartes. 

Pour intervenir dans celui-ci, en présentant vos recherches ou vos développements industriels, veuillez contacter Luca De Feo. Pour être tenu au courant des séances, veuillez vous inscrire à la liste de diffusion en visitant cette page, ou en envoyant un mail à Cette adresse e-mail est protégée contre les robots spammeurs. Vous devez activer le JavaScript pour la visualiser..

2015-2016

  • 10 décembre2015 - Vincent Grosso (UCLouvain) Masquage pour la protection des chiffrements par bloc.

    Depuis la fin des années 90 les attaques par canaux auxiliaires sont une menace pour les implémentations cryptographiques. Ces attaques utilisent les observations de phénomènes physiques d’un appareil lors de l’exécution d’un programme cryptographique. Ces observations peuvent fournir de l’information sur la clef. Le masquage est une contre-mesure classique contre les attaques par canaux auxiliaires. L’idée du masquage est de rendre aléatoire l’état interne de l’appareil de telle façon que la combinaison de plusieurs observations devient nécessaire pour réaliser une attaque. Le masquage a un impact sur l’efficacité des implémentations. Dans cet exposé nous nous intéresserons à différentes techniques pour réduire le surcoût lié au masquage.

  • 3 décembre2015 - Sébastien Duval (INRIA Paris) Construction de S-Boxes à bas coût par des réseaux Feistel et MISTY

    En chiffrement symétrique, l'une des approches classiques est de chiffrer les messages par blocs de bits. Dans ce contexte, C. Shannon a établi des critères de sécurité appelés confusion et diffusion. La confusion est généralement obtenue par des fonctions non-linéaires, aussi appelées S-Boxes.

    L'une des problématiques de la cryptographie actuelle est la popularisation de machines aux moyens très restreints, comme par exemple les puces RFID. Ces environnements ajoutent aux critères de sécurité un critère de coût. Malheureusement, les chiffrements usuels comme le standard AES ont un coût d'implémentation généralement trop élevé pour de tels moyens. La majorité du coût d'implémentation se situe dans la S-Box, et il est donc naturel de tenter d'implémenter des S-Boxes à bas coût.

    La difficulté majeure des S-Boxes classiques comme celle de l'AES est leur taille : ces fonctions travaillent sur 8 bits, et il est difficile d'étudier (et coûteux d'implémenter) des fonctions non-linéaires de GF(2⁸) dans GF(2⁸). Utiliser des S-Boxes de taille plus petite est envisageable mais impose de nouvelles contraintes.

    Dans mes travaux, j'ai étudié un compromis : construire des S-Boxes de 8 bits à partir de S-Boxes de 4 bits. L'avantage est que les S-Boxes de 4 bits sont peu chères à implémenter et beaucoup plus simples à étudier. Pour passer de S-Boxes de 4 bits à des S-Boxes de 8 bits en garantissant une bonne sécurité, plusieurs structures existent. J'ai étudié les deux structures offrant un coût peu élevé : les réseaux de Feistel et les réseaux MISTY.

    Mes travaux apportent de nouveaux résultats théoriques sur la sécurité des réseaux de Feistel et des réseaux MISTY face aux attaques statistiques classiques (différentielles et linéaires), entre autres des conditions nécessaires pour construire à bas coût des fonctions de 8 bits offrant une bonne sécurité à partir de fonctions de 4 bits. Grâce à ces résultats théoriques, j'ai pu obtenir des implémentations pratiques de S-Boxes de 8 bits avec une excellente sécurité et un coût d'implémentation faible, plus performantes que les S-Boxes utilisées à l'heure actuelle dans les chiffrements par blocs.

  • 26 novembre 2015 - Aurore Guillevic (INRIA Saclay, LIX) Individual discrete logarithms in non-prime finite fields with the NFS algorithm

    This talk is about computing discrete logarithms in non-prime finite fields. These fields arise in pairing-based cryptography. In this setting, the pairing-friendly curve is defined over GF(q) and the pairing takes its values in an extension GF(qk), where k is the embedding degree.

    For example, GF(p2) is the embedding field of supersingular elliptic curves in large characteristic; GF(p3), GF(p4), GF(p6) are the embedding fields of MNT curves, and GF(p12) is the embedding field of the well-known Barreto-Naehrig curves. In small characteristic, GF(24n), GF(36m) are considered.

    To compute discrete logarithms in these fields, one uses the Number Field Sieve algorithm (NFS) in large characteristic (e.g. GF(p2)), the NFS-High-Degree variant (NFS-HD) in medium characteristic (e.g. GF(p12)) and the Quasi Polynomial-time Algorithm (QPA) in small characteristic when applicable. These algorithms are made of four steps: polynomial selection, relation collection, linear algebra modulo the prime order of the target group and finally, individual logarithm computation.

    All these finite fields are extensions, hence have subfields. We use their structure to speed-up the individual discrete logarithm computation. We obtain an important speed-up in practice and the best case is when the embedding degree k is even. We will illustrate the improvements with the practical case of GF(p4) with p4 of 400 bits (120 decimal digits).

  • 26 novembre 2015 - Cécile Pierrot (UPMC) Simplified Settings for Discrete Logarithms in Small Characteristic Finite Fields

    Public key cryptography is based on hard problems, such as the discrete logarithm problem (DLP). In this talk, I focus on the discrete logarithm problem in finite fields:

    Given GF(q^k) and a generator g of GF(q^k)*, we say that we solve the DLP in GF(q^k) if, for any arbitrary element h in GF(q^k)*, we are able to recover an integer x such that: g^x = h.

    When the characteristic is small compared to the extension degree, the best complexity that can be achieved is quasipolynomial in log(q^k). I present here a simplified version of this quasipolynomial algorithm that has several advantages:

    1. I swear it is simple, or at least I will do my best to make it understandable.
    2. Together with additional ideas, simplifying the original settings permits to decrease the complexity of relation collection, linear algebra and extension phases, that dominate in practice all discrete logarithms computations. Namely, the complexity is reduced from O(q^7) to O(q^6).
    3. With our simplified settings, the complexity achieved in the general case became similar to the complexity known for Kummer (or twisted Kummer) extensions. Thus it permitted to achieve a discrete log computation in GF_(3^(5*497)), that is not only the highest cardinality reached in characteristic 3, but also not a special extension field as previous target fields were.

    This is a joint work with Antoine Joux.

 Imprimer  E-mail

Séminaires 2012 -2013

2012-2013

  • 19 juin 2013 - Cyril Hugounenq (UVSQ). Étude de l'action du Frobenius sur les volcans de l-isogénies.

    On va d'abord introduire et voir les structures de volcan de ℓ-isogénie. Ensuite on va voir le lien entre la structure de ℓ-torsion d'une courbe et le volcan de l-isogénie. On va présenter notre objectif d'amélioration de l'algorithme de Couveignes. Enfin on va étudier l'action de l'endomorphisme de Frobenius sur les volcans de ℓ-isogénie et voir les pistes/opportunités qui s'ouvrent/se ferment à nous, le tout en regardant si cela a un apport pour l'algorithme de Couveignes.

  • 22 mai 2013 - Jacques Patarin (UVSQ). Sécurité du XOR de deux bijections.

    On dispose de deux boîtes noires. L'une calcule une fonction aléatoire de n bits vers n bits. L'autre calcule f XOR g où f et g sont deux bijections aléatoires indépendantes de n bits vers n bits. On peut choisir les entrées de façon adaptative et observer les sorties (attaque CPA-2). On dispose d'une puissance de calcul infinie mais on est limité à q messages. Jusqu'à quelle valeur de q la probabilité de distinguer les 2 boîtes est-elle négligeable ?

    Dans cet exposé nous verrons que la réponse est de 'dre de q voisin de 2n. Mais plus que le résultat, c'est la méthode de preuve qui sera intéressante. En effet ce problème "simple et pur" est une bonne introduction à la "théorie des miroirs" (évaluation du nombre de solutions de systèmes d'égalité et de non égalité linéaires dans les corps finis), et à ses difficultés. Cette méthode peut ensuite s'appliquer à de très nombreux autres systèmes cryptographiques (comme les divers schémas de Feistel).

  • 24 avril 2013 - Malika Izabachene (LORIA). Structural Lattice Reduction and Application to Average Hardness

    Lattice based cryptography is supported by worst-case to average-case reductions for the SIS and LWE problems, showing that if there exists any hard instance of a lattice reduction then almost all lattice instances are hard in average. In all such reductions, the average case problem instance refers to a special class of lattices related to the group structure G=Zqn. In this talk, we consider more general classes of random lattices where G can be any sufficiently large finite abelian group and show that worst-case to average-case reduction is still preserved in this case. To achieve this, we will introduce a novel group generalization of lattice reduction called structural lattice reduction.

    This a a joint work with Nicolas Gama and Phong Nguyen.

  • 24 avril 2013 - Bastien Vayssière (UVSQ). Design of Key Schedule and Related-key Slide Attacks

    In the recent years, the design of several lightweight block ciphers has reduced the key schedule to an affine function, or even no key schedule at all. It raises the question: how much can we reduce the key schedule in the design of a secure block cipher? Resistance to slide attacks is a minimal requirement, since for a wide class of block ciphers, these attacks cannot be thwarted only with a strong round function. We analyze the class RXP of affine key schedules based on xors, rotations, and a bit permuted choice. The linearity of those key schedules permits to prove the resistance against single-key and related-key slide attacks.

  • 19 avril 2013 - Dario Fiore (MPI-SWS). Publicly Verifiable Delegation of Large Polynomials and Matrix Computations.

    Outsourced computations (where a client requests a server to perform some computation on its behalf) are becoming increasingly important due to the rise of Cloud Computing and the proliferation of mobile devices. Since cloud providers may not be trusted, a crucial problem is the verification of the integrity and correctness of such computation, possibly in a public way, i.e., the result of a computation can be verified by any third party, and requires no secret key - akin to a digital signature on a message.

    In this talk I will present new protocols for publicly verifiable secure outsourcing of Evaluation of High Degree Polynomials and Matrix Multiplication. Compared to previously proposed solutions, ours improve in efficiency and offer security in a stronger model and under standard assumptions. Moreover, we propose the first solutions that can easily handle operations over finite fields of any prime characteristic, most notably small fields (such as F2). Towards solving this problem we formalized a new cryptographic primitive, called Algebraic One-Way Function, which turned out to be useful to solve open problems in other cryptographic areas, such as linearly-homomorphic signatures and identification protocols.

    This is based on works joint with D. Catalano, R. Gennaro and K. Vamvourellis.

  • 1 mars 2013 - Gaëtan Leurent (UCL). Differential Attacks against ARX Designs.[transparents]

    In this talk, we study differential attacks against ARX schemes. We build upon the generalized characteristics of de Cannière and Rechberger; we introduce new multi-bit constraints to describe differential characteristics in ARX designs more accurately, and quartet constraints to analyze boomerang attacks. We also describe an efficient way to propagate those constraints.

    We have developed a set of tools for the analysis of ARX primitives based on this set of constraints. We show that the new constraints are more precise than what was used in previous works, and can detect several cases of incompatibility. In particular, we show that several published attacks are in fact invalid because the differential characteristics cannot be satisfied. This highlights the importance of verifying differential attacks more thoroughly.

    Moreover, we are able to build automatically complex non-linear differential characteristics for reduced versions of the hash function Skein. We describe several characteristics for use in various attack scenarios; this results in attacks with a relatively low complexity, in relatively strong settings. In particular, we show practical free-start and semi-free-start collision attacks for 20 rounds and 12 rounds of Skein-256, respectively.

  • 30 janvier 2013 - Daniel Augot (LIX et INRIA Saclay). Les connexions entre le logarithme discret sur les corps finis non premiers et le décodage des codes de Reed-Solomon. [transparents]

    En commun avec François Morain.

    Cheng et Wan étudient depuis 2004 comment le logarithme discret sur les corps non premiers se réduit à un certain problème de décodage des codes de Reed-Solomon. Leur objectif est de prouver la difficulté du décodage des codes de Reed-Solomon, en présence d'un grand nombre d'erreurs, sous l'hypothèse que le logarithme discret est difficile. Nous nous sommes proposés d'étudier la réduction dans un sens direct : comment utiliser des algorithmes de décodage connus pour construire un algorithme de calcul de logarithmes discrets sur les corps finis. La méthode se situe dans le contexte général de calcul de bases d'index, où la technique de découverte de relations repose sur le décodage. Dans un premier temps, nous avons utilisé des algorithmes de décodage unique, comme celui de Gao, par opposition au décodage en liste. Ces méthodes ont été implantées en Magma et NTL. Bien que cette méthode ne semble pas aussi performante que les méthodes classiques à la Adleman, il y a toutefois de nombreuses thématiques originales qui émergent.

    Nous ferons aussi le point sur la difficulté du décodage des codes de Reed-Solomon.

  • 23 janvier 2013 - Romain Basson (IRMAR). Algèbre d'invariants des formes binaires en caractéristique positive. [transparents]

    Le développement d'une algorithmique pour les espaces de modules de courbes hyperelliptiques (en petit genre) peut s'envisager via la théorie classique des invariants des formes binaires ; une courbe hyperelliptique de genre g étant simplement reliée à une forme binaire de degré 2g+2. La description et la construction effective de ces algèbres d'invariants en caractéristique nulle ont débuté dans la seconde moitié du XIXème siècle, donnant d'ailleurs naissance aux prémices de l'algèbre commutative, et culminé en 1967 avec le résultat de Shioda concernant les octiques (qualifié de "tour de force" par Mumford !). En revanche, le cas des petites caractéristiques positives reste largement ouvert, notamment pour les octiques. Ainsi, après avoir donné un aperçu de la théorie classique, j'exposerai les résultats actuels concernant les algèbres de formes octiques en petites caractéristiques positives.

  • 9 janvier 2013 - Pierre-Jean Spaenlehauer (University of Western Ontario). Bases de Gröbner de systèmes structurés et applications en Cryptologie.[transparents]

    Pour de nombreuses applications en Cryptologie, en Géométrie Réelle ou en Optimisation, il est essentiel d'avoir des estimations précises de la complexité de résolution de systèmes polynomiaux multi-homogènes, déterminantiels et booléens.

    Dans cet exposé, par des méthodes de type bases de Gröbner et sous des hypothèses de généricité sur les coefficients de ces systèmes, je présente de nouvelles bornes de complexité asymptotique :

    • pour les systèmes déterminantiels et bilinéaires, ces bornes permettent d'identifier des sous-familles de systèmes pour lesquelles la complexité de résolution est polynomiale en le nombre de solutions ;
    • pour les systèmes quadratiques booléens, un nouvel algorithme de résolution est proposé. Pour un système de n équations en n variables, l'espérance de la complexité d'une variante probabiliste est O(2^(0.792 n)), sous des hypothèses algébriques sur le système d'entrée. Ceci permet de résoudre ces systèmes exponentiellement plus rapidement que par recherche exhaustive (de complexité 4 log(n) 2^n).

    L'obtention de ces bornes passe par une analyse de la structure algébrique de ces systèmes ; ceci conduit à des formules explicites pour la série de Hilbert générique des idéaux associés.

    Enfin, je présenterai des applications de ces résultats à l'analyse de la sécurité des cryptosystèmes MinRank, HFE et QUAD.

    Travaux commun avec Jean-Charles Faugère et Mohab Safey El Din (systèmes déterminantiels et multi-homogènes) et avec Magali Bardet, Jean-Charles Faugère et Bruno Salvy (systèmes booléens).

  • 28 novembre 2012 - Sorina Ionica (ENS). Endomorphism rings of genus 2 jacobians.

    Algorithms for computing the endomorphism ring of a small dimension abelian variety rely on the exploration of the isogeny graph. Using Galois cohomology, we relate the endomorphism ring structure to certain properties of the ell-Tate pairing, such as non-degeneracy on subgroups of the ell-torsion giving kernels of isogenies of principally polarized abelian varieties in the ell-isogeny graph. In genus 2, we derive an efficient method to check whether the jacobian has locally maximal endomorphism ring at ell. We also present an algorithm to compute horizontal ell-isogenies starting from a jacobian with maximal endomorphism ring. No nice pictures of isogeny graphs this time, sorry!

  • 14 novembre 2012 - Rodolphe Lampe (PRiSM). L'indistinguabilité du schéma d'Even-Mansour itéré.

    We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to O(N^2/3) queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(N^t/(t+1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries:

    1. for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of O(N^t/(t+1)) queries;
    2. for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to O(N^t/(t+2)) queries (for t even). This improves previous results for t ≥ 6.

    Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.

  • 7 novembre 2012 - Emmanuel Fouotsa (Université de Bamenda et IRMAR). Sur un modèle d'Edwards de courbe elliptique défini en toutes caractéristiques.[transparents]

    En 2007, Edwards a introduit un modèle de courbe elliptique défini sur les corps finis de caractéristique différente de 2, avec une loi de groupe non complète. Cette lacune sera comblée en 2008 par Bernstein et al. qui généralisent ce modèle. Toutefois, ce modèle reste défini en caractéristique différente de deux. Entre 2008 et 2009, des modèles binaires vont être proposés mais la relation avec le modèle original reste mystérieuse. Dans cet exposé, je présente un nouveau modèle d'Edwards défini en toutes caractéristiques, et qui est isomorphe au modèle original en caractéristique différente de 2. L'obtention de ce modèle et la loi de groupe se fait grâce aux fonctions théta. En particulier, ce nouveau modèle présente une arithmétique efficace et compétitive en caractéristique 2 et sur la ligne de Kummer, comparativement aux autres modèles de courbes elliptiques.

 

 

 

 

 Imprimer  E-mail

DMC Firewall is a Joomla Security extension!