Closed form decoding failure rate estimation for code-based post-quantum cryptosystems

Post-Quantum Cryptography has seen an increase in interest during the last decades, due to the advancements in quantum computing research that threatens the security of current asymmetric encryption methods. Cryptosystems based on Error Correction Codes prove to be a valid solution, being resistant to classical and quantum attackers while providing efficient communication primitives. A particular family of error correction codes, named QC-MDPC codes, have been employed in code-based post-quantum cryptosystems such as BIKE and LEDAcrypt, along with iterative decoders. Iterative bit-flipping decoders lead to a non-zero decoding failure probability, and estimating the Decoding Failure Rate (DFR) is a crucial yet challenging task. Indeed, such decoding failures can leak information about the private key, making accurate DFR estimates critical, and validation via Monte Carlo simulations is computationally unfeasible for the required failure rates. In this thesis, we introduce a novel technique to estimate the decoding failure rate of a two- and three-iterations parallel bit-flipping decoder, offering a closed form solution for quantifying the DFR of cryptographic-grade codes. We analyse the possibility of employing syndrome dependent thresholds in the decoding procedure, proposing concrete criteria for selecting such thresholds and evaluating their impact. We extensively validate the results of our models, and quantify the impact of a reliable DFR estimate on code-based post-quantum cryptosystems.

La ricerca in Crittografia Post-Quantum ha visto un aumento di interesse, dovuto ai progressi nello sviluppo di computer quantistici in grado di rompere i crittosistemi attualmente utilizzati. I crittosistemi basati su codici di correzione errori costituiscono una valida alternativa, in quanto resistono ad attacchi classici e quantistici e offrono primitive di comunicazione efficienti. Alcuni sistemi crittografici basati su codici, come BIKE e LEDAcrypt, utilizzano un particolare gruppo di codici di correzione errori, chiamati QC-MDPC, insieme ad algoritmi iterativi a punto fisso per la loro decodifica. Gli algoritmi di decodifica iterativa utilizzati in questi sistemi hanno una probabilità non nulla di fallire, e stimare il tasso di fallimento in decodifica (Decoding Failure Rate, DFR) risulta essere un problema difficile. I fallimenti in decodifica rivelano informazioni sulla chiave privata dei crittosistemi, rendendo critica una stima accurata del DFR dei codici utilizzati, ma la valutazione del tasso di fallimento con simulazioni Monte Carlo è computazionalmente irrealizzabile per i tassi di errore richiesti (dell'ordine di 2^-128 o inferiori). In questa tesi, presentiamo una nuova tecnica per stimare il tasso di fallimento in decodifica di un decoder parallelo a due e tre iterazioni, offrendo un modello in forma chiusa per quantificare il DFR di codici crittografici. Analizziamo la possibilità di utilizzare soglie dipendenti dal valore della sindrome nell'algoritmo di decodifica, proponendo criteri concreti per la selezione di tali soglie e la valutazione del loro impatto. Presentiamo un'ampia validazione dei risultati dei nostri modelli, e quantifichiamo l'impatto di una stima affidabile del DFR sulle dimensioni dei parametri (chiave pubblica, cifrato) di crittosistemi post-quantum basati su codici.