Ciphertext-Only Attacks Against Compact-LWE Submitted to NIST PQC Project

doi:10.1007/s11424-021-0042-3

Journal of Systems Science and Complexity ›› 2022, Vol. 35 ›› Issue (3): 1173-1190.DOI: 10.1007/s11424-021-0042-3

Ciphertext-Only Attacks Against Compact-LWE Submitted to NIST PQC Project

LI Haoyu^1,2,3, LIU Renzhang⁴, LIU Zhen^1,3, PAN Yanbin¹, XIE Tianyuan^1,3

1. Key Laboratory of Mathematics Mechanization, NCMIS, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China; 2. State Key Laboratory of Cryptology, Beijing 100878, China; 3. School of Mathematical Sciences, University of Chinese Academy of Sciences, Beijing 100049, China; 4. Westone Cryptologic Research Center, Westone Information Industry INC., Beijing 100070, China

Received:2020-03-11 Revised:2020-08-18 Published:2022-06-20

PDF ( 0 ) Cited

LI Haoyu, LIU Renzhang, LIU Zhen, PAN Yanbin, XIE Tianyuan. Ciphertext-Only Attacks Against Compact-LWE Submitted to NIST PQC Project[J]. Journal of Systems Science and Complexity, 2022, 35(3): 1173-1190.

As a candidate of the standard of post-quantum cryptography for NIST, Liu, et al. submitted a new public-key encryption scheme Compact-LWE, whose structure is similar to LWE, but with different distribution of errors. They thought that the special error distribution would protect Compact-LWE from known lattice-based attacks. Furthermore, they recommended a set of small parameters to improve the efficiency of Compact-LWE and claimed it can offer 192-bit security. However, in this paper, the authors show that Compact-LWE is not secure under recommended parameters by presenting two ciphertext-only attacks. First, the authors show that the message can be recovered efficiently from the ciphertext. Then the authors go further to recover an equivalent private key efficiently from the public key by exploiting the special structure of Compact-LWE.

Key words: Ciphertext-only attack, Compact-LWE, NIST, post-quantum cryptography

[1] Shor P W, Algorithms for quantum computation:Discrete logarithms and factoring, Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, USA, IEEE, 1994, 124-134.
[2] Shor P W, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM J. Comput., 1997, 26(5):1484-1509.
[3] Grover L K, A fast quantum mechanical algorithm for database search, Proceedings of the 28th Annual ACM Symposium on Theory of Computing, Pennsylvania, USA, ACM, 1996, 212-219.
[4] Regev O, On lattices, learning with errors, random linear codes, and cryptography, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, USA, ACM, 2005, 84-93.
[5] Liu D X, Li N, Kim J, et al., Compact-LWE:A public key encryption scheme, Round 1 submission for NIST Post-Quantum Cryptography Standardization, available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/submissions/Compact LWE.zip, 2017.
[6] Liu D X, Li N, Kim J, et al., Compact-LWE:Enabling practically lightweight public key encryption for leveled IoT device authentication, Cryptology ePrint Archive, 2017, Report 2017/685.
[7] Bootle J, Tibouchi M, and Xagawa K, Cryptanalysis of compact-LWE, Proceedings of Topics in Cryptology-CT-RSA 2018(Ed. by Smart N P), San Francisco, USA, LNCS, Springer Cham, 2018, 10808:80-97.
[8] Xiao D Y and Yu Y, Cryptanalysis of compact-LWE and related lightweight public key encryption, Security and Communication Networks, 2018, 2018(Article ID 4957045):1-9.
[9] Keita X, Tibouchi M, et al., Official comments for Compact-LWE, available at https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Compact-LWE-official-comment.pdf, 2018.
[10] Ajtai M, The shortest vector problem in L2 is NP-hard for randomized reductions (extended abstract), Proceedings of the 30th Annual ACM Symposium on Theory of Computing, Dallas, Texas, USA, ACM, 1998, 10-19.
[11] Lenstra A K, Lenstra H W, and Lovász L, Factoring polynomials with rational coefficients, Mathematische Annalen, 1982, 261(4):515-534.
[12] Van Emde Boas P, Another NP-complete problem and the complexity of computing short vectors in lattices, Math. Dept. Report, 81-04, Univ. of Amsterdam, 1981.
[13] Dinur I, Kindler G, and Safra S, Approximating-CVP to within almost-polynomial factors is NPhard, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, California, USA, 1998, 99-109.
[14] Babai L, On Lovász'lattice reduction and the nearest lattice point problem, Proceedings of the 2nd Annual Symposium on Theoretical Aspects of Computer Science (Ed. by Mehlhorn K), Saarbrücken, Germany, Springer Berlin Heidelberg, 1985, 13-20.
[15] Nguyen P Q and Stern J, Merkle-Hellman revisited:A cryptanalysis of the Qu-Vanstone cryptosystem based on group factorizations, Proceedings of Annual International Cryptology Conference, Santa Barbara, USA, LNCS, Springer Berlin Heidelberg, 1997, 1294:198-212.
[16] Gentry C, Peikert C, and Vaikuntanathan V, Trapdoors for hard lattices and new cryptographic constructions, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, Canada, ACM, 2008, 197-206.
[17] Shoup V, NTL:A library for doing number theory, version 5.5.2, http://www.shoup.net/ntl, 2009.
[18] Sage Development Team, Sage Mathematics Software, version 7.5.1, http://www.sagemath.org, 2017.
[19] Gama N and Nguyen P Q, Predicting lattice reduction, Proceedings of the Annual International Conference on the Theory and Applications of Cryptographic Techniques, Istanbul, Turkey, LNCS, Springer, 2008, 4965:31-51.

[1]	Wolfgang L\"OHR. PREDICTIVE MODELS AND GENERATIVE COMPLEXITY [J]. Journal of Systems Science and Complexity, 2012, 25(1): 30-45.

Viewed

Full text

Abstract