Paper 2018/020

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

Haoyu Li, Renzhang Liu, Yanbin Pan, and Tianyuan Xie


In 2017, 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, but with different distribution of errors. Liu, Li, Kim and Nepal thought that the special error distribution they employed would protect Compact-LWE from the 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 bits of security. However, in this paper, we show that Compact-LWE is not secure with recommended parameters by presenting two efficient ciphertext-only attacks against it. \begin{itemize} \item The first one is to recover the equivalent private keys just from the public keys. By exploiting the special structure of Compact-LWE, employing some known skills such as orthogonal-lattice technique, and also developing some new techniques, we finally recovered the equivalent private keys for more than 80\% of the random generated instances in our experiments. \item The second one is to recover the corresponding message given the public keys and a ciphertext. Note that any short enough solutions of corresponding inhomogeneous linear systems can be used to decrypt a ciphertext equivalently. We recovered all the messages without knowing the private keys in our experiments. \end{itemize}

Note: A key recovery attack is added.

Available format(s)
Publication info
Preprint. MAJOR revision.
Post-quantum encryptionLWEciphertext-only attacklattice.
Contact author(s)
panyanbin @ amss ac cn
2018-07-08: revised
2018-01-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Haoyu Li and Renzhang Liu and Yanbin Pan and Tianyuan Xie},
      title = {Ciphertext-Only Attacks against Compact-LWE Submitted to NIST PQC Project},
      howpublished = {Cryptology ePrint Archive, Paper 2018/020},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.