IACR News item: 31 December 2014
Martin Albrecht, Carlos Cid, Jean-Charles Faugère, Robert Fitzpatrick, Ludovic Perret
ePrint ReportWe also consider a variant of LWE known as BinaryError-LWE introduced by Micciancio and Peikert recently. By combining Gröbner basis algorithms with the Arora-Ge modelling, we show under a natural algebraic assumption that BinaryError-LWE can be solved in subexponential time as soon as the number of samples is quasi-linear, e.g.\\
$m=O(n \\log \\log n)$. We also derive precise complexity bounds for BinaryError-\\LWE with $m=O(n)$, showing that this new approach yields better results than best currently-known generic (exact) CVP solver as soon as $m/n \\geq 6.6$. More generally, our results provide a good picture of the hardness degradation of BinaryError-LWE for a number of samples ranging from $m=n\\left(1+\\Omega\\big(1/{\\rm log}(n)\\big)$ (a case for which BinaryError-\\LWE{} is as hard as solving some lattice problem in the worst case) to $m=O(n^2)$ (a case for which it can be solved in polynomial-time). This addresses an open question from Micciancio and Peikert. Whilst our results do not contradict the hardness results obtained by Micciancio and Peikert, they should rule out BinaryError-\\LWE for many cryptographic applications. The results in this work depend crucially on the assumption the algebraic systems considered systems are not easier and not harder to solve than a random system of equations. We have verified experimentally such hypothesis. We also have been able to prove formally the assumptions is several restricted situations. We emphasize that these issues are highly non-trivial since proving our assumptions in full generality would allow to prove a famous conjecture in commutative algebra known as Fröberg\'s Conjecture.
Additional news items may be found on the IACR news page.