-
Vendredi 27 octobre 2017 11:00–12:00 – Alexandre Gélin – UVSQ
Calcul de Groupes de Classes d’un Corps de Nombres et Applications à la Cryptologie
Résumé : Dans cet exposé, nous nous intéressons au calcul du groupe de classes d’un corps de nombres. Nous débutons par décrire un algorithme de réduction du polynôme de définition d’un corps de nombres. Il existe une infinité de polynômes qui définissent un corps de nombres fixé, avec des coefficients arbitrairement gros. Notre algorithme calcule celui qui a les plus petits coefficients. L’avantage de connaître un petit polynôme de définition est qu’il simplifie les calculs entre éléments de ce corps de nombres, en impliquant des quantités plus petites. En outre, la connaissance d’un tel polynôme permet l’utilisation d’algorithmes plus efficaces que dans le cas général pour calculer le groupe de classes.
L’algorithme général pour calculer la structure du groupe de classes repose sur la réduction d’idéaux, vus comme des réseaux. Nous décrivons et simplifions l’algorithme présenté par Biasse et Fieker en 2014 à ANTS et approfondissons l’analyse de complexité. Nous nous sommes aussi intéressés au cas des corps de nombres définis par un polynôme à petits coefficients. Nous décrivons un algorithme similaire au crible par corps de nombres (NFS) dont la complexité en fonction des paramètres du corps de nombres peut atteindre L(1/3).
Enfin, nos algorithmes peuvent être adaptés pour résoudre un problème lié : le Problème de l’Idéal Principal. Étant donné n’importe quelle base d’un idéal principal (généré par un seul élément), nous sommes capables de retrouver ce générateur. Cette application de nos algorithmes fournit une attaque efficace contre certains schémas de chiffrement homomorphe basés sur ce problème.Lieu : Bât. Descartes, Salle 301
-
Vendredi 15 décembre 2017 11:00–12:00 – Christina Boura – UVSQ
Two Notions of Differential Equivalence on Sboxes
Résumé : The security of symmetric constructions, such as block ciphers and hash functions, heavily relies on the choice of the Sboxes, whose main role is to provide non-linearity. In this work we discuss two notions of differential equivalence on Sboxes. First, we introduce the notion of DDT-equivalence which applies to vectorial Boolean functions that share the same difference distribution table (DDT). Next, we compare this notion, to what we call the γ-equivalence, applying to vectorial Boolean functions whose DDTs have the same support. We discuss the relation between these two equivalence notions and show how they behave for two classical equivalences for vectorial Boolean functions, namely the Affine Equivalence and the CCZ equivalence. We provide further an algorithm for computing the DDT-equivalence and the γ-equivalence classes for a given function and we study the sizes of these classes for some important families of Sboxes. Finally, we prove a result that shows that the rows of the DDT of an APN permutation are pairwise distinct.
This is a joint work with Anne Canteaut, Jérémy Jean and Valentin Suder.Lieu : Bât. Descartes, Salle 301
-
Vendredi 19 janvier 2018 11:00–12:00 – Xavier Bonnetain – Inria Paris
Quantum Key-Recovery on AEZ
Résumé : AEZ is an authenticated encryption algorithm, candidate in the CAESAR competition. While some classical analysis on the algorithm have been published, the cost of these attacks is beyond the security claimed by the designers.
In this talk, I’ll present how all the versions of AEZ are completely broken against a quantum adversary, using a generalisation of Simon’s quantum algorithm for period finding.Lieu : Bât. Descartes, Salle 301
-
Vendredi 2 février 2018 11:00–12:00 – Anand Narayanan – LIP6
Nearly linear time encodable codes beating the Gilbert-Varshamov bound
Résumé : Error-correcting codes enable reliable transmission of information over an erroneous channel. One typically desires codes to transmit information at a high rate while still being able to correct a large fraction of errors. However, rate and relative distance (which quantifies the fraction of errors corrected) are competing quantities with a trade off. The Gilbert-Varshamov bound assures for every rate R, relative distance D and alphabet size Q, there exists an infinite family of codes with R + H_Q(D) >= 1-\epsilon. Constructing codes meeting or beating the Gilbert-Varshamov bound remained a long-standing open problem, until the advent of algebraic geometry codes by Goppa. In a seminal paper, for prime power squares Q ≥ 7², Tsfasman-Vladut-Zink constructed algebraic geometry codes beating the Gilbert-Varshamov bound. A rare occasion where an explicit construction yields better parameters than guaranteed by randomized arguments ! For codes to find use in practice, one often requires fast encoding and decoding algorithms in addition to satisfying a good trade off between rate and minimum distance. A natural question, which remains unresolved, is if there exist linear time encodable and decodable codes meeting or beating the Gilbert-Varshamov bound. In this talk, I shall present the first nearly linear time encodable codes beating the Gilbert-Varshamov bound, along with a nearly quadratic decoding algorithm. Time permitting, applications to secret sharing, explicit construction of pseudorandom objects and the like will also be discussed.
The talk will be based on joint work with Matthew Weidner (Caltech). A preprint is available here https://arxiv.org/abs/1712.10052Lieu : Bât. Descartes, Salle 301
-
Mardi 10 avril 2018 14:00–15:00 – Ferdinand Sibleyras – Inria Paris
The Missing Difference Problem, and its Applications to Counter Mode Encryption
Résumé : The widely deployed counter mode (CTR) is known for its efficiency and simplicity as it comes with a security proof that guarantees no attack up to the birthday bound and a matching distinguishing attack. However, unlike in CBC mode, a ciphertext collision in CTR mode hardly reveals anything to the attacker. Therefore we define an algorithmic problem, the missing difference problem, and show how its resolution leads to a message recovery attack with complexity close to the birthday bound. As a further result efficiently solving this problem also allows to describe an universal forgery attack against polynomial MACs such as GMAC and Poly1305 in complexity Õ(2^(2n/3)).
This is a joint work with Gaëtan Leurent.Lieu : Bât. Descartes, Salle 301
-
Mardi 17 avril 2018 14:00–15:00 – Albrecht Petzoldt – UVSQ
Improved Cryptanalysis of HFEv- via Projection
Résumé : The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank attacks. By our work, we therefore give new insights in the security of the HFEv- signature scheme and restrictions for the parameter choice of a possible future standardized HFEv- instance.