CATREL

The discrete logarithm problem (DLP) in finite fields is a fundamental problem whose difficulty underpins the security of a large part of modern public-key cryptography. Key exchange protocols, for instance, typically rely on the assumed hardness of the DLP in finite fields. The area of pairing-based cryptography, which has been growing to maturity for slightly more than a decade, is another context where the finite field DLP is crucially important. The algorithms for solving the finite field DLP are the Function Field Sieve (FFS) and Number Field Sieve (NFS-DL) algorithms. The runtime of these ``sub-exponential'' algorithms is very hard to predict: theoretical complexity estimates fall short of providing reliable predictions. Computational difficulty is best shown by practice, for example with record computations. While the (similar) ``original'' NFS algorithm, which tackles the integer factorization problem, has historically received constant attention in this regard, its discrete logarithm counterpart has not enjoyed the same continuous interest. The current project proposes to study algorithmic and practical aspects of NFS-DL/FFS, and provide a thorough implementation work, which is also to be put into practice by computing records. The proposed work is a key ingredient for the assessment of the security of cryptosystems which rely on the hardness of the finite field DLP, and for deciding on the relevant key sizes. Moreover, the ongoing standardization effort for pairing-based cryptography inevitably needs to make similar choices. Such choices can be made sensible with respect to the security aspect only based on experimental data, which this project intends to provide. Both algorithmic and implementation work on this kind of research may undoubtedly be enriched by one another. Practical improvements are only made possible by thorough work on the algorithms, often including redesigning better-performing algorithms. Our work plan therefore targets objectives of both kinds. The precise aims of the current project are as follows: * Provide accessible software, with multiple facets. Emerging platforms such as general-purpose graphics processing units (GPGPU) and field-programmable gate arrays (FPGAs) are capable of contributing to such calculations in several fruitful ways. * Demonstrate and publicize our work by setting new DLP records, which are highly visible landmarks used for assessing the real security of cryptosystems. * Seek a better understanding of the NFS and FFS algorithms, and applications of this family of algorithms to other contexts. Another more strategic goal of this project is to affirm the position of the proponents as worldwide leaders on this topic.