Partenaires





« octobre 2017 »
L M M J V S D
25 26 27 28 29 30 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 1 2 3 4 5

Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Séminaires et journées internes > Séminaires de CRYPTO > Séminaires CRYPTO 2015-2016

Agenda

séminaire

    • Jeudi 26 novembre 2015 11:00-12:00 - Cécile Pierrot - UPMC

      Cécile Pierrot (UPMC) Simplified Settings for Discrete Logarithms in Small Characteristic Finite Fields

      Résumé : 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.
      • 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).
      • 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\cdot 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.


    • Jeudi 26 novembre 2015 11:00-12:00 - Aurore Guillevic - INRIA Saclay, LIX

      Individual discrete logarithms in non-prime finite fields with the NFS algorithm

      Résumé : 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).


    • Jeudi 3 décembre 2015 11:00-12:00 - Sébastien Duval - INRIA Paris

      Construction de S-Boxes à bas coût par des réseaux Feistel et MISTY

      Résumé : 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.


    • Jeudi 10 décembre 2015 11:00-12:00 - Vincent Grosso - UCLouvain

      Masquage pour la protection des chiffrements par bloc

      Résumé : 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.

      Lieu : Batiment Descartes, salle 301


    • Jeudi 18 février 2016 11:00-12:00 - Nicolas Courtois - University College London

      How to Compute Private Keys In Bitcoin

      Résumé : We study various methods which allow us to recover thousands of ECDSA private keys in bitcoin blockchain. In particular we explain our work on cracking brain wallets and accelerating the elliptic curve computations in secp256k1, and a number of advanced combination attacks which operate on a certain graph, and can in addition benefit from HD wallet key management method in order to break, if certain events occur, up to all keys in up to whole larger security domains.

      Lieu : Bât. Descartes, Salle 301

      Notes de dernières minutes : Transparents : http://www.nicolascourtois.com/bitcoin/paycoin_dig_sign_combination_attacks_cold_storage_3d.pdf


    • Jeudi 24 mars 2016 11:00-12:00 - Dhiman Saha - IIT Kharagpur

      Key Recovery Attack against 2.5-round π-Cipher

      Résumé : This work presents a guess and determine attack against some variants of π-Cipher which is a second round candidate of the on-going CAESAR competition for authenticated ciphers. The attack exploits low diffusion in the internal permutation when reduced to 2.5 rounds. The ideas presented manage to exploit the parallel structure to extract the common internal state which finally leads to a key-recovery. In general for variants with ω-bit words the attack has a time complexity of little higher that 2^ω and requires only one known plaintext with at least 16ω blocks. This translates to a attack with time complexity 2⁷² against the variant π16-Cipher096 (using 16-bit words) reduced to 2.5 rounds, while the authors claim 96 bits of security with 3 rounds in their second-round submission. This implies a very limited security margin for this variant of π-Cipher.
      The attack can also be applied to lightweight variants that are not included in the CAESAR proposal, and use only two rounds. The lightweight variants π16-Cipher096 and π16-Cipher128 claim 96 bits and 128 bits of security respectively, but our attack can break the full 2 rounds with complexity 2⁷².
      Finally, the attack can be applied to reduced versions of two more variants of π-Cipher that were proposed in the first-round submission with 4 rounds : π16-Cipher128 (using 16-bit words) and π32-Cipher256 (using 32-bit words). The attack on 2.5 rounds has complexity 2⁷² and 2¹³⁷ respectively, while the security claim for 4 rounds are 128 bits and 256 bits of security.
      This is a joint work with Christina Boura, Avik Chakraborti, Gaëtan Leurent, Goutam Paul, Hadi Soleimany and Valentin Suder.
      Télécharger les transparents de l’exposé.

      Lieu : Bât. Descartes, Salle 301


    • Jeudi 31 mars 2016 11:00-12:00 - Cyril Hugounenq - UVSQ

      Calcul d’isogénies en temps quadratique à l’aide de volcans d’isogénies

      Résumé : Le but de ce travail conjoint avec Luca De Feo, Jérôme Plût et Eric Schost est de résoudre le problème suivant :
      Soient E, E’ deux courbes elliptiques que l’on sait r-isogènes, on veut alors calculer la r-isogénie en un temps quadratique en r.
      Couveignes [1994] avait proposé un algorithme permettant de résoudre ce problème en temps quasi quadratique, cependant celui-ci était exponentiel en p la caractéristique du corps sur lequel étaient définies les courbes elliptiques. En effet Couveignes interpolait l’isogénie en considérant les groupes cycliques de p^k-torsion et prenait en compte pour l’interpolation la loi de groupe.
      Notre approche est de travailler avec la ℓ^k torsion, cependant si l’on fait cela naïvement on aura alors un trop grand nombre d’essais d’interpolation à considérer. L’exposé va donc montrer comment à l’aide des volcans d’isogénie résoudre ce problème à faible coût.
      Les volcans d’isogénie ont été introduit par Eric Kohel dans sa thèse [1996], puis ont été étudiés notamment par Fouquet et Morain [2001] afin de trouver des algorithmes qui permettent de décrire la structure du volcan. Une étude sur le lien entre le volcan et la structure algébrique de la courbe a été faite notamment par Miret, Moreno, Sadornil, Tena et Valls [2005] ou encore Ionica et Joux [2010], qui ont amélioré dans certains cas l’algorithme de Fouquet et Morain.
      L’exposé va présenter dans un premier temps les volcans de ℓ-iosgénies, le lien entre le niveau d’une courbe dans le volcan et sa structure algébrique d’après les travaux de Miret, Moreno, Sadornil, Tena, Valls, et Ionica, Joux.
      Dans un deuxième temps on va voir comment l’on peut trouver des informations sur le volcan à l’aide de l’étude de l’action du Frobenius sur la ℓ^∞-torsion. On verra alors comment considérer un ensemble restreint de points à interpoler.
      Si le temps le permet l’exposé abordera comment prendre avantage des constructions de tours 2-adiques (ℓ-adique) d’après le travail de Doliskani-Schost [2015], afin de réduire le coût de l’interpolation.

      Lieu : Bât. Descartes, Salle 301


    • Jeudi 14 avril 2016 11:00-12:00 - Thomas Camus - UJF

      Algorithmique des réseaux sur un anneau d’entiers algébriques

      Résumé : Les réseaux sur un anneau d’entiers algébriques (ou réseaux algébriques) sont une généralisation de la notion de ℤ-réseau euclidien. Nous présenterons quelques résultats théoriques et algorithmiques qui prolongent les propriétés classique des ℤ-réseaux. Nous insisterons notamment sur la détermination des automorphismes d’un réseau algébrique.

      Lieu : Bât. Descartes, Salle 301Les réseaux sur un anneau d'entiers algébriques (ou réseaux algébriques) sont une généralisation de la notion de ℤ-réseau euclidien. Nous présenterons quelques résultats théoriques et algorithmiques qui prolongent les propriétés classique des ℤ-réseaux. Nous insisterons notamment sur la détermination des automorphismes d'un réseau algébrique.


    • Jeudi 21 avril 2016 11:00-12:00 - Ilaria Chilotti - UVSQ

      An homomorphic LWE based E-voting Scheme

      Résumé : I’ll present a new post-quantum electronic-voting protocol. This work is the result of a collaboration with Nicolas Gama, Mariya Georgieva and Malika Izabachène. Our construction is based on LWE fully homomorphic encryption and the protocol is inspired by existing e-voting schemes, in particular Helios. The strengths of our scheme are its simplicity and transparency, since it relies on public homomorphic operations. Furthermore, the use of lattice-based primitives greatly simplifies the proofs of correctness, privacy and verifiability, as no zero-knowledge proof are needed to prove the validity of individual ballots or the correctness of the final election result. The security of our scheme is based on classical SIS/LWE assumptions, which are asymptotically as hard as worst-case lattice problems and relies on the random oracle heuristic. We also propose a new procedure to distribute the decryption task, where each trustee provides an independent proof of correct decryption in the form of a Publicly Verifiable Ciphertext Trapdoor. In particular, our protocol requires only two trustees, unlike classical proposals using threshold decryption via Shamir’s secret sharing.

      Lieu : Bât. Descartes, Salle 301


    • Pages 1 | 2

Ajouter un événement iCal

Cliquer sur "avec résumé" pour tout dérouler.


Mots-clés

Cryptographie

Dhiman Saha - Key Recovery Attack against 2.5-round π-Cipher - 7.8 Mo

transparents de l’exposé