Nicolas T. COURTOIS' research in cryptography

Press report: w attacks on KeeLoq that is used to unlock doors and deactivate the alarm in many cars, see (in Polish) a report on IPSEC.PL online news service.
Nicolas Courtois, Gregory V. Bard: Algebraic and Slide Attacks on KeeLoq, eprint/2007/062/. This paper describes the first successful algebraic attack in history on a full round real-life block cipher.
Nicolas Courtois, Gregory V. Bard, Chris Jefferson: Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via SAT-Solvers, eprint/2007/024/.
Nicolas Courtois, Gregory V. Bard:
Algebraic Cryptanalysis of the Data Encryption Standard, eprint.iacr.org/2006/402/.
Invited talk at CLC 2006, Darmstadt, Germany 25-27 September 2006.
Nicolas Courtois, Blandine Debraize and Eric Garrido: On Exact Algebraic [Non-]Immunity of S-boxes Based on Power Functions, eprint/2005/203/. In ACISP 2006, 11th Australasian Conference on Information Security and Privacy. 3 - 5 July 2006. Melbourne. Australia.
New methods for attacking block ciphers, article in Polish "Nowe metody ataków na szyfry blokowe", In Security - Computerworld polish edition, 3 April 2006.
Nicolas Courtois: Cryptanalysis of Sfinks, eprint/2005/243/. In ICISC 2005, LNCS 3935, Springer.
Nicolas Courtois, Louis Goubin: An Algebraic Masking Method to Protect AES Against Power Attacks, eprint/2005/204/. In ICISC 2005, LNCS 3935, Springer.
Nicolas Courtois: The Best Differential Characteristics and Subtleties of the Biham-Shamir Attacks on DES, eprint/2005/202/.
Fast Moving Fronts in Computer Science: interview published on the internet on 1st of July 2005, read it here.
C. Berbain, O. Billet, A. Canteaut, N. Courtois, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin, and H. Sibert: SOSEMANUK, a fast software-oriented stream cipher, submission to ECRYPT call for stream ciphers and presented at SKEW 2005 workshop in Aarhus, Denmark on 26 May 2005.
C. Berbain, O. Billet, A. Canteaut, N. Courtois, H. Gilbert, L. Goubin, A. Gouget, L. Granboulan, C. Lauradoux, M. Minier, T. Pornin, and H. Sibert: DECIM, a new stream cipher for hardware applications, submission to ECRYPT call for stream ciphers and presented at SKEW 2005 workshop in Aarhus, Denmark on 27 May 2005.
Aline Gouget, Hervé Sibert, Côme Berbain, Nicolas Courtois, Blandine Debraize, Chris Mitchell: Analysis of the Bit-Search Generator and sequence compression techniques, FSE 2005, LNCS 3557, pp. 196-214, Springer, 2006.
Nicolas Courtois: Algebraic Attacks on Combiners with Memory and Several Outputs, In ICISC 2004, LNCS, Springer. The extended and recently updated version of this paper is available at eprint.iacr.org/2003/125/.
Nicolas Courtois, Feistel Schemes and Bi-Linear Cryptanalysis, In Crypto 2004, LNCS 3152, pp. 23-40, Springer. The extended version is available at eprint.iacr.org/2005/251/.
Nicolas Courtois, The Inverse S-box and Two Paradoxes of Whitening, Presented at the Rump Session of Crypto 2004. Here is the long, very much extended version of the slides.
Jiun-Ming Chen, Nicolas Courtois and Bo-Yin Yang: On Asymptotic Security Estimates in XL and Gröbner Bases-Related Algebraic Cryptanalysis, In ICICS'04, LNCS 3269, pp. 401-413, Springer, 2004.
Nicolas Courtois, Short Signatures, Provable Security, Generic Attacks and Computational Security of Multivariate Polynomial Schemes such as HFE, Quartz and Sflash, draft, eprint 2004/143.
Nicolas Courtois, The Inverse S-box, Non-linear Polynomial Relations and Cryptanalysis of Block Ciphers, in AES 4 Conference, Bonn May 10-12 2004, LNCS 3373, pp. pp. 170-188, Springer. Available for Springer subscribers.
Nicolas Courtois, General Principles of Algebraic Attacks and New Design Criteria for Components of Symmetric Ciphers. Invited talk, AES 4 Conference, Bonn May 10-12 2004, LNCS 3373, pp. 67-83, Springer. Available for Springer subscribers.
Patent: Nicolas Courtois: Procédé de protection d'un ensemble cryptographique par masquage homographique, European Patent Application 04291204.8-, filled on 11.05.04.
Nicolas Courtois, Louis Goubin and Jacques Patarin: SFLASHv3, a fast asymmetric signature scheme available on eprint.iacr.org/2003/211/. This paper specifies the new version of Sflash. The previous version is no longer recommended. Sflash-v3 should remain the fastest signature scheme known and can only be rivalled by NTRU.
Nicolas Courtois: Algebraic Attacks over GF(2^k), Application to HFE Challenge 2 and Sflash-v2. PKC 2004, LNCS, Springer. Warning: all numeric complexity estimates of this paper are out of date.
Nicolas Courtois, Guilhem Castagnos and Louis Goubin: What do DES S-boxes Say to Each Other ? Available on eprint.iacr.org/2003/184/. This paper exhibits some structure in the DES S-boxes, probably nothing serious. It also introduces a new type of algebraic attack on block ciphers.
Press Article:
In New Scientist, 07 June 2003 issue, page 36, Dana Mackenzie, describes the current situation regarding the security of world encryption standards, as "A Game of Chance". A short abstract of this article can be found here.
Nicolas Courtois: Fast Algebraic Attacks on Stream Ciphers with Linear Feedback. Crypto 2003, August 17-21 2003, LNCS 2729, pp. 177-194, Springer.
Nicolas Courtois, Willi Meier: Algebraic Attacks on Stream Ciphers with Linear Feedback. Eurocrypt 2003, LNCS 2656, pp. 345-359, Springer.
This attack has been now implemented by Nicolas Courtois, see the extended version of the paper.
Nicolas Courtois, Robert T. Johnson, Pascal Junod, Thomas Pornin and Michael Scott: Did Filiol Break AES ? Available at eprint.iacr.org/2003/022/. See also this page.
Nicolas Courtois, Jacques Patarin: About the XL Algorithm over GF(2), in Cryptographers' Track RSA 2003, April 13-17, San Francisco, LNCS 2612, pages 141-157, Springer.
Nicolas Courtois: Higher Order Correlation Attacks, XL algorithm, and Cryptanalysis of Toyocrypt. Will be presented at 5th International Conference on Information Security and Cryptology (ICISC 2002), November 28-29, 2002, Seoul, Korea, LNCS 2587, pp. 182-199, Springer.
See also my web page page about algebraic attacks on stream ciphers.
Nicolas Courtois, Josef Pieprzyk: Cryptanalysis of Block Ciphers with Overdefined Systems of Equations; (or the XSL attack on block ciphers), in Asiacrypt 2002, LNCS 2501, pp.267-287, Springer.
Two different versions of the XSL attack are available on eprint.iacr.org.
Here is my AES / Rijndael page with the latest news about algebraic attacks on AES. This page is frequently updated.
Press Release: "Strict codes observed at conference", by Leah McFall, a report about Courtois and Pieprzyk attack on AES, appeared in Otago Daily, New Zealand, during the Asiacrypt 2002 conference, Tuesday, 3-December 2002, page 15. Read it here.
Press Release: Hank Wolfe speaks about the weakness of AES: "Code-breakers may have found US computer weakness", by Joanna Norris, in Otago Daily, New Zealand, Friday, 29-November 2002.
Press Release: "Crucial Cipher Flawed, Cryptographers Claim", by Charles Seife, Science Magazine, 27 September 2002, page 2193.
AES News: a Cryptogram article by Bruce Schneier, 15 September 2002. Some related comments etc.
An article entitled Comment Tout Dire Sans Rien Révéler, published special issue of the French magazine Pour La Science (French edition of Scientific American), available everywhere in France in July-October 2002.
Nicolas Courtois, Magnus Daum and Patrick Felke: On the Security of HFE, HFEv- and Quartz, PKC 2003, LNCS 2567, Springer, pp. 337-350. An extended version can be found on eprint.
Patent: Nicolas Courtois: Procédé de protection d'un ensemble cryptographique par masquage multivariable linéaire, European Patent Application 02291625.8-, filled on 28.06.02, Priority FRA 0205486, filled on 30.04.02.
Patent: Mehdi-Laurent Akkar, Nicolas Courtois and Louis Goubin: Procédé et système de génération de signature, European Patent Application 02292253.8, filled on 13.09.02.
Mehdi-Laurent Akkar, Nicolas Courtois, Louis Goubin, Romain Duteuil, A Fast and Secure Implementation of Slash, PKC 2003, LNCS 2567, Springer, pp. 267-278. See also the Sflash web page.
Nicolas Courtois: Generic Attacks and the Security of Quartz, PKC 2003, LLNCS 2567, Springer, pp. 351-364. A preliminary version has been presented at the second Nessie workshop, September 13th 2001, Royal Holloway, University of London. Download the extended version of the paper / download my PKC presentation.
Nicolas Courtois, Louis Goubin, Willi Meier, Jean-Daniel Tacier:
Solving Underdefined Systems of Multivariate Quadratic Equations;
PKC 2002, Paris, February 2002, LNCS 2274, pp. 211-227, Springer.
Nicolas Courtois: The security of cryptographic primitives based on multivariate algebraic problems: MQ, MinRank, IP, HFE. PhD thesis, Paris 6 university, September 25th 2001, in French, under the direction of Sami HARARI. The PhD thesis is available here. And here are slides from my PhD defense.
Nicolas Courtois, Matthieu Finiasz and Nicolas Sendrier:
How to achieve a McEliece-based Digital Signature Scheme.
The McEliece signature scheme paper published at Asiacrypt 2001, LNCS 2248, Springer, pp. 157-174. An early version was published as Inria rapport de recherche 4118, February 2001. And here are the slides presented at the rump session of Crypto 2001. Check also the homepage of McEliece signature scheme.
Nicolas Courtois: Efficient Zero-knowledge authentication based on a linear algebra problem MinRank. Presented at the Asiacrypt 2001, LNCS 2248, Springer, pp. 402-421. The full paper is available at the iacr server, download directly the ps/pdf file. Here is the presentation from Asiacrypt 2001
A preliminary version was presented at the Rump Session of Crypto 2000 and also at the PKC&CNT conference. Here is the official MinRank home page.
A slide showing some difficult problems and reductions known in multivariate cryptography.
Patent: Nicolas Courtois and Jacques Patarin: Anti-Pirate Method for the Distribution of Digital Content, European Patent 02788390.9-2415-IB0205520, filled on 19.12.02, Priority FRA 0116585 filled on 12.02.01.
A web page presenting the GPT cryptosystem.
Nicolas Courtois: The security of Hidden Field Equations (HFE), Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 266-281, Springer-Verlag. Donwload the paper hfesec.dvi / hfesec.ps / hfesec.pdf.
The slides on HFE security from RSA2001: hfesecsl.dvi / hfesecsl.ps / hfesecsl.pdf.
Comments: This paper describes a subexponential attack on HFE and is the best attack ever found on HFE and HFE Challenge 1. At Crypto 2003 Joux and Faugère will explain why this attack works and improve it slightly. See also the "official" HFE cryptosystem home page.
Nicolas Courtois, Louis Goubin and Jacques Patarin: Quartz, 128-bit long digital signatures, submitted to Nessie European Call for Primitives, and also published in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp.282-297, Springer-Verlag.
The official homepage for Quartz .
Nicolas Courtois, Louis Goubin and Jacques Patarin: Flash, a fast multivariate signature algorithm, submitted to Nessie European Call for Primitives, and also published in Cryptographers' Track Rsa Conference 2001, LNCS 2020, pp. 298-307, Springer.
The official homepages for Flash/Sflash.
Nicolas Courtois: On multivariate signature-only public key cryptosystems,
paper available at eprint.iacr.org/2001/029/.
My talk Hfe and MinRank at the PKC&CNT conference. hfemr.dvi/hfemr.ps/hfemr.pdf
Nicolas Courtois and Louis Goubin: The Cryptanalysis of TTM
Asiacrypt 2000 conference, Asiacrypt'2000, LNCS 1976, Springer, pp.44-57.
Slides from Asiacrypt 2000 talk on the cryptanalysis of TTM.
A web page about TTM.
My talk from the Enigma 2000 conference (in Polish),
Nicolas Courtois: Algorytm klucza publicznego HFE, corrected and extended, hfepl.ps.
An intoduction to multivariate cryptography, (in Polish), presented also at the Enigma 2000 conference (in Polish),
Nicolas Courtois: Kryptografia Wielu Zmiennych, corrected and extended kurs.pdf
Nicolas Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir:
Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations, Eurocrypt 2000, LNCS 1807, Springer, pp. 392-407.
The extended version of the paper is available here.
Here are slides from my talk at Eurocrypt 2000 (but does not include 2 slides I made by hand).
Mes transparents (en français) sur HFE et polynômes multivariables (Batz-sur-Mer, 1er Juin 1999). Corrigé.
English-French-Polish cryptology dictionary .
Nicolas Courtois, Louis Goubin and Jacques Patarin: C*-+ and HM - Variations around two schemes of T. Matsumoto and H. Imai; Asiacrypt' 98, Springer, pp.35-49.
Here is the extended version of the paper dvi / ps / pdf.
Nicolas Courtois, Louis Goubin and Jacques Patarin: Improved Algorithms for Isomorphism of Polynomials. Eurocrypt'98, Springer, pp.184-200.
Here is the extended version of the paper as a dvi/ ps or pdf file.
Here are slides from my talk at Eurocrypt'98.
Nicolas Courtois: Extensive study of Isomorphism of Polynomials and Asymmetric Cryptography (1997),
Download it's abstract (English/French).
Or the whole work in French (quite out of date now).
Nicolas Courtois: Article Metoda Hylemorficzna presented at VIth Philosophical Symposium, Toruñ, Poland, September 7th 1995.
Nicolas Courtois: Report on the cryptanalysis of the HARALIA cryptosystem (1995).
You can download it's abstract (English/French) and introduction (in French).
Nicolas Courtois: A student project about Quantum teleportation (EPR pairs) - scanned bad quality .gif in french and quite out of date (1993).
A short note about protecting radio communications from eavesdropping, published in the "Pomysly" of the popular Polish magazine "Mlody Technik", in the early 80s.