Sujet du stage : Quantum-resistant Code-based Signature Primitives

Within the SystemX Technological Research Institute, located in the heart of the world-class scientific campus of Paris-Saclay, you will take an active part in the development and influence of a world-class technological research center in the field of digital systems engineering. Every day, our engineersresearchers address new uses that meet the major societal and technological challenges of our time.
Within mixed teams made up of industrialists and academics, in relation with the best French research organizations in the field, they generate new knowledge and technological solutions and participate in the dissemination of these skills in all economic sectors. Together, they accelerate the digital transformation of industries, services and territories.

You will be supervised by a SystemX research engineer from the Digital Security and Networks research team.
The position is based at IRT SystemX – Palaiseau

Présentation du sujet du stage

Objectifs du stage 

Cryptographic systems are built upon complex mathematical problems such as integer factorization and computing discrete logarithms [1] [2], which can only be solved if knowledge of some secret data is available; typically a very large number. Without these numbers, it is impossible to reverse-engineer encrypted data or create a fraudulent digital signature. These numbers are what we know as cryptographic keys. For instance, the RSA algorithm [3] works by using pairs of very large prime numbers
to generate public and private keys. The public key can be used to create a mathematical challenge that can only be solved by someone who holds the private key. Attempting to guess the answer, by way of a brute-force search, would take thousands of years using contemporary computers. Unlike their classical counterparts, quantum computers will be able to solve these mathematical problems incredibly quickly for example: the security algorithms we use today that would take roughly 10 billion years to decrypt could take as little as 10 seconds.

The asymmetric algorithms we use today for digital signatures and key exchange will no longer be strong enough to keep data secret once a sufficiently powerful quantum computer can be built. This context alludes to the fact that both symmetric and asymmetric algorithms which are in widespread use today can succumb to quantum attacks and hence, quantum attack resistant or in other words postquantum cryptographic algorithms need to be evolved.
Code-based cryptography (CBC) is one of the well-known post-quantum cryptography (PQC) and secured its position in the outcome of 3rd round NIST competition as a one of finalist encryption scheme. One of its most promising applications is the design of cryptographic schemes with exceptionally strong security guarantees and other esirable properties. Examples are the McEliece and the Niederreiter encryption schemes [4, 5]. The underlying problem, the Syndrome Decoding problem, has been proven NPcomplete.

CBC allows the construction of different cryptographic schemes (e.g. public-key cryptosystem, digital signature, identification scheme, etc.). CBC has been recommended by the PQC Project of Europe that it has managed to withstand attacks. Usually quite fast and does not require a crypto-processor. However, CBC usually suffers from large keys (of order megabytes). This drawback is usually dealt with using structured codes such as quasi-cyclic or alternant codes. One of the most promising solutions for encryption exploits quasi-cyclic moderate density parity check codes (QC-MDPC), yielding key sizes of several thousands bytes. Thus, CBC can be made more efficient using structured codes but it has an issue of long key sizes.

The use of too much structured codes within the McEliece framework has unfortunately a dramatically long record of weaknesses, where the hidden structure of the secret key can be exhibited using distinguishers. Introducing other techniques (such as quasi-cyclicity) to obtain compact representations of the public key might also introduce weaknesses at the same time. The most efficient approach to solve coding theory problems is generally Information Set Decoding (ISD) algorithms. It is widely admitted that such algorithms do not perform much better in presence of structured codes than for the generic case, except for certain problems [7]. Yet, given that two alternate candidates in the 3rd round of the NIST PQC standardization effort use such codes, it is of prime importance investigating these aspects further.

Missions :

  • Investigation and study of existing state of the art code-based signature schemes, and their analysis and comparisons
  • Proposal of a solution to solve one of limitations in existing code-based signature scheme
  • Design and implementation of code-based signature primitives
  • Implementation of the novel code-based signature scheme and analysis of results
  • Submission of the obtained results to conference/workshop.

References  :

[1] P. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997
[2] S. Y. Yan. Integer factorization and discrete logarithms. In Primality testing and integer factorization in public-Key cryptography, pages 139-191. Springer, 2004.
[3] R. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital for signatures and public-key cryptosystems. Communications of the ACM, 21:120–126, 1978.
[4] M. R. A public-key cryptosystem based on algebraic coding theory, 1978.
[5] N. H. Knapsack-type cryptosystems and algebraic coding theory. Problems of Control and Information Theory, 15(2):159–166, 1986.
[6] R. Misoczki, J. P. Tillich, N. Sendrier, and P. S. Barreto. Mdpc-mceliece: New mceliece variants from moderate density parity-check codes. In IEEE International Symposium on Information Theory Proceedings (ISIT), page 2069–2073, 2013.
[7] N. Sendrier. Decoding One Out of Many. Available at https://eprint.iacr.org/2011/367.pdf

Profil et compétences

De formation : De formation : BAC +5/école d’ingénieur 3 année, dans le domaine de la cryptographie

Skills :

  • Candidates are expected to have a Masters degree, in either Engineering, Computer Science or Mathematics.
  • Programming skills: Rust/C++/Python
  • Good knowledge of cryptography and information security.
  • Good communication skills, both written and spoken in English.

    Personal skills
    Good interpersonal skills
    have a desire to work collaboratively

Informations clés

Durée du stage : 6 mois
Date de démarrage envisagée : mars 2022
Localisation du poste : Cluster Paris Saclay (91)
Référence de l’offre à mentionner dans l’objet de votre e-mail de candidature : DSR-2021-32-Explo


Postuler à cette offre d’emploi

Merci d’indiquer la référence du stage dans l’objet de votre mail de candidature


Partager cette offre d’emploi :

Inscrivez-vous à la newsletter de l'IRT SystemX

et recevez chaque mois les dernières actualités de l'institut :