Paper 2018/822

LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS

Jonathan Bootle, Claire Delaplace, Thomas Espitau, Pierre-Alain Fouque, and Mehdi Tibouchi

Abstract

This paper is devoted to analyzing the variant of Regev's learning with errors (LWE) problem in which modular reduction is omitted: namely, the problem (ILWE) of recovering a vector $\vec s\in\mathbb{Z}^n$ given polynomially many samples of the form $(\vec a,\langle\vec a,\vec s\rangle + e)\in\mathbb{Z}^{n+1}$ where $\vec a$ and $e$ follow fixed distributions. Unsurprisingly, this problem is much easier than LWE: under mild conditions on the distributions, we show that the problem can be solved efficiently as long as the variance of $e$ is not superpolynomially larger than that of $\vec a$. We also provide almost tight bounds on the number of samples needed to recover $\vec s$. Our interest in studying this problem stems from the side-channel attack against the BLISS lattice-based signature scheme described by Espitau et al. at CCS 2017. The attack targets a quadratic function of the secret that leaks in the rejection sampling step of BLISS. The same part of the algorithm also suffers from a linear leakage, but the authors claimed that this leakage could not be exploited due to signature compression: the linear system arising from it turns out to be noisy, and hence key recovery amounts to solving a high-dimensional problem analogous to LWE, which seemed infeasible. However, this noisy linear algebra problem does not involve any modular reduction: it is essentially an instance of ILWE, and can therefore be solved efficiently using our techniques. This allows us to obtain an improved side-channel attack on BLISS, which applies to 100% of secret keys (as opposed to ~7% in the CCS paper), and is also considerably faster.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in ASIACRYPT 2018
Keywords
LWE problemlattice-based cryptographyside-channel analysisBLISSleast squares regressionstatistical learningcompressed sensingconcentration inequalities
Contact author(s)
mehdi tibouchi @ normalesup org
History
2018-09-06: received
Short URL
https://ia.cr/2018/822
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/822,
      author = {Jonathan Bootle and Claire Delaplace and Thomas Espitau and Pierre-Alain Fouque and Mehdi Tibouchi},
      title = {LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS},
      howpublished = {Cryptology ePrint Archive, Paper 2018/822},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/822}},
      url = {https://eprint.iacr.org/2018/822}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.