Towards an efficient lattice basis reduction implementation

Abstract

The security of most digital systems is under serious threats due to major technology breakthroughs we are experienced in nowadays. Lattice-based cryptosystems are one of the most promising post-quantum types of cryptography, since it is believed to be secure against quantum computer attacks. Their security is based on the hardness of the Shortest Vector Problem and Closest Vector Problem. Lattice basis reduction algorithms are used in several fields, such as lattice-based cryptography and signal processing. They aim to make the problem easier to solve by obtaining shorter and more orthogonal basis. Some case studies work with numbers with hundreds of digits to ensure harder problems, which require Multiple Precision (MP) arithmetic. This dissertation presents a novel integer representation for MP arithmetic and the algorithms for the associated operations, MpIM. It also compares these implementations with other libraries, such as GNU Multiple Precision Arithmetic Library, where our experimental results display a similar performance and for some operations better performances. This dissertation also describes a novel lattice basis reduction module, LattBRed, which included a novel efficient implementation of the Qiao’s Jacobi method, a Lenstra-LenstraLovasz (LLL) algorithm and associated parallel implementations, a parallel variant of the ´ Block Korkine-Zolotarev (BKZ) algorithm and its implementation and MP versions of the the Qiao’s Jacobi method, the LLL and BKZ algorithms. Experimental performances measurements with the set of implemented modifications of the Qiao’s Jacobi method show some performance improvements and some degradations but speedups greater than 100 in Ajtai-type bases.

Atualmente existe um grande avanço tecnológico que poderá colocar em causa a segurança da maioria dos sistemas informáticos. Sistemas criptográficos baseados em reticulados são um dos mais promissores tipos de criptografia pós-quântica, uma vez que se acredita que estes sistemas são seguros contra possíveis ataques de computadores quânticos. A segurança destes sistemas está baseada na dificuldade de resolver o problema do vetor mais curto e o problema do vetor mais próximo. Algoritmos de redução de bases de reticulados são usados em muitos campos científicos, tais como criptografia baseada em reticulados. O seu principal objetivo e tornar o problema mais fácil de resolver, tornando a base do reticulado mais curta e ortogonal. Alguns casos de estudo requerem o uso de números com centenas de dígitos para garantir problemas mais difíceis. Portanto, é importante o uso de módulos de precisão múltipla. Esta dissertação apresenta uma nova representação de inteiros para aritmética de precisão múltipla e todas as respetivas funções de um módulo, ‘MpIM’. Também comparamos as nossas implementações com outras bibliotecas de precisão múltipla, tais como ‘GNU Multiple Precision Arithmetic Library’, em que obtivemos desempenhos semelhantes e em alguns casos melhores. A dissertação também apresenta um novo módulo para a redução de bases de reticulados, ‘MpIM’, que inclui uma nova e eficiente implementação do ‘Qiao’s Jacobi method’, o algoritmo ‘Lenstra-Lenstra-Lovasz’ (LLL) e respetiva implementação paralela, uma variante paralela do algoritmo ‘Block Korkine-Zolotarev’ (BKZ) e a sua versão sequencial e versões de precisão múltipla do ‘Qiao’s Jacobi method’, LLL e BKZ. Trabalhos experimentais mostraram que a versão do ‘Qiao’s Jacobi method’ que implementa todas as modificações sugeridas mostra ganhos e degradações de desempenho, contudo com aumentos de desempenho superiores a 100 vezes em bases ‘Ajtai-type’.