Description
Secure multi-party computing often enhances efficiency by leveraging correlated randomness. Recently, Boyle et al. showcased the effectiveness of pseudorandom correlation generators (PCGs) in producing substantial correlated (pseudo)randomness, specifically for two-party random oblivious linear evaluations (OLEs). This process involves minimal interactions and subsequent local computations, enabling secure two-party computation with silent pre-processing. The methodology is extendable to N-party through programmable PCGs. However, existing programmable PCGs for OLEs face limitations, as they generate OLEs exclusively over large fields and relying on a recent divisible ring-LPN assumption lacking a robust security foundation. In this talk, I'll introduce the Quasi-Abelian Syndrome Decoding Problem, a broader interpretation of the Quasi-Cyclic decoding problem. The hardness of this new problem enables constructing programmable PCGs for OLE correlation on any field Fq (with q>2). This instantiation is resilient to attacks on the linear test framework and allows a reduction in search to decision, addressing weaknesses in previous constructions. This work is based on a joint work with Maxime Bombar, Geoffroy Couteau and Alain Couvreur.
Next sessions
-
Cyclotomic Cosets: Hidden Subgroup and Quantum Sieving Algorithm for Prime-Power Moduli
Speaker : Mathias Boucher - Université de Rennes
The Dihedral Coset Problem (DCP), also known as the hidden shift problem, plays a fundamental role in post-quantum public-key cryptography, since the Learning-With-Error problem reduces to DCP. The “Simon meets Kuperberg” quantum algorithm by Bonnetain and Naya-Plasencia solves the DCP in quasi-polynomial time when the modulus is a power of two. We provide a generalization of this algorithm for[…] -
Adelic reduction of module lattices
Speaker : Henry Bambury - DGA-MI et Inria Rennes
We give a strict generalisation of the LLL algorithm over number fields, based on the reduction theory of $GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. -- based on joint work with Seungki Kim, Changmin Lee and Phong Nguyen ---
Cryptography
-
-
European Cyber Week: atelier cryptographie post-quantique
Dans la continuité des éditions 2021, 2022 et 2024, la DGA — en partenariat avec CREACH LABS et avec le soutien de l'ANSSI, de l'IRISA, de l'IRMAR et du Pôle d'Excellence Cyber — organise la 4e édition de l'atelier consacré à la cryptographie post-quantique dans le cadre de l'European Cyber Week 2026. Attention, il faut s'inscrire (gratuitement) au préalable — s'inscrire à la conférence Les[…] -
Post-quantum day of the cryptography seminar
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. The talks will take place at Amphi E in building 02A. To register for lunch, please do so before oct 30th using this link. -
Chiffrement homomorphe à l'aide des groupes après Nuida
Speaker : 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
-
-
Nouveaux doctorants
Exposés courts des nouveaux doctorants (Elouan, Quentin, Eliot)