Wagner's Algorithm Provably Runs in Subexponential Time for SIS${}^{\infty }$

Léo Ducas, Lynn Engelberts, Johanna Loyer

At CRYPTO 2015, Kirchner and Fouque claimed that a carefully tuned variant of the Blum-Kalai-Wasserman (BKW) algorithm (JACM 2003) should solve the Learning with Errors problem (LW…