Accelerating Lattice Reduction with FPGAs
Accelerating Lattice Reduction with FPGAs
复制标题
使用 FPGA 加速晶格缩减
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Stehlé
中科院分区：
文献类型：
--
作者：
J. Detrey;G. Hanrot;X. Pujol;D. Stehlé
描述了一种用于求解最短格子向量问题(SVP)的Kannan-Fincke-Pohst枚举算法(KFP)的FPGA加速器。这是第一个专门针对加密相关维度的KFP的FPGA实现。为了优化KFP的实现，我们从理论和实验上研究了KFP的几个方面，包括KFP的高效并行化和底层算法。我们的FPGA加速器既可以用于解决SVP的独立实例(在CPU-FPGA混合体中)，也可以用于解决BKZ类型算法中产生的无数较小维度的SVP实例。对于成本相当的设备，我们的FPGA实现速度比多核CPU实现快约2.12倍。
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.