On the suitability of parallel computer architectures for attacks on lattice-based cryptography

• Applicant: Dr.-Ing. Artur Mariano
• Subject Area: Computer Architecture, Embedded and Massively Parallel Systems ; Data Management, Data-Intensive Systems, Computer Science Methods in Business Informatics
• Term: from 2017 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 382285730

• Final Report Year: 2020

Final Report Abstract

This project was based on lattice-based cryptography, as current forms of cryptography were shown to be vulnerable if general purpose quantum computers are developed. A critical task in this field is to study - through cryptanalysis - the potential of algorithms to attack lattice-based cryptography. In essence, this project intended to address and study the safeness of lattice-based cryptosystems, and propose ways to upgrade current attacks at the same time it intended to make them practical and available. The project had two particular goals: on one hand, it aimed at enhancing the knowledge one had of the parallelization and optimization of certain attacks for lattice-based cryptography on modern computer architectures. On the other hand, but related to the first goal, it aimed to produce practical tools for lattice-based cryptography, in the form of a parallel, highly optimized library or modules. This project was very relevant in the lattice-based cryptanalysis as it contributed with the following scientific advances: 1. It resulted in a library that is particularly useful to the community as it is extremely simple to use as well as very efficient (providing implementations that are much more efficient - and parallel - than average implementions). 2. It showed that Voroinoi-cell algorithms are to be considered, as they can be considerably improved and are highly suited to parallel computer architectures. In this project, we also concluded that in parallel version of Sieving algorithms, adapting them to work on ideal lattices does not result in a significant speedup as it introduces data races in the computation of ideal lattice vectors.

Publications

• “Heterogeneous Implementation of a Voronoi Cell-Based SVP Solver”. IEEE Access 7, 127012-127023
  G Falcao, F Cabeleira, A Mariano, LP Santos
  
• “Memory-Optimized Voronoi Cell-based Parallel Kernels for the Shortest Vector Problem on Lattices”. 27th European Signal Processing Conference (EUSIPCO), 1-5
  F Cabeleira, A Mariano, G Falcao