Analisi e ottimizzazione di uno schema di firma digitale basato su codici derivato dal problema di decodifica della sindrome nel caso ristretto

This thesis provides a better understanding of the security of CROSS (Codes and Restricted Objects Signature Scheme), a digital signature scheme derived from an interactive Zero Knowledge Identification Protocol (ZKID) by applying the Fiat-Shamir Transformation. CROSS is currently in the NIST competition for the standardization of a quantum-resistant digital signature scheme. In particular, in this thesis we focus on the security of the problem underlying CROSS, namely the Restricted Syndrome Decoding Problem (R-SDP). This is a problem based on the decoding of linear codes proven to be NP-hard. However, R-SDP is a relatively new problem and, therefore, its security needs to be carefully studied. The contribution of the following work is to study a possible application of the Locality Sensitive Framework, an approach for solving the Nearest Neighbour search problem in the case of binary vectors, to the best solvers for R-SDP which are, to date, the algorithms based on Information Set Decoding (ISD). The result of this analysis is the realization of a new attack for R-SDP. By formulating a theoretical cost for this new approach, it was possible to evaluate its performance on different instances of the restricted problem. The results obtained in this thesis allow for two important interpretations: on the one hand, the cryptanalysis of some schemes in the literature based on R-SDP is improved by reducing their security level, and on the other hand, although the performance of existing attacks is improved, it can be established that CROSS, as designed, achieves the NIST security level I even for this new attack.

In questa tesi viene fornita una migliore compresione della sicurezza di CROSS (Codes and Restricted Objects Signature Scheme), uno schema di firma digitale derivato da un protocollo interattivo di identificazione Zero Knowledge (ZKID) applicando la Trasformazione di Fiat-Shamir. CROSS è attualmente in gara nella competizione indetta dal NIST per la standizzazione di uno schema di firma digitale che sia sicuro in un'ottica post-quantum. In particolare in questa tesi ci si focalizza sulla sicurezza del problema alla base di CROSS, ovvero il Restricted Syndrome Decoding Problem (R-SDP). Si tratta di un problema basato sulla decodifica di codici lineari dimostrato essere NP-hard. Tuttavia R-SDP è un problema relativamente nuovo e, pertanto, la sua sicurezza ha bisogno di essere studiata attentamente. Il contributo del seguente lavoro è quello di studiare una possibile applicazione del Locality Sensitive Framework, un approccio per la risoluzione del Nearest Neighbor search problem nel caso di vettori binari, ai migliori risolutori per R-SDP che sono, ad oggi, gli algoritmi della famiglia Information Set Decoding (ISD). Il risultato di questa analisi è stato la realizzazione di un nuovo attacco per R-SDP. Tramite la formulazione di un costo teorico per questo nuovo approccio è stato possibile valutarne le prestazioni su diverse istanze del problema ristretto. I risultati ottenuti in questa tesi sono soggetti ad una duplice interpretazione: se da una parte la crittoanalisi di alcuni schemi presenti in letteratura basati su R-SDP viene migliorata riducendo il loro security level, dall'altra, pur avendo ottenuto un miglioramento in termini di performance degli attacchi esistenti, è possibile stabilire che CROSS, anche di fronte a questo nuovo approccio, risulta raggiungere i criteri di sicurezza stabiliti dal NIST.