Résumé du séminaire du 28 juin 2013

  • Julia Wolf, Ecole Polytechnique – A quadratic Goldreich-Levin theorem

We present a local self-correction procedure for Reed-Muller codes of order 2 for functions at distance 1/2-epsilon from a codeword. This is an algorithmic analogue of Samorodnitsky’s tester for this problem, and to our knowledge, the first instance of a correction procedure beyond the list-decoding radius for any class of codes. It also forms the key ingredient of a « quadratic Goldreich-Levin theorem », which computes with high probability the large quadratic Fourier coefficients of a function in polynomial time.

This is joint work with Madhur Tulsiani.

  • Julia Pieltant, INRIA Saclay Île-de-France – Tours de corps de fonctions algébriques et algorithme de type Chudnovsky pour la détermination de bornes sur la complexité bilinéaire de la multiplication dans les corps finis.

On s’intéresse ici aux algorithmes de multiplication dans les corps finis, et plus précisément à la détermination de bornes sur la complexité bilinéaire de la multiplication dans une extension de degré n de F_q. On distingue en effet deux types d’opérations élémentaires : les opérations scalaires (additions, multiplications par des constantes) comptabilisées par la complexité scalaire et les opérations bilinéaires (multiplications de deux éléments de F_q dépendants directement des éléments de F_{q^n} dont on effectue le produit) comptabilisées par la complexité bilinéaire. Ce dernier type de complexité est indépendant de la base de F_{q^n} sur F_q choisie et correspond au rang du tenseur de la multiplication dans F_{q^n}.

L’algorithme de type évaluation-interpolation introduit en 1987 par D.V. et G.V. Chudnovsky est actuellement le meilleur algorithme de multiplication connu en terme de complexité bilinéaire : il a permis d’établir que le rang de tenseur de la multiplication dans F_{q^n} est linéaire en le degré n de l’extension considérée, et en fournit désormais les meilleures bornes connues dans le cas d’extensions de degré grand relativement au cardinal du corps de base.

Au cours de cet exposé, on présentera la dernière version de l’algorithme de type Chudnovsky, ainsi qu’une méthode d’obtention de bornes uniformes en n pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q à partir de tours de corps de fonctions algébriques ayant de bonnes propriétés. En particulier, l’étude des tours de Garcia-Stichtenoth d’extensions d’Artin-Schreier et de Kummer qui atteignent la borne de Drinfeld-Vladut permet d’obtenir les meilleures bornes actuellement connues pour la complexité bilinéaire de la multiplication dans F_{q^n} sur F_q, pour tout q premier ou puissance d’un premier.

Julia.Pieltant-28-06-2013 (format pdf)

  • Antoine Joux, DGA et Université de Versailles – Logarithmes discrets dans les corps finis. Application en caractéristiques petite et moyenne

Cet exposé commencera par une introduction aux algorithmes génériques de calcul de logarithmes discrets. Ensuite, nous nous intéresserons aux algorithmes de calcul d’index dans le cas le plus simple: celui de la petite ou moyenne caractéristique. Après une présentation des algorithmes précédemment connus, nous montrerons comment une transformation simple de ces algorithmes permet un amélioration importante de la complexité asymptotique et conduit à de nouveaux records de calcul de logarithmes discrets.

  • Gaëtan Leurent, Université catholique de Louvain -« Differential Attacks against ARX Designs »

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 describe an efficient way to propagate multi-bit constraints, that allows us to use the complete set of 2^32 2.5-bit constraints.

We have developed a set of tools for this 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 n detect several cases of incompatibility. In particular, we show that several published attacks are in fact 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 ttack 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. These are some of the first examples of complex differential trails built for pure ARX designs.

Gaetan.Leurent-28-6-2013 (format pdf)

Résumé du séminaire du 11 janvier 2013

  • Gilles Van Assche, – Keccak and permutation-based symmetric cryptography

In the last decades, mainstream symmetric cryptography has been dominated by block ciphers: block cipher modes of use have been employed to perform encryption, MAC computation, authenticated encryption and even internally in hash functions. One could therefore argue that the « swiss army knife » title usually attributed to the hash function belongs to the block cipher. In the last 5 years, Guido Bertoni, Joan Daemen, Michaël Peeters and I have proposed hashing (keyed or non-keyed), encryption (authenticated or plain) and other modes of use based on a fixed-length permutation rather than a block cipher. Such a permutation can be seen as a block cipher without a dedicated key input and can be constructed in the same way: by iterating a simple round function. Our modes, built on top of the sponge and duplex constructions, are simpler than the traditional block cipher modes and offer at the same time more flexibility. When designing a permutation suitable for this purpose, an obvious advantage is the absence of a key schedule. Moreover, thanks to the fact that the modes do not require the inverse permutation, there is also more freedom in the round function design than in the case of a block cipher.

This will be illustrated by the design of Keccak, which was submitted to the NIST SHA-3 competition and selected on October 2, 2012, to become the future SHA-3 standard.

Gilles.van.Asche-11-01-2012 (format pdf) Voir aussi keccak.noekeon.org, et sponge.noekeon.org

  • Anja Becker, – How to improve information set decoding exploiting that 1+1=0.

