On the acceleration of lattice based algorithms for post-quantum cryptosystems

Abstract

Sistemas criptográficos clássicos, como o RSA e o ElGamal, mostraram ser vulneráveis na presença de um computador quântico suficientemente poderoso. Dada esta descoberta, a comunidade científica focou a sua atenção no desenvolvimento e estudo de alternativas imunes a arquiteturas quânticas. Sistemas baseados em treliças são um dos criptossistemas que se provou serem resistentes a ataques por parte de computadores quânticos. Estes criptossistemas baseiam a sua segurança em problemas matemáticos duros, como o Problema do Vetor mais Curto (Shortest Vector Problem, SVP), Problema do Vetor mais Próximo (Closest Vector Problem, CVP), e outros. Assim sendo, o estudo de algoritmos desenhados para resolver estes problemas -- também conhecidos como ataques -- é de extrema importância, com o objetivo de os entender melhor, e por forma a melhor selecionar os parâmetros de construção destes criptossistemas. O foco desta dissertação é um tipo específico de ataque: algoritmos baseados em célula de Voronoi, que são frequentemente mencionados na literatura como sendo impráticos, mas que têm sido alvo de muito pouca pesquisa, especialmente quando comparados com outros tipos. Nesta dissertação, várias otimizações para um algoritmo baseado em célula de Voronoi são propostas, com o objetivo de reduzir tanto o tempo de execução, como os requisitos de memória das implementações. De modo a aproveitar todo o poder computacional disponível nos computadores modernos, versões paralelas em CPU, GPU e heterogénea CPU + GPU são propostas, apresentando ganhos lineares no primeiro caso (e algum benefício com Hyper-Threading), e reportando ganhos de 13.37x e 15.03x, para as versões GPU e heterogénea, respetivamente, quando comparadas com a versão sequencial base em CPU. Adicionalmente, diversas variantes heurísticas com implementações paralelas em CPU são propostas, com o intuito de acelerar a computação da solução do SVP, com a melhor estratégia de "poda" desenvolvida a alcançar ganhos até 256.51x, usando 8 threads (quando comparada com a versão sequencial base em CPU), calculando a solução correta para 99.84% das bases testadas. Finalmente, conduzida no âmbito desta dissertação, a integração de todo o trabalho na biblioteca Lattice Unified Set of Algorithms (LUSA) -- um projeto que ambiciona disponibilizar acesso público a uma coleção de implementações rápidas e fáceis de utilizar, de algoritmos relacionados com treliças. Os resultados obtidos nesta dissertação mostram, ainda que longe das dimensões do estado da arte, que é possível acelerar imensamente um algoritmo baseado em célula de Voronoi, mantendo taxas de sucesso extremamente elevadas.

Classical cryptographic systems, such as RSA and ElGamal, have been found to be vulnerable in the presence of a sufficiently powerful quantum computer. In light of this discovery, the scientific community shifted its attention to the design and study of quantum-immune alternatives. Lattice-based systems are one type of cryptosystem that was proved to be resilient against attacks from quantum computers. These cryptosystems base their security on hard mathematical problems, like the Shortest Vector Problem, Closest Vector Problem, and others. As such, the study of algorithms designed to solve these problems -- also known as attacks -- is paramount in order to better understand them, and to better select the parameters for the construction of these cryptosystems. This dissertation focuses on a specific type of attack: Voronoi cell-based, which are often mentioned in the literature as being impractical, but very little research has actually been conducted, especially when compared to other types. In this dissertation, several optimizations of a Voronoi cell-based algorithm are presented, with the goal of reducing both the execution time and the memory requirements of the implementations. In order to harness the full computational power available in modern computers, parallel CPU, parallel GPU and heterogeneous CPU + GPU versions are proposed, reporting linear speedups for the first (and some benefit from Hyper-Threading), and yielding maximum speedups of 13.37x and 15.03x, for the GPU and heterogeneous versions, respectively, compared to the baseline, sequential CPU version. Additionally, several heuristic variants with parallel CPU implementations are proposed to accelerate the computation of the solution of the SVP, with the best pruning strategy devised achieving speedups of up to 256.51x, using 8 threads (compared to the sequential, non-pruned implementation), while computing the correct solution for 99.84% of the tested lattice bases. Finally, conducted in the scope of this dissertation, the integration of all work into the Lattice Unified Set of Algorithms (LUSA) library -- a project that aims to provide public access to simple and fast implementations of lattice-related algorithms. The results obtained in this dissertation show that, while far from state of the art dimensions, it is still possible to greatly accelerate Voronoi cell-based algorithms, maintaining very high success rates.