Project

Back to overview

New discrete logarithm algorithms: theory and practice

English title New discrete logarithm algorithms: theory and practice
Applicant Lenstra Arjen K.
Number 156420
Funding scheme Project funding
Research institution Laboratoire de cryptologie algorithmique EPFL - IC - IIF - LACAL
Institution of higher education EPF Lausanne - EPFL
Main discipline Information Technology
Start/End 01.10.2014 - 30.09.2017
Approved amount 468'993.00
Show all

All Disciplines (2)

Discipline
Information Technology
Mathematics

Keywords (6)

discrete logarithm; complexity; cryptanalysis; extension fields; finite fields; index calculus

Lay Summary (German)

Lead
Dieses Projekt widmet sich der aktuellen Forschung im Bereich des diskreten Logarithmus Problems (DLP) in endlichen Körpern von kleiner Charakteristik. Vor einem Jahr wurde die 30 jährige Abwehr gegen vielseitige Angriffe auf das DLP ins Schwanken gebracht. Dieses grundlegende mathematische Problem ist von wesentlicher Bedeutung in der Kryptographie seit der Entdeckung der Public-Key Kryptosysteme in 1976. Neueste Ergebnisse der Forschung eröffnen verschiedene Möglichkeiten die Angriffe weiterzuentwickeln. Das übergeordnete Ziel des Projekts ist es die Gruppe LACAL zu einer führenden Forschergruppe im Bereich diskreter Logarithmus zu erheben, wie sie es bereits im Bereich Faktorisierung von ganzen Zahlen ist.
Lay summary
Dieses Projekt widmet sich der aktuellen Forschung im Bereich des diskreten Logarithmus Problems (DLP) in endlichen Körpern von kleiner Charakteristik. Vor einem Jahr wurde die 30 jährige Abwehr gegen vielseitige Angriffe auf das DLP ins Schwanken gebracht. Dieses grundlegende mathematische Problem ist von wesentlicher Bedeutung in der Kryptographie seit der Entdeckung der Public-Key Kryptosysteme in 1976. Neueste Ergebnisse der Forschung eröffnen verschiedene Möglichkeiten die Angriffe weiterzuentwickeln.
Das übergeordnete Ziel des Projekts ist es die Gruppe LACAL zu einer führenden Forschergruppe im Bereich diskreter Logarithmus zu erheben, wie sie es bereits im Bereich Faktorisierung von ganzen Zahlen ist.

Dr. Robert Granger hat sich vor kurzem LACAL angeschlossen. Er hat von Anfang an bei den neuesten Entwicklungen teilgenommen und sowohl die praktische als auch die theoretische Seite beleuchtet. Zusammen mit seinen Kollegen an der Universität Dublin haben sie die erste polynomielle Relationen Generation entwickelt und drei DLPs für große Zahlen gelöst, zwei darunter waren Rekorde.
Robert Granger, Thorsten Kleinjung (LACAL) und Jens Zumbrügel (TU Dresden) haben kürzlich die Schwäche des DLP für eine 128-bit singuläre binäre Kurve aufgezeigt. Diese Arbeit zeigte zum ersten Mal das eine bisher als sicher eingestuft Kurve tatsächlich keine Sicherheit bot. LACAL plant hier weiter zu forschen.

Neben dem puren Interesse ein DLP zu lösen, gibt es einige Anwendungen der benutzten DLP Algorithmen in der Mathematik. Während in der Kryptograhphie kleine Charakteristiken aufgrund der Entwicklungen weniger zum Einsatz kommen, kann es somit gut Auswirkungen auf andere Bereiche geben. Die derzeitigen Techniken sind noch im Stadium der Entwicklung und können während ihrer Verfeinerung noch weitere Überraschungen bereit halten.
Direct link to Lay Summary Last update: 26.09.2014

Responsible applicant and co-applicants

Employees

Publications

Publication
Indiscreet discrete logarithms
Granger Robert (2017), Indiscreet discrete logarithms, in Nieuw Archief voor Wiskunde, 5(18), 176-183.
Improved Masking for Tweakable Blockciphers with Applications to Authenticated Encryption.
Granger Robert, Jovanovic Philip, Mennink Bart, Neves Samuel (2016), Improved Masking for Tweakable Blockciphers with Applications to Authenticated Encryption., in Advances in Cryptology - EUROCRYPT 2016, ViennaSpringer, Berlin.
On the discrete logarithm problem in finite fields of fixed characteristic.
Granger Robert, Kleinjung Thorsten, Zumbr\"agel Jens (2016), On the discrete logarithm problem in finite fields of fixed characteristic., in Transactions of the AMS, 1-15.
Breaking `128-bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in $\F_{2^{4 \cdot 1223}}$ and $\F_{2^{12 \cdot 367}}$
Grange Robert, Kleinjung Thorsten, Zumbr\"agel Jens (2014), Breaking `128-bit Secure' Supersingular Binary Curves (or how to solve discrete logarithms in $\F_{2^{4 \cdot 1223}}$ and $\F_{2^{12 \cdot 367}}$, in Advances in Cryptology - CRYPTO 2014, Santa BarbaraSpringer, Berlin.

Collaboration

Group / person Country
Types of collaboration
Institute of Algebra, TU Dresden Germany (Europe)
- in-depth/constructive exchanges on approaches, methods or results
- Publication
Magma group Australia (Oceania)
- in-depth/constructive exchanges on approaches, methods or results
- Publication

Associated projects

Number Title Start Funding scheme
128727 Tightly coupled cluster 01.12.2009 R'EQUIP
144981 Scientific computing using commodity hardware 01.10.2014 R'EQUIP

Abstract

This proposal intends to continue the revolution taking place in the understanding of the discrete logarithm problem (DLP) in finite fields of small to medium characteristic, which began just one year ago after three decades of steadfast resistance against all cryptanalytic efforts. This fundamental computational problem has been of immense importance to cryptography since the invention of public key cryptography in 1976 and the recent developments have opened up the field completely, with several new and exciting vistas to explore. The overarching aim of the present proposal is to enable the laboratory for cryptologic algorithms (LACAL) at EPFL to become a world-leading centre for research in this area, thus complementing its leading role in integer factorization research.As well as being of intrinsic interest in itself, there are several applications of efficient DLP algorithms in coding theory and computational number theory. Therefore while cryptography may no longer be an appropriate application domain for small characteristic discrete logarithms in particular, the fledgling techniques are so immature that at this point it is impossible to predict what their full impact will be, or whether they can be extended to other important domains. With the proposed team and its existing resources, LACAL will be ideally placed to make great strides towards determining and shaping what this impact will be.
-