Randomized Mixed-Radix Scalar Multiplication

Eleonora Guerrini 1 Laurent Imbert 1 Theo Winterhalter 2
1 ECO - Exact Computing
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : A set of congruence relations is a Z-covering if each integer belongs to at least one congruence class from that set. In this paper, we first 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 with built-in protections against most passive side-channel attacks. Our algorithm randomizes the addition chain using a mixed-radix representation of the scalar. Its reduced overhead and purposeful robustness could make it a sound replacement to several conventional countermeasures. In particular, it is significantly faster than Coron's scalar blinding technique for elliptic curves when the choice of a particular finite field tailored for speed compels to double the size of the scalar, hence the cost of the scalar multiplication.
Type de document :
Article dans une revue
IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2017, In press. 〈10.1109/TC.2017.2750677〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01587488
Contributeur : Laurent Imbert <>
Soumis le : vendredi 6 octobre 2017 - 10:20:00
Dernière modification le : jeudi 24 mai 2018 - 15:59:24

Fichier

cover_systems_ieeetc.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Eleonora Guerrini, Laurent Imbert, Theo Winterhalter. Randomized Mixed-Radix Scalar Multiplication. IEEE Transactions on Computers, Institute of Electrical and Electronics Engineers, 2017, In press. 〈10.1109/TC.2017.2750677〉. 〈lirmm-01587488v2〉

Partager

Métriques

Consultations de la notice

86

Téléchargements de fichiers

65