logo IMB
Retour

Séminaire de Théorie des Nombres

The General Sieve Kernel and New Records in Lattice Reduction

Léo Ducas

( CWI Amsterdam )

Salle de Conférences

le 05 octobre 2018 à 14:00

Sieving algorithms are asymptotically the fastest heuristic algorithms for solving the shortest vector problem, and therefore for solving other problems such as LWE or SIS, due to the Block-Korkine-Zolotarev lattice reduction algorithm (BKZ). Until recently, sieving was considered as a function to be used as a blackbox SVP oracle inside BKZ. The works of Ducas (Eurocrypt 2018), and of Laarhoven and Mariano (PQCrypto 2018), however, proposed improvements to lattice reduction that go beyond this blackbox use of Sieve-style algorithms. To formalise and generalise these new strategies, we propose the General Sieve Kernel (G6K, pronounced /ȝe.si.ka/), an abstract machine supporting a wide variety of lattice reduction strategies based on sieving algorithms. It is designed to minimise the sieving computation effort per reduction quality, and achieves this via mechanisms such as recycling and on-the-fly lifting. We provide a highly optimised, multi-threaded, tweakable, and open-source implementation of this stateful machine. Finally, we apply G6K to various lattice challenges (SVP, LWE). Our work demonstrates that sieving significantly outperforms enumeration in dimensions achievable in practice. Joint work with Martin R. Albrecht, Gottfried Herold, Elena Kirshanova, Eamonn Postlethwaite and Marc Stevens.