Quantum Key Search for Ternary LWE

Iggy van Hoof; Elena Kirshanova; Alexander May

Paper 2021/865

Quantum Key Search for Ternary LWE

Iggy van Hoof, Elena Kirshanova, and Alexander May

Abstract

Ternary LWE, i.e., LWE with coefficients of the secret and the error vectors taken from $\{-1, 0, 1\}$, is a popular choice among NTRU-type cryptosystems and some signatures schemes like BLISS and GLP. In this work we consider quantum combinatorial attacks on ternary LWE. Our algorithms are based on the quantum walk framework of Magniez-Nayak-Roland-Santha. At the heart of our algorithms is a combinatorial tool called the representation technique that appears in algorithms for the subset sum problem. This technique can also be applied to ternary LWE resulting in faster attacks. The focus of this work is quantum speed-ups for such representation-based attacks on LWE. When expressed in terms of the search space $\mathcal{S}$ for LWE keys, the asymptotic complexity of the representation attack drops from $\mathcal{S}^{0.24}$ (classical) down to $\mathcal{S}^{0.19}$ (quantum). This translates into noticeable attack's speed-ups for concrete NTRU instantiations like NTRU-HRSS and NTRU Prime. Our algorithms do not undermine current security claims for NTRU or other ternary LWE based schemes, yet they can lay ground for improvements of the combinatorial subroutines inside hybrid attacks on LWE.

Note: update 2021-12-10: fixed some typos and confusing variable names

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Minor revision. PQCrypto 2021
Keywords: small secret LWE representations quantum random walk
Contact author(s): iggy hoof @ rub de
elena kirshanova @ rub de
alex may @ rub de
History: 2021-12-10: revised; 2021-06-24: received; See all versions
Short URL: https://ia.cr/2021/865
License: CC BY

BibTeX

@misc{cryptoeprint:2021/865,
      author = {Iggy van Hoof and Elena Kirshanova and Alexander May},
      title = {Quantum Key Search for Ternary LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2021/865},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/865}},
      url = {https://eprint.iacr.org/2021/865}
}