C++ redesign of attack algorithms to code-based cryptography

The rise of quantum computing poses a threat to the most widely used public-key cryptographic systems, such as RSA and Elliptic Curve Cryptography, whose security can be compromised by quantum algorithms such as Shor's algorithm. In this context, Post-Quantum Cryptography aims to develop cryptographic primitives that are resistant to both classical and quantum attacks. Among the various families of post-quantum solutions, code-based cryptography bases its security on the computational difficulty of decoding linear codes, such as General Decoding Problem and Syndrome Decoding Problem. The Information Set Decoding algorithms represent the main class of attacks used to evaluate the practical security of such systems. However, existing analyses primarily consider the serial case, ignoring the possibility that an adversary might exploit parallel computing resources to accelerate the attack. This thesis addresses this gap by designing and integrating the parallelization of the well-known Information Set Decoding algorithms within the CryptAttackTester framework, which provides a formalized environment for the quantitative analysis of cryptographic attacks based on a Boolean circuit computational model. In particular, a parallel variant of the isd1 algorithm, called isd1_parallel, has been designed and implemented, which distributes the computation across a network of concurrent machines following Bernstein's parallel brute-force model. An experimental campaign conducted over sets of parameters compares isd1_parallel against its serial counterpart in terms of depth speedup, area-time product, and security margin. The results show that, while parallelism can significantly reduce the circuit depth of an Information Set Decoding attack, the parameters maintain a robust security margin compliant with the required levels, confirming that the attack complexity remains exponential even under the parallel circuit model.

L'avvento dell'informatica quantistica rappresenta una minaccia per i sistemi crittografici a chiave pubblica più diffusi, come RSA e Elliptic Curve Cryptography, la cui sicurezza può essere compromessa da algoritmi quantistici quali l'algoritmo di Shor. In questo contesto, la Post-Quantum Cryptography mira a sviluppare primitive crittografiche resistenti ad attacchi sia classici che quantistici. Tra le varie famiglie di soluzioni post-quantistiche, la crittografia basata su codici fonda la propria sicurezza sulla difficoltà computazionale di decodificare codici lineari, quali General Decoding Problem e Syndrome Decoding Problem. Gli algoritmi Information Set Decoding rappresentano la principale classe di attacchi per valutare la sicurezza pratica di tali sistemi. Tuttavia, le analisi esistenti considerano prevalentemente il caso seriale, ignorando la possibilità che un avversario sfrutti risorse di calcolo parallele per accelerare l'attacco. La presente tesi colma questa lacuna progettando e integrando la parallelizzazione dei ben noti algoritmi Information Set Decoding all'interno del framework CryptAttackTester, che fornisce un ambiente formalizzato per l'analisi quantitativa degli attacchi crittografici basata su un modello computazionale a circuiti booleani. In particolare, è stata progettata e implementata una variante parallela dell'algoritmo isd1, denominata isd1_parallel, che distribuisce il calcolo su una rete di macchine concorrenti seguendo il modello di forza bruta parallela di Bernstein. Una campagna sperimentale condotta su diverse combinazioni di parametri mette a confronto isd1_parallel con la sua controparte seriale in termini di accelerazione della profondità, prodotto area-tempo e margine di sicurezza. I risultati mostrano che, sebbene il parallelismo possa ridurre significativamente la profondità del circuito di un attacco Information Set Decoding, i parametri mantengono un margine di sicurezza robusto e conforme ai livelli richiesti, confermando che la complessità dell'attacco rimane esponenziale anche nel modello di circuito parallelo.