Cryptology ePrint Archive: Report 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.

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

Date: received 27 Oct 2016, last revised 1 Nov 2016

Contact author: Laurent Imbert at lirmm fr

Available format(s): PDF | BibTeX Citation

Version: 20161101:102730 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]