LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith's Binary Matrix LWE

Alexander May; Gottfried Herold

Paper 2018/741

LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith's Binary Matrix LWE

Alexander May and Gottfried Herold

Abstract

We consider Galbraith's space efficient LWE variant, where the $(m \times n)$ -matrix $A$ is binary. In this binary case, solving a vectorial subset sum problem over the integers allows for decryption. We show how to solve this problem using (Integer) Linear Programming. Our attack requires only a fraction of a second for all instances in a regime for $m$ that cannot be attacked by current lattice algorithms. E.g.\ we are able to solve 100 instances of Galbraith's small LWE challenge $(n, m) = (256, 400)$ all in a fraction of a second. We also show under a mild assumption that instances with $m \leq 2 n$ can be broken in polynomial time via LP relaxation. Moreover, we develop a method that identifies weak instances for Galbraith's large LWE challenge $(n, m) = (256, 640)$ .

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in PKC 2017
DOI: 10.1007/978-3-662-54365-8_1
Keywords: Binary matrix LWE Linear Programming Cryptanalysis
Contact author(s): gottfried herold @ rub de
History: 2018-08-15: received
Short URL: https://ia.cr/2018/741
License: CC BY

BibTeX

@misc{cryptoeprint:2018/741,
      author = {Alexander May and Gottfried Herold},
      title = {{LP} Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith's Binary Matrix {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2018/741},
      year = {2018},
      doi = {10.1007/978-3-662-54365-8_1},
      url = {https://eprint.iacr.org/2018/741}
}