International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Jonathan Bootle
Claire Delaplace
Thomas Espitau
Pierre-Alain Fouque
Mehdi Tibouchi
Download:
DOI: 10.1007/978-3-030-03326-2_17
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2018
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 $$\mathbf {s}\in \mathbb {Z}^n$$ given polynomially many samples of the form $$(\mathbf {a},\langle \mathbf {a},\mathbf {s}\rangle + e)\in \mathbb {Z}^{n+1}$$ where $$\mathbf { 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 $$\mathbf { a}$$. We also provide almost tight bounds on the number of samples needed to recover $$\mathbf {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 $${\approx }7\%$$ in the CCS paper), and is also considerably faster.
BibTeX
@inproceedings{asiacrypt-2018-29152,
  title={LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS},
  booktitle={Advances in Cryptology – ASIACRYPT 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={11272},
  pages={494-524},
  doi={10.1007/978-3-030-03326-2_17},
  author={Jonathan Bootle and Claire Delaplace and Thomas Espitau and Pierre-Alain Fouque and Mehdi Tibouchi},
  year=2018
}