Solving ECDLP over F p with Pre-computation via Representation Technique

Claire Delaplace (1, 2) , Pierre-Alain Fouque (3, 4) , Paul Kirchner (3, 4) , Alexander May (1, 2)

1 RUB - Ruhr University Bochum = Ruhr-Universität Bochum
2 Horst Görtz Institute for IT-security
3 UR - Université de Rennes
4 EMSEC - EMbedded SEcurity and Cryptography

We present a new algorithm solving the elliptic curve discrete logarithm problem (ECDLP) with pre-computation. Our method is based on recent work from Delaplace and May (NuTMiC 2019) which aims to solve ECDLP over some quadratic field F p 2 using the so-called representation technique. We first revisit Delaplace and May's algorithm and show that with better routines, it runs in time p, improving on the p 1.314 time complexity given by the authors. Then, we show that this method can be converted to a p 4/5-algorithm, assuming that we have performed a p 6/5-pre-computation step in advance. Finally, we extend our method to other fields F p , where ≥ 2 is a constant, leading to a p 2 /(2 +1)-algorithm, after a p (+1)/(2 +1)-pre-computation step. Although our method does not improve on previous ECDLP with pre-computation algorithm (namely the one from Bernstein and Lange), we think it offers an elegant alternative, which can hopefully lead to further improvements, the idea of using the representation technique for ECDLP being very new.

Domaines: Cryptographie et sécurité [cs.CR]

Claire Delaplace, Pierre-Alain Fouque, Paul Kirchner, Alexander May. Solving ECDLP over F p with Pre-computation via Representation Technique. 2020. ⟨hal-02427655⟩