Paper 2021/1255
How to Find Ternary LWE Keys Using Locality Sensitive Hashing
Elena Kirshanova and Alexander May
Abstract
Let $As = b + e \bmod q$ be an LWE-instance with ternary keys $s,e \in \{0, \pm 1\}^n$. Let $s$ be taken from a search space of size $\mathcal{S}$. A standard Meet-in-the-Middle attack recovers $s$ in time $\mathcal{S}^{0.5}$. Using the representation technique, a recent improvement of May shows that this can be lowered to approximately $\mathcal{S}^{0.25}$ by guessing a sub-linear number of $\Theta(\frac{n}{\log n})$ coordinates from $e$. While guessing such an amount of $e$ can asymptotically be neglected, for concrete instantiations of e.g. NTRU, BLISS or GLP the additional cost of guessing leads to complexities around $\mathcal{S}^{0.3}$. We introduce a locality sensitive hashing (LSH) technique based on Odlyzko's work that avoids any guessing of $e$'s coordinates. This LSH technique involves a comparably small cost such that we can significantly improve on previous results, pushing complexities towards the asymptotic bound $\mathcal{S}^{0.25}$. Concretely, using LSH we lower the MitM complexity estimates for the currently suggested NTRU and NTRU Prime instantiations by a factor in the range $2^{20}-2^{49}$, and for BLISS and GLP parameters by a factor in the range $2^{18}-2^{41}$.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. IMACC
- Keywords
- Ternary LWECombinatorial attackRepresentationsLSH
- Contact author(s)
-
elena kirshanova @ rub de
alex may @ rub de - History
- 2021-09-21: revised
- 2021-09-21: received
- See all versions
- Short URL
- https://ia.cr/2021/1255
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/1255, author = {Elena Kirshanova and Alexander May}, title = {How to Find Ternary {LWE} Keys Using Locality Sensitive Hashing}, howpublished = {Cryptology {ePrint} Archive, Paper 2021/1255}, year = {2021}, url = {https://eprint.iacr.org/2021/1255} }