Paper 2021/1255

How to Find Ternary LWE Keys Using Locality Sensitive Hashing

Elena Kirshanova and Alexander May

Abstract

Let As=b+emodq be an LWE-instance with ternary keys s,e{0,±1}n. Let s be taken from a search space of size S. A standard Meet-in-the-Middle attack recovers s in time S0.5. Using the representation technique, a recent improvement of May shows that this can be lowered to approximately S0.25 by guessing a sub-linear number of Θ(nlogn) 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 S0.3. We introduce a locality sensitive hashing (LSH) technique based on Odlyzko's work that avoids any guessing of '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 . Concretely, using LSH we lower the MitM complexity estimates for the currently suggested NTRU and NTRU Prime instantiations by a factor in the range , and for BLISS and GLP parameters by a factor in the range .

Metadata
Available format(s)
PDF
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.