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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01587488
Contributor : Laurent Imbert <>
Submitted on : Friday, October 6, 2017 - 10:20:00 AM
Last modification on : Wednesday, October 9, 2019 - 9:42:02 AM

File

cover_systems_ieeetc.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

231

Files downloads

317