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 sidechannel 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)
 Publication info
 Preprint. MINOR revision.
 Keywords
 Scalar multiplicationsidechannel attacksrandomized algorithmscovering systems of congruence
 Contact author(s)
 laurent imbert @ lirmm fr
 History
 20160212: revised
 20150519: received
 See all versions
 Short URL
 https://ia.cr/2015/475
 License

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} }