Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Compact-LWElattice-based cryptographycryptanalysisIoT
Contact author(s)
tibouchi mehdi @ lab ntt co jp
History
2017-08-07: received
Short URL
https://ia.cr/2017/742
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/742,
      author = {Jonathan Bootle and Mehdi Tibouchi},
      title = {Cryptanalysis of Compact-LWE},
      howpublished = {Cryptology ePrint Archive, Paper 2017/742},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/742}},
      url = {https://eprint.iacr.org/2017/742}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.