Quasi-subfield polynomials and the elliptic curve discrete logarithm problem

Research output: Contribution to journalArticle

Authors

Colleges, School and Institutes

External organisations

  • University of Southern California
  • University of California, Irvine
  • Institute for Infocomm Research, Singapore
  • Nanyang Technical University

Abstract

We initiate the study of a new class of polynomials which we call quasi-subfield polynomials. First, we show that this class of polynomials could lead to more efficient attacks for the elliptic curve discrete logarithm problem via the index calculus approach. Specifically, we use these polynomials to construct factor bases for the index calculus approach and we provide explicit complexity bounds. Next, we investigate the existence of quasi-subfield polynomials.

Details

Original languageEnglish
Number of pages21
JournalJournal of Mathematical Cryptology
Publication statusAccepted/In press - 28 Nov 2018

Keywords

  • Elliptic Curve Discrete Logarithm Problem, Cryptanalysis, Finite fields