Random Euclidean Addition Chain Generation and Its Application to Point Multiplication

Abstract : Efficiency and security are the two main objectives of every elliptic curve scalar multiplication implementations. Many schemes have been proposed in order to speed up or secure its computation, usually thanks to efficient scalar representation [30,10,24], faster point operation formulae [8,25,13] or new curve shapes [2]. As an alternative to those general methods, authors have suggested to use scalar belonging to some subset with good computational properties [15,14,36,41,42], leading to faster but usually cryptographically weaker systems. In this paper, we use a similar approach. We propose to modify the key generation pro- cess using a small Euclidean addition chain c instead of a scalar k. This allows us to use a previous scheme, secure against side channel attacks, but whose efficiency relies on the computation of small chains computing the scalar. We propose two different ways to generate short Euclidean addition chains and give a first theoretical analysis of the size and dis- tribution of the obtained keys. We also propose a new scheme in the context of fixed base point scalar multiplication.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [37 references]  Display  Hide  Download

Contributor : Pascal Véron <>
Submitted on : Tuesday, March 20, 2012 - 4:14:31 PM
Last modification on : Monday, December 17, 2018 - 2:42:02 PM
Document(s) archivé(s) le : Thursday, June 21, 2012 - 2:21:24 AM


Publisher files allowed on an open archive




Fabien Herbaut, Pierre-Yvan Liardet, Nicolas Méloni, Yannick Teglia, Pascal Véron. Random Euclidean Addition Chain Generation and Its Application to Point Multiplication. INDOCRYPT 2010, Dec 2010, Hyderabad, India. pp.238-261, ⟨10.1007/978-3-642-17401-8_18⟩. ⟨hal-00674251⟩



Record views


Files downloads