A concrete evaluation of information set decoding techniques

Nowadays, the most used public-key cryptosystems are based on the hardness of factoring very large numbers or on the intractability of the discrete logarithm problem. We already know that in the future, when it will be possible to build large quantum computers, these problems will be solvable easily thanks to the Shor's algorithm. Therefore, there is a need to study alternative cryptosystems based on different hard mathematical problems that will be resistant in the era of the quantum computers. One of this alternative is code-based cryptography on which the McEliece and Niederreiter cryptosystems are based on. The functioning of these cryptosystems is founded on the hardness of the syndrome decoding problem, or equivalently, the decoding of a random linear code. In this work we are going to analyze and implement the algorithms with the best complexities in the current state of the art that are called Information Set Decoding algorithms: they try to break the code-based cryptosystems solving the syndrome decoding problem. After analyzing subroutines that will be used in the implementation of the ISD algorithms, evaluating different procedures to understand the most efficient one, we are going to study how the Information Set Decoding algorithms work with their complexities and then, we will present the results obtained by a concrete evaluation of them to understand their behaviours in practice.

Attualmente, i crittosistemi a chiave pubblica maggiormente utilizzati, sono basati sulla difficoltà di fattorizzare numeri molto grandi oppure sull'intrattabilità del problema del logaritmo discreto. Sappiamo già che nel futuro, quando saranno disponibili computer quantistici sufficientemente potenti, sarà possibile risolvere questi problemi facilmente grazie al noto algoritmo di Shor. Dunque, c'è bisogno di studiare crittosistemi alternativi, basati su diversi problemi matematici difficili, che saranno resistenti nell'era dei computer quantistici. Una di queste alternative è la crittografia basata su codici lineari che è alla base dei crittosistemi di McEliece e di Niederreiter. Il funzionamento di questi crittosistemi è fondato sulla difficoltà di risolvere il problema di decodifica di una sindrome, o equivalentemente, la decodifica casuale di un codice lineare. In questo lavoro andremo ad analizzare e ad implementare gli algoritmi con la miglior complessità attualmente conosciuti nello stato dell'arte chiamati algoritmi di Information Set Decoding: essi cercano di rompere i crittosistemi basati su codici lineari risolvendo il problema di decodifica di una sindrome. Dopo aver analizzato diversi sottoprogrammi che saranno utili nell'implementazione degli algoritmi ISD, valutando diverse procedure per capire la più efficiente da utilizzare, andremo a studiare come funzionano i vari algoritmi Information Set Decoding con le relative complessità, e infine, saranno presentati i risultati ottenuti da una concreta valutazione di questi algoritmi per capire il loro comportamento nella pratica.