Kévin Carrier

About

I am an Associate Professor at École Polytechnique in the GRACE project-team since September 2025. My research interests focus on post-quantum cryptography, in particular code-based and lattice-based cryptography. I am also interested in a closely related topic, namely telecommunications reverse engineering, with a special emphasis on the blind recognition of error-correcting codes. I received my PhD in 2019 on Near-Collision Search for Decoding and Code Recognition, which I completed within the SECRET project-team (now COSMIQ) at Inria de Paris, under the supervision of Jean-Pierre Tillich and Nicolas Sendrier. This doctoral work was conducted as a joint collaboration between the French Ministry of the Armed Forces, Inria de Paris, and Sorbonne Université. Prior to joining École Polytechnique, I was an Associate Professor at CY Cergy-Paris Université for four years, where I was a member of the ICI team within the ETIS laboratory. Since September 2025, I have been teaching at École Polytechnique and EPITA, covering topics such as Python programming, reverse engineering, and graph theory. Previously, I have also taught cybersecurity, cryptography, information theory, and error-correcting codes at several institutions, including ENSEA, CY Cergy-Paris Université, and Université Paris Cité.

Teaching

Supervision & Students

• PhD Student: Elric Isoardo, co-advised with Alain Couvreur (Inria Saclay) (Jan. 2026 - Now)
  Hybrid Algebraic-Combinatorial Attacks on Post-Quantum Cryptosystems
• PhD Student: Valérian Hatey, co-advised with Laura Luzzi (ENSEA) (Oct. 2023 - Now)
  Code and Lattice based Cryptanalysis
• MSc Projects: Valérian Hatey (Apr. 2023 - Aug. 2023)
  Ternary decoding at large distance
• MSc Projects: Julien Chaput (Apr. 2021 - Aug. 2021)
  Non-binary LDPC codes
• MSc Projects: Émile Lalo (Apr. 2021 - Aug. 2021)
  Polar codes in 5G
• Bachelor Projects: Thomas Remy (June 2023 - Aug. 2023)
  Technological watch on Smart Cards

Scientific Activities

• Principal Investigator and Coordinator of the ANR JCJC DECODE Project
• Program Committee and Reviewing: CRYPTO, EUROCRYPT, ASIACRYPT, PQCrypto, WCC, DCC, Journal of Cryptography, IEEE IT, and IEEE ISIT.

Publications

• Assessing the Impact of a Variant of the Latest Dual Attack

  Kévin Carrier, Charles Meyer-Hilfiger, Yixin Shen, Jean-Pierre Tillich. Advances in Cryptology – CRYPTO 2025

  Link: https://eprint.iacr.org/2022/1750

  Abstract: The dual attacks on the Learning With Errors (LWE) problem are currently a subject of controversy. In particular, the results of [Matzov,2022], which claim to significantly lower the security level of Kyber a lattice-based cryptosystem currently being standardized by NIST, are not widely accepted. The analysis behind their attack depends on a series of assumptions that, in certain scenarios, have been shown to contradict established theorems or well-tested heuristics [Ducas,Pulles,2023].
  In this paper, we introduce a new dual lattice attack on LWE, drawing from ideas in coding theory. Our approach revisits the dual attack proposed by [Matzov,2022], replacing modulus switching with an efficient decoding algorithm. This decoding is achieved by generalizing polar codes over Z/qZ, and we confirm their strong distortion properties through benchmarks. This modification enables a reduction from small-LWE to plain-LWE, with a notable decrease in the secret dimension. Additionally, we replace the enumeration step in the attack by assuming the secret is zero for the portion being enumerated, iterating this assumption over various choices for the enumeration part.
  We make an analysis of our attack without using the flawed independence assumptions used in [Matzov,2022] and we fully back up our analysis with experimental evidences.
  Lastly, we assess the complexity of our attack on Kyber; showing that the security levels for Kyber-512/768/1024 are 3/12/12 bits below the NIST requirements (143/207/272 bits) in the same nearest-neighbor cost model as in [Matzov,2022}.

• Reduction from Sparse LPN to LPN, Dual Attack 3.0

  Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. Advances in Cryptology – EUROCRYPT 2024

  Link: https://eprint.iacr.org/2023/1852

  Abstract: The security of code-based cryptography relies primarily on the hardness of decoding generic linear codes. Until very recently, all the best algorithms for solving the decoding problem were information set decoders (ISD). However, recently a new algorithm called RLPN-decoding which relies on a completely different approach was introduced and it has been shown that RLPN outperforms significantly ISD decoders for a rather large range of rates. This RLPN decoder relies on two ingredients, first reducing decoding to some underlying LPN problem, and then computing efficiently many parity-checks of small weight when restricted to some positions. We revisit RLPN-decoding by noticing that, in this algorithm, decoding is in fact reduced to a sparse-LPN problem, namely with a secret whose Hamming weight is small. Our new approach consists this time in making an additional reduction from sparse-LPN to plain-LPN with a coding approach inspired by coded-BKW. It outperforms significantly the ISD's and RLPN for code rates smaller than 0.42. This algorithm can be viewed as the code-based cryptography cousin of recent dual attacks in lattice-based cryptography. We depart completely from the traditional analysis of this kind of algorithm which uses a certain number of independence assumptions that have been strongly questioned recently in the latter domain. We give instead a formula for the LPN noise relying on duality which allows to analyze the behavior of the algorithm by relying only on the analysis of a certain weight distribution. By using only a minimal assumption whose validity has been verified experimentally we are able to justify the correctness of our algorithm. This key tool, namely the duality formula, can be readily adapted to the lattice setting and is shown to give a simple explanation for some phenomena observed on dual attacks in lattices in [DP23].

