Blanc SIMI 2 - Blanc - SIMI 2 - Science informatique et applications

Sieve Algorithms: Theoretical Advances, and Effective Resolution of the Discete Logarithm Problem. – CATREL

CATREL

Sieve Algorithms: Theoretical Advances, and Effective Resolution of the Discrete Logarithm Problem.

Aims

Study of the algorithms for solving the discrete logarithm problem in finite fields. The difficulty of this algorithmic problem is the keystone of the security of many cryptographic protocols.

Number field sieve, algorithms, programming, software optimisation.

Publications are online:

catrel.loria.fr/publications.en.html

We expect to provide new algorithms, as well as new software computation, intended to serve as a primary ingredient for assessing the state of the art and feasibility limits for the discrete logarithm problem in finite fields.

Publications are online:

catrel.loria.fr/publications.en.html

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.

Project coordination

Emmanuel THOMÉ (Centre de Recherche INRIA Nancy Grand Est) – Emmanuel.Thome@gmail.com

The author of this summary is the project coordinator, who is responsible for the content of this summary. The ANR declines any responsibility as for its contents.

Partner

INRIA Centre de Recherche INRIA Nancy Grand Est
Centre de Recherche Inria Saclay-Ile-de-France - équipe projet TANC Institut National de Recherche en Informatique et en Automatiques - Centre de Recherche Inria Saclay-Île-de-France équipe TANC
CNRS - LIRMM Laboratoire d'informatique, de robotique et de microéléctronique de Montpellier

Help of the ANR 673,202 euros
Beginning and duration of the scientific project: December 2012 - 36 Months

Useful links

Explorez notre base de projets financés

 

 

ANR makes available its datasets on funded projects, click here to find more.

Sign up for the latest news:
Subscribe to our newsletter