Cryptology ePrint Archive: Report 2015/475

Randomizing Scalar Multiplication Using Exact Covering Systems of Congruences

Eleonora Guerrini and Laurent Imbert and Théo Winterhalter

Abstract: In this paper we present a generic, uniformly randomized scalar multiplication algorithm based on covering systems of congruences, with built-in protections against various side-channel attacks. It has been tailored to resist a recent class of attacks called horizontal attacks. These very powerful attacks exploit some unsuspected weaknesses hidden in most, if not all, highly regular and constant time algorithms. We provide a thorough complexity analysis, several arguments to support its robustness and some encouraging numerical experiments.

Category / Keywords: public-key cryptography / Scalar Multiplication, Side-Channel Attacks, Randomized Algorithms

Date: received 19 May 2015

Contact author: Laurent Imbert at lirmm fr

Available format(s): PDF | BibTeX Citation

Version: 20150519:210258 (All versions of this report)

Short URL: ia.cr/2015/475

Discussion forum: Show discussion | Start new discussion