Design and implementation of a QC-MDPC code-based post-quantum KEM targeting FPGAs

Quantum computing is expected to break the traditional public-key cryptography solutions in the upcoming decades, making it paramount to design new security solutions that can also resist attacks carried out by quantum computers. Post-quantum cryptography aims to design cryptoschemes that can be deployed on traditional computers and resist both traditional and quantum attacks. The deployed post-quantum cryptography solutions will have to satisfy not only security requirements but also performance ones. Providing effective hardware support for such cryptosystems is indeed one of the requirements set by NIST within its ongoing post-quantum cryptography standardization process, and it is particularly crucial to ensuring a wide adoption of post-quantum security solutions across embedded devices at the edge. This thesis delivers a configurable FPGA-based hardware architecture to support BIKE, a post-quantum QC-MDPC code-based cryptoscheme. In particular, BIKE implements a key encapsulation mechanism, i.e., a cryptoscheme that generates and shares a symmetric key between two parties by employing a public-private key pair. The proposed architecture aims to improve performance over the existing state-of-the-art software and hardware solutions, and it is configurable through a set of architectural and code parameters, which make it efficient, providing good performance while using the resources available on FPGAs effectively, flexible, allowing to support different large QC-MDPC codes defined from the designers of the cryptosystem, and scalable, targeting the whole Xilinx Artix-7 FPGA family. The hardware components implementing QC-MDPC bit-flipping decoding, binary polynomial inversion, and binary polynomial multiplication, i.e., the three most complex operations employed within the BIKE cryptoscheme, are indeed specifically designed in a parametric way to exploit parallelism as desired according to the performance requirements and the area constraints given by the target platform. Two separate modules target the cryptographic functionality of the client and server nodes of the quantum-resistant key exchange, respectively. This thesis delivers a preliminary definition of a methodology to identify the best parameterization of the configurable hardware components implemented within the proposed architecture's BIKE client and server cores. The methodology uses a complexity-based heuristic that leverages the knowledge of the time and space complexity of such parametric components to steer the design space exploration. The proposed architecture's performance was evaluated against state-of-the-art software and hardware implementations. The proposed architecture's client- and server-side instances outperform the state-of-the-art reference software, exploiting the Intel AVX2 extension and running on a desktop-class CPU, by up to 1.91 and 1.83 times, respectively. Moreover, compared to the fastest reference state-of-the-art FPGA-based architecture, which targets the same Xilinx Artix-7 FPGA family, the architecture described in this thesis provides a performance speedup of up to six times. In particular, the proposed architecture executes the whole BIKE key encapsulation mechanism in a time ranging from 5.74ms to 0.61ms for AES-128-equivalent security and from 19.35ms to 1.77ms for AES-192-equivalent security, with the lowest performance obtained on the smallest FPGAs and the highest performance when targeting the largest Artix-7 200 chips.

Si prevede che i computer quantistici romperanno le tradizionali soluzioni di crittografia a chiave pubblica nei prossimi decenni, rendendo fondamentale la progettazione di nuove soluzioni di sicurezza in grado di resistere anche agli attacchi effettuati dai computer quantistici. La crittografia post-quantistica ha l'obiettivo di progettare schemi crittografici che possano essere implementati sui computer tradizionali e che siano in grado di resistere sia agli attacchi tradizionali che a quelli quantistici. Le soluzioni di crittografia post-quantistica implementate dovranno soddisfare non solo i requisiti di sicurezza ma anche quelli prestazionali. Fornire un supporto hardware efficace per tali sistemi crittografici è infatti uno dei requisiti fissati dal NIST nell'ambito del processo di standardizzazione della crittografia post-quantistica attualmente in corso, ed è particolarmente cruciale per garantire un'ampia adozione di soluzioni di sicurezza post-quantistica su dispositivi embedded all'edge. Questa tesi fornisce un'architettura hardware configurabile basata su FPGA per supportare BIKE, un sistema crittografico post-quantistico basato su codici QC-MDPC. In particolare, BIKE implementa un meccanismo di incapsulamento della chiave, ovvero uno schema crittografico che genera e condivide una chiave simmetrica tra due parti impiegando una coppia di chiavi pubblica e privata. L'architettura proposta punta a migliorare le prestazioni rispetto alle soluzioni software e hardware esistenti ed è configurabile attraverso una serie di parametri architetturali e del codice, che la rendono efficiente, fornendo buone prestazioni e allo stesso tempo utilizzando efficacemente le risorse disponibili sugli FPGA, flessibile, consentendo di supportare diversi codici QC-MDPC di grandi dimensioni definiti dai progettisti del crittosistema, e scalabile, essendo rivolta all'intera famiglia di FPGA Xilinx Artix-7. I componenti hardware che implementano la decodifica bit-flipping di codici QC-MDPC, l'inversione di polinomi binari e la moltiplicazione di polinomi binari, ossia le tre operazioni più complesse impiegate all'interno dello schema crittografico BIKE, sono infatti appositamente progettati in modo parametrico per sfruttare il parallelismo desiderato in base ai requisiti prestazionali e i vincoli di area dati dalla piattaforma di destinazione. Due componenti distinti realizzano rispettivamente la funzionalità crittografica dei nodi client e server dello scambio di chiave resistente ad attacchi quantistici. Questa tesi fornisce una definizione preliminare di una metodologia per identificare la migliore parametrizzazione dei componenti hardware configurabili implementati all'interno dei core client e server BIKE dell'architettura proposta. La metodologia utilizza un'euristica basata sulla complessità che sfrutta la conoscenza della complessità temporale e spaziale di tali componenti parametrici per guidare l'esplorazione dello spazio di progettazione. Le prestazioni dell'architettura proposta sono state valutate rispetto alle implementazioni hardware e software dallo stato dell'arte. Le istanze lato client e lato server dell'architettura proposta superano le prestazioni del software di riferimento, eseguito su una CPU di classe desktop sfruttando l'estensione Intel AVX2, rispettivamente fino a 1.91 e 1.83 volte. Inoltre, rispetto all'architettura per FPGA di riferimento più performante, che ha come target la stessa famiglia di FPGA Xilinx Artix-7, l'architettura descritta in questa tesi fornisce un miglioramento delle prestazioni fino a sei volte. In particolare, l'architettura proposta esegue l'intero crittosistema BIKE in un tempo che va da 5.74ms a 0.61ms per una sicurezza equivalente ad AES-128 e da 19.35ms a 1.77ms per una sicurezza equivalente ad AES-192, con le prestazioni inferiori ottenute sugli FPGA con meno risorse e le prestazioni più elevate quando ha come target i chip di fascia più alta Artix-7 200.