**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 2n$ 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)$.

**Category / Keywords: **public-key cryptography / Binary matrix LWE, Linear Programming, Cryptanalysis

**Original Publication**** (in the same form): **IACR-PKC-2017
**DOI: **10.1007/978-3-662-54365-8_1

**Date: **received 13 Aug 2018

**Contact author: **gottfried herold at rub de

**Available format(s): **PDF | BibTeX Citation

**Version: **20180815:132424 (All versions of this report)

**Short URL: **ia.cr/2018/741

[ Cryptology ePrint archive ]