Paper 2018/020
Cryptanalysis of Compact-LWE Submitted to NIST PQC Project
Haoyu Li and Renzhang Liu and Yanbin Pan and Tianyuan Xie
Abstract
Very recently, Liu, Li, Kim and Nepal submitted Compact-LWE, a new public key encryption scheme, to NIST as a candidate of the standard of post-quantum cryptography. About the security of Compact-LWE, the authors claimed that "even if the hard problems in lattice, such as CVP and SIS, can be efficiently solved, the secret values or private key in Compact-LWE still cannot be efficiently recovered. This allows Compact-LWE to choose very small dimension parameters, such as n = 8 in our experiment". However, in this paper, we show it is not true by proposing a ciphertext-only attack against Compact-LWE. More precisely, if we can solve CVP, we can decrypt any ciphertext without knowing the private keys. Since the dimension of the underlying lattice is very small (128) for the authors' parameter choice, (approximation-)CVP can be efficiently solved with lattice basis reduction algorithm. Hence, we can always break Compact-LWE with the authors' parameter choice in our experiments, which means that Compact-LWE with the recommended parameters is not secure.
Metadata
- Available format(s)
- Publication info
- Preprint.
- Keywords
- Ciphertext-only attacklatticeLWE
- Contact author(s)
- panyanbin @ amss ac cn
- History
- 2018-07-08: revised
- 2018-01-05: received
- See all versions
- Short URL
- https://ia.cr/2018/020
- License
-
CC BY