Design and development of a quantum circuit to solve the information set decoding problem

Cryptosystems based on linear codes are gaining momentum due to their stronger resistance to quantum attacks. They rely on the hardness of finding a minimum-weight codeword in a large linear code with an apparently random structure. In this work we designed and implemented several quantum circuits to specifically solve the Information Set Decoding problem, which is currently the most effective attack against code-based cryptoschemes. Relying on Grover's algorithm, the proposed algorithms were shown capable of effectively recover the original error vector simulating the computation of a quantum computer. Both an exhaustive search and a variant of Lee-Brickell's algorithm are proposed, with the former relying only on a quantum circuit and the latter using a hybrid classic-quantum approach. In both cases, two variants have been analyzed and compared, showing how a proper preparation of the initial state of the system can drastically reduce the number of iterations with respect to the uniform superposition of the classic Grover's algorithm. We provide, for the proposed algorithms, a quantitative evaluation of their computational complexity in terms of the number of involved quantum gates and required storage in qubits.

Negli ultimi anni i crittosistemi basati su codici lineari sono stati oggetto di studi sempre più approfonditi data la loro maggior resistenza ad attacchi tramite calcolatori quantistici. La sicurezza di questo tipo di crittosistemi si basa sulla difficoltà di ricavare il valore di una parola di codice corretta a partire da una affetta da errore dato un codice lineare con una struttura apparentemente casuale. In questo lavoro abbiamo progettato e implementato diversi circuiti quantistici in grado di risolvere il problema noto come Information Set Decoding, che è attualmente il più efficace tipo di attacco a tali crittosistemi. Basati sull'algoritmo di Grover, gli algoritmi quantistici proposti si sono dimostrati in grado di identificare l'errore originale con un'elevata percentuale di affidabilità, durante la loro validazione tramite simulatore di calcolatore quantistico. Abbiamo esplorato due tipi di attacchi diversi: il primo, basato su un algoritmo di ricerca esaustiva tradizionale, è puramente quantistico; il secondo, basato sull'algoritmo di Lee-Brickell, è un algoritmo ibrido classico-quantistico. In entrambi i casi, sono state utilizzate e comparate modalità di esecuzione diverse, dimostrando come un'attenta preparazione dello stato iniziale del sistema possa ridurre drasticamente il numero di iterazioni rispetto all'utilizzo di una versione base dell'algoritmo di Grover. In questo lavoro abbiamo inoltre fornito una misura quantitativa della complessità di calcolo di entrambi gli algoritmi proposti in termini di numero di quantum gates e numero complessivo di qubit.