Description
The hardness of the decoding problem and its generalization, the learning with errors problem, are respectively at the heart of the security of the Post-Quantum code-based scheme HQC and the lattice-based scheme Kyber. Both schemes are to be/now NIST standards. These problems have been actively studied for decades, and the complexity of the state-of-the-art algorithms to solve them is crucially used to correctly choose the secure parameters of those schemes. Dual attacks are a type of attack against these problems that were introduced some 20 years ago. They were at first uncompetitive against other techniques but they have been massively improved in recent years and now significantly outperform the state of the art in some regimes.
In the first part of the talk, I will quickly recall these recent advances with a focus on two of our code-based works in 2022 and 2023. Those attacks are tricky to analyze, and traditionally, some independence assumptions were used to make their analysis tractable. In particular, the analysis of two of the recent lattice-based attacks by Guo & Johansson (2021) and MATZOZ (2022) that both claimed to diminish the security of Kyber was critically based on them. Problematically, in this lattice setting, Ducas & Pulles showed in 2023 that these assumptions were critically flawed, casting serious doubts on the previous claims. In the code-based setting, these assumptions also cannot be used. The matter is now settled in both worlds as tools have been developed to carry out the analysis without those assumptions. In code, in 2023 we introduced an analysis technique based on an experimentally verified model in which the weight-enumerator of random linear codes acts like a Poisson variable with a good expected value. In lattices, we introduced in 2025 a new attack that we analyzed with an experimentally verified model and ultimately showed that our attack indeed dents the security of Kyber. In either case, these new analyses are quite involved. In the second part of this talk, we will recall the rough idea behind these techniques and introduce a novel algorithmic tweak that allows us to prove these attacks without using any assumptions whatsoever. This comes at the cost of a small polynomial overhead but also greatly simplifies the analysis. I will focus on the code-based setting for simplicity but will make a quick comparison with the lattice world.
This talk contains different joint works with Kévin Carrier, Thomas Debris-Alazard, Yixin Shen and Jean-Pierre Tillich.
Infos pratiques
Prochains exposés
-
Design of fast AES-based Universal Hash Functions and MACs
Orateur : Augustin Bariant - ANSSI
Ultra-fast AES round-based software cryptographic authentication/encryption primitives have recently seen important developments, fuelled by the authenticated encryption competition CAESAR and the prospect of future high-profile applications such as post-5G telecommunication technology security standards. In particular, Universal Hash Functions (UHF) are crucial primitives used as core components[…]-
Cryptography
-
-
Combining Partial Sums and FFT for the Fastest Known Attack on 6‑Round AES
Orateur : Shibam Ghosh - Inria
The partial-sums technique introduced by Ferguson et al. (2000) achieved a 6‑round AES attack with time complexity 2^{52} S‑box evaluations, a benchmark that has stood since. In 2014, Todo and Aoki proposed a comparable approach based on the Fast Fourier Transform (FFT). In this talk, I will show how to combine partial sums with FFT to get "the best of both worlds". The resulting attack on 6[…]-
Cryptography
-
-
Lie algebras and the security of cryptosystems based on classical varieties in disguise
Orateur : Mingjie Chen - KU Leuven
In 2006, de Graaf et al. proposed a strategy based on Lie algebras for finding a linear transformation in the projective linear group that connects two linearly equivalent projective varieties defined over the rational numbers. Their method succeeds for several families of “classical” varieties, such as Veronese varieties, which are known to have large automorphism groups. In this talk, we[…]-
Cryptography
-
-
Some applications of linear programming to Dilithium
Orateur : Paco AZEVEDO OLIVEIRA - Thales & UVSQ
Dilithium is a signature algorithm, considered post-quantum, and recently standardized under the name ML-DSA by NIST. Due to its security and performance, it is recommended in most use cases. During this presentation, I will outline the main ideas behind two studies, conducted in collaboration with Andersson Calle-Vierra, Benoît Cogliati, and Louis Goubin, which provide a better understanding of[…] -
Wagner’s Algorithm Provably Runs in Subexponential Time for SIS^∞
Orateur : Johanna Loyer - Inria Saclay
At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LWE) in slightly subexponential time for modulus q = poly(n) and narrow error distribution, when given enough LWE samples. Taking a modular view, one may regard BKW as a combination of Wagner’s algorithm (CRYPTO 2002), run[…]-
Cryptography
-
-
CryptoVerif: a computationally-sound security protocol verifier
Orateur : Bruno Blanchet - Inria
CryptoVerif is a security protocol verifier sound in the computational model of cryptography. It produces proofs by sequences of games, like those done manually by cryptographers. It has an automatic proof strategy and can also be guided by the user. It provides a generic method for specifying security assumptions on many cryptographic primitives, and can prove secrecy, authentication, and[…]-
Cryptography
-
-
Structured-Seed Local Pseudorandom Generators and their Applications
Orateur : Nikolas Melissaris - IRIF
We introduce structured‑seed local pseudorandom generators (SSL-PRGs), pseudorandom generators whose seed is drawn from an efficiently sampleable, structured distribution rather than uniformly. This seemingly modest relaxation turns out to capture many known applications of local PRGs, yet it can be realized from a broader family of hardness assumptions. Our main technical contribution is a[…]-
Cryptography
-