A systematic analysis and optimization of information set decoding techniques : theoretical bounds and software realization

Most of the currently existing cryptographic algorithms are based on hard mathematical problem that are easier to resolve, with the advent of quantum computers. For this reason cryptographers started looking for new cryptographic algorithm based on harder mathematical problem respect to the previous one, finding the answer in code-based cryptography with the relative syndrome decoding problem. In this thesis we will analyze the best algorithm to solve syndrome decoding problem that are the information set decoding algorithms. Initially we will do a theoretical analysis of these algorithms, pointing out the complexities of every part of these algorithms, studying the possible optimizations. Subsequently we will compare the theoretical results with the practical results obtained through the implementation of these algorithms to study the relative behaviour and pointing out the differences.

La maggior parte degli algoritmi crittografici attualmente esistenti sono basati su difficili problemi matematici che, con l'avvento dei computer quantistici, sono risolvibili pi'u facilmente. Per questo motivo crittografi hanno iniziato a cercare nuovi algoritmi crittografici basati su problemi matematici maggiormente complessi rispetto ai problemi precedenti, trovando la risposta nella crittografia basata sui codici con il relativo problema della decodifica della sindrome. In questa tesi analizzeremo gli algoritmi migliori per risolvere il probelma di decodifica della sindrome, ovvero gli algoritmi di decodifica dell' information set. Inizialmente faremo un' analisi teorica di questi algoritmi, indicando le complessit'a di ogni parte di questi algoritmi studiandone le possibili ottimizzazioni. Successivamente andremo ad comparare i risultati teorici con dei risultati pratici ottenuti con l'implementazione di questi algoritmi per studiarne i comportamenti e valutarne le differenze.