Randomized Mixed-Radix Scalar Multiplication - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles IEEE Transactions on Computers Year : 2018

Randomized Mixed-Radix Scalar Multiplication

Eleonora Guerrini
Laurent Imbert


A set of congruence relations is a Z-covering if each integer belongs to at least one congruence class from that set. In this paper, we first show that most existing scalar multiplication algorithms can be formulated in terms of covering systems of congruences. Then, using a special form of covering systems called exact n-covers, we present a novel uniformly randomized scalar multiplication algorithm with built-in protections against most passive side-channel attacks. Our algorithm randomizes the addition chain using a mixed-radix representation of the scalar. Its reduced overhead and purposeful robustness could make it a sound replacement to several conventional countermeasures. In particular, it is significantly faster than Coron's scalar blinding technique for elliptic curves when the choice of a particular finite field tailored for speed compels to double the size of the scalar, hence the cost of the scalar multiplication.
Fichier principal
Vignette du fichier
cover_systems_ieeetc.pdf (845.29 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-01587488 , version 1 (14-09-2017)
lirmm-01587488 , version 2 (06-10-2017)



Eleonora Guerrini, Laurent Imbert, Théo Winterhalter. Randomized Mixed-Radix Scalar Multiplication. IEEE Transactions on Computers, 2018, 67 (3), pp.418-431. ⟨10.1109/TC.2017.2750677⟩. ⟨lirmm-01587488v2⟩
267 View
421 Download



Gmail Mastodon Facebook X LinkedIn More