At Eurocrypt 2010, Howgrave-Graham and Joux described an algorithm for solving hard knapsacks of n elements and density close to 1 in time O(2^{0.337n}0 and memory O(2^{0.256n}). This improved a 30-year old algorithm by Shamir and Schroeppel of running time O(2^{0.5n}) and memory requirement O(2^{0.25n}). In this talk we will present the following: Using the simple observation that the solution to the knapsack problem, a binary vector, can be represented by two overlapping vectors with coefficients in {-1,0,1} , we can obtain a better algorithm of running time O(2^{0.291n}). Furthermore, this technique can be applied to improve information set decoding attacking linear codes such as used in McEliece public key encryption. We can improve recent results on half-distance decoding such as Ball-collision decoding and May-Meurer-Thomae–ISD of asymptotic time complexity O({2^{0.056n}}) and O(2^{0.054n}), respectively. Previous attempts split the solution vector in disjoint parts. We search the solution as decomposition of two overlapping vectors which permits to reduce the running time to O(2^{0.049n}) in the asymptotic case. The talk is based on the publications: http://eprint.iacr.org/2011/474 http://eprint.iacr.org/2012/026\\ a joint work with Jean-Sébastien Coron, Antoine Joux, Alexander Meurer and Alexander May.

Anja.Becker-11-01-2012 (format pdf)

  • Emmanuel Prouff, – Partage de Secret et Preuves de Sécurité En présence de Fuites d’Information

L’implantation des algorithmes cryptographiques est particulièrement sensible aux attaques dites par canaux auxiliaires. Ces dernières sont capables d’extraire de l’information sensible grâce à l’observation du comportement du matériel sur lequel se déroule les calculs. Depuis leur introduction dans le milieu des années 90, la protection des implantations contre ce type d’attaques a servi de base à une nouveau domaine de recherche, soutenu à la fois par les milieux de la recherche industrielle et académique. Parmi les nombreuses approches proposées, un technique appelée masquage des données s’est imposée comme étant celle offrant les meilleures garanties de sécurité. Les méthodes utilisées pour masquer un algorithme se sont révélées être très proches des schémas roposés en théorie du calcul multipartie sécurisé (SMC en anglais). Au cours de mon exposé, je propose de dresser une état de l’art des techniques de masquage et d’identifier précisément les ressemblances et différences avec les problématiques étudiées en SMC. J’en profiterai pour montrer comment il est possible d’exhiber des bornes de sécurité pour les implantations protégées grâce au masquage.

  • Matthieu Legeay, -« Utilisation du groupe de permutations des codes correcteurs pour améliorer l’efficacité du décodage »

Résumé du séminaire du 29 juin 2012

  • Rafael Fourquet, Université Paris 8 Saint-Denis, – Décodage par liste des codes de Reed-Muller binaires

Nous présenterons un algorithme déterministe de décodage par liste des codes de Reed-Muller. Jusqu’à la borne de Johnson, sa complexité est linéaire en la longueur du code (complexité optimale pour un algorithme déterministe). Il s’agit d’une généralisation à tous les ordres de l’algorithme « sums » pour l’ordre un de Kabatianski-Tavernier (qui peut être vu comme le déroulement non-exhaustif d’une transformée de Fourier rapide). A titre d’exemple, nous appliquerons l’algorithme au calcul du profil de non-linéarité d’une fonction booléenne.

  • Nicolas Delfosse, Institut de mathématiques de Bordeaux, – Construction et performances des codes quantiques topologiques

Les codes topologiques sont des codes quantiques construits à partir de pavages de surfaces. Ces codes ont été introduits par Kitaev, qui a défini un code quantique en utilisant un pavage carré du tore. Après avoir rappelé la construction de Kitaev, nous verrons comment les paramètres du code quantique s’expriment géométriquement en fonction du pavage. Nous nous intéresserons aux codes de surfaces hyperboliques de Zémor, qui forment l’une des rares familles de codes LDPC quantiques de rendement constant dont la distance minimale est croissante. En utilisant des pavages hyperboliques 3-coloriés nous obtenons une nouvelle famille de codes topologiques. Nous verrons que ces codes couleur hyperboliques possèdent aussi un rendement constant et une distance croissante.

Nous nous intéresserons ensuite aux performances de ces codes sur le canal à effacement. Nous verrons que les codes construits à partir de pavages réguliers n’atteignent pas la capacité du canal. Ce résultat nous permet de mieux comprendre les propriétés nécessaires pour approcher la capacité du canal.

Enfin, nous appliquerons ce résultat à un problème combinatoire. En utilisant la ressemblance entre effacements quantiques pour les codes hyperboliques et phénomène de percolation, nous déterminons une borne sur le seuil de percolation d’une famille de graphes hyperboliques auto-duaux. Nous obtenons ainsi une borne en théorie de la percolation provenant de la théorie de l’information quantique.

Travail en commun avec Gilles Zémor.

  • Charles Bouillaguet, Université de Versailles-Saint-Quentin-en-Yvelines, – Symbolic Methods for the Automatic Search of Attacks Against Some Block Ciphers

Résumé. The block cipher cryptanalyst usually faces the following problem: she may interact with a black box containing the block cipher instantiated with a secret random key, and her goal is, in most cases, to retrieve this secret key using less time than exhaustive search and asking less encryptions/decryptions to the black box than the whole codebook. Several researchers had previously observed that the Advanced Encryption Standard (AES), the most widespread block cipher, had a relatively simple algebraic description over the field with 256 elements, because of its byte-oriented design. However, this property has not been harnessed by cryptanalysts to this day. In particular the (tempting) approach consisting in writing down the equations describing the AES, and trying to solve them directly using off-the-shelf tools such as SAT-solvers, has systematically failed to provide any result. In this talk, I will present the results we obtained using a slightly different method. We have designed tools that take as input a system of AES-like equations, and that search for an efficient ad hoc solving procedure. The result of these tools is the source code of a solver that can only solve the input system, but which can in some cases be efficient (its complexity can be predicted accurately). This solver can then be compiled and run to find the actual solutions. Our tools, which « reason » from the equations describing the AES (or similar looking symmetric primitives) are intrinsically symbolic, and they are inspired by standard tools from the field of automated deduction, such as the DPLL algorithm for SAT, the Knuth-Bendix completion algorithm, or the resolution algorithm for first-order logic. These tools found, nearly automatically, the best known Low-Data-Complexity attacks on reduced versions of the AES, and the best known attack on the full versions of AES-derived primitives, such as the Message Authentication code Pelican-MAC, and the stream cipher LEX.

Résumé à venir

  • Patrick Derbez, École normale supérieure, –Généralisation des attaques de Demirci et Selçuk

Résumé: En 2008, Demirci et Selçuk présentent de nouvelles attaques sur 7 tours d’AES-192 et d’AES-256 reposant pour l’essentiel sur la technique du meet-in-the-middle. Dans cet exposé nous montrerons que ces attaques appartiennent en fait à une classe plus générale d’attaques et que celles trouvées par Demirci et Selçuk n’étaient pas optimales. Nous discuterons également de la méthode utilisée pour exhauster cette nouvelle classe ainsi que des résultats obtenus.

Résumé du séminaire du 06 avril 2012

  • Carlos Aguilar, Université de Limoges, – De l’utilisation du produit tensoriel pour le chiffrement complètement homomorphe

Résumé : Très récemment d’importantes avancées ont été réalisées en cryptographie au niveau des systèmes de chiffrement homomorphe, outils permettant de réaliser des calculs sur des données chiffrées sans passer par les données en clair. L’obtention de ces outils, souvent décrits comme le Graal de la cryptographie, a été un des problèmes ouverts les plus importants de la cryptographie depuis trente ans.

Dans cet exposé nous montrons comment l’utilisation de primitives cryptographiques basées sur des problèmes autres que ceux de la théorie des nombres a permis de débloquer ce problème en présentant rapidement les grandes constructions et en se focalisant ensuite sur l’utilisation du produit tensoriel.

  • Sylvain Duquesne, Université de Rennes 1,- Représentation RNS des nombres et calcul de couplages

Résumé : Dans cet exposé, Je présenterai rapidement le système de représentation des nombres basé sur le théorème des restes chinois (RNS) et je montrerai comment et pourquoi il est bien adapté au calcul de couplages, en particulier pour les grands degrés d’extension comme pour les courbes BN et pour les implémentations matérielles (FPGA dans notre cas).

  • Elodie Leducq, Université Paris 7, – Rayon de recouvrement des codes de Reed-Muller généralisés

Résumé : Le rayon de recouvrement des codes de Reed-Muller a surtout été étudié pour les codes de Reed-Muller binaires. Dans cet exposé, nous nous proposons d’étendre certains résultats aux codes de Reed-Muller généralisés. Plus, précisément nous en donnerons un encadrement qui permet de le calculer pour un nombre pair de variables. Dans le cas d’un nombre impair de variable, nous améliorerons cet encadrement pour un corps à trois éléments.

  • Christophe Petit, Université Catholique de Louvain, –On polynomial systems arising from a Weil descent

Résumé : Polynomial systems of equations appearing in cryptography tend to have special structures that simplify their resolution. In this talk, we discuss a class of polynomial systems arising after deploying a ultivariate polynomial equation over an extension field into a system of polynomial equations over the ground prime field (a technique commonly called Weil descent). We provide theoretical and perimental evidence that the degrees of regularity of these systems are very low, in fact only slightly larger than the maximal degrees of the equations. We then discuss cryptographic applications of particular instances of) these systems to the hidden field equation (HFE) cryptosystem, to the factorization problem in SL(2,2^n) and to the elliptic curve discrete logarithm over binary fields. In particular, e show (under a classical heuristic assumption in algebraic cryptanalysis) that an elliptic curve index calculus algorithm due to Claus Diem has subexponential time complexity (2^{c\,n^{2/3}\log n})\) over the binary field GF(2^n), where c is a constant smaller than 7/3.

Based on joint work with Jean-Charles Faugère, Ludovic Perret, Jean-Jacques Quisquater and Guénaël Renault.

Résumé du séminaire du 03 février

  • 10h00-11h00 : Clément Pernet, Université Joseph Fourier,- Adaptive decoding for evaluation/interpolation codes

Résumé : We will present recent work on CRT (Chinese Remainder Theorem) and more generally codes based on an evaluation-interpolation scheme that include the better known Reed-Solomon codes. It was motivated in the study of algorithm based fault tolerance (ABFT) applied to parallel exact linear algebra.In this area, Chinese Remainder Theorem is used to split computations over integers or rational numbers into several computations over finite rings, allowing a simple parallelization. CRT codes enable the use of Chinese Remainder reconstruction with errors in some of the residues, provided that some amount of redundant information has been computed. We will first introduce a more general error model allowing to derive tighter bounds on the error correction capacities of such codes. Then we will describe two adaptations of the usual unique decoding algorithm (based on the extended euclidean algorithm), making the correction capacity adaptive. Several termination criteria allow to efficiently use these codes without knowing their parameters, and use the maximal amount of redundancy available for correction. Furthermore they make it possible to adapt fault tolerance in algorithms with early termination. We will lastly present some recent insights on the application of these adaptive decoding to a problem in computer algebra: interpolation of sparse polynomials with errors.

