Paper 2022/1330
Hybrid Dual and Meet-LWE Attack
, Institute of Information Engineering, CASAbstract
The Learning with Errors (LWE) problem is one of the most prominent problems in lattice-based cryptography. Many practical LWE-based schemes, including Fully Homomorphic encryption (FHE), use sparse ternary secret for the sake of efficiency. Several (hybrid) attacks have been proposed that benefit from such sparseness, thus researchers believe the security of the schemes with sparse ternary secrets is not well-understood yet. Recently, May [Crypto 2021] proposed an efficient meet-in-the-middle attack named Meet-LWE for LWE with ternary se- cret, which significantly improves Odlyzko’s algorithm. In this work, we generalize May’s Meet-LWE and then introduce a new hybrid attack which combines Meet-LWE with lattice dual attack. We implement our algorithm to FHE-type parameters of LWE problem and compare it with the previous hybrid dual attacks. The result shows that our attack outperforms other attacks in a large range of parameters. We note that our attack has no impact on the LWE-based schemes in the PQC Standardization held by NIST as their secrets are not sparse and/or ternary.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Published elsewhere. ACISP
- DOI
- 10.1007/978-3-031-22301-3_9
- Keywords
- LWEMeet-in-the-MiddleDual AttackHybrid Attack
- Contact author(s)
-
bilei121 @ outlook com
luxianhui @ iie ac cn
jjluo1 @ bjtu edu cn
wangkunpeng @ iie ac cn - History
- 2022-12-23: last of 2 revisions
- 2022-10-06: received
- See all versions
- Short URL
- https://ia.cr/2022/1330
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2022/1330,
author = {Lei Bi and Xianhui Lu and Junjie Luo and Kunpeng Wang},
title = {Hybrid Dual and Meet-LWE Attack},
howpublished = {Cryptology ePrint Archive, Paper 2022/1330},
year = {2022},
doi = {10.1007/978-3-031-22301-3_9},
note = {\url{https://eprint.iacr.org/2022/1330}},
url = {https://eprint.iacr.org/2022/1330}
}
