Accelerating lattice reduction with FPGAs

Jérémie Detrey 1, * Guillaume Hanrot 2 Xavier Pujol 2 Damien Stehlé 2, 3, 4
* Auteur correspondant
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.
Type de document :
Communication dans un congrès
Michel Abdalla and Paulo S. L. M. Barreto. First International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10), Aug 2010, Puebla, Mexico. 6212, pp.124-143, 2010, Lecture Notes in Computer Science. <10.1007/978-3-642-14712-8_8>
Liste complète des métadonnées


https://hal.inria.fr/inria-00539929
Contributeur : Jérémie Detrey <>
Soumis le : jeudi 25 novembre 2010 - 15:34:26
Dernière modification le : jeudi 22 septembre 2016 - 14:31:11
Document(s) archivé(s) le : samedi 26 février 2011 - 03:01:04

Fichier

enum.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jérémie Detrey, Guillaume Hanrot, Xavier Pujol, Damien Stehlé. Accelerating lattice reduction with FPGAs. Michel Abdalla and Paulo S. L. M. Barreto. First International Conference on Cryptology and Information Security in Latin America (LATINCRYPT'10), Aug 2010, Puebla, Mexico. 6212, pp.124-143, 2010, Lecture Notes in Computer Science. <10.1007/978-3-642-14712-8_8>. <inria-00539929>

Partager

Métriques

Consultations de
la notice

237

Téléchargements du document

298