Skip to Main content Skip to Navigation
Journal articles

Randomized Mixed-Radix Scalar Multiplication

Eleonora Guerrini 1 Laurent Imbert 1 Théo Winterhalter 2
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [43 references]  Display  Hide  Download
Contributor : Laurent Imbert <>
Submitted on : Friday, October 6, 2017 - 10:20:00 AM
Last modification on : Wednesday, October 9, 2019 - 9:42:02 AM


Files produced by the author(s)



Eleonora Guerrini, Laurent Imbert, Théo Winterhalter. Randomized Mixed-Radix Scalar Multiplication. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2017, 67 (3), pp.418-431. ⟨10.1109/TC.2017.2750677⟩. ⟨lirmm-01587488v2⟩



Record views


Files downloads