Temporary scientific engineer - algorithmics computer algebra and number theory - graduate degree or equivalent h/f

A propos d'Inria

Inria est l'institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l'interface d'autres disciplines. L'institut fait appel à de nombreux talents dans plus d'une quarantaine de métiers différents. 900 personnels d'appui à la recherche et à l'innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'eorce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie. Temporary scientific engineer / Algorithmics, Computer Algebra and Number Theory / Graduate degree or equivalent
Le descriptif de l'offre ci-dessous est en Anglais
Type de contrat : CDD

Contrat renouvelable : Oui

Niveau de diplôme exigé : Bac +5 ou équivalent

Fonction : Ingénieur scientifique contractuel

Niveau d'expérience souhaité : De 3 à 5 ans

Contexte et atouts du poste

Motivation :

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.

Mission confiée

Responsibilities :

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 existingsubroutines 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

Compétences

Technical skills and required level : Master's degree in mathematics, at least 3 years' experience in development or working in an academic setting or PhD in math.

Languages : working knowledge of English (essential, as documents will BE provided in English). If the employee is comfortable with French, French may also BE used as a working language, butthis is not mandatory. Any research articles will BE written in English.

Additional skills appreciated : this is a project that requires strong background in Math and Computer Science, and we are aware that is a combination that hardly ever exists, so curiosity about the other discipline will make the position more enjoyable for the candidate !

Rémunération

From 2692€ gross/month according to experience andqualifications