Sommaire

  • Cet exposé a été présenté le 19 septembre 2025 (13:45 - 14:45).

Description

  • Orateur

    Charles Meyer-Hilfiger - Inria Rennes

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

  • Post-quantum day of the cryptography seminar

    • 20 novembre 2026 (09:30 - 15:15)

    • Inria / IRISA - Room Aurigny (D165) - A map of the Beaulieu campus can be viewed at: https://www.univ-rennes.fr/en/beaulieu-campus-map (the building is south of the campus)

    A scientific day devoted to post-quantum cryptography, held in the wake of the European Cyber Week, with talks more technical than those presented at the ECW. To register for lunch, please do so before oct 30th using this link. The event has been moved to the IRISA / Inria building, Room Aurigny (D165). You will need an ID card to enter the building. 
  • Chiffrement homomorphe à l'aide des groupes après Nuida

    • 27 novembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Pierre Guillot - Ravel Technologies/Université de strasbourg

    Nuida et d'autres ont montré comment on peut obtenir un protocole de chiffrement pleinement homomorphe si l'on sait chiffrer les éléments d'un groupe G convenable, tout en sachant faire l'opération de G "en homomorphe". Les exemples étaient jusqu'à présent limités au chiffrement d'un bit à la fois, avec beaucoup d'opérations à effectuer pour "simuler" les portes logiques usuelles. Je vais[…]
    • Cryptography

  • Post-Quantum Signatures from Symmetric-Key-Friendly Techniques: From MPC-in-the-Head to VOLE-in-the-Head

    • 04 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Dung Bui - Northwestern University

    The MPC-in-the-Head (MPCitH) paradigm turns a secure multiparty computation protocol into a zero-knowledge proof and, via Fiat–Shamir, into a signature scheme whose security relies only on symmetric-key primitives. The framework of Katz, Kolesnikov and Wang (KKW, CCS18), which moves most of the MPC work into a committed preprocessing phase that the verifier checks by opening all-but-one of the[…]
  • Distinguishing and Attacking McEliece Cryptosystems Using GRS Codes with Higher-Weight Mask

    • 11 décembre 2026 (13:45 - 14:45)

    • IRMAR - Université de Rennes - Campus Beaulieu Bat. 22, RDC, Rennes - Amphi Lebesgue

    Orateur : Michael Schaller - University of Zürich, Applied Algebra group

    Due to the insecurity of McEliece cryptosystems instantiated with Generalized Reed-Solomon (GRS) codes, there have been several proposals of McEliece type systems that replace the permutation matrix by a matrix $M$ with larger row and column weight. In many of them, the secret key is still a GRS code.There have been successful attacks on some of those schemes with row and column weight between $1$[…]
  • Nouveaux doctorants

    • 08 janvier 2027 (13:45 - 14:45)

    • Salle Guernesey à l'ISTIC

    Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)
Voir les exposés passés