Algebraic Approaches for the Elliptic Curve Discrete Logarithm Problem over Prime Fields

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Authors

Colleges, School and Institutes

External organisations

  • Mathematical Institute, University of Oxford
  • University of California, Irvine, USA
  • University of Passau, Germany

Abstract

The elliptic curve discrete logarithm problem is one of the most important problems in cryptography. In recent years, several index calculus algorithms have been introduced for elliptic curves defined over extension fields, but the most important curves in practice, defined over prime fields, have so far appeared immune to these attacks.

In this paper we formally generalize previous attacks from binary curves to prime curves. We study the efficiency of our algorithms with computer experiments and we discuss their current and potential impact on elliptic curve standards.

Our algorithms are only practical for small parameters at the moment and their asymptotic analysis is limited by our understanding of Gröbner basis algorithms. Nevertheless, they highlight a potential vulnerability on prime curves which our community needs to explore further.

Details

Original languageEnglish
Title of host publicationPublic-Key Cryptography – PKC 2016
Subtitle of host publication19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II
EditorsChen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang
Publication statusPublished - 18 Feb 2016
Event19th IACR International Conference on Practice and Theory in Public-Key Cryptography - Taipei, Taiwan, Province of China
Duration: 6 Mar 20169 Mar 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9615
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th IACR International Conference on Practice and Theory in Public-Key Cryptography
CountryTaiwan, Province of China
CityTaipei
Period6/03/169/03/16