Paper 2017/742

Cryptanalysis of Compact-LWE

Jonathan Bootle and Mehdi Tibouchi


As an invited speaker of the ACISP 2017 conference, Dongxi Liu recently introduced a new lattice-based encryption scheme (joint work with Li, Kim and Nepal) designed for lightweight IoT applications, and announced plans to submit it to the NIST postquantum competition. The new scheme is based on a variant of standard LWE called Compact-LWE, but is claimed to achieve high security levels in considerably smaller dimensions than usual lattice-based schemes. In fact, the proposed parameters, allegedly suitable for 138-bit security, involve the Compact-LWE assumption in dimension only 13. In this note, we show that this particularly aggressive choice of parameters fails to achieve the stated security level. More precisely, we show that ciphertexts in the new encryption scheme can be decrypted using the public key alone with >99.9% probability in a fraction of a second on a standard PC, which is not quite as fast as legitimate decryption, but not too far off.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Compact-LWElattice-based cryptographycryptanalysisIoT
Contact author(s)
tibouchi mehdi @ lab ntt co jp
2017-08-07: received
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Mehdi Tibouchi},
      title = {Cryptanalysis of Compact-LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/742},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.