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
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download

https://hal.inria.fr/hal-00674251
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
Long-term archiving on : Thursday, June 21, 2012 - 2:21:24 AM

File

rand_eac_ecc.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

341

Files downloads

366