Improved algorithms for an efficient arithmetic on some categories of elliptic curves. (2016)

• Record Type: Journal Article
• Authors: Hedabou, Mustapha
• Is Part Of: International journal of computational complexity and intelligent algorithms. Volume 1:Number 1(2016)
• Page Start: 54
• Page End: 67
• Publication Date: 2016
• Subjects: elliptic curves -- scalar multiplication -- Frobenius map -- normal basis -- tau-adic expansion -- precomputed tables -- Frobenius endomorphism -- cryptography -- security; Computational complexity -- Periodicals; Heuristic algorithms -- Periodicals; Neural networks (Computer science) -- Periodicals; 006.3
• Languages: English
• ISSNs: 2048-4720

Abstract

The Frobenius endomorphism τ is known to be useful for an efficient scalar multiplication on elliptic curves E(Fq m ) defined either over fields with small characteristics or over optimal extension fields. In this paper, we will present two techniques that aim to enhance the Frobenius-based methods for computing the scalar multiplication on these curves. The first method, called the generalised τ-adic method, is dedicated to improve the efficiency of the generalised τ-adic method when the elliptic curves are defined over fields of small characteristics. The generalised τ-adic with even digits improves substantially the computation time and the number of stored points whereas the generalised τ-adic with odd digits reduces only the number of stored points but it offers better resistance against the SPA attacks. The generalised τ-adic method is particularly efficient when the trace of the used curve is small. The second method allows to reduce by about 50% the number of the stored points by the Frobenius-based algorithm on elliptic curve defined over optimal extension fields. Finally, we show that there are a lot of curves which are well suited for cryptography, and for which the proposed methods can be applied.