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.