Note: in Cryptology, authors are listed in alphabetical order; in my case with a P for Perthuis. When citing my name, use only Perthuis without de, e.g. `In Noorden—Perthuis [NP26], the authors etc.'.
Unpublished
2026
EPR:PerTre26
How Secure are NTRU+ Keys? Analysing the Best Module Attacks
A recent analysis of module-BKZ [Ducas–Engleberts–Perthuis, Asiacrypt’25] predicts subexponential speedups for lattice reduction on module lattices over cyclotomic fields whose conductor has small odd prime factors. This threatens NTRU+, the South Korean standard for key encapsulation, and related schemes; however, the short vectors one seeks to find are short in the coefficient geometry, whereas module-BKZ operates in the canonical geometry. We introduce relative canonical and relative coefficient embeddings, realising a module over a cyclotomic field K as a module over any subfield L, and characterise when the two agree up to scaling: exactly when the radicals of their respective conductors c and \ell satisfy rad(c)/rad(\ell) ∈{1,2}. Furthermore we quantify the distortion incurred in general when passing between embeddings, and hence identify the optimal subfield for module-BKZ and BKZ to use. Estimating the cost of the best attack with simulation-based models [Perthuis–Trenkić, PQCrypto’26], we find that the best module attack saves only 4–10 blocksizes, costing NTRU+ keys at most three bits of security in the Core-SVP model. We further extend the analysis of overstretched NTRU regimes [Ducas–Woerden, Asiacrypt’19] to the module setting, and find the fatigue point is reached sooner than with unstructured counterparts, though NTRU+ parameterisations remain safe.
@unpublished{EPRINT:PerTre25,author={Perthuis, {Paola de} and Trenki\'c, Filip},title={How Secure are NTRU+ Keys? Analysing the Best Module Attacks},year={2026},month=oct,}
Conference Articles
2026
SCN:NooPer26
Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action
Chris van Noorden, and Paola de Perthuis
In Security and Cryptography for Networks, Sep 2026
Post-quantum assumptions may not rely on the difficulty of finding secret subgroups as many classical schemes did. Instead, several assumptions make use of more general group actions, with the hope that quantum algorithms are not helpful in this less structured setting. Group action-based constructions were first presented in the context of isogenies in which an ideal class group acts on elliptic curves, but equivalence problems in error-correcting codes and lattices also exhibit such structures. Previous works presented anonymity-preserving constructions in a generic group action framework; however, they were not general enough to encompass the group action underlying the Lattice Isomorphism Problem (LIP), for which the acting group is countably infinite and non-commutative. We bridge this gap by, from zero-knowledge proofs of OR statements, building generic blind signatures and strong designated-verifier signatures with non-delegatability from standard assumptions corresponding to a generalised group action inverse problem.
@inproceedings{SCN:NooPer26,author={Noorden, {Chris van} and Perthuis, {Paola de}},title={Post-Quantum Anonymous Signatures from the Lattice Isomorphism Group Action},year={2026},booktitle={Security and Cryptography for Networks},journal={Security and Cryptography for Networks},month=sep,publisher={Springer International Publishing}}
PKC:PerPet26
Post-Quantum Privacy for Traceable Receipt-Free Encryption
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={Perthuis, {Paola de} and Trenki\'c, Filip},title={Refined Modelling of the Primal Attack, and Variants Against Module-Learning With Errors},year={2026},month=apr,journal={Post-Quantum Cryptology},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 Perthuis, {Paola de}},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 Perthuis, {Paola de} 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 Perthuis, {Paola de}},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 Perthuis, {Paola de} 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:PerPoi22
Two-Client Inner-Product Functional Encryption with an Application to Money-Laundering Detection
@inproceedings{CCS:PerPoi22,author={Perthuis, {Paola de} 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 Perthuis, Paola de 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},}
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={Perthuis, {Paola de}},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 Perthuis, {Paola de} 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},}