Designing quantum walk circuits to accelerate list-based information Set Decoding attacks

The advent of quantum computing poses a fundamental threat to the widely used public-key cryptosystems whose security relies on the hardness of integer factorization and discrete logarithm problems. Shor developed a quantum algorithm capable of solving these problems in polynomial time, starting the search for new cryptographic primitives that remain secure even in the presence of quantum computers. Code-based cryptography is a promising candidate where its security is based on the hardness of decoding a random linear code or, equivalently, to solve the Syndrome Decoding Problem (SDP). Classically, the most efficient approach to solving the SDP is the Information Set Decoding (ISD), which exhibits an exponential complexity. This thesis investigates quantum attacks on code-based cryptosystems through the application of quantum ISD algorithms based on Quantum Walks on Johnson graphs. We present the design of these quantum ISD algorithms together with the quantum circuit implementations of their key components. A detailed circuit-level complexity analysis is performed, evaluating gate counts, circuit depth, and number of qubit required, in order to assess the feasibility and the impact of such attacks. These results are applied to several code-based cryptosystems, in particular BIKE, HQC, and McEliece, to provide an understanding of their security in a post-quantum setting.

L’avvento del calcolo quantistico rappresenta una minaccia fondamentale per i crittosistemi a chiave pubblica attualmente più diffusi, la cui sicurezza si basa sulla difficoltà della fattorizzazione di grandi numeri interi o la risoluzione dei logaritmi discreti. L’algoritmo quantistico di Shor mostra la possibilità di risolvere tali problemi in tempo polinomiale, incentivando la ricerca di nuove primitive crittografiche capaci di preservare la propria sicurezza anche di fronte ad attacchi quantistici. In questo contesto, la crittografia basata su codici lineari emerge come uno dei candidati più promettenti, la cui sicurezza si fonda sulla difficoltà di decodificare codici lineari casuali o sul problema equivalente della decodifica della sindrome (Syndrome Decoding Problem, SDP). Classicamente, l’approccio più efficace per risolvere l’SDP è rappresentato dagli algoritmi di Information Set Decoding (ISD), di complessità esponenziale. Questa tesi analizza attacchi quantistici ai crittosistemi basati su codici lineari mediante versioni quantistiche degli algoritmi ISD, basati su Quantum Walk su grafi di Johnson. Vengono presentati gli algoritmi e l’implementazione, a livello di circuito quantistico, dei loro componenti principali. Segue un’analisi della complessità a livello circuitale, che prende in esame il numero di porte quantistiche, la profondità dei circuiti e il numero di qubit richiesti, al fine di valutare la fattibilità e l’impatto reale degli attacchi presentati. Infine, i risultati ottenuti sono applicati a diversi crittosistemi basati su codici lineari, quali BIKE, HQC e McEliece, fornendo una valutazione del loro livello di sicurezza in uno scenario post-quantistico.