CryptoDB
LWE Without Modular Reduction and Improved Side-Channel Attacks Against BLISS
| Authors: | |
|---|---|
| Download: | |
| 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
}