Clement.Pernet-03-02-2012 (format pdf)

  • 11h15-12h15 : Christophe Guyeux, Université de Franche-Comté,-Quelques avancées pour une approche topologique en sécurité informatique

Résumé : Nous nous intéressons à la possibilité de concevoir des machines de Turing au comportement imprévisible et désordonné. Le cadre théorique de cette étude est la topologie mathématique, avec de possibles ramifications dans les domaines de la complexité et de la théorie de la mesure. Les applications visées ont trait à la sécurité informatique et aux simulations numériques de phénomènes chaotiques. Cette conception et cette étude sont possibles en tenant compte des points suivants : de telles machines sont des processus itératifs, diverses distances naturelles sont envisageables, on peut donc étudier topologiquement le comportement de ces systèmes dynamiques. Nous nous focalisons en particulier sur les propriétés suivantes : régularité, transitivité, expansivité, sensibilité, mélange topologique, instabilité, entropies topologique et métrique, exposant de Lyapounov, etc.

Cette approche théorique prouve rigoureusement qu’il est possible d’obtenir du chaos sur machine, et ce de manière exacte et mathématiquement correcte. D’autre part, ce modèle nous donne la marche à suivre concrètement pour préserver intégralement toutes ces propriétés lors d’implémentations : l’espace sur lequel itérer est le produit cartésien entre les états finis de la machine et l’ensemble infini des rubans possibles. Ainsi, on doit itérer sur des vecteurs de bits, et prendre à chaque itérée une nouvelle entrée, si l’on veut se prémunir des cas dégénérés, et notamment éviter de boucler systématiquement. La situation idéale correspond aux traitements de flux audio ou vidéo.

Nous avons commencé par appliquer nos réflexions à des situations concrètes. Notre approche consiste à utiliser des algorithmes prouvés sûrs par la communauté, et à réaliser un traitement dessus de sorte que le nouvel objet a ses propriétés de sécurité préservées, et possède en sus de nouvelles propriétés de désordre topologique. Ainsi, nous avons détaillé comment réaliser un post-traitement sur une fonction de hachage de sorte que ses propriétés de résistance aux collisions et à la première préimage soient préservées tout en possédant de nouvelles propriétés reliées au caractère imprédictible de la valeur hachée 1,2. Dans le même esprit, nous avons proposé une approche pour mixer deux générateurs de nombres pseudo-aléatoires avec une fonction dont la suite récurrente est chaotique, de sorte que le nouveau générateur reste rapide, devienne parallélisable, possède une kyrielle de propriétés de désordre topologique tout en préservant des propriétés telles que l’uniforme distribution 3. De telles preuves s’appuient notamment sur la théorie des graphes et les chaînes de Markov. Ce générateur passe avec succès les tests DieHARD, NIST et TestU01, même quand les PRNGs fournis en entrée n’en sont pas capables. Enfin, dans le domaine de la dissimulation d’informations, nous avons proposé des schéma de tatouage et de stéganographie prouvés stégo-sûrs, et ayant de bonnes propriétés topologiques. Nous avons relié ces propriétés à des classes d’attaques jusqu’alors impossibles à étudier 4,5.

1 Jacques M. Bahi and Christophe Guyeux. Topological chaos and chaotic iterations, application to hash functions. In IJCNN’10, IEEE Int. Joint Conference on Neural Networks, pages 1–7, Barcelona, Spain, July 2010. Best paper award. (Conférence de rang A)

2 Christophe Guyeux et Jacques M. Bahi. A Topological Study of Chaotic Iterations. Application to Hash Functions. In Computational Intelligence for Privacy and Security (CIPS). Springer. Accepted paper, to appear.

3 Jacques M. Bahi, Jean-François Couchot, Christophe Guyeux, Adrien Richard. Chaotic discrete dynamical systems: why getting strongly connected iteration graph and how. In FCT’11, 18th Int. Symposium on fundamentals of computational theory. August 2011, Oslo, Norway. (rang A)

4 Jacques Bahi and Christophe Guyeux. A new chaos-based watermarking algorithm. In SECRYPT’10, Int. conf. on security and cryptography, pages 455–458, Athens, Greece, July 2010. SciTePress.

5 Nicolas Friot, Christophe Guyeux, et Jacques M. Bahi. Chaotic iterations for steganography – Stego-security and chaos-security. In SECRYPT’11, Int. conf. on security and cryptography, pages ***-***, Spain, July 2011.

  • 14h15-15h15 : Christophe Ritzenthaler, Université de Marseille – Invariants et courbes hyperelliptiques : aspects géométriques, arithmétiques et algorithmiques

Travail en commun avec Reynald Lercier.

Résumé : De nombreuses questions géométriques ou arithmétiques sur les courbes hyperelliptiques peuvent être étudiées grâce aux invariants des formes binaires. S’il est relativement standard de calculer un système générateur de ces derniers, il est par contre nettement plus difficile de retrouver une forme binaire d’invariants donnés. En particulier la résolution par les bases de Gröbner est hors de portée des ordinateurs actuels dans le cas générique. Nous montrerons comment palier à ce problème par l’utilisation de la notion de covariants et de la méthode de Mestre. Nous compléterons ces résultats en étudiant si la courbe peut être construite sur son corps des modules.

