Preventing differential analysis in GLV elliptic curve scalar multiplication

Mathieu Ciet, Jean Jacques Quisquater, Francesco Sica

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

In [2], Gallant, Lambert and Vanstone proposed a very efficient algorithm to compute Q = kP on elliptic curves having non-trivial efficiently computable endomorphisms. Cryptographic protocols are sensitive to implementations, indeed as shown in [6,7] information about the secret can be revealed analysing external leakage of the support, typically a smart card. Several software countermeasures have been proposed to protect the secret. However, speed computation is needed for practical use. In this paper, we propose & method to protect scalar multiplication on elliptic curves against Differential Analysis, that benefits from the speed of the Gallant, Lambert and Vanstone method. It can be viewed as a two-dimensional analogue of Coron's method [1] of randomising the exponent k. We propose two variants of this method (one linear and one affine), the second one slightly more effective, whereas the first one offers "two in one", combining point-blinding and exponent randomisation, which have hitherto been dealt separately. For instance, for at most a mere 37.5% (resp. 25%) computation speed loss on elliptic curves over fields with 160 (resp. 240) bits the computation of kP can take on 2 40 different consumption patterns.

Original languageEnglish
Pages (from-to)540-550
Number of pages11
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2523
Publication statusPublished - 2003
Externally publishedYes

Fingerprint

Scalar multiplication
Elliptic Curves
Smart cards
Exponent
Cryptographic Protocols
Smart Card
Endomorphisms
Countermeasures
Random Allocation
Randomisation
Leakage
Efficient Algorithms
Software
Analogue

Keywords

  • Differential power analysis
  • Elliptic curve cryptosystem
  • Fast computation
  • Public key cryptography

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)
  • Theoretical Computer Science

Cite this

@article{d68142e65c4a49dd890567dba87bbf3f,
title = "Preventing differential analysis in GLV elliptic curve scalar multiplication",
abstract = "In [2], Gallant, Lambert and Vanstone proposed a very efficient algorithm to compute Q = kP on elliptic curves having non-trivial efficiently computable endomorphisms. Cryptographic protocols are sensitive to implementations, indeed as shown in [6,7] information about the secret can be revealed analysing external leakage of the support, typically a smart card. Several software countermeasures have been proposed to protect the secret. However, speed computation is needed for practical use. In this paper, we propose & method to protect scalar multiplication on elliptic curves against Differential Analysis, that benefits from the speed of the Gallant, Lambert and Vanstone method. It can be viewed as a two-dimensional analogue of Coron's method [1] of randomising the exponent k. We propose two variants of this method (one linear and one affine), the second one slightly more effective, whereas the first one offers {"}two in one{"}, combining point-blinding and exponent randomisation, which have hitherto been dealt separately. For instance, for at most a mere 37.5{\%} (resp. 25{\%}) computation speed loss on elliptic curves over fields with 160 (resp. 240) bits the computation of kP can take on 2 40 different consumption patterns.",
keywords = "Differential power analysis, Elliptic curve cryptosystem, Fast computation, Public key cryptography",
author = "Mathieu Ciet and Quisquater, {Jean Jacques} and Francesco Sica",
year = "2003",
language = "English",
volume = "2523",
pages = "540--550",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Preventing differential analysis in GLV elliptic curve scalar multiplication

AU - Ciet, Mathieu

AU - Quisquater, Jean Jacques

AU - Sica, Francesco

PY - 2003

Y1 - 2003

N2 - In [2], Gallant, Lambert and Vanstone proposed a very efficient algorithm to compute Q = kP on elliptic curves having non-trivial efficiently computable endomorphisms. Cryptographic protocols are sensitive to implementations, indeed as shown in [6,7] information about the secret can be revealed analysing external leakage of the support, typically a smart card. Several software countermeasures have been proposed to protect the secret. However, speed computation is needed for practical use. In this paper, we propose & method to protect scalar multiplication on elliptic curves against Differential Analysis, that benefits from the speed of the Gallant, Lambert and Vanstone method. It can be viewed as a two-dimensional analogue of Coron's method [1] of randomising the exponent k. We propose two variants of this method (one linear and one affine), the second one slightly more effective, whereas the first one offers "two in one", combining point-blinding and exponent randomisation, which have hitherto been dealt separately. For instance, for at most a mere 37.5% (resp. 25%) computation speed loss on elliptic curves over fields with 160 (resp. 240) bits the computation of kP can take on 2 40 different consumption patterns.

AB - In [2], Gallant, Lambert and Vanstone proposed a very efficient algorithm to compute Q = kP on elliptic curves having non-trivial efficiently computable endomorphisms. Cryptographic protocols are sensitive to implementations, indeed as shown in [6,7] information about the secret can be revealed analysing external leakage of the support, typically a smart card. Several software countermeasures have been proposed to protect the secret. However, speed computation is needed for practical use. In this paper, we propose & method to protect scalar multiplication on elliptic curves against Differential Analysis, that benefits from the speed of the Gallant, Lambert and Vanstone method. It can be viewed as a two-dimensional analogue of Coron's method [1] of randomising the exponent k. We propose two variants of this method (one linear and one affine), the second one slightly more effective, whereas the first one offers "two in one", combining point-blinding and exponent randomisation, which have hitherto been dealt separately. For instance, for at most a mere 37.5% (resp. 25%) computation speed loss on elliptic curves over fields with 160 (resp. 240) bits the computation of kP can take on 2 40 different consumption patterns.

KW - Differential power analysis

KW - Elliptic curve cryptosystem

KW - Fast computation

KW - Public key cryptography

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

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

M3 - Article

VL - 2523

SP - 540

EP - 550

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -