Skip to Main content Skip to Navigation
New interface
Conference papers

Accelerating lattice reduction with FPGAs

Jérémie Detrey 1, * Guillaume Hanrot 2 Xavier Pujol 2 Damien Stehlé 2, 3, 4 
* Corresponding author
1 CARAMEL - Cryptology, Arithmetic: Hardware and Software
Inria Nancy - Grand Est, LORIA - ALGO - Department of Algorithms, Computation, Image and Geometry
2 ARENAIRE - Computer arithmetic
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We describe an FPGA accelerator for the Kannan­–Fincke­–Pohst enumeration algorithm (KFP) solving the Shortest Lattice Vector Problem (SVP). This is the first FPGA implementation of KFP specifically targeting cryptographically relevant dimensions. In order to optimize this implementation, we theoretically and experimentally study several facets of KFP, including its efficient parallelization and its underlying arithmetic. Our FPGA accelerator can be used for both solving stand-alone instances of SVP (within a hybrid CPU­–FPGA compound) or myriads of smaller dimensional SVP instances arising in a BKZ-type algorithm. For devices of comparable costs, our FPGA implementation is faster than a multi-core CPU implementation by a factor around 2.12.
Document type :
Conference papers
Complete list of metadata

Cited literature [50 references]  Display  Hide  Download
Contributor : Jérémie Detrey Connect in order to contact the contributor
Submitted on : Thursday, November 25, 2010 - 3:34:26 PM
Last modification on : Friday, November 18, 2022 - 10:14:12 AM
Long-term archiving on: : Saturday, February 26, 2011 - 3:01:04 AM


Files produced by the author(s)



Jérémie Detrey, Guillaume Hanrot, Xavier Pujol, Damien Stehlé. Accelerating lattice reduction with FPGAs. First International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10), Aug 2010, Puebla, Mexico. pp.124-143, ⟨10.1007/978-3-642-14712-8_8⟩. ⟨inria-00539929⟩



Record views


Files downloads