Christophe.Ritzenthaler-03-02-2012 (format pdf)

  • 15h30-16h30 : Gohar Kyureghyan, Université de Magdebourg, – Permutation Polynomials over Finite Fields: Proof Techniques

Résumé : Permutation polynomials describe the bijective mappings on finite fields and play an important role in both theoretical and practical aspects of finite fields. For example, mappings used for applications in Coding Theory or Cryptology are often required to be bijective in order to ensure a unique decoding/decryption or to provide a good resistance against several attacks.

There are very few known explicit families of permutation polynomials, because lack of efficient methods for proving that a given polynomial defines a permutation on infinite many finite fields.

In the talk we will present some of known classes of permutation polynomials and give the key ideas used for proving them.

Résumé des exposés du séminaire du 07 octobre

  • Matthieu Finiasz (ENSTA ParisTech) –  »Surcoût asymptotique en communication pour la protection de la vie privée dans une recherche par mots clefs »

Le chiffrement homomorphique (simplement homomorphique ou pleinement homomorphique) est un outil central des protocoles de protection de la vie privée. Il permet de chiffrer une requête qu’un serveur peut ensuite traiter (sans avoir à la déchiffrer) pour retourner une réponse que seul l’utilisateur peut déchiffrer. Ostrovsky et Skeith ont ainsi proposé en 2005 un protocole de recherche par mots clef, utilisant le cryptosystème de Paillier, permettant de masquer les mots recherchés. L’inconvénient principal de ce protocole (mis à part les calculs un peu lourds liés au chiffrement homomorphique) est le volume des communications : la taille de la requête et celle de la réponse du serveur.

Nous proposons deux variantes de ce protocole permettant d’optimiser ces communications en utilisant des codes correcteurs d’erreur : des codes de Reed-Solomon pour l’un, et des LDPC irréguliers pour l’autre. Asymptotiquement, le surcoût en communication lié à la protection de la vie privée peut devenir négligeable par rapport au volume des documents récupérés.

  • Christophe Guyeux (Université de Franche-Comté) – Annulé et reporté au 3 février
  • Maria Naya-Plasencia (Université de Versalilles-Saint Quentin)– 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.

Résumé des exposés du 27 mai

  • Thierry Berger (Université de Limoges) – Une approche globale des automates algébriques (LFSR, FCSR, AFSR…). Application au design des générateurs pseudo-aléatoires

Résumé : Les automates LFSR et FCSR sont des automates qui calculent le développement selon les puissances croissantes de fractions rationnelles. Dans le cas LFSR, il s’agit de quotients de polynômes binaires (ou à coefficients dans un corps fini), dans le cas FCSR, il s’agit du développement 2-adique de quotients d’entiers. La principale différence entre LFSR et FCSR est la propagation de retenues, ce qui rend les automates FCSR non-linéaires au sens de la GF(2)-linéarité. Cette propriété a permis de les utiliser efficacement pour construire une famille de générateurs pseudo-aléatoires pour le chiffrement à flot (F-FCSR).

Dans cet exposé, nous présentons les propriétés de base des LFSR et des FCSR, le fonctionnement des générateurs F-FCSR et l’attaque de Hell et Johansson sur les F-FCSR basés sur des automates FCSR en mode Galois.

Cette attaque nous a poussé à adopter une approche matricielle pour la construction d’automates FCSR. Cette approche nous a permis de contrecarrer l’attaque précédente et de construire ainsi des automates plus performants simultanément en hardware et software.

Cette approche matricielle peut se généraliser à des anneaux munis d’une topologie I-adique relativement à un élément p particulier. Ceci permet de construire des automates appelés AFSR (Algebraic Feedback Shift Register). Nous donnerons plusieurs exemples d’applications, aussi bien dans le cas classique GF(2)[x] que dans certains anneaux non euclidiens.

Thierry.Berger-27-05-2011 (format pdf)

  • Delphine Boucher (Université de Rennes 1) – Autour des codes définis sur des anneaux de polynômes tordus

Résumé : Dans cet exposé, après avoir fait un bref rappel sur les codes d’évaluation et les codes « q-cycliques » inventés par Gabidulin en 1985, on introduit la classe des codes tordus modules. Ces codes sont définis sur des anneaux de polynômes non commutatifs F[x,theta] où F est un corps fini et la multiplication est régie par la règle x*a=theta(a)*x pour a dans F. On s’intéressera en particulier à donner une matrice génératrice et une matrice de contrôle pour ces codes et on construira des codes tordus auto-duaux.

Delphine.Boucher-27-05-2011 (format pdf)

  • Benoît Gérard (Université Catholique de Louvain)– L’entropie de Shannon : un outil générique pour analyser les attaques statistiques

Résumé : L’entropie de Shannon: un outil générique pour analyser les attaques statistiques.

Les liens étroits qu’entretiennent cryptographie et théorie de l’information sont connus depuis la fondation de cette dernière par Claude Shannon en 1948. Dès 1949, il applique sa théorie de la communication à la science du secret et depuis, la théorie de l’information a été principalement employée dans le cadre de la cryptographie à sécurité prouvée.

En 2009, on retrouve la notion d’entropie pour quantifier la force d’une attaque dans deux cadres assez différents: les attaques par canaux auxiliaires et la cryptanalyse linéaire multiple. L’objectif recherché dans le cadres des attaques par canaux auxiliaires est de pouvoir comparer, avec une métrique unique, différentes attaques (ou différentes implémentations). Dans le cadre de l’analyse de la cryptanalyse linéaire multiple, le but est de contourner la difficulté due à l’aspect multidimensionnel de l’attaque.

