2011/06/25 by Peter Birkner, Birkner, Peter, Patrick Longa +3
Computer Science · Mathematics · #11A05 #11R04 #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #G.1.0 #Number Theory (math.NT) #acm:11A05 #acm:11R04 #cs.CR #math.NT #msc:11A05 #msc:11R04
paper · pdf · doi:10.48550/arxiv.1106.5149
23 pages, 3 figures. Changes from v3: corrected typo in proof of Lemma 5
arxiv created 2011/11/16 · arxiv updated 2011/11/17
The GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) computes any multiple kP of a point P of prime order n lying on an elliptic curve with a low-degree endomorphism Φ (called GLV curve) over \mathbbFp as [kP = k1P + k2Φ(P), \quadwith max|k1|,|k2|≤ C1√ n] for some explicit constant C1>0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over \mathbbFp2 which are twists of curves defined over \mathbbFp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over \mathbbFp2, a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over \mathbbFp2 acting on the group generated by a point P of prime order n, resulting in a proved decomposition for any scalar k∈[1,n] kP=k1P+ k2Φ(P)+ k3Ψ(P) + k4ΨΦ(P) with maxi (|ki|)< C2 n1/4 for some explicit C2>0. Furthermore, taking the best C1, C2, we get C2/C1<408, independently of the curve, ensuring a constant relative speedup. We also derive new families of GLV curves, corresponding to those curves with degree 3 endomorphisms.