### Abstract

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 double-struck F _{p} as kP = k_{1}P + k_{2}Φ(P), with max{|k _{1}|, |k_{2}|} ≤ C_{1}√n, for some explicit constant C_{1} > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck F_{p}2 which are twists of curves defined over double-struck F_{p}. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck F_{p}2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck F_{p}2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k_{1}P + k_{2}Φ(P) + k_{3}Ψ(P) + k_{4}ΨΦ(P) with max_{i}(|k_{i}|) <C_{2} n^{1/4}, for some explicit C_{2} <0. Remarkably, taking the best C_{1}, C_{2}, we obtain C_{2}/C_{1} <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

Original language | English |
---|---|

Title of host publication | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Pages | 718-739 |

Number of pages | 22 |

Volume | 7658 LNCS |

DOIs | |

Publication status | Published - 2012 |

Event | 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 - Beijing, China Duration: Dec 2 2012 → Dec 6 2012 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 7658 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Other

Other | 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012 |
---|---|

Country | China |

City | Beijing |

Period | 12/2/12 → 12/6/12 |

### Fingerprint

### Keywords

- Elliptic curves
- GLV-GLS method
- Multicore computation
- Scalar multiplication
- Side-channel protection
- Twisted Edwards curve

### ASJC Scopus subject areas

- Computer Science(all)
- Theoretical Computer Science

### Cite this

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)*(Vol. 7658 LNCS, pp. 718-739). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7658 LNCS). https://doi.org/10.1007/978-3-642-34961-4_43

**Four-dimensional Gallant-Lambert-Vanstone scalar multiplication.** / Longa, Patrick; Sica, Francesco.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

*Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics).*vol. 7658 LNCS, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7658 LNCS, pp. 718-739, 18th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2012, Beijing, China, 12/2/12. https://doi.org/10.1007/978-3-642-34961-4_43

}

TY - GEN

T1 - Four-dimensional Gallant-Lambert-Vanstone scalar multiplication

AU - Longa, Patrick

AU - Sica, Francesco

PY - 2012

Y1 - 2012

N2 - 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 double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

AB - 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 double-struck F p as kP = k1P + k2Φ(P), with max{|k 1|, |k2|} ≤ C1√n, for some explicit constant C1 > 0. Recently, Galbraith, Lin and Scott (EUROCRYPT 2009) extended this method to all curves over double-struck Fp2 which are twists of curves defined over double-struck Fp. We show in this work how to merge the two approaches in order to get, for twists of any GLV curve over double-struck Fp2 , a four-dimensional decomposition together with fast endomorphisms Φ, Ψ over double-struck Fp2 acting on the group generated by a point P of prime order n, resulting in a proven decomposition for any scalar k ∈ [1, n] given by kP = k1P + k2Φ(P) + k3Ψ(P) + k4ΨΦ(P) with maxi(|ki|) <C2 n1/4, for some explicit C2 <0. Remarkably, taking the best C1, C2, we obtain C2/C1 <412, independently of the curve, ensuring in theory an almost constant relative speedup. In practice, our experiments reveal that the use of the merged GLV-GLS approach supports a scalar multiplication that runs up to 50% times faster than the original GLV method. We then improve this performance even further by exploiting the Twisted Edwards model and show that curves originally slower may become extremely efficient on this model. In addition, we analyze the performance of the method on a multicore setting and describe how to efficiently protect GLV-based scalar multiplication against several side-channel attacks. Our implementations improve the state-of-the-art performance of point multiplication for a variety of scenarios including side-channel protected and unprotected cases with sequential and multicore execution.

KW - Elliptic curves

KW - GLV-GLS method

KW - Multicore computation

KW - Scalar multiplication

KW - Side-channel protection

KW - Twisted Edwards curve

UR - http://www.scopus.com/inward/record.url?scp=84871584771&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84871584771&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-34961-4_43

DO - 10.1007/978-3-642-34961-4_43

M3 - Conference contribution

SN - 9783642349607

VL - 7658 LNCS

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 718

EP - 739

BT - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

ER -