HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Randomizing scalar multiplication using exact covering systems of congruences

Eleonora Guerrini 1 Laurent Imbert 1 Théo Winterhalter
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A covering system of congruences can be defined as a set of congruence relations of the form: $\{r_1\;(\mathrm{mod}\;m_1), r_2\;(\mathrm{mod}\;m_2), \dots, r_t\;(\mathrm{mod}\;m_t)\}$ for $m_1, \dots, m_t \in \mathbb{N}$ satisfying the property that for every integer $k$ in $\mathbb{Z}$, there exists at least an index $i \in \{1, \dots, t\}$ such that $k \equiv r_i \pmod{m_i}$. First, we 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 that may be used to counter differential side-channel attacks, and more generally physical attacks that require multiple executions of the algorithm. This algorithm can be an alternative to Coron's scalar blinding technique for elliptic curves, in particular when the choice of a particular finite field tailored for speed compels to use a large random factor.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [25 references]  Display  Hide  Download

Contributor : Laurent Imbert Connect in order to contact the contributor
Submitted on : Wednesday, May 29, 2019 - 11:08:58 AM
Last modification on : Tuesday, March 15, 2022 - 12:55:40 PM


Files produced by the author(s)


  • HAL Id : lirmm-01340672, version 1



Eleonora Guerrini, Laurent Imbert, Théo Winterhalter. Randomizing scalar multiplication using exact covering systems of congruences. 2015. ⟨lirmm-01340672⟩



Record views


Files downloads