Embedded Files
Algebraic Coding and Cryptography
Online Event
ACCESS is a joint effort designed to highlight world-class research in coding theory, cryptography, and related areas and to encourage collaboration among its participants.
ACCESS is a joint effort designed to highlight world-class research in coding theory, cryptography, and related areas and to encourage collaboration among its participants.
Next seminar
March 03
Next seminar
March 03
Jean-Pierre Tillich
INRIA
Jean-Pierre Tillich
INRIA
Biography. Jean-Pierre Tillich received his Ph.D. from 'Ecole Nationale Sup'erieure des T'el'ecommunications (ENST), Paris, in 1994. From 1997 to 2003, he was Assistant Professor at the University Paris XI. He is now a senior researcher at the Institut de Recherche en Informatique et Automatique (INRIA), Paris, France. From 2009 to 2012 he was an Associate Editor for Coding Theory for the IEEE Transactions on Information Theory. His research interests include classical and quantum coding theory, cryptography and graph theory.
An attack on the CFS scheme and on TII McEliece challenges
An attack on the CFS scheme and on TII McEliece challenges
Authors. Magali Bardet (University of Rouen) and Axel Lemoine (DGA & Inria de Paris), Jean-Pierre Tillich (Inria de Paris)
Abstract. It has been a very long standing open question whether the CFS signature scheme [CFS01] whose security is basically that of a McEliece scheme based on very high rate binary Goppa codes could be attacked or not. There was a first cryptanalytic result [FGOPT11] consisting in finding a distinguisher for the binary Goppa codes used in this scheme showing that these codes can be distinguished in polynomial time from a random binary linear code. However despite numerous cryptanalytic attempts and even if the original distinguisher has been significantly improved, no attack on the McEliece scheme based on binary Goppa codes has been found so far except for very peculiar Goppa codes of degree $2$ [M25]. We show here that the Pfaffian modeling used in the distinguishing attack of [CMT23] can actually be used together with a shortening trick and looking for squares in the corresponding ideal to find a polynomial attack on the CFS scheme based on very high rate binary Goppa codes. This breaks this 25 years old signature scheme. We demonstrate the effectiveness of this approach by recovering the key of TII McEliece challenges with a claimed key security of up to 210 bits.
References.
[CFS01] Nicolas Courtois, Matthieu Finiasz, and Nicolas Sendrier, "How to achieve a {McEliece}-based digital signature scheme", In Advances in Cryptology - ASIACRYPT 2001, volume 2248 of LNCS, pages 157--174, Gold Coast, Australia, 2001. Springer.
[CMT23] Alain Couvreur, Rocco Mora, and Jean-Pierre Tillich, "A new approach based on quadratic forms to attack the McEliece cryptosystem", in Jian Guo and Ron Steinfeld, editors, Advances in Cryptology -ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Guangzhou, China, December 4-8, 2023, Proceedings, Part IV, volume 14441 of LNCS, pages 3--38. Springer, 2023.
[FGOPT11] Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich. "A distinguisher for high rate {McEliece} cryptosystems", in Proc. IEEE Inf. Theory Workshop- ITW 2011, pages 282--286, Paraty, Brasil, October 2011.
[M25] Rocco Mora, "On the matrix code of quadratic relationships for a Goppa code", Adv. Math. Commun., 19(3): pages 829--852, 2025.
Organizing team
Organizing team
Page updated
Google Sites
Report abuse