Supervision : Damien VERGNAUD

Mathematical studies of arithmetical pseudo-random numbers generators

Linear pseudo-random number generators are easy to understand and implement. The most famous of these is the linear congruential generator. In the first part of this thesis, we present this generator and the various key recovery algorithms that have been designed against it since the 1970s. Because this generator is simple, it has been used to design more complex generators, which we have attacked.

Other pseudo-random number generators are based on difficult problems, such as the Knapsack generator and its variants. Unfortunately they are unproven, even under the assumption that the underlying problem, the Subset Sum problem, is hard. We have also tackled them successfully.

Phd defence : 07/04/2023

Jury members :

Adeline Roux-Langlois, chargée de recherche au CNRS [rapporteur]
Mehdi Tibouchi, Industriel chez NTT (Japon) [rapporteur]
Jean-Sébastion Coron, Professeur à l'Université du Luxembourg
María Naya-Plasencia,directrice de recherche à Inria Paris
Damien Vergnaud, Professeur à Sorbonne Université
Vincent Zucca, maître de conférences à l'Université de Perpignan

2020-2023 Publications

• 2023
  • F. Martinez : “Mathematical studies of arithmetical pseudo-random numbers generators”, thesis, phd defence 07/04/2023, supervision Vergnaud, Damien (2023)
  • Ch. Bouillaguet, F. Martinez, D. Vergnaud : “Cryptanalysis of a Generalized Subset-Sum Pseudorandom Generator”, 48^th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Leibniz-Zentrum für Informatik, Leibniz International Proceedings in Informatics (LIPIcs), Bordeaux, France, (Schloss Dagstuhl) (2023)
• 2022
  • F. Martinez : “Practical Seed-Recovery of Fast Cryptographic Pseudo-Random Number Generators”, Applied Cryptography and Network Security, vol. 13269, Lecture Notes in Computer Science, Rome, Italy, pp. 212-229, (Springer International Publishing) (2022)
  • F. Martinez : “Attacks on Pseudo Random Number Generators Hiding a Linear Structure”, Topics in Cryptology – CT-RSA 2022, vol. 13161, Lecture Notes in Computer Science, Virtual Event, United States, pp. 145-168, (Springer International Publishing) (2022)
  • Ch. Bouillaguet, F. Martinez, D. Vergnaud : “Cryptanalysis of Modular Exponentiation Outsourcing Protocols”, The Computer Journal, vol. 65 (9), pp. 2299–2314, (Oxford University Press (UK)) (2022)
• 2020
  • Ch. Bouillaguet, F. Martinez, J. Sauvage : “Practical seed-recovery for the PCG Pseudo-Random Number Generator”, IACR Transactions on Symmetric Cryptology, (Ruhr Universität Bochum) (2020)