Randomized Mixed-Radix Scalar Multiplication

Eleonora Guerrini; Laurent Imbert; Théo Winterhalter

Paper 2016/1022

Randomized Mixed-Radix Scalar Multiplication

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} (\mod m_{1}), r_{2} (\mod m_{2}), \dots, r_{t} (\mod 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} (\mod 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{-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.

Metadata

Available format(s): PDF
Publication info: Preprint.
Keywords: Elliptic curve arithmetic Side-channel attacks
Contact author(s): Laurent Imbert @ lirmm fr
History: 2017-10-06: last of 3 revisions; 2016-11-01: received; See all versions
Short URL: https://ia.cr/2016/1022
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1022,
      author = {Eleonora Guerrini and Laurent Imbert and Théo Winterhalter},
      title = {Randomized Mixed-Radix Scalar Multiplication},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1022},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1022}
}