Cryptology ePrint Archive: Report 2017/742

Cryptanalysis of Compact-LWE

Jonathan Bootle and Mehdi Tibouchi

Abstract: 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.

Category / Keywords: public-key cryptography / Compact-LWE, lattice-based cryptography, cryptanalysis, IoT

Date: received 1 Aug 2017

Contact author: tibouchi mehdi at lab ntt co jp

Available format(s): PDF | BibTeX Citation

Version: 20170807:161448 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]