Paper 2022/1473

Let's Meet Ternary Keys on Babai's Plane: A Hybrid of Lattice-reduction and Meet-LWE

Minki Hhan, Korea Institute for Advanced Study
Jiseung Kim, Jeonbuk National University
Changmin Lee, Korea Institute for Advanced Study
Yongha Son, Samsung SDS
Abstract

A cryptographic primitive based on the Learning With Errors (LWE) problem with variants is a promising candidate for the efficient quantum-resistant public key cryptosystem. As the parameters for such cryptosystems are chosen by the concrete attack cost for the corresponding LWE problem, improving LWE solving algorithm has a significant importance. In this paper, we present a new hybrid attack on the LWE problem. This new attack combines the primal lattice attack and an improved variant of the MitM attack, Meet-LWE, recently suggested by May [Crypto'21]. This resolves the major open problem posed in the same paper. To this end, we develop several technical tools for hybrid attacks; a new property of Babai's nearest plane algorithm with respect to projection, an approximate variant of Meet-LWE, and a locality-sensitive hashing-based near-collision finding algorithm. We also present a comprehensive analysis of the proposed attack, which involves the complicated arguments of both lattice and representation techniques. In particular, we take special care in specifying the relevant heuristics and also provide some experimental evidence for them. We finally estimate the concrete cost of our attack, and observe better cost for sparse LWE/NTRU keys than the other existing attacks. In particular, this result has a direct effect on the currently deployed parameter sets used in some fully homomorphic encryption libraries.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Learing with ErrorsHybrid lattice attackMeet-in-the-middle algorithmCryptanalysis
Contact author(s)
minkihhan @ kias re kr
jiseungkim @ jbnu ac kr
changminlee @ kias re kr
yongha son @ samsung com
History
2024-01-10: last of 2 revisions
2022-10-27: received
See all versions
Short URL
https://ia.cr/2022/1473
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1473,
      author = {Minki Hhan and Jiseung Kim and Changmin Lee and Yongha Son},
      title = {Let's Meet Ternary Keys on Babai's Plane: A Hybrid of Lattice-reduction and Meet-{LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/1473},
      year = {2022},
      url = {https://eprint.iacr.org/2022/1473}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.