Welcome to the resource topic for 2018/741
Title:
LP Solutions of Vectorial Integer Subset Sums - Cryptanalysis of Galbraith’s Binary Matrix LWE
Authors: Alexander May, 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).
ePrint: https://eprint.iacr.org/2018/741
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .