Paper 2015/475

Randomizing scalar multiplication using exact covering systems of congruences

Eleonora Guerrini, Laurent Imbert, and Théo Winterhalter

Abstract

A covering system of congruences can be defined as a set of congruence relations of the form: $\{r_1 \pmod{m_1}, r_2 \pmod{m_2}, \dots, r_t \pmod{m_t}\}$ for $m_1, \dots, m_t \in \N$ satisfying the property that for every integer $k$ in $\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.

Note: Updated version

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Scalar multiplicationside-channel attacksrandomized algorithmscovering systems of congruence
Contact author(s)
laurent imbert @ lirmm fr
History
2016-02-12: revised
2015-05-19: received
See all versions
Short URL
https://ia.cr/2015/475
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/475,
      author = {Eleonora Guerrini and Laurent Imbert and Théo Winterhalter},
      title = {Randomizing scalar multiplication using exact covering systems of congruences},
      howpublished = {Cryptology ePrint Archive, Paper 2015/475},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/475}},
      url = {https://eprint.iacr.org/2015/475}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.