Paper 2016/1022

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.