Cryptology ePrint Archive: Report 2018/020

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

Haoyu Li and Renzhang Liu and 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}

Category / Keywords: Post-quantum encryption, LWE, ciphertext-only attack, lattice.

Date: received 5 Jan 2018, last revised 8 Jul 2018

Contact author: panyanbin at amss ac cn

Available format(s): PDF | BibTeX Citation

Note: A key recovery attack is added.

Version: 20180708:110817 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]