Improvement of FPPR method to solve ECDLP

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • Kyushu University, Nishi-ku, Japan
  • University College London
  • National Institute of Information and Communications Technology, Koganei, Japan
  • Institute of Systems, Information Technologies and Nanotechnologies, Sawara-ku, Japan
  • CREST, Japan Science and Technology Agency, Chiyoda-ku, Japan

Abstract

Solving the elliptic curve discrete logarithm problem (ECDLP) by using Gröbner basis has recently appeared as a new threat to the security of elliptic curve cryptography and pairing-based cryptosystems. At Eurocrypt 2012, Faugère,
Perret, Petit and Renault proposed a new method (FPPR method) using a multivariable polynomial system to solve ECDLP over finite fields of characteristic 2. At Asiacrypt 2012, Petit and Quisquater showed that this method may beat generic algorithms for extension degrees larger than about 2000. In this paper, we propose a variant of FPPR method that practically reduces the computation time and memory required. Our variant is based on the idea of symmetrization. This idea already provided practical improvements in several previous works for composite-degree extension fields, but its application to prime-degree extension fields has been more challenging. To exploit symmetries in an efficient way in that case, we specialize the definition of factor basis used in FPPR method to replace the original polynomial system by a new and simpler one. We provide theoretical and experimental evidence that our method is faster and requires less memory than FPPR method when the extension degree is large enough.

Details

Original languageEnglish
Article number1
JournalPacific Journal of Mathematics for Industry
Volume7
Issue number1
Early online date25 Mar 2015
Publication statusPublished - 1 Dec 2015

Keywords

  • Elliptic curve , Discrete logarithm problem, Index calculus, Multivariable polynomial system, Gröbner basis