• Projective Space Stern Decoding and Application to SDitH

  Kévin Carrier, Valérian Hatey, Jean-Pierre Tillich. Applied Cryptography and Network Security Workshops: ACNS 2024

  Link: https://eprint.iacr.org/2023/1865

  Abstract: We show that here standard decoding algorithms for generic linear codes over a finite field can speeded up by a factor which is essentially the size of the finite field by reducing it to a low weight codeword problem and working in the relevant projective space. We apply this technique to SDitH and show that the parameters of both the original submission and the updated version fall short of meeting the security requirements asked by the NIST.

• WAVE: Round 1 submission

  Gustavo Banegas, Kévin Carrier, André Chailloux, Alain Couvreur, Thomas Debris-Alazard, Philippe Gaborit, Pierre Karpman, Johanna Loyer, Ruben Niederhagen, Nicolas Sendrier, Benjamin Smith, Jean-Pierre Tillich. NIST competition, June 2023

  Link: https://wave-sign.org/

  Abstract: Wave is a post-quantum signature scheme based on hard problems in coding theory.

• Statistical Decoding 2.0: Reducing Decoding to LPN.

  Kévin Carrier, Thomas Debris-Alazard, Charles Meyer-Hilfiger, Jean-Pierre Tillich. Advances in Cryptology – ASIACRYPT 2022

  Link: https://eprint.iacr.org/2022/1000

  Abstract: The security of code-based cryptography relies primarily on the hardness of generic decoding with linear codes. The best generic decoding algorithms are all improvements of an old algorithm due to Prange: they are known under the name of information set decoders (ISD). A while ago, a generic decoding algorithm which does not belong to this family was proposed: statistical decoding. It is a randomized algorithm that requires the computation of a large set of parity-checks of moderate weight, and uses some kind of majority voting on these equations to recover the error. This algorithm was long forgotten because even the best variants of it performed poorly when compared to the simplest ISD algorithm. We revisit this old algorithm by using parity-check equations in a more general way. Here the parity-checks are used to get LPN samples with a secret which is part of the error and the LPN noise is related to the weight of the parity-checks we produce. The corresponding LPN problem is then solved by standard Fourier techniques. By properly choosing the method of producing these low weight equations and the size of the LPN problem, we are able to outperform in this way significantly information set decodings at code rates smaller than 0.3. It gives for the first time after 60 years, a better decoding algorithm for a significant range which does not belong to the ISD family.

• Faster Dual Lattice Attacks by Using Coding Theory

  Kévin Carrier, Yixin Shen, Jean-Pierre Tillich. IACR pre-print, December 2022

  Link: https://eprint.iacr.org/archive/2022/1750

  Abstract: We present a faster dual lattice attack on the Learning with Errors (LWE) problem, based on ideas from coding theory. Basically, it consists of revisiting the most recent dual attack of [Matzov22] and replacing modulus switching by a decoding algorithm. This replacement achieves a reduction from small LWE to plain LWE with a very significant reduction of the secret dimension. We also replace the enumeration part of this attack by betting that the secret is zero on the part where we want to enumerate it and iterate this bet over other choices of the enumeration part. We estimate the complexity of this attack by making the optimistic, but realistic guess that we can use polar codes for this decoding task. We show that under this assumption the best attacks on Kyber and Saber can be improved by 1 and 6 bits.

• Near-collisions finding problem for decoding and recognition of error correcting codes

  Kévin Carrier. PhD thesis, Sorbonne Université (France), June 2020.

  Link: https://hal.science/tel-03370678v4

  Abstract: Error correcting codes are tools whose initial function is to correct errors caused by imperfect communication channels. In a non-cooperative context, there is the problem of identifying unknown codes based solely on knowledge of noisy codewords. This problem can be difficult for certain code families, in particular LDPC codes which are very common in modern telecommunication systems. In this thesis, we propose new techniques to more easily recognize these codes. At the end of the 1970s, McEliece had the idea of ​​redirecting the original function of codes to use in ciphers; thus initiating a family of cryptographic solutions which is an alternative to those based on number theory problems. One of the advantages of code-based cryptography is that it seems to withstand the quantum computing paradigm; notably thanks to the robustness of the generic decoding problem. The latter has been thoroughly studied for more than 60 years. The latest improvements all rely on using algorithms for finding pairs of points that are close to each other in a list. This is the so called near-collisions search problem. In this thesis, we improve the generic decoding by asking in particular for a new way to find close pairs. To do this, we use list decoding of Arikan's polar codes to build new fuzzy hashing functions. In this manuscript, we also deal with the search for pairs of far points. Our solution can be used to improve decoding over long distances. This new type of decoding finds very recent applications in certain signature models.

• Identifying an Unknown Code by Partial Gaussian Elimination

  Kévin Carrier, Jean-Pierre Tillich. Designs, Codes and Cryptography (DCC), Springer, March 2019.

  Link: https://link.springer.com/article/10.1007/s10623-018-00593-7

  Abstract: We consider in this paper the problem of reconstructing a linear code from a set of noisy codewords. We revisit the algorithms that have been devised for solving this problem and show that by generalizing and mixing two approaches that have been proposed in this setting, we obtain a significantly better algorithm. It basically consists in setting up a matrix whose rows are the noisy codewords, then running a partial Gaussian algorithm on it and detecting a small set of columns outside the echelon part of the matrix whose sum is sparse. We view the last task of the algorithm as an instance of the well known close neighbors search problem and we use an algorithm due to Dubiner to solve it more efficiently than the naive projection method which is generally invoked in this case. We analyze the complexity of our algorithm by focusing on an important practical case, namely when the code is an LDPC code. In doing so, we also obtain a result of independent interest, namely a tight upper-bound on the expected weight distribution of the dual of an LDPC code in a form that allows to derive an asymptotic formula.

→ View full list of publications