Nous nous intéresserons à ce dernier point: l’utilisation de la théorie de l’information pour l’analyse des cryptanalyses statistiques. Nous verrons sur plusieurs exemples que cette technique permet, de façon relativement simple, d’obtenir des résultats intéressants.

Benoit.Gerard-27-05-2011 (format pdf)

  • Eleonora Guerrini (Université de Caen)–Deux problèmes difficiles dans les graphes et leurs applications

Résumé : Dans cet exposé nous allons introduire deux problèmes difficiles dans les graphes: la recherche d’un code identifiant et la recherche d’un noyau, et nous discuterons des applications possibles. Un code identifiant est un sous ensemble structuré de sommets d’un graphe et nous verrons comment utiliser cet objet pour détecter une panne dans un réseau d’ordinateurs. L’existence d’un tel code est garantie pour tout graphe à voisinages disjoints, mais il est difficile de trouver des bornes sur sa taille minimale. Nous verrons des solutions pour résoudre cette question. Un noyau est un sous-ensemble de sommets à la fois stable et dominant. Le problème de savoir si un graphe possède un noyau est un problème NP-complet. Nous montrerons d’une part comment utiliser cette propriété en cryptographie (on cache un noyau dans un graphe aléatoire). D’autre part, nous proposerons des algorithmes qui recherchent un noyau et étudierons leur complexité afin de déterminer comment construire des instances difficiles.

Eleonora.Guerrini-27-05-2011 (format pdf)

  • Sorina Ionica (Ecole Polytechnique)– Couplages, volcans d’isogénies et calcul de l’anneau d’endomorphismes d’une courbe elliptique

Résumé : En 1996, D. Kohel propose un premier algorithme pour le calcul de l’anneau d’endomorphismes d’une courbe elliptique. Sa méthode repose, entre autres, sur un algorithme de parcours en profondeur du graphe d’isogénies (ce qu’on appelle un volcan). Les méthodes existantes a nos jours pour déterminer l’anneau d’endomorphismes utilisent des algorithmes de parcours de graphes d’isogénies. J’expliquerai l’algorithme de Kohel et je montrerai, en utilisant des résultats de ma thèse, que l’on peut calculer l’anneau d’endomorphismes sans avoir a parcourir les volcans d’isogénies et juste en calculant un petit nombre de couplages. Cela est possible lorsque la factorisation du conducteur de l’anneau d’endomorphismes contient que des facteurs premiers de taille pas très grande. Néanmoins, cette méthode a l’avantage d’éviter les calculs coûteux d’isogénies, en les remplaçant par un calcul rapide de couplage.

Sorina.Ionica-27-05-2011 (format pdf)

Résumé des exposés du 21 janvier

  • Oded Regev (CNRS, ENS, Paris, and Tel Aviv University) – Learning with Errors over Rings

Based on joint work with Vadim Lyubashevsky and Chris Peikert.

RESUME :The « learning with errors » (LWE) problem is to distinguish randomlinear equations, which have been perturbed by a small amount ofnoise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications.

Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. After a short introduction to the area, we will discuss recent work on making LWE and its applications truly efficient by exploiting extra algebraic structure. Namely, we will define the ring-LWE problem, and prove that it too enjoys very strong hardness guarantees. We will mention some recent cryptographic applications in this line of work. Oded.Regev-21-01-2011 (format pdf)

  • Marine Minier (INSA Lyon) – Quelques propriétés intégrales de Rijndael, LANE et Groestl

RESUME : Derrière ces étranges noms se cachent tout d’abord un chiffrement par blocs ou plutôt plusieurs versions d’un même chiffrement « Rijndael » dont la version pour des blocs de 128 bits est devenue le dernier standard de chiffrement américain l’AES en 2001. Quant à LANE et Groestl, il s’agit de deux candidats de la phase 1 de l’appel du NIST à la compétition SHA3 afin de standardiser une nouvelle fonction de hachage.

Nous nous intéresserons, dans cet exposé, à une forme d’attaques particulière contre ces algorithmes appelée cryptanalyse intégrale. Cette attaque a été introduite en 1997 par Lars Knudsen contre le chiffrement SQUARE puis ensuite formalisée en 2002 par David Wagner et Lars Knudsen. Il s’agit ici de faire prendre à un mot particulier du bloc à chiffrer toutes les valeurs possibles, les autres mots étant constants, afin d’observer après un certain nombre de tours de chiffrement des sommes de mots à 0. Ce type de propriétés, au même titre que les propriétés différentielles ou linéaires, permet de construire des relations statistiques ayant de grandes chances de se produire entre les entrées et les sorties d’un chiffrement limité à un nombre particulier de tours. On peut alors distinguer les sorties d’un chiffrement d’une suite aléatoire. Marine.Minier-21-01-2011 (format pdf)

  • Tony Ezome (Université de Toulouse) – Les nombres premiers : recherche et intérêt

RESUME : Le théorème fondamental de l’arithmétique stipule que tout entier se décompose, de manière unique à l’ordre près des facteurs, en produit de nombres premiers. Mais en pratique la factorisation des grands entiers est un problème difficile. La preuve de primalité est à la base du processus de factorisation d’un entier. Et aujourd’hui, la cryptographie symétrique utilise les nombres premiers pour chiffrer les messages. On peut le voir dans la construction de grands entiers difficilement factorisables réalisée par les cryptosystèmes RSA. D’autre part, on se sert des nombres premiers en cryptographie asymétrique pour fixer un corps de base $F_p$, considérer des courbes elliptiques $E/F_p$ définies sur ce corps de base et profiter de la difficulté du problème du logarithme discret dans le groupe des points de $E$ pour produire des cryptosystèmes d’une grande robustesse. La conception de critères de primalité et des algorithmes qui en découlent a donc toute son importance.

