**Randomized Mixed-Radix Scalar Multiplication**

*Eleonora Guerrini and 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 \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 \mbox{$n$-covers}, we present a novel uniformly randomized scalar
multiplication algorithm with built-in protections against various types of
side-channel attacks. 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.

**Category / Keywords: **Elliptic curve arithmetic, Side-channel attacks

**Date: **received 27 Oct 2016, last revised 6 Oct 2017

**Contact author: **Laurent Imbert at lirmm fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20171006:082510 (All versions of this report)

**Short URL: **ia.cr/2016/1022

[ Cryptology ePrint archive ]