Randomizing scalar multiplication using exact covering systems of congruences - Archive ouverte HAL Access content directly
Preprints, Working Papers, ... Year :

Randomizing scalar multiplication using exact covering systems of congruences

(1) , (1) ,
1
Eleonora Guerrini
Laurent Imbert
Théo Winterhalter
  • Function : Author
  • PersonId : 984344

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.
Fichier principal
Vignette du fichier
293955d0ed64b96bb02b5e6359890bf05fa4.pdf (436 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

lirmm-01340672 , version 1 (29-05-2019)

Identifiers

  • HAL Id : lirmm-01340672 , version 1

Cite

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

Share

Gmail Facebook Twitter LinkedIn More