Anzeige
Erschienen in:
2018 | OriginalPaper | Buchkapitel
Cryptanalysis of Compact-LWE
verfasst von : Jonathan Bootle, Mehdi Tibouchi, Keita Xagawa
Erschienen in: Topics in Cryptology – CT-RSA 2018
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. The new scheme, which has been submitted to the NIST post-quantum 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 fact, the proposed parameters, allegedly suitable for 138-bit security, involve the Compact-LWE assumption in dimension only 13.
In this paper, 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. We also describe a more advanced attack which, given the public key, recovers a secret key essentially equivalent to the correct one (in the sense that it correctly decrypts ciphertexts with \(100\%\) probability as fast as legitimate decryption) in a little more than a second.
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 any meaningful way.