[PhD position] Discrete logarithm in finite fields with small extensions
Context: Cryptology is the study of techniques used by two entities to communicate in secret in the presence of adversaries. These techniques, or cryptosystems, which detail how to encrypt and decrypt messages, are designed around computational hard problems. The mathematical properties underlying these problems ensure that the attack of such algorithms remains unfeasible in practice by a malicious adversary, even if he has the entire computing power of the planet. Thus, the protocols involved are based on various assumptions often from number theory, such as the presumed hardness of factoring large integers or computing the discrete logarithm of a random element in some groups.
The aim of this thesis is to evaluate the weaknesses of one of the major problems on which current public key cryptography is based: the discrete logarithm problem, here considered in the case of finite fields of small extensions. For this, the PhD student will have to analyze the different existing algorithms to attack this problem, to design new efficient variants in practice or with a better theoretical asymptotic complexity, and to validate his results by efficient implementations.
Travel to conferences or seminars, in France or abroad, is possible for this position, depending on the evolution of local and global health conditions. Should this be the case, travel expenses will be covered within the limits of the current scale. Also depending on the health conditions, it is possible that part of the mission will be carried out remotely.
This thesis will focus on several questions. The PhD student will first learn about the number field sieve (NFS) as well as its various variants. All of these algorithms, however, are built around several steps: polynomial selection, sieving, linear algebra and final reconstruction of a discrete logarithm.
For non prime extensions, the PhD student will have to appropriate the most relevant attack algorithm in this context, TNFS. A better understanding of TNFS is essential today, as existing key size estimates are based on the general algorithm (NFS) and are therefore likely no longer adequate. For example, the GF(p^4) field with p a prime number of 298 bits appears naturally in some proposals, like blockchains. These bodies, which come from cryptography based on pairings, are necessary for the implementation of new zero-knowledge protocols (Zk-znark), which are essential for the writing of smart contracts. However, the size of the keys seems alarming: p^4 is 1192 bits, which is certainly well beyond the current records (392 bits attacked in 2015 for a field with extension 4) but it is now a potential target for TNFS.
In this context, different and complementary tracks will be explored. Sieving in TNFS requires enumerating vectors in Euclidean lattices of dimension greater than 4, where NFS stopped in dimension 2. Several ideas to improve the sieve are to be considered: study spaces of various geometries (spheres, orthotopes, ellipsoids…), find an alternative to the first step of network orthogonalization etc.
The last phase of reconstruction of individual logarithm also requires an adaptation. First works of Guillevic go in this direction, and propose a step particularly adapted to TNFS. A promising avenue of research for the candidate would be to combine it with the usual methods of NFS.
Finally, all the research carried out will not lose sight of the objective of tackling also finite fields of small but non-prime extensions. The adequate variants of TNFS do not apply anymore. It is then necessary to come back to NFS, and more precisely to its multiple variant: MNFS. Asymptotically, MNFS is known to be the most efficient algorithm but its behavior in practice is still unknown. One axis of this thesis will therefore be to explore this path. Similarly, if in theory the composition of T and M variants of NFS is possible and gives optimal results, the behavior of such a hybrid algorithm is still unclear for concrete parameter sizes. Strong improvements are expected, when MNFS is put into practice.
For a better understanding of the proposed research topic:
A state of the art on the discrete logarithm problem is available here:
Some seminal articles that can also be consulted:
- TNFS algorithm: Razvan Barbulescu, Pierrick Gaudry, et Thorsten Kleinjung. The tower number field sieve. In Tetsu Iwata and Jung Hee Cheon, editors, ASIACRYPT 2015, Part II, volume 9453 of LNCS, pages 31–55. Springer, Heidelberg, November / December 2015.
- MNFS algorithm: Razvan Barbulescu et Cécile Pierrot. The Multiple Number Field Sieve for Medium and High Characteristic Finite Fields. LMS Journal of Computation and Mathematics, 17 : 230– 246, 2014.
- Individual discrete logarithm for TNFS: Aurore Guillevic. Faster individual discrete logarithms in finite fields of composite extension degree. Mathematics of Computation, 88(317) :1273–1301, January 2019.
Collaboration / Supervision:
The recruited person will be under the supervision of Emmanuel Thomé, Directeur de Recherche, and Cécile Pierrot, Chargée de Recherche. He/she will be fully integrated in CARAMBA, a research team whose members are interested in algorithmic issues related to cryptography. More information here: https://www.inria.fr/equipes/caramba
Teaching: The person recruited will be able to apply to carry out a complementary teaching activity on the Nancy site (Faculty of Science, IUT, Ecole des Mines de Nancy…). This activity, which is in no way mandatory or guaranteed, may be covered by a rider to the doctoral contract allowing for a salary supplement.
Main activities :
- Analyze different Euclidean lattice enumeration algorithms for high-dimensional screening and define the best strategy in the framework of TNFS.
- Design algorithmic solutions for the discrete log reconstruction of TNFS.
- Propose concrete parameters for the implementation of MNFS and perform a first practical attack with it.
- To study the possibility of combining MNFS and TNFS in practice.
- To propagate the obtained advances towards factorization.
- Write the obtained advances in the form of scientific papers.
- Present the work in conference before an audience of experts in the field.
Technical skills and level required:
Master 2 (or equivalent) in Computer Science or Mathematics
French or English
The person recruited will be required to communicate regularly with his/her supervisors. He/she is expected to be present in the laboratory on a daily basis (depending on health conditions) and to integrate and actively participate in the life of the team.
No offers are available for now.