Progettazione di decoder efficienti per HQC, un crittosistema post-quantum basato su codici

This thesis explores the Hamming Quasi Cyclic (HQC) post-quantum code-based cryptosystem, delving into coding theory principles and examining code families such as repetition, BCH, Reed-Solomon, and Reed-Muller codes. Additionally, mathematical aspects, particularly the Syndrome Decoding Problem (SDP) and its variants (2-QCSD, 3-QCSD), are scrutinized, with a brief introduction of complexity theory. The theoretical foundations of HQC, distinguishing between Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM) versions, are thoroughly detailed. The parameters and configurations of NIST competition rounds are extensively discussed, accompanied by a mathematical analysis of the Decoding Failure Rate (DFR) for the original HQC decoder. The focal point of the thesis is the groundbreaking introduction of a new HQC decoder. This innovative decoder incorporates noise pre-filtering based on a correlation strategy, harnessing information completely overlooked in the classic HQC decoder. This pivotal addition unequivocally ensures greater efficiency. Furthermore, the DFR for the new decoder is meticulously analyzed and compared with the classical HQC decoder. Simulations, conducted using both C and Python code, validate theoretical findings, highlighting the proposed decoder's advantages in reducing public key and ciphertext sizes leading to a decrease in data transmitted over a public channel. The degree of reduction is configuration-dependent, prompting a detailed examination of various HQC configurations in subsequent chapters. Finally, some practical scenarios are outlined in which the introduction of the new decoder can bring benefits, especially in contexts where ephemeral keys are used to ensure Perfect Forward Secrecy (PFS), such as in the TLS (Transport Layer Security) protocol and in Virtual Private Networks (VPNs).

Nella tesi, redatta in lingua inglese, si conduce uno studio dettagliato su HQC (Hamming Quasi Cyclic), un crittosistema post-quantum basato su codici. Inizialmente, si offre una panoramica dei concetti fondamentali della teoria dei codici, per poi procedere con l'analisi delle diverse famiglie di codici impiegate in HQC: codici a ripetizione, codici BCH, codici Reed-Solomon e, infine, i codici Reed-Muller. Successivamente, si esamina con dovizia di particolari il background matematico su cui si fonda HQC, con attenzione alla definizione del problema SDP (Syndrome Decoding Problem) nella sua versione decisionale. Inoltre, vengono presentate le varianti di questo problema, ovvero 2-QCSD e 3-QCSD con parità e cancellazioni. Nel prosieguo, senza pretesa di esaustività, si affronta il tema della teoria della complessità. In particolare, vengono definite diverse classi di complessità (P, NP, NP-complete e NP-Hard) ed i relativi problemi noti, tra cui la fattorizzazione di interi, SDP, SAT, vertexCover, setCover e Halting Problem. Inoltre, si assume ragionevolmente che le varianti di SDP considerate appartengano alla classe di complessità di SDP, cioè la classe dei problemi NP-Complete. Il lavoro prosegue con una minuziosa descrizione delle basi teoriche di HQC, delineando chiaramente la distinzione tra la versione PKE (Public Key Encryption) e KEM (Key Encapsulation Mechanism). Vengono forniti dettagli approfonditi riguardanti i parametri e le diverse configurazioni dei quattro round della competizione NIST, comprendenti le dimensioni di chiave pubblica, chiave segreta, testo cifrato, e l'eventuale chiave segreta condivisa. In aggiunta, si offre un approfondito e rigoroso studio matematico del DFR (Decoding Failure Rate) relativo al decoder HQC originale. Il culmine del lavoro di tesi è rappresentato dalla presentazione del nuovo decoder HQC, il quale incorpora il tradizionale decoder HQC arricchendolo con un pre-filtraggio del rumore basato su una strategia di correlazione. È cruciale sottolineare che la concezione di questo nuovo decoder HQC è il cuore pulsante del lavoro, la sua parte più significativa e il punto focale dell'intera ricerca. Tale decoder nasce da una considerazione strettamente ancorata alla teoria dell'informazione: c'è informazione che nella decodifica classica di HQC rimane inutilizzata, quindi, il suo impiego si traduce inevitabilmente in un notevole aumento dell'efficienza. La tesi offre, pertanto, un'analisi matematica dettagliata del DFR per il nuovo decoder, comparandolo esplicitamente con il DFR del decoder HQC tradizionale. In aggiunta, si valuta attentamente la complessità computazionale del nuovo decoder, evidenziando in modo esplicito il suo esiguo incremento rispetto alla controparte originale. In conclusione, vengono presentate simulazioni implementate in C e Python a conferma dei risultati teorici, con l'intento di evidenziare i benefici derivanti dall'introduzione del decoder proposto. In particolare, il nuovo decoder consente di ridurre le dimensioni della chiave pubblica e del testo cifrato, contribuendo così a ridurre la quantità di dati trasmessi su canale pubblico. Va notato che l'entità di questa riduzione è fortemente influenzata dalla configurazione utilizzata, pertanto, nei prossimi capitoli di tale tesi, questo aspetto verrà esaminato dettagliatamente per le diverse configurazioni di HQC. Infine, nella parte finale della tesi sono delineati alcuni scenari di interesse pratico in cui l'introduzione del nuovo decoder può apportare benefici, specialmente in contesti in cui si adoperano chiavi effimere per garantire la Perfect Forward Secrecy (PFS), come ad esempio nel protocollo TLS (Transport Layer Security) e nelle VPN (Virtual Private Network).