Accelerating Lattice Reduction with FPGAs
Jérémie Detrey and Guillaume Hanrot and Xavier Pujol and Damien Stehlé
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.
Download: pdf.
Homepage