The primal attack reduces Learning with Errors (LWE) to the unique Shortest Vector Problem (uSVP), and then applies lattice reduction such as BKZ to solve the latter. Estimating the cost of the attack is required to evaluate the security of constructions based on LWE. Existing fine-grained estimators for the cost of the primal attack, due to Dachman-Soled–Ducas–Gong–Rossi (CRYPTO 2020) and Postlethwaite–Virdia (PKC 2021), differ from experimental data as they implicitly assume the unique shortest vector is resampled several times during the attack, changing its length. Furthermore, these estimators consider only the first two moments of the LWE secret and error, and therefore do not differentiate between distinct centred distributions with equal variances. We remedy both issues by initially fixing the short vector’s length, and later integrating over its distribution. We provide extensive experimental evidence that our estimators are more accurate and faithfully capture the behaviour of different LWE distributions. In the case of Module-LWE, lattice reduction utilising the module structure could lead to cheaper attacks. We build upon the analysis of module lattice reduction by Ducas–Engelberts–Perthuis (Asiacrypt 2025), providing a simulator for Module-BKZ generalising the BKZ simulator of Chen–Nguyen (Asiacrypt 2011). We design estimators for a module variant of the primal attack, supporting our analysis with experimental evidence. Asymptotically, we show the module primal attack over a degree d number field K has a reduced cost, resulting in a subexponential gain, whenever the discriminant \Delta_K satisfies \abs\Delta_K < d^d, one such case being non-power-two cyclotomics.
@inproceedings{PQC:PerTre26,author={{Paola de Perthuis} and Trenki\'c, Filip},title={Refined Modelling of the Primal Attack, and Variants Against Module-Learning With Errors},year={2026},month=apr,journal={PQCrypto},booktitle={Advances in Cryptology - {PQCrypto} 2026 - 17th International Conference on Post-Quantum Cryptology, Saint-Malo, France, April 14-16, 2026, Proceedings}}
@inproceedings{AC:DucEngPer25,author={Ducas, Léo and Engelberts, Lynn and {Paola de Perthuis}},title={Predicting Module-Lattice Reduction},year={2025},month=dec,journal={ASIACRYPT},booktitle={Advances in Cryptology - {ASIACRYPT} 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, Australia, December 8-12, 2025, Proceedings},}
ESOR:BHPP25
Security Analysis of Covercrypt: A Quantum-Safe Hybrid Key Encapsulation Mechanism for Hidden Access Policies
@inproceedings{ESORICS:BHPP25,author={Brézot, Théophile and Hébant, Chloé and {Paola de Perthuis} and Pointcheval, David},title={Security Analysis of Covercrypt: A Quantum-Safe Hybrid Key Encapsulation Mechanism for Hidden Access Policies},booktitle={Computer Security - {ESORICS} 2025 - 30th European Symposium on Research
in Computer Security, Toulouse, France, September 22-26,
2025, Proceedings},series={Lecture Notes in Computer Science},publisher={Springer},journal={ESORICS},year={2025},month=sep,}
2023
AC:FKP23
Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces
@inproceedings{AC:FioKolPer23,author={Fiore, Dario and Kolonelos, Dimitris and {Paola de Perthuis}},title={Cuckoo Commitments: Registration-Based Encryption and Key-Value Map
Commitments for Large Spaces},editor={Guo, Jian and Steinfeld, Ron},booktitle={Advances in Cryptology - {ASIACRYPT} 2023 - 29th International Conference
on the Theory and Application of Cryptology and Information Security,
Guangzhou, China, December 4-8, 2023, Proceedings, Part {V}},series={Lecture Notes in Computer Science},volume={14442},pages={166--200},publisher={Springer},journal={ASIACRYPT},year={2023},month=dec,doi={10.1007/978-981-99-8733-7_6},}
ESOR:BPP23
Covercrypt: An Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE
@inproceedings{ESORICS:BrePerPoi23,author={Brézot, Théophile and {Paola de Perthuis} and Pointcheval, David},title={Covercrypt: An Efficient Early-Abort {KEM} for Hidden Access Policies
with Traceability from the {DDH} and {LWE}},editor={Tsudik, Gene and Conti, Mauro and Liang, Kaitai and Smaragdakis, Georgios},booktitle={Computer Security - {ESORICS} 2023 - 28th European Symposium on Research
in Computer Security, The Hague, The Netherlands, September 25-29,
2023, Proceedings, Part {I}},series={Lecture Notes in Computer Science},volume={14344},pages={372--392},publisher={Springer},journal={ESORICS},year={2023},month=sep,doi={10.1007/978-3-031-50594-2_19},}
2022
CCS:PP22
Two-Client Inner-Product Functional Encryption with an Application to Money-Laundering Detection
@inproceedings{CCS:PerPoi22,author={{Paola de Perthuis} and Pointcheval, David},title={Two-Client Inner-Product Functional Encryption with an Application
to Money-Laundering Detection},editor={Yin, Heng and Stavrou, Angelos and Cremers, Cas and Shi, Elaine},booktitle={Proceedings of the 2022 {ACM} {SIGSAC} Conference on Computer and
Communications Security, {CCS} 2022, Los Angeles, CA, USA, November
7-11, 2022},pages={725--737},publisher={{ACM}},journal={ACM CCS},year={2022},month=nov,doi={10.1145/3548606.3559374},}
SCN:INPP22
MyOPE: Malicious SecuritY for Oblivious Polynomial Evaluation
Oblivious Polynomial Evaluation (OPE) schemes are interactive protocols between a sender with a private polynomial and a receiver with a private evaluation point where the receiver learns the evaluation of the polynomial in their point and no additional information. In this work, we introduce MyOPE, a “short-sighted” non-interactive polynomial evaluation scheme with a poly-logarithmic communication complexity in the presence of malicious senders. In addition to strong privacy guarantees, MyOPE enforces honest sender behavior and consistency by adding verifiability to the calculations.
@inproceedings{SCN:INPP22,author={Izabach{\`e}ne, Malika and Nitulescu, Anca and de Perthuis, Paola and Pointcheval, David},editor={Galdi, Clemente and Jarecki, Stanislaw},title={MyOPE: Malicious SecuritY for Oblivious Polynomial Evaluation},booktitle={Security and Cryptography for Networks},journal={Security and Cryptography for Networks},year={2022},month=sep,publisher={Springer International Publishing},address={Cham},pages={663--686},isbn={978-3-031-14791-3},}
Unpublished
2025
EPR:PerTre25
Refined Modelling of the Primal Attack, and Variants Against Module-Learning With Errors
The primal attack reduces Learning with Errors (LWE) to the unique Shortest Vector Problem (uSVP), and then applies lattice reduction such as BKZ to solve the latter. Estimating the cost of the attack is required to evaluate the security of constructions based on LWE. Existing fine-grained estimators for the cost of the primal attack, due to Dachman-Soled–Ducas–Gong–Rossi (CRYPTO 2020) and Postlethwaite–Virdia (PKC 2021), differ from experimental data as they implicitly assume the unique shortest vector is resampled several times during the attack, changing its length. Furthermore, these estimators consider only the first two moments of the LWE secret and error, and therefore do not differentiate between distinct centred distributions with equal variances. We remedy both issues by initially fixing the short vector’s length, and later integrating over its distribution. We provide extensive experimental evidence that our estimators are more accurate and faithfully capture the behaviour of different LWE distributions. In the case of Module-LWE, lattice reduction utilising the module structure could lead to cheaper attacks. We build upon the analysis of module lattice reduction by Ducas–Engelberts–Perthuis (Asiacrypt 2025), providing a simulator for Module-BKZ generalising the BKZ simulator of Chen–Nguyen (Asiacrypt 2011). We design estimators for a module variant of the primal attack, supporting our analysis with experimental evidence. Asymptotically, we show the module primal attack over a degree d number field K has a reduced cost, resulting in a subexponential gain, whenever the discriminant \Delta_K satisfies \abs\Delta_K < d^d, one such case being non-power-two cyclotomics.
@unpublished{EPRINT:PerTre25,author={{Paola de Perthuis} and Trenki\'c, Filip},title={Refined Modelling of the Primal Attack, and Variants Against Module-Learning With Errors},year={2025},month=oct,}
@unpublished{EPRINT:DucEngPer25,author={Ducas, Léo and Engelberts, Lynn and de Perthuis, Paola},title={Predicting Module-Lattice Reduction},howpublished={Cryptology {ePrint} Archive, Paper 2025/1904},year={2025},journal={Cryptology {ePrint} Archive, Paper 2025/1904},month={},}
@unpublished{ARX:DucEngPer25,title={Predicting Module-Lattice Reduction},author={Ducas, Léo and Engelberts, Lynn and de Perthuis, Paola},year={2025},month={},eprint={2510.10540},archiveprefix={arXiv},journal={arXiv},primaryclass={cs.CR},}
EPR:BHPP25
Security Analysis of Covercrypt: A Quantum-Safe Hybrid Key Encapsulation Mechanism for Hidden Access Policies
@unpublished{EPRINT:BHPP25,author={Brézot, Théophile and Hébant, Chloé and {Paola de Perthuis} and Pointcheval, David},title={Security Analysis of Covercrypt: A Quantum-Safe Hybrid Key Encapsulation Mechanism for Hidden Access Policies},howpublished={Cryptology {ePrint} Archive, Paper 2025/544},journal={Cryptology {ePrint} Archive, Paper 2025/544},year={2025},month={},}
2024
EPR:PP24
Post-Quantum Privacy for Traceable Receipt-Free Encryption
@unpublished{EPRINT:PerPet24,author={{Paola de Perthuis} and Peters, Thomas},title={Post-Quantum Privacy for Traceable Receipt-Free Encryption},howpublished={Cryptology {ePrint} Archive, Paper 2024/2087},journal={Cryptology {ePrint} Archive, Paper 2024/2087},year={2024},month={},}
2023
EPR:FKP23
Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces
@unpublished{EPRINT:FioKolPer23,author={Fiore, Dario and Kolonelos, Dimitris and {Paola de Perthuis}},title={Cuckoo Commitments: Registration-Based Encryption and Key-Value Map Commitments for Large Spaces},howpublished={Cryptology {ePrint} Archive, Paper 2023/1389},year={2023},journal={Cryptology {ePrint} Archive, Paper 2023/1389},month={},}
EPR:BPP23
Covercrypt: an Efficient Early-Abort KEM for Hidden Access Policies with Traceability from the DDH and LWE
@unpublished{EPRINT:BrePerPoi23,author={Brézot, Théophile and {Paola de Perthuis} and Pointcheval, David},title={Covercrypt: an Efficient Early-Abort {KEM} for Hidden Access Policies with Traceability from the {DDH} and {LWE}},howpublished={Cryptology {ePrint} Archive, Paper 2023/836},journal={Cryptology {ePrint} Archive, Paper 2023/836},year={2023},month={},}
ARX:KHCPM23
Catch Me If You Can: Semi-supervised Graph Learning for Spotting Money Laundering
Md. Rezaul Karim, Felix Hermsen, Sisay Adugna Chala, Paola de Perthuis, and Avikarsha Mandal
@unpublished{ARXIV:KHCPM23,title={Catch Me If You Can: Semi-supervised Graph Learning for Spotting Money Laundering},author={Karim, Md. Rezaul and Hermsen, Felix and Chala, Sisay Adugna and {Paola de Perthuis} and Mandal, Avikarsha},year={2023},month={},eprint={2302.11880},journal={arXiv},archiveprefix={arXiv},primaryclass={cs.AI},}
2022
EPR:PP22
Two-Client Inner-Product Functional Encryption, with an Application to Money-Laundering Detection
@unpublished{EPRINT:PerPoi22,author={{Paola de Perthuis} and Pointcheval, David},title={Two-Client Inner-Product Functional Encryption, with an Application to Money-Laundering Detection},year={2022},month={},howpublished={Cryptology ePrint Archive, Report 2022/441},journal={Cryptology ePrint Archive, Report 2022/441},}
2021
EPR:INPP21
MyOPE: Malicious securitY for Oblivious Polynomial Evaluation
@unpublished{EPRINT:INPP21,author={Izabach{\`e}ne, Malika and Nitulescu, Anca and {Paola de Perthuis} and Pointcheval, David},title={{MyOPE}: Malicious {securitY} for Oblivious Polynomial Evaluation},year={2021},month={},howpublished={Cryptology ePrint Archive, Report 2021/1291},journal={Cryptology ePrint Archive, Report 2021/1291},}
Theses
2024
Perthuis24
Calculs sous garanties et chiffrement à clé publique extensible dans des contextes non interactifs
Les constructions avancées de chiffrement à clé publique élargissent les horizons d’utilisation des primitives cryptographiques, permettant entre autres la réalisation de calculs sur des données inconnues cachées dans des chiffrés, ou d’étendre des fonctionnalités de chiffrement à des systèmes comprenant de nombreuses personnes de manière efficace. De plus, lorsque les entités prenant part à un protocole cryptographique ne sont pas systématiquement synchrones ou disponibles en même temps, l’élaboration de techniques non-interactives devient plus avantageuse ; en outre, lors d’un déploiement pour une grande communauté, l’évitement d’une solution avec une entité centrale, en plus de ne pas nécessiter sa disponibilité constante, diminue son pouvoir au sein du système. Ces fonctionnalités de pointe amènent des problématiques spécifiques ; ainsi, si un calcul combinant des informations confidentielles issues de sources distinctes est permis, l’étendue des opérations réalisables devra être surveillée attentivement afin d’éviter que celles-ci ne provoquent de trop grosses fuites sur les informations en jeu. À l’avenant, le chiffrement au sein d’une grande communauté, sans interactions avec une entité centrale, soulève des problématiques d’efficacité, à là fois pour atteindre des sous-ensembles de personnes, ou pour leur envoyer des messages individuellement, et d’autant plus dans des cas où celles-ci généreraient leurs propres clés secrètes sans les divulguer à une autorité. Cette thèse apportera des réponses aux questions évoquées ci-avant dans des contextes de calculs ou d’utilisations particulières. Dans une première partie, deux contributions permettront d’accéder à des modèles de sécurité plus réalistes que dans l’état de l’art précédent, pour des types de calculs restreints. Ensuite, deux autres permettront de rendre utilisables en pratique des protocoles de chiffrement au sein de grandes structures, avec des tailles et temps de calculs effectifs efficaces, au sein de modèles de sécurité conformes aux exigences actuelles.
@phdthesis{Perthuis24,author={{Paola de Perthuis}},school={École Normale Supérieure de Paris},title={Calculs sous garanties et chiffrement à clé publique extensible dans des contextes non interactifs},year={2024},month={},}
Journal Articles
2024
IEEE:KHCPM24
Scalable Semi-Supervised Graph Learning Techniques for Anti Money Laundering
Md. Rezaul Karim, Felix Hermsen, Sisay Adugna Chala, Paola de Perthuis, and Avikarsha Mandal
@article{IEEE:KHCPM24,author={Karim, Md. Rezaul and Hermsen, Felix and Chala, Sisay Adugna and {Paola de Perthuis} and Mandal, Avikarsha},title={Scalable Semi-Supervised Graph Learning Techniques for Anti Money
Laundering},journal={{IEEE} Access},volume={12},pages={50012--50029},year={2024},month={},doi={10.1109/ACCESS.2024.3383784},timestamp={Tue, 16 Apr 2024 13:57:09 +0200},}