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.
Practical infos
Next sessions
-
Attacks and Remedies for Randomness in AI: Cryptanalysis of PHILOX and THREEFRY
Speaker : Yevhen Perehuda - Ruhr-University Bochum
In this work, we address the critical yet understudied question of the security of the most widely deployed pseudorandom number generators (PRNGs) in AI applications. We show that these generators are vulnerable to practical and low-cost attacks. With this in mind, we conduct an extensive survey of randomness usage in current applications to understand the efficiency requirements imposed in[…]-
Cryptography
-
-
Lightweight (AND, XOR) Implementations of Large-Degree S-boxes
Speaker : Marie Bolzer - LORIA
The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. In cryptography, the focus is on small functions, especially on S-boxes which are classically the only non-linear functions in iterated block ciphers. In this work, we propose new ad-hoc automatic tools to look for lightweight implementations of non-linear functions on up to 5 variables for[…]-
Cryptography
-
Symmetrical primitive
-
Implementation of cryptographic algorithm
-
-
Algorithms for post-quantum commutative group actions
Speaker : Marc Houben - Inria Bordeaux
At the historical foundation of isogeny-based cryptography lies a scheme known as CRS; a key exchange protocol based on class group actions on elliptic curves. Along with more efficient variants, such as CSIDH, this framework has emerged as a powerful building block for the construction of advanced post-quantum cryptographic primitives. Unfortunately, all protocols in this line of work are[…] -
Endomorphisms via Splittings
Speaker : Min-Yi Shen - No Affiliation
One of the fundamental hardness assumptions underlying isogeny-based cryptography is the problem of finding a non-trivial endomorphism of a given supersingular elliptic curve. In this talk, we show that the problem is related to the problem of finding a splitting of a principally polarised superspecial abelian surface. In particular, we provide formal security reductions and a proof-of-concept[…]-
Cryptography
-