Analisi di chiavi deboli nei sistemi crittografici post-quantum basati su codici LDPC e MDPC

In this thesis we propose a new methodology to evaluate a lower-bound for the Decoding Failure Rate of LDPC and MDPC codes, that can be used to evaluate the security of cryptographics system based on these types of codes. These cryptosystems are being studied because they are possibly "quantum-resistant", meaning that they may not be broken by quantuum computer. Their security is strictly related to their DFR; however there are required values so small that it is impossible to study them through simulations. The work here propose a new technique to have a lower-bound for the DFR based on the analysis of weak keys, and applies it to 2 cryptoschemes proposed for the Post-Quantum Cryptography Standardization project of NIST, namely LEDAcrypt and BIKE.

Nei prossimi anni verranno sviluppati i computer quantistici, i quali sono sensibilmente più performanti dei dispositivi attuali. Si sa che questi sistemi saranno in grado di rompere sistemi crittografici attualmente in uso. Per questo motivo il NIST (National Institute of Standards and Technology) ha indetto una gara per valutare quali crittosistemi siano in grado di resistere ad attacchi da parte di computer quantistici, per scegliere infine quale sia quello più adatto a diventare il nuovo standard. Alcune proposte sono basate sull'uso di codici sparsi, come i codici LDPC o MDPC (Low/Moderate Density Parity Check). Questa tipologia di codici è stata largamente studiata nell'ambito delle comunicazioni, date le ottime caratteristiche ed in particolare per l'efficienza nel correggere errori. Di recente sta assumendo particolare interesse la possibilità di impiegarli anche in ambito crittografico. Basandosi su crittosistemi quali quelli di McEliece e Niederreiter, alcune proposte sono state avanzate per utilizzare i codici sparsi per garantire sicurezza post-quantum. Alcuni esempi di interesse in questo ambito sono LEDAcrypt e BIKE. Una delle principali criticità da valutare affinché si possano usare codici sparsi in sicurezza è il valore della Decoding Failure Rate (DFR). Esiste infatti una probabilità non nulla che il decoder in ricezione non riesca a recuperare il messaggio originario quando questi codici vengono impiegati. Il problema è stato approfonditamente studiato, e gli attuali sistemi presentano una DFR estremamente bassa per scopi comunicazionistici. Tuttavia se lo scopo è quello di garantire sicurezza post-quantum, le specifiche riguardo la DFR diventano ancora più stringenti. Il problema studiato in questo lavoro è stato di trovare un approccio che rendesse possibile definire un metodo per calcolare un limite inferiore per la DFR dei sistemi crittografici, nonostante si tratti di valori talmente piccoli da richiedere un numero di simulazioni eccessivamente grande per essere svolto in tempi ragionevoli, anche avendo a disposizione elaboratori molto performanti. Si descriverà quindi una metodologia innovativa che permette di avere una stima della DFR ed una prima valutazione della sicurezza. Questa stima è in alcuni casi sufficiente a minare i presupposti per l'affidabilità del crittosistema. Per fare ciò sarà necessario studiare l'impatto delle chiavi dette "deboli", perché presentano particolari caratteristiche per le quali ci si aspetta che la DFR aumenti (anche notevolmente) quando queste vengono scelte come chiavi. Si applicherà questa idea ai due algoritmi già citati, LEDAcrypt e BIKE, per due particolari tipi di chiavi deboli, in modo da valutarne la sicurezza e fornire degli esempi di come la metodologia qui presentata possa essere applicata.