DESCRIPTION :
The RSA cryptosystem and the Diffie-Hellman key exchange protocol in finite fields (FF-DH) were the first primitives invented for public-key cryptography in the late 1970s. While post-quantum primitives are gaining considerable ground in academic research and are increasingly ready for large-scale use, their practical application is slow to take off. RSA and FF-DH are still very much alive and dominant in several contexts. These primitives are linked to difficult questions in number theory such as integer factorisation or the discrete logarithm problem in a finite field, which are therefore the basis of most modern cryptography, both today and for the next decade.
The main cryptographic tool for assessing the difficulty of these problems, and therefore the security of cryptography, is the algebraic sieve algorithm known as Number Field Sieve (NFS). The main focus of this work programme is to refine the accuracy with which we can assess the practical scope of cryptanalysis with NFS.
It is difficult to estimate the time and resources required to factor an integer. All regulatory bodies such as ANSSI recommend avoiding RSA, or preferring large RSA keys for security reasons, for example at least 2048 bits until 2030, and at least 3072 bits after that date. In environments where computing power is abundant, this recommendation is most often followed. However, in practice, we use cryptography that uses smaller keys. For example, the entire certification chain for French bank cards is based on the security of 1408-bit RSA. This is well below the recommended key sizes, but also well above the latest published academic records (829 bits in 2020). This situation is the result of a balance between risk assessment (danger of cryptanalysis) and costs (cost of upgrading equipment, for example on all payment terminals).
Context:
This short-term contract is part of a larger ANR project, Kleyptomaniac, in which we plan to use our expertise to provide robust assessments of the difficulty of discrete logarithms and factorisation, and advice on key sizes that are relevant today. We assume that over the next decade, post-quantum cryptographic primitives will penetrate a significant portion of the cryptographic landscape. However, given the importance of RSA and FF-DH, we assume that it will take more than a decade before RSA and Diffie-Hellman no longer protect important secrets. This situation requires that the resistance of RSA and FF-DH be studied even after the possible emergence of post-quantum alternatives, both to determine how long current products will remain secure and to determine when and how it will remain safe to use these primitives in future products.
Travel is possible for this position, to meet and collaborate with experts in the field, and to disseminate results at conferences. In all cases, this will be decided in consultation with the engineer and travel expenses will be covered within the limits of the current scale., The originality of this engineering position (which is part of Kleyptomaniac) lies not in attempting to make a breakthrough in cryptanalysis of the discrete logarithm or factorisation problem, but in accurately assessing the impact of potential technological breakthroughs. More specifically, the NFS algorithm breaks down into a complete chain of steps or sub-algorithms. The question we are asking is one of complexity: which sub-algorithm is most likely to give way? What complexity and what gains could we imagine achieving? Are there lower limits below which the algorithm cannot go? And above all, if breakthroughs occur in one or other of these sub-steps, what would be the consequence for the entire algorithm and for the vulnerability of related protocols? Could these breakthroughs be combined? All these questions arise from a heuristic point of view, and it will be necessary to simulate the behaviour of certain algorithms without worrying about building
them or proving their feasibility. Nevertheless, the complexity of the mathematical tools used in NFS requires a very solid background in number theory.
One question to consider, for example, is the impact of an 'ideal' polynomial selection. This question has already been addressed in previous work, but a more detailed analysis is desirable. There are no studies on the consequences of improvements in the subroutines of sparse linear algebra algorithms, which would make NFS even more efficient.
Collaboration and reference tool:
This research support position revolves around the free software CADO-NFS. It is a complete implementation of NFS in C and C++, developed through collaborative work over more than 15 years, with more than 23 regular authors.
The successful candidate will liaise with members of the Kleyptomaniac project who are part of the Caramba team. In particular, they will collaborate with the founders of CADO-NFS.
Principales activités
Main activities:
Analyse existing subroutines of NFS
Target where an improvement could change the game
Simulate the consequences of such a change on the whole algorithm
Give new advice on key sizes
Additional activities:
Write explanatory documentation for the algorithms developed
Contribute to the writing of scientific articles for the dissemination of results
Present the progress of the work internally and at conferences
Code d'emploi : Chercheur en Informatique (h/f)
Domaine professionnel actuel : Scientifiques
Niveau de formation : Bac+5
Temps partiel / Temps plein : Plein temps
Type de contrat : Contrat à durée déterminée (CDD)
Compétences : Public-Key Cryptography, C ++ (Langage de Programmation), RSA (Cryptosystem), Technologies Informatiques, Anglais, Français, Sens de l'Inclusion, Esprit d'Équipe, Recherche, Algèbre, Algorithmes, Activités de Conseil, Cryptographie, Organisation d'Événements, Algèbre Linéaire, Mathématiques, Analyse de Risques, Documentation Scientifique, Simulations, Vulnérabilité, Langue de Travail, Réalisation d'Évaluations, La Théorie du Nombre
Courriel :
cecile.pierrot@inria.fr
Téléphone :
0139635511
Type d'annonceur : Employeur direct
