Welcome to the resource topic for 2021/1255
Title:
How to Find Ternary LWE Keys Using Locality Sensitive Hashing
Authors: Elena Kirshanova, 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}.
ePrint: https://eprint.iacr.org/2021/1255
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .