seminar
ALMASTY seminar
This page gives the program of the ALMASTY seminar and the joint Parisian cryptography seminar (currently organized by the CASCADE team).
Upcoming talks
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.
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, Nov 3, 2025 - 09:30 - 24-25/405
Christophe Levrat
TBD
(ALMASTY Seminar)