Paper 2019/1180
Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over NTRU Lattices
Pierre-Alain Fouque, Paul Kirchner, Mehdi Tibouchi, Alexandre Wallet, and Yang Yu
Abstract
In this paper, we initiate the study of side-channel leakage in hash-and-sign lattice-based signatures, with particular emphasis on the two efficient implementations of the original GPV lattice-trapdoor paradigm for signatures, namely NIST second-round candidate Falcon and its simpler predecessor DLP. Both of these schemes implement the GPV signature scheme over NTRU lattices, achieving great speed-ups over the general lattice case. Our results are mainly threefold.
First, we identify a specific source of side-channel leakage in most implementations of those schemes. Signing in lattice-based hash-and-sign schemes involves sampling a lattice point according to a Gaussian distribution. This reduces to sampling several one-dimensional discrete Gaussian distributions with standard deviations determined by the Gram--Schmidt norms of the secret lattice basis. Our observation is that those norms often leak through timing side-channels in the implementation of the one-dimensional Gaussian samplers.
Second, we elucidate the link between this leakage and the secret key, by showing that the entire secret key can be efficiently reconstructed solely from those Gram--Schmidt norms. The result makes heavy use of the algebraic structure of the corresponding schemes, which work over a power-of-two cyclotomic field. To establish it, we propose efficient algorithms of independent interest which, given the leading principal minors of the matrix associated to a totally positive field element (in the power basis for DLP and the bit-reversed order basis for Falcon) recover the element up to conjugation. In the case of those schemes, that element is
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A major revision of an IACR publication in EUROCRYPT 2020
- Keywords
- CryptanalysisLattice-Based CryptographyNTRULattice Gaussian SamplingTiming AttacksAlgebraic Number Theory
- Contact author(s)
-
pa fouque @ gmail com
paul kirchner @ irisa fr
mtibouchi @ gmail com
wallet alexandre @ gmail com
yang yu0986 @ gmail com - History
- 2020-03-26: last of 4 revisions
- 2019-10-10: received
- See all versions
- Short URL
- https://ia.cr/2019/1180
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/1180, author = {Pierre-Alain Fouque and Paul Kirchner and Mehdi Tibouchi and Alexandre Wallet and Yang Yu}, title = {Key Recovery from Gram-Schmidt Norm Leakage in Hash-and-Sign Signatures over {NTRU} Lattices}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/1180}, year = {2019}, url = {https://eprint.iacr.org/2019/1180} }