Flexible hardware design of the LEDApkc encryption for FPGA

Technology is becoming everyday more pervasive in our lives, and cybersecurity represents an ever increasing concern for the final users. Cryptography currently represents the de-facto solution to enforce security, but is threatened by advancements in quantum computing research. Quantum computers provide an exponential speedup in solving the integer factoring and discrete logarithm problems, which are at the basis of almost all of the currently deployed public-key cryptography schemes. The main technology companies, such as IBM and Google, are working on implementing quantum computer, therefore it is mandatory to start designing quantum-resistant cryptoschemes so that the Internet infrastructure will be secure from quantum attacks when these will be possible to carry out in the next few decades. Post-quantum cryptography focuses on the design of novel cryptographic algorithms for traditional computing platforms that are secure against quantum computers. Some classes of cryptographic algorithms for public key cryptography which are believed to be quantum-resistant are code-based, lattice-based, hash-based and multivariate polynomial cryptography. LEDApkc is a code-based post-quantum public-key cryptosystem (PKC), which exploits the advantages of relying on quasi-cyclic low-density parity-check (QC-LDPC) codes, therefore providing high decoding speeds and compact key pairs, and is implemented in order to achieve indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2). This thesis proposes a hardware accelerator for LEDApkc encryption on a FPGA (Field Programmable Gate Array) family, developing a flexible and scalable solution which allows having high throughput when deployed on high-end FPGAs while at the same time requiring few resources on lower-end FPGAs. The proposed architecture targets Artix7 FPGAs, which provide a good tradeoff between performance, power and cost, thus being widely available and the de-facto academic standard for FPGAs. In particular, we focus on optimizing the performance of the carry-less polynomial multiplication, which takes around 90% of the execution time in the reference C99 software implementation. The chosen approach has been to employ the Karatsuba multiplication formula, applying it recursively while at the same time parallelizing the computation by replicating the multiplication units in the accelerator core. We achieve an improvement in terms of performance up to 24x with respect to the software implementation. Post-quantum cryptography focuses on the design of novel cryptographic algorithms for traditional computing platforms that are secure against quantum computers. Some classes of cryptographic algorithms for public key cryptography which are believed to be quantum-resistant are code-based, lattice-based, hash-based and multivariate polynomial cryptography. LEDApkc is a code-based post-quantum public-key cryptosystem (PKC), which exploits the advantages of relying on quasi-cyclic low-density parity-check (QC-LDPC) codes, therefore providing high decoding speeds and compact keypairs, and is implemented in order to achieve indistinguishability under adaptive chosen ciphertext attacks (IND-CCA2). This thesis proposes a hardware accelerator for LEDApkc encryption on a FPGA (Field Programmable Gate Array) family, developing a flexible and scalable solution which allows having high throughput when deployed on high-end FPGAs while at the same time requiring few resources on lower-end FPGAs. The proposed architecture targets Artix 7 FPGAs, which provide a good tradeoff between performance, power and cost, thus being widely available and the de-facto academic standard for FPGAs. In particular, we focus on optimizing the performance of the carry-less polynomial multiplication, which takes around 90% of the execution time in the reference C99 software implementation. The chosen approach has been to employ the Karatsuba multiplication formula, applying it recursively while at the same time parallelizing the computation by replicating the multiplication units in the accelerator core.

