Cryptanalysis of Compact-LWE Submitted to NIST PQC Project
Very recently, Liu, Li, Kim and Nepal submitted a new public-key encryption scheme Compact-LWE to NIST as a candidate of the standard of post-quantum cryptography.Compact-LWE features its structure similar to LWE 11, but requiring small number of samples and somewhat big errors, its encryption process is related to Knapsack problem 12.In terms of 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.In this paper, we show the claim is not true by proposing a ciphertext-only attack against Compact-LWE.More precisely, we can decrypt any ciphertext without knowing the private keys with the help of CVP algorithm.Since the dimension of the underlying lattice of Compact-LWE is quite small (128) for the authors parameter choice, approximate CVP can be efficiently solved using lattice basis reduction algorithm, consequently Compact-LWE was broken in our experiments, we conclude that Compact-LWE with recommended parameters is not secure.
encryption LWE ciphertext-only attack lattice CVP
Haoyu Li Renzhang Liu Yanbin Pan Tianyuan Xie
Key Laboratory of Mathematics Mechanization, NCMIS,Academy of Mathematics and Systems Science, Chine State Key Laboratory of Information Security, Institute of Information Engineering,Chinese Academy o Key Laboratory of Mathematics Mechanization, NCMIS,Academy of Mathematics and Systems Science, Chine
国际会议
广州
英文
75-86
2018-05-01（万方平台首次上网日期，不代表论文的发表时间）