seminar

Monday, Sep 22, 2025 - 10:30 - 24-25/405

Mickaël Hamdad

Practical cryptanalysis of pseudorandom correlation generators based on quasi-Abelian syndrome decoding

(ALMASTY Seminar)

Quasi-Abelian Syndrome Decoding (QA-SD) is a recently introduced generalization of Ring-LPN that uses multivariate polynomials rings. As opposed to Ring-LPN, it enables the use of small finite field such as GF(3) and GF(4). It was introduced by Bombar et al (Crypto 2023) in order to obtain pseudorandom correlation generators for Beaver triples over small fields. This theoretical work was turned into a concrete and efficient protocol called F4OLEage by Bombar et al. (Asiacrypt 2024) that allows several parties to generate Beaver triples over GF(2).

We propose efficient algorithms to solve the decoding problem underlying the QA-SD assumption. We observe that it reduce to a sparse multivariate polynomial interpolation problem over a small finite field where the adversary only has access to random evaluation points, a blind spot in the otherwise rich landscape of sparse multivariate interpolation. We develop new algorithms for this problem: using simple techniques we interpolate polynomials with up to two monomials. By sending the problem to the field of complex numbers and using convex optimization techniques inspired by the field of “compressed sensing”, we can interpolate polynomials with more terms.

This enables us to break in practice parameters proposed by Bombar et al. at Crypto’23 and Asiacrypt’24 as well as Li et al. at Eurocrypt’25 (IACR flagship conferences Grand Slam). In the case of the F4OLEage protocol, our implementation recovers all the secrets in a few hours with probability 60%. This not only invalidates the security proofs, but it yields real-life privacy attacks against multiparty protocols using the Beaver triples generated by the broken pseudorandom correlation generators.

Monday, Sep 29, 2025 - 10:30 - 24-25/405

Ky Nguyen

TBD

(ALMASTY Seminar)

Monday, Oct 13, 2025 - 10:30 - 24-25/405

Haetham Al Aswad

Computing Discrete Logarithms in Finite Fields Faster with Galois automorphisms

(ALMASTY Seminar)

The Number Field Sieve (NFS) algorithm and its variants are the best algorithms to solve the discrete logarithm problem in finite fields. We will first take a look on how NFS works, and second, explore how Galois automorphisms can accelerate the hardest steps of NFS by quite large factors. We discuss an open problem of using Galois automorphisms of any order, and present our work that solves the problem for the two orders 6 and 12—whereas the previous solved orders stand at the only order 2. Consequently, this brings acceleration factors approximately equal to 36 and 144 to one of the two hardest steps in NFS, surpassing the prior record acceleration factor of 4. The work can be found here

Prior knowledge of NFS is not required.

Monday, Nov 3, 2025 - 09:30 - 24-25/405

Christophe Levrat

Highway to Hull: A new algorithm solving the matrix code equivalence problem

(ALMASTY Seminar)

The matrix code equivalence (MCE) problem, which is an algorithmic problem in rank metric coding theory, is at the core of a few recent signature schemes such as MEDS and ALTEQ. Recent works by Narayanan, Qiao and Tang on the one hand and by Ran and Samardjiska on the other hand tackle specific instances of MCE. In this talk, I will introduce the MCE problem, give an overview of these existing algorithms, and present a new algorithm which deals with a much broader range of possible parameters of MCE while preserving a similar complexity. This is joint work with Alain Couvreur.

Monday, Dec 15, 2025 - 09:30 - 24-25/405

Clémence Chevignard

TBD

(ALMASTY Seminar)

Monday, Sep 15, 2025 - 14:30 - 25-26/105

Samuel Bouaziz--Ermann

Cryptographic Primitives in Quantum Idealized Models

(Soutenance Thèse)

In this thesis, we study both classical and quantum cryptography within idealized quantum models. Previous work has shown that quantum resources can be used to construct cryptographic tasks that are proven or conjectured to be impossible in the classical setting. Here, we first prove lower bounds on the efficiency of any quantum algorithm that finds a subset-cover of a random function, a problem that has been conjectured to be hard for assessing the security of the post-quantum digital signature scheme SPHINCS+. Next, we extend existing impossibility results for constructing public-key encryption schemes in the quantum random oracle model by showing that a more general type of public-key encryption does not exist in this model. We then study quantum assumptions for cryptography that appear weaker than one-way functions, namely quantum pseudorandomness, and its relationship to quantum public key encryption and signature schemes, both clarifying and improving upon prior constructions and impossibility proofs. Finally, we establish the importance of the size of pseudorandomness by proving that quantum pseudorandomness cannot be shrunk, and we make progress toward showing that it cannot be amplified.