Skip to Main content Skip to Navigation
Conference papers

Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication

Dahmun Goudarzi 1, 2, 3 Matthieu Rivain 1 Damien Vergnaud 2, 3
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique - ENS Paris, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
Abstract : Elliptic curve cryptography is today the prevailing approach to get efficient public-key cryptosystems and digital signatures. Most of elliptic curve signature schemes use a \emph{nonce} in the computation of each signature and the knowledge of this nonce is sufficient to fully recover the secret key of the scheme. Even a few bits of the nonce over several signatures allow a complete break of the scheme by lattice-based attacks. Several works have investigated how to efficiently apply such attacks when partial information on the nonce can be recovered through side-channel attacks. However, these attacks usually target unprotected implementation and/or make ideal assumptions on the recovered information, and it is not clear how they would perform in a scenario where common countermeasures are included and where only noisy information leaks via side channels. In this paper, we close this gap by applying such attack techniques against elliptic-curve signature implementations based on a blinded scalar multiplication. Specifically, we extend the famous Howgrave-Graham and Smart lattice attack when the nonces are blinded by the addition of a random multiple of the elliptic-curve group order or by a random Euclidean splitting. We then assume that noisy information on the blinded nonce can be obtained through a template attack targeting the underlying scalar multiplication and we show how to characterize the obtained likelihood scores under a realistic leakage assumption. To deal with this scenario, we introduce a filtering method which given a set of signatures and associated likelihood scores maximizes the success probability of the lattice attack. Our approach is backed up with attack simulation results for several signal-to-noise ratio of the exploited leakage.
Document type :
Conference papers
Complete list of metadata

Cited literature [36 references]  Display  Hide  Download
Contributor : Damien Vergnaud Connect in order to contact the contributor
Submitted on : Wednesday, May 13, 2020 - 11:19:18 AM
Last modification on : Thursday, March 17, 2022 - 10:08:54 AM


Files produced by the author(s)


  • HAL Id : hal-01379249, version 1



Dahmun Goudarzi, Matthieu Rivain, Damien Vergnaud. Lattice Attacks against Elliptic-Curve Signatures with Blinded Scalar Multiplication. Selected Areas in Cryptography - SAC 2016, Aug 2016, St. John’s, Canada. ⟨hal-01379249⟩



Record views


Files downloads