## 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 DOI: 10.1007/978-3-030-03326-2_17 Search ePrint Search Google Slides ASIACRYPT 2018 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
}