-
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: 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
-
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
-
Jeudi 26 mai 2016 10:30–11:30 – Jérôme Plût – ANSSI
Une attaque en récupération de clé contre le schéma ASASA avec expansion de message
Résumé : La construction ASASA (Biryukov, Bouillaguet, Khovratovich 2014) est une tentative de rapprocher la cryptographie symétrique et asymétrique. Ce chiffrement symétrique utilise des boîtes S définies par des polynômes quadratiques afin de proposer également une implémentation « en boîte-blanche » et une version asymétrique du chiffrement. Une particularité de la construction est l’expansion de message : un clair de 128 bits devient un chiffré de 512 bits.
Nous présenterons une cryptanalyse totale de la construction ASASA, récupérant la clé secrète à partir de la clé publique seule. Cette attaque utilise uniquement des outils simples (algèbre linéaire). De façon intéressante, elle peut s’interpréter à la fois comme une cryptanalyse différentielle, ou comme des différentielles algébriques, et pourrait donc intéresser les spécialistes de cryptographie symétrique aussi bien qu’asymétrique.(travail commun avec H. Gilbert et J. Marim-Treger)
Lieu : Bât. Descartes, Salle 301
-
Jeudi 26 mai 2016 11:45–12:45 – Yann Rotella – INRIA Paris
Des nouvelles attaques sur les registres filtrés exploitant la structure des corps finis
Résumé : Les registres filtrés sont vulnérables à des attaques bien connues, ce qui impose de prendre en considération des critères de sécurité classiques sur les fonctions booléennes utilisées dans ce type de chiffrement. En 2005, Ronjom et Cid ont exhibé des classes équivalentes de générateurs filtrés. Dans nos travaux, nous avons regardé l’impact de ces équivalences non-linéaires sur les critères classiques connus. Notre principale contribution a été de monter une nouvelle attaque en utilisant la structure des corps finis et une technique de type « diviser pour régner », ce qui peut paraître surprenant étant donné que notre cryptosystème n’est composé que d’un unique état interne.
Lieu : Bât. Descartes, Salle 301
-
Jeudi 2 juin 2016 11:00–12:00 – Christophe Petit – Oxford
Recent advances in Elliptic Curve Discrete Logarithm algorithms
Résumé : The elliptic curve discrete logarithm problem (ECDLP) is one of the core number theory problems used in cryptography today. The elliptic curve discrete logarithm problem is believed to be much harder than the discrete logarithm problem over finite fields and the factorization problem, as the best attacks for commonly used parameters are still generic DLP algorithms. As key sizes in applications are chosen accordingly, it is important to understand the exact hardness of ECDLP.
In this talk, I will review recent advances in solving this problem using index calculus algorithms, starting from the work of Semaev in 2004. As it happens, we now have subexponential (in L(2/3) time) algorithms for special families of parameters, but these parameters are however not really used in practice. I will then show how these algorithms can potentially be adapted to elliptic curves defined over binary fields of prime degree extensions and to elliptic curve defined over prime fields (the two families that appear in standards and applications), and I will describe remaining challenges in improving both their complexity and their analysis.Lieu : Bât. Descartes, Salle 301