Hardware design and implementation of post-quantum cryptographic algorithms: the case of NTRU, HQC and CROSS

During the last decade, public key cryptography received renewed attention from academic, industrial and institutional stakeholders due to the consistent advancements in the development of more capable quantum computers, which are deemed able to break in the near future the security guarantees provided by the currently deployed cryptographic algorithms based on the hardness of the integer factorization or discrete logarithm problems (e.g., RSA and ECC) thanks to Shor's algorithm. In 2016, the U.S.A. National Institute of Standards and Technology published a call for public key schemes resistant to quantum-computer-aided attacks, intending to replace the vulnerable algorithms currently in use and asking the community for cryptanalysis and optimized software and hardware implementations of the proposals. After several rounds of selection, schemes based on lattices and forward error-correction codes proved to be the most promising. Taking a hardware design perspective, I focused on analyzing the key encapsulation mechanism based on the Hoffstein, Pipher, and Silverman's NTRUEncrypt encryption scheme, commonly referred to as NTRU, the key encapsulation mechanism named "Hamming Quasi-Cyclic" (HQC), and the digital signature algorithm named "Codes and Restricted Objects Signature Scheme" (CROSS), with a particular emphasis on the optimization of the latency and the efficiency of their building blocks such as polynomial multipliers, random polynomial samplers and encoders/decoders for the Reed-Muller/Reed-Solomon concatenated code, ideating and comparing novel specialized algorithms for the sub-procedures composing the cryptoschemes and providing results for both FPGA and ASIC design flows. The results show a substantially improved latency and efficiency compared to the state-of-the-art, and a proposed algorithmic optimization for HQC was recently included in the official specification.

Durante l'ultimo decennio, la crittografia a chiave pubblica ha ricevuto una rinnovata attenzione da parte di accademia, industria, e parti istituzionali interessate a causa dei continui progressi nello sviluppo di computer quantistici, i quali sono ritenuti in grado di violare nel prossimo futuro le garanzie di sicurezza fornite dagli algoritmi a chiave pubblica attualmente utilizzati che sono basati sulla difficoltà della fattorizzazione di numeri interi estremamente grandi, o del logaritmo discreto (ad esempio, RSA ed ECC) grazie all'algoritmo di Shor. Nel 2016, il National Institute of Standards and Technology degli Stati Uniti d'America ha pubblicato un bando per nuovi schemi a chiave pubblica resistenti ad attacchi per mezzo di computer quantistici con l'intento di sostituire gli algoritmi vulnerabili attualmente in uso, e al chiedendo alla comunità di effettuare crittoanalisi e implementazioni software e hardware ottimizzate delle proposte. Dopo diversi round di selezione, gli schemi basati su reticoli e codici a correzione degli errori si sono dimostrati i più promettenti. Considerando lo sviluppo di sistemi digitali, la mia ricerca si focalizza sull'analisi del meccanismo di generazione delle chiavi di sessione basato sull'algoritmo NTRUEncrypt di Hoffstein, Pipher, e Silverman, comunemente chiamato NTRU, il meccanismo di condivisione "Hamming Quasi-Cyclic" (HQC) e dell'algoritmo di firma digitale "Codes and Restricted Objects Signature Scheme" (CROSS), ponendo particolare enfasi sull'ottimizzazione della latenza e dell'efficienza dei componenti chiave come moltiplicatori polinomiali, generatori di polinomi casuali e codificatori/decodificatori per il codice concatenato Reed-Muller/Reed-Solomon, ideando e confrontando nuovi algoritmi specializzati per le sotto-procedure che compongono i crittosistemi, e analizzando i risultato con flussi di progettazione per FPGA e ASIC. I risultati ottenuti mostrano una latenza e un'efficienza sostanzialmente migliorate rispetto ai risultati precedenti, e un'ottimizzazione algoritmica proposta per HQC è stata recentemente inclusa nella specifica ufficiale.