## 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.

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.

Original language | English |
---|---|

Title of host publication | Public-Key Cryptography – PKC 2016 |

Subtitle of host publication | 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Taipei, Taiwan, March 6-9, 2016, Proceedings, Part II |

Editors | Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, Bo-Yin Yang |

Publisher | Springer |

Pages | 3-18 |

ISBN (Electronic) | 978-3-662-49387-8 |

ISBN (Print) | 978-3-662-49386-1 |

DOIs | |

Publication status | Published - 18 Feb 2016 |

Event | 19th IACR International Conference on Practice and Theory in Public-Key Cryptography - Taipei, Taiwan, Province of China Duration: 6 Mar 2016 → 9 Mar 2016 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 9615 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 19th IACR International Conference on Practice and Theory in Public-Key Cryptography |
---|---|

Country/Territory | Taiwan, Province of China |

City | Taipei |

Period | 6/03/16 → 9/03/16 |