Paper 2018/020

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

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

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. MAJOR revision.
Keywords
Post-quantum encryptionLWEciphertext-only attacklattice.
Contact author(s)
panyanbin @ amss ac cn
History
2018-07-08: revised
2018-01-05: received
See all versions
Short URL
https://ia.cr/2018/020
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/020,
      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{https://eprint.iacr.org/2018/020}},
      url = {https://eprint.iacr.org/2018/020}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.