Cryptanalysis of Compact-LWE

Jonathan Bootle


As an invited speaker of the ACISP conference held in July 2017, Dongxi Liu introduced a new lattice-based encryption scheme (joint work with Li, Kim and Nepal) designed for lightweight IoT applications. The scheme, which has been submitted to the NIST postquantum competition, 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 our paper, we show, for the proposed parameters, that ciphertexts in the new encryption scheme can be decrypted using the public key alone, and given the public key, how to recover a functional secret key which can be used to correctly decrypt ciphertexts with 100%. Furthermore, even setting aside parameter choices, our results show that the ways in which Compact-LWE departs from usual LWE-based encryption schemes do not appear to enhance security in a meaningful way.


I am a PhD candidate in the area of cryptography, working under the supervision of Dr Jens Groth and Dr Sarah Meiklejohn. I am currently working on efficient zero-knowledge proofs. More specifically, I am looking at zero-knowledge membership proofs. I am also interested in lattices and post-quantum cryptography.

Time and Place

Thursday, April 19, 4:15pm
Gates 415