Dans cet exposé nous reviendrons sur les tests de primalité Miller-Rabin (probabiliste et très efficace en pratique), AKS (déterministe utilisant les extensions cyclotomiques, mais lent nn pratique) et ECPP (probabiliste et très puissant, il fournit un certificat de primalité) avant de présenter un nouveau critère de primalité : le critère AKS elliptique. Il s’agit d’une amélioration du test AKS qui utilise les courbes elliptiques. Tony.Ezome-21-01-2011 (format pdf). Une version longue est disponible.

  • Thomas Fuhr (ANSSI)– Cryptanalyse de fonctions de hachage : RadioGatun et Hamsi-256

RESUME : Les fonctions de hachage cryptographiques constituent un domaine dans lequel de nombreux développements sont apparus ces dernières années, tant du point de vue de la conception que du point de vue des attaques. Les techniques liées à la cryptanalyse différentielle ont mis à mal les standards de hachage existants. Cela a conduit le NIST à organiser la compétition SHA-3, dont l’objectif est la définition d’une nouvelle norme en matière de hachage.

Dans cet exposé nous nous intéressons à la cryptanalyse des fonctions de hachage, et à son évolution au cours des dernières années. La compétition SHA-3 requiert une capacité à évaluer la sécurité d’un nombre conséquent de fonctions de hachage en l’espace de 3 ans. De nombreux travaux récents mettent donc en lumière des vulnérabilités pas toujours directement exploitables de fonctions de hachage. De nouvelles techniques de cryptanalyse sont également apparues. Nous évoquerons particulièrement deux attaques contre des fonctions de hachage dont la fonction de compression est de bas degré algebrique. La première est une attaque en recherche de collisions sur RadioGatun, dont une partie des principes de conceptions ont conduit à la définition du candidat SHA-3 Keccak. Nous décrirons également une attaque en recherche de secondes préimages sur la fonction Hamsi-256, basée sur l’étude de ses propriétés algébriques. Thomas.Furr-21-01-2011 (format pdf)

Résumé des exposés du 22 octobre

  • Gary McGuire (University College Dublin)-« Further results on divisibility of Kloosterman Sums over Finite Fields »

Travaux commun avec Richard Moloney, Faruk Gologlu

RESUME : Kloosterman sums, their values and distribution of values, have several connections to coding theory, cryptography, bent functions, and aspects of number theory (see Dillon, Lachaud-Wolfmann for example). The value 0 has particular interest. A characterization of zeros of Kloosterman sums over binary and ternary fields appears to be difficult to find. Authors such as Lisonek, Helleseth, Zinoviev, Charpin, have recently focused on characterizations of Kloosterman sums that are divisible by certain powers of 2 and 3. We will first give an introduction to the topic, and then present some recent results that characterize Kloosterman sums modulo higher powers of 2 and 3.

Présentation annulée et reportée sine die.

  • Damien Vergnaud (ENS) – Systèmes de preuve Groth-Sahai et applications

Travaux en commun avec O. Blazy, G. Fuchsbauer, M. Izabachène, A. Jambert, B. Libert, D. Pointcheval & H. Sibert.

RESUME : Les preuves à divulgation nulle de connaissance sont des protocoles qui permettent à un utilisateur de prouver qu’un énoncé mathématique est vrai sans toutefois révéler une autre information que la véracité de l’énoncé. Une telle preuve est dite non-interactive si elle se compose d’un seul message. Ces preuves ont permis de développer un grand nombre d’applications en cryptographie mais qui sont rarement utilisées en pratique, car les constructions obtenues sont le plus souvent inefficaces. Une ligne récente de travaux, initiée par Groth, Ostrovsky et Sahai, a permis de réaliser des systèmes de preuve beaucoup plus performants pour certains types d’énoncés. Ces systèmes, basés sur les applications bilinéaires, permettent par exemple de prouver de façon efficace qu’un message a été signé sans révéler le message (ou la signature) ou de prouver qu’un texte chiffré possède certaines propriétés sans révéler le message clair.

Cet exposé donnera un aperçu de la construction de ces preuves et discutera ensuite certaines applications récentes développées dans le cadre du projet ANR PACE.

Damien.Vergnaud-22-10-2010 (format pdf)

  • Hugues Randriam (Telecom ParisTech) – Construction de systèmes (2,1)-séparants battant la borne probabiliste

RESUME : Les systèmes séparants sont des objets combinatoires dont l’étude a commencé au début des années 1960. Ils ont été réintroduits plus récemment au sein de la communauté cryptographique en relation avec le problème du traçage de traîtres ; dans ce contexte, les codes (t,1)-séparants sont aussi appelés « t-frameproof codes ».

Dans cet exposé on améliore un résultat de Xing en donnant une construction de codes algébro-géométriques t-frameproof sur un alphabet q-aire (q grand) dont le rendement asymptotique est le meilleur connu à ce jour.

Au moyen d’une concaténation, ceci permet de construire de bons codes t-frameproof *binaires*. Un cas particulièrement intéressant est celui où t=2 ; il s’agit là d’un pur problème de combinatoire extrémale, pour lequel on obtient ainsi une construction battant la borne probabiliste. Cette question était restée ouverte depuis une trentaine d’années.

