Name
Title | ||
|---|---|---|
Lp Solutions Of Vectorial Integer Subset Sums - Cryptanalysis Of Galbraith'S Binary Matrix Lwe |
Abstract | ||
|---|---|---|
We consider Galbraith's space efficient LWE variant, where the (m x 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 <= 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). |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-662-54365-8_1 | PUBLIC-KEY CRYPTOGRAPHY (PKC 2017), PT I |
Keywords | Field | DocType |
Binary matrix LWE, Linear programming, Cryptanalysis | Integer,Discrete mathematics,Subset sum problem,Combinatorics,Lattice (order),Logical matrix,Linear programming,Time complexity,Linear programming relaxation,Mathematics,Binary number | Conference |
Volume | ISSN | Citations |
10174 | 0302-9743 | 1 |
PageRank | References | Authors |
0.35 | 11 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gottfried Herold | 1 | 58 | 4.02 |
| Alexander May | 2 | 89 | 5.98 |