Protocolli a conoscenza zero basati sulla decodifica di vettori ristretti per firme digitali post-quantum

New approaches to code-based digital signatures have been studied in this work. In particular, we focused on zero-knowledge ID schemes and then applied the Fiat-Shamir transform to obtain ZKID-based signature schemes. Information Set Decoder generic solvers for Syndrome Decoding Problem have been analyzed. A relatively new problem based on sets of restricted elements, R-SDP, has been introduced. New ISD solvers have been developed for this setting, where the appropriate choice of the elements search space aims to increase the number of representations while keeping the lists as small as possible. For low values of z it is also possible to further exploit the algebraic structure of E, making attacks even more successful. It is then clear that even or small orders of the restricted set have to be avoided. We explored some of the already existing ZKID-based signature schemes, such as CVE, GPS and BG. By applying R-SDP to these schemes, we highlighted a saving in signature sizes. The R-GPS scheme achieves signature sizes of the order of 12 kB, which is 8 to 10 kB times less than GPS. The proof-of-concept Python implementation of R-GPS shows that the scheme can correctly work, even if it requires the execution of non-trivial subroutines for the management of Merkle Trees and binary trees. The timings are large but expected for a Python proof-of-concept. For full-weight instances, an even newer problem has been introduced, R-SDP(G), based on a restriction of the set of diagonal matrices with entries in E, showing that it leads to even smaller signatures when applied to the considered schemes. The obtained signature sizes in the order of 7 kB are highly competitive with respect to other state-of-the-art solutions.

Nella tesi vengono studiati gli schemi di firma digitale, in particolare quelli basati sugli schemi di identificazione a conoscenza zero (ZKID). Sono anche analizzati i cosiddetti Information Set Decoders (ISD), dei risolutori generici per il Syndrome Decoding Problem (SDP). Viene introdotta una variante del problema SDP basata su insiemi di elementi ristretti, R-SDP. Nuovi risolutori ISD vengono inoltre sviluppati, in modo da permettere l’uso della tecnica delle rappresentazioni. Sfruttando la struttura algebrica del set ristretto è infatti possibile aumentare il numero delle rappresentazioni pur mantenendo contenute le dimensioni delle liste. I set di cardinalità particolarmente ridotta possiedono inoltre più struttura, perciò la complessità degli attacchi si riduce ulteriormente in questi casi. Ne consegue che cardinalità pari o molto basse vanno evitate. Vengono discussi diversi algoritmi di firma già esistenti basati su ZKID, come CVE, GPS e BG. Applicando loro il problema R-SDP, si denotano riduzioni delle dimensioni di firma. Lo schema R-GPS ottiene dimensioni dell’ordine di 12 kB, ovvero da 8 a 10 kB inferiori rispetto a GPS. Viene realizzata una proof-of-concept in Python di R-GPS, che dimostra che lo schema funziona pur richedendo l’implementazione di funzioni complesse per la gestione dei Merkle Tree e degli alberi binari. I tempi di firma e verifica ottenuti sono elevati ma in linea con quanto aspettato da una proof-of-concept in Python. Per instanze full-weight, un nuovo problema può essere impiegato. R-SDP(G) è basato su di un’ulteriore restrizione del set di matrici diagonali con elementi in E e risulta in firme ancora più contenute quando viene applicato sugli schemi precedentemente discussi. Le risultanti dimensioni di firma nell’ordine di 7 kB sono notevolmente competitive rispetto alle alternative dello stato dell’arte.