Computer Science – Cryptography and Security
Scientific paper
2011-06-25
Computer Science
Cryptography and Security
23 pages, 3 figures. Changes from v3: corrected typo in proof of Lemma 5
Scientific paper
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 $\Phi$ (called GLV curve) over $\mathbb{F}_p$ as [kP = k_1P + k_2\Phi(P), \quad\text{with} \max{|k_1|,|k_2|}\leq C_1\sqrt n] for some explicit constant $C_1>0$. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over $\mathbb{F}_{p^2}$ which are twists of curves defined over $\mathbb{F}_p$. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over $\mathbb{F}_{p^2}$, a four-dimensional decomposition together with fast endomorphisms $\Phi, \Psi$ over $\mathbb{F}_{p^2}$ acting on the group generated by a point $P$ of prime order $n$, resulting in a proved decomposition for any scalar $k\in[1,n]$ $$ kP=k_1P+ k_2\Phi(P)+ k_3\Psi(P) + k_4\Psi\Phi(P)\quad \text{with} \max_i (|k_i|)< C_2\, n^{1/4} $$ for some explicit $C_2>0$. Furthermore, taking the best $C_1, C_2$, we get $C_2/C_1<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.
Birkner Peter
Longa Patrick
Sica Francesco
No associations
LandOfFree
Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Four-Dimensional Gallant-Lambert-Vanstone Scalar Multiplication will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-144972