Designing a quantum circuit to accelerate the solution of the search-learning with errors problem

The forecast growth of quantum computers leads to a new thread in cryptography. Indeed, these computers of a new kind are working in a very different way than classical computers, and this theoretically enables them to quickly break some ciphers, thus putting the asymmetric encryption and signature paradigms in danger. The post-quantum cryptography, which is the field aiming at providing new, secure and efficient cryptographic primitives so that, when quantum computers arrive, the security world will be ready. In this thesis, we focus on this field. More precisely, we focus on the "Learling With Errors" (LWE) problem, which is a promising mathematical problem on top of which several cryptosystems have been built. Despite current attacks targeting this mathematical problem are mostly classical, some quantum-accelerated ones exist. However, to my knowledge, none of them present a complete implementation, and none of them has been practically tried. This thesis provides a quantum-acceleration algorithm that enables to solve Search-LWE problem faster than a classical simple enumeration, this algorithm is not the most efficient that the field enables, however, I believe that the fact it was fully implemented is an interesting point. In this thesis, the different parts of the algorithms will be provided after a large introduction over the mentioned fields of study this work involves.

La crescita prevista dei computer quantistici porta a un nuovo filo conduttore nella crittografia. In effetti, questi computer di un nuovo tipo funzionano in un modo molto diverso rispetto ai computer classici, e questo teoricamente consente loro di violare rapidamente alcuni codici, mettendo così in pericolo la crittografia asimmetrica e i paradigmi della firma. La crittografia post-quantistica, che è il campo che mira a fornire primitive crittografiche nuove, sicure ed efficienti in modo che, quando arriveranno i computer quantistici, il mondo della sicurezza sarà pronto. In questa tesi ci concentriamo su questo campo. Più precisamente, ci concentriamo sul problema "Learling With Errors" (LWE), che è un promettente problema matematico su cui sono stati costruiti diversi crittosistemi. Nonostante gli attuali attacchi mirati a questo problema matematico siano per lo più classici, ne esistono alcuni con accelerazione quantistica. Tuttavia, per quanto ne so, nessuno di essi presenta un'implementazione completa e nessuno di essi è stato praticamente provato. Questa tesi fornisce un algoritmo di accelerazione quantistica che consente di risolvere il problema Search-LWE più velocemente di una classica semplice enumerazione, questo algoritmo non è il più efficiente che il campo abilita, tuttavia, credo che il fatto che sia stato completamente implementato sia un punto interessante. In questa tesi, le diverse parti degli algoritmi verranno fornite dopo un'ampia introduzione sui campi di studio menzionati in questo lavoro.