Accelerating decoding failure rate validation for post quantum encryption algorithms on GPU

The advancement of quantum computing research threatens the security of current cryptographic systems. For this reason, the National Institute of Standards and Technology (NIST) has organized a competition to select new standards among cryptographic algorithms that are resistant to quantum computers. Among these algorithms is BIKE, a cryptographic key encapsulation algorithm based on code-based cryptography. This work proposes an implementation of the BIKE decoder on a GPU. The goal of the implementation is to create a tool capable of more accurately evaluating security margins, such as the Decoding Failure Rate, provided by the creators of the cryptosystem. The proposed implementation uses an approach that leverages all the potential of the GPU used, an NVIDIA A100-SXM4-40GB, by completing a large number of simultaneous decodings, in order to achieve the maximum performance possible in terms of the number of decodings done in a given time. Through various optimizations for the three security categories of BIKE, the proposed implementation is able to achieve a number of thousands of decodings per second equal to 779, 264, and 133 for categories 1, 3, and 5 respectively. Comparing these results with the CPU counterpart, improvements of 163.6x, 155.5x, and 200.2x respectively for categories 1, 3, and 5 in the single-processor CPU version, and 8.33x, 7.90x, and 10.10x respectively for categories 1, 3, and 5 in the 20-processor CPU version were obtained.

L'avanzamento della ricerca sui computer quantistici minaccia la sicurezza dei sistemi crittografici attuali. Per questo motivo, il National Institute of Standards and Technology (NIST) ha organizzato un concorso per selezionare dei nuovi standard tra gli algoritmi crittografici resistenti ai computer quantistici. Tra questi algoritmi è presente BIKE, un algoritmo di encapsulazione di chiavi crittografiche basato sulla crittografia dei codici. Questo lavoro propone un'implementazione del decodificatore di BIKE su GPU. L'obiettivo dell'implementazione è quello di creare uno strumento in grado di valutare con più precisione affermazioni sui margini di sicurezza, quali la Decoding Failure Rate, forniti dai creatori del criptosistema. L'implementazione proposta utilizza un approccio che sfrutta tutte le potenzialità della GPU utilizzata, una NVIDIA A100-SXM4-40GB, tramite il completamento di un numero ingente di decodifiche simultanee, in modo da ottenere il massimo rendimento possibile del numero di decodifiche fatte in un tempo dato. Tramite varie ottimizzazioni per le tre categorie di sicurezza di BIKE, l'implementazione proposta è in grado di ottenere un numero di migliaia di decodifiche al secondo pari a 779, 264, e 133 per le categorie 1, 3 e 5 rispettivamente. Confrontando questi risultati con la controparte implementata in CPU si ottengono dei miglioramenti del 163.6x, 155.5x, e 200.2x rispettivamente per le categorie 1, 3 e 5 nella versione CPU a singlolo processore, e del 8.33x, 7.90x, e 10.10x rispettivamente per le categorie 1, 3 e 5 nella versione CPU a 20 processori.