Hugues.Randriam-22-10-2010 (format pdf)

  • François-Xavier Standaert (Université Catholique de Louvain)– « Recent results about side-channel attacks and countermeasures »

RESUME : Traditionally, cryptographic algorithms provide security against an adversary who has only black box access to cryptographic devices. That is, the only thing the adversary can do is to query the cryptographic algorithm on inputs of its choice and analyze the responses, which are always computed according to the correct original secret information. However, such a model does not always correspond to the realities of physical implementations. During the last decade, significant attention has been paid to the physical security evaluation of cryptographic devices. In particular, it has been demonstrated that actual attackers may be much more powerful than what is captured by the black box model. For example, they can actually get a side-channel information, based on the device’s physical computational steps. As a consequence, some kind of obfuscation is required to protect integrated circuits from these physical attacks. This is especially important for small embedded devices (e.g. smart card, RFIDs, sensor networks, …) that can typically be under an adversary’s control for a short period of time. This implies new theoretical concerns (how to exactly model and evaluate these physical threats) and practical ones (how to prevent them). In this talk, I will discuss different results in the area of side-channel attacks, with a particular focus on formal tools that can be used to evaluate physical security on a fair basis. Starting from an introductive view of the field, I will describe some well known attacks and countermeasures, present a framework for the analysis of side-channel key-recovery from Eurocrypt 2009, with some of its applications, and finally discuss the connection of this framework with recent works in leakage-resilient cryptography.

Francois-Xavier.Standaert-22-10-2010 (format pdf)

Résumé des exposés du 18 juin

  • Delphine Boucher (Université de Rennes 1) – Autour des codes définis sur des anneaux de polynômes tordus

Travail en commun avec W. Geiselmann et F. Ulmer.

RESUME : Les codes tordus sont définis dans des anneaux (non commutatifs) de polynômes tordus sur un corps fini Fq noté Fq[X,theta] où theta est un automorphisme de Fq et la multiplication est régie par la règle X a = theta(a) X pour a dans Fq. Les codes ‘idéaux’ theta-cycliques sont obtenus comme des idéaux à gauche de l’anneau quotient Fq[X,theta]/(X^n-1) où n est un multiple de l’ordre de l’automorphisme theta. On peut généraliser cette construction en considérant des quotients Fq[X,theta]/(f) où f est un polynôme central de Fq[X,theta] (on parle alors de codes ‘ideaux’ theta-centraux) mais aussi en considérant des modules à gauche des modules quotients Fq[X,theta]/(f) où f est un polynôme quelconque de Fq[X,theta]. On parlera alors de codes ‘modules’ tordus. Dans cet exposé, après avoir défini les codes tordus, on s’intéressera plus particulièrement à la caractérisation des codes tordus auto-duaux et à leur construction sur F4 pour les produits scalaires euclidiens et hermitiens.

Exposé annulé

  • Pierrick Gaudry (LORIA) – Factorisation d’entiers et RSA768

RESUME : En janvier dernier, la factorisation de RSA-768 a été annoncée. Après avoir rappelé quelques éléments généraux sur la factorisation d’entiers, nous expliquerons avec un peu plus de détails l’algorithme du crible algébrique qui est utilisé pour factoriser les modules RSA. Nous détaillerons ensuite comment cet algorithme a été mis en oeuvre dans le cas de RSA-768. Il aura fallu environ 2 ans et demi et la collaboration des équipes de l’EPFL, du CWI, de NTT et de notre équipe nancéienne pour venir à bout de ce calcul.

Pierrick.Gaudry-18-06-2010 (format pdf)

  • Didier Alquié (DGA) – « Branch Number » d’un automate linéaire et codes convolutifs récursifs systématiques

Travail commun avec Franck Landelle.

RESUME : Dans ce travail nous proposons un nouveau cadre pour estimer le biais linéaire d’un générateur pseudo aléatoire. Nous définissons le « branch number » d’un automate intermédiaire défini sur un corps fini GF(q) comme le nombre de boîtes actives liées aux entrées et sorties. Cette valeur est utile pour évaluer le biais linéaire global du générateur. Nous montrons qu’elle peut être reliée à la distance libre d’un code convolutif sur GF(q) convenablement défini, et que les codes optimaux par rapport à cette distance conduisent à une borne inférieure – fine – sur le « branch number ». En conséquence, l’utilisation de notre proposition spécifique comme partie d’un générateur pseudo aléatoire permet de fournir une borne supérieure « prouvée » du biais global.

Didier.Alquie-18-06-2010 (format pdf)

  • Christophe Chabot (Université de Rennes 1)– Codes quasi-cycliques et polynômes à coefficients matriciels

RESUME : Nous nous intéressons ici à la généralisation de résultats connus sur les suites récurrentes linéaires classiques aux suites récurrentes linéaires ayant un polynôme caractéristique à coefficients matriciels. Nous montrerons qu’il est possible de construire des codes quasi-cycliques à partir de telles suites (par analogie avec la construction de codes cycliques à partir de suites récurrentes linéaires classiques). Nous obtiendrons alors la notion de code quasi-cyclique annulé par un polynôme à coefficients matriciels. Finalement nous construirons des codes quasi-cycliques auto-duaux Euclidiens et Hermitiens qui dans la plupart des cas atteignent les bornes connues pour les distances minimales.

Christophe.Chabot-18-06-2010 (format pdf)