La tecnologia sta diventando sempre più pervasiva nella vita quotidiana, e la cybersicurezza rappresenta sempre più una preoccupazione per tutti gli utenti finali. La crittografia rappresenta attualmente il mezzo con cui viene garantita la sicurezza, ma è fortemente minacciata dai progressi nella ricerca dei computer quantistici. I computer quantistici forniscono un aumento esponenziale delle prestazioni nella risoluzione dei problemi di fattorizzazione degli interi e di calcolo del logaritmo discreto, che sono alla base di quasi tutti gli schemi di crittografia a chiave pubblica attualmente impiegati. Le principali aziende tecnologiche, tra cui IBM e Google, stanno investendo fortemente nell’implementazione dei computer quantistici, e questo rende fondamentale iniziare sin da ora a progettare nuovi crittosistemi che siano resistanti agli attacchi quantistici quando essi saranno possibili nei prossimi anni. La crittografia post quantica si concentra sulla progettazione di nuovi algoritmi crittografici per piattaforme di calcolo tradizionali che siano sicuri contro i computer quantistici. Alcune classi di algoritmi crittografici per crittografia a chiave pubblica che sono ritenuti resistenti anche a questi nuovi tipi di attacchi si basano sui codici a correzione di errore, sui reticoli, sulle funzioni di hash e sulle equazioni polinomiali multivariate. LEDApkc è un crittosistema a chiave pubblica (PKC) post quantico basato sui codici a correzione d’errore, che sfrutta i vantaggi dei codici a controllo di parità a bassa densità quasi-ciclici (QC-LDPC) ottenendo quindi alte velocità di decodifica e chiavi sia pubbliche che private di ridotte dimensioni, e che è implementato in modo da garantire l’indistinguibilità rispetto agli attacchi adattivi con testo cifrato scelto (IND-CCA2). Questa tesi propone un acceleratore hardware per l’encryption del crittosistema LEDApkc su una famiglia di FPGA (Field Programmable Gate Array), sviluppando uno soluzione flessibile e scalabile che fornisca elevate prestazioni quando impiegata su FPGA di fascia alta e allo stesso tempo richieda l’utilizzo di poche risorse su FPGA di fascia più bassa. L’architettura proposta ha come oggetto gli FPGA Xilinx Artix7, che forniscono un buon compromesso tra prestazioni, potenza e costo, e sono quindi ampiamente disponibili e rappresentano di fatto lo standard nel mondo accademico. In particolare, ci concentriamo sull’ottimizzazione delle prestazioni della moltiplicazione polinomiale, che nell’implementazione software di riferimento richiede circa il 90% del tempo di esecuzione. L’approccio scelto è stato quello di impiegare l’algoritmo di moltiplicazione rapida di Karatsuba, applicandolo ricorsivamente e allo stesso tempo parallelizzando la computazione replicando le unità di moltiplicazione nell’acceleratore. È stato ottenuto un miglioramento delle prestazioni fino a 24 volte rispetto alla versione software.La crittografia post quantica si concentra sulla progettazione di nuovi algoritmi crittografici per piattaforme di calcolo tradizionali che siano sicuri contro i computer quantistici. Alcune classi di algoritmi crittografici per crittografia a chiave pubblica che sono ritenuti resistenti anche a questi nuovi tipi di attacchi si basano sui codici a correzione di errore, sui reticoli, sulle funzioni di hash e sulle equazioni polinomiali multivariate. LEDApkc è una crittosistema a chiave pubblica (PKC) post quantico basato sui codici a correzione d'errore, che sfrutta i vantaggi dei codici a controllo di parità a bassa densità quasi-ciclici (QC-LDPC) ottenendo quindi alte velocità di decodifica e chiavi sia pubbliche che private di ridotte dimensioni, e che è implementato in modo da garantire l'indistinguibilità rispetto agli attacchi adattivi con testo cifrato scelto (IND-CCA2). Questa tesi propone un acceleratore hardware per l'encryption del crittosistema LEDApkc su una famiglia di FPGA (Field Programmable Gate Array), sviluppando uno soluzione flessibile e scalabile che fornisca elevate prestazioni quando impiegata su FPGA di fascia alta e allo stesso tempo richieda l'utilizzo di poche risorse su FPGA di fascia più bassa. L'architettura proposta ha come oggetto gli FPGA Xilinx Artix 7, che forniscono un buon compromesso tra prestazioni, potenza e costo, e sono quindi ampiamente disponibili e rappresentano di fatto lo standard nel mondo accademico. In particolare, ci concentriamo sull'ottimizzazione delle prestazioni della moltiplicazione polinomiale, che nell'implementazione software di riferimento richiede circa il 90% del tempo di esecuzione. L'approccio scelto è stato quello di impiegare l'algoritmo di moltiplicazione rapida di Karatsuba, applicandolo ricorsivamente e allo stesso tempo parallelizzando la computazione replicando le unità di moltiplicazione nell'acceleratore.