Code-based cryptosystems have been thoroughly studied in literature due to their quantum resistant properties. The most effective attacks to such systems are based on solving the Information Set Decoding problem. Our work is based on Kachigar and Tillich’s studies on Quantum Random Walks used to tackle this issue. We detail the construction of a quantum circuit that explores a Johnson graph, which to the best of our knowledge has never been accomplished in literature. This thesis also shows how to apply such circuit to solve a sub-procedure of the Finiasz-Sendrier ISD algorithm. We provide a quantitative analysis of the performance of the circuit in term of the required amount of qubits and total quantum gates.

I crittosistemi basati su codici lineari sono oggetto di approfonditi studi a causa delle loro proprietà di resistenza agli attacchi quantistici. Gli attacchi più efficaci a questi sistemi sono basati sul risolvere il problema chiamato Information Set Decoding. Il nostro lavoro si fonda sugli studi di Kachigar e Tillich sulla risoluzione del problema sfruttando le Camminate Casuali Quantistiche. Mostriamo in dettaglio la costruzione di un circuito quantistico che esplora un grafo di Johnson, circuito che, al meglio delle nostre conoscenze, non è mai stato definito in letteratura. Questa tesi definisce come applicare il suddetto circuito per risolvere una sotto procedura dell’algoritmo di ISD di Finiasz-Sendrier. Forniamo infine un’analisi quantitativa delle prestazioni del circuito in termini di numero di qubit e porte quantistiche usate.

Design of a quantum circuit for quantum random walks on Johnson Graphs

Lancellotti, Giacomo;Lodi, Matteo
2020/2021

Abstract

Code-based cryptosystems have been thoroughly studied in literature due to their quantum resistant properties. The most effective attacks to such systems are based on solving the Information Set Decoding problem. Our work is based on Kachigar and Tillich’s studies on Quantum Random Walks used to tackle this issue. We detail the construction of a quantum circuit that explores a Johnson graph, which to the best of our knowledge has never been accomplished in literature. This thesis also shows how to apply such circuit to solve a sub-procedure of the Finiasz-Sendrier ISD algorithm. We provide a quantitative analysis of the performance of the circuit in term of the required amount of qubits and total quantum gates.
PELOSI, GERARDO
PERRIELLO, SIMONE
ING - Scuola di Ingegneria Industriale e dell'Informazione
28-apr-2022
2020/2021
I crittosistemi basati su codici lineari sono oggetto di approfonditi studi a causa delle loro proprietà di resistenza agli attacchi quantistici. Gli attacchi più efficaci a questi sistemi sono basati sul risolvere il problema chiamato Information Set Decoding. Il nostro lavoro si fonda sugli studi di Kachigar e Tillich sulla risoluzione del problema sfruttando le Camminate Casuali Quantistiche. Mostriamo in dettaglio la costruzione di un circuito quantistico che esplora un grafo di Johnson, circuito che, al meglio delle nostre conoscenze, non è mai stato definito in letteratura. Questa tesi definisce come applicare il suddetto circuito per risolvere una sotto procedura dell’algoritmo di ISD di Finiasz-Sendrier. Forniamo infine un’analisi quantitativa delle prestazioni del circuito in termini di numero di qubit e porte quantistiche usate.
File allegati
File Dimensione Formato  
2022_4_Lancellotti_Lodi.pdf

accessibile in internet per tutti

Descrizione: Thesis
Dimensione 1.26 MB
Formato Adobe PDF
1.26 MB Adobe PDF Visualizza/Apri
2022_4_Lancellotti_Lodi_Executive.pdf

accessibile in internet per tutti

Descrizione: Executive Summary
Dimensione 649.4 kB
Formato Adobe PDF
649.4 kB Adobe PDF Visualizza/Apri

I documenti in POLITesi sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10589/187455