Studio di attacchi al problema dell'equivalenza tra codici lineari

Asymmetric cryptographic schemes, such as digital signatures, have foundational relevance in communication scheme security and cybersecurity. They are based on the difficulty in solving certain mathematical problems, which must be computationally intractable (i.e., solvable only by algorithms with exponential time complexity), otherwise the schemes would not be secure. A recently proposed scheme is LESS, whose security is based on the Code Equivalence Problem, that is, on the problem of finding, given a pair of codes, a linear equivalence that maps one code into the other. A special case of code equivalence is the Permutation Equivalence Problem (PEP), in which the equivalence is required to be a permutation. LESS is among the participants in the NIST process for standardizing post-quantum signature schemes and is an interesting candidate because, with recent improvements, it can go so far as to have very compact signatures. This thesis advances the state of the art on cryptanalysis of PEP, improving on some of the existing attacks and demonstrating how, in some cases (when codes are defined over finite nonprimary fields), instances of PEP considered difficult can instead be solved in polynomial time. The results obtained are justified through theoretical analysis and have been verified experimentally through intensive simulations (using Sagemath and Python). As a first contribution, Support Splitting Algorithm (SSA) was improved by finding a new way to compute the function of signature (used as a discriminant to reconstruct the permutation action). Compared with the function originally used in SSA, the new function proposed in this thesis retains the same computational complexity but is more discriminative. This makes SSA more efficient overall, as it reduces the number of steps required to reconstruct the permutation. The tests performed confirm the effectiveness of the proposed function. As a second contribution of the thesis, two ways of transforming instances of PEP that are considered difficult into instances of PEP that, instead, can be solved in polynomial time using SSA or a Graph Isomorphism Problem (GIP) solver were proposed and studied. The transformations considered apply only to codes over finite fields of dimension not before. The idea is to consider PEP on subfield codes, which maintain the permutation structure. Although starting from codes that are difficult to attack (called self-dual), thanks to the proposed transformations we are able to obtain codes for which PEP can be solved easily (with algorithms whose cost is polynomial). These results show how instances of PEP thought to be difficult are actually solvable in polynomial time. This means that for LESS, as well as for other cryptographic schemes, there are parameter choices that make the problem vulnerable. In particular, thanks to the results presented in this thesis, it can be concluded that working on non-prime fields is an unsafe choice. For this reason, it is strongly recommended to avoid using such codes for cryptographic applications, as they are easy to attack.

Gli schemi crittografici asimmetrici, come le firme digitali, hanno una rilevanza fondamendale nell’ ambito della sicurezza degli schemi di comunicazione e della cybersecurity. Essi si basano sulla difficoltà nel risolvere alcuni problemi matematici, che devono essere computazionalmente intrattabili (ovvero, risolubili solamente con algoritmi con complessità temporale esponenziale), altrimenti gli schemi non sarebbero sicuri. Uno schema recentemente proposto è LESS, la cui sicurezza si basa sul Code Equivalence Problem, ovvero, sul problema di trovare, data una coppia di codici, un’equivalenza lineare che mappa un codice nell’altro. Un caso particolare del code equivalence è quello del Permutation Equivalence Problem (PEP), in cui si richiede che l’equivalenza sia una permutazione. LESS è tra i partecipanti al processo NIST per la standardizzazione di schemi di firma post-quantum e rappresenta un candidato interessante in quanto, grazie a recenti miglioramenti, può arrivare ad avere firme molto compatte. Questa tesi avanza lo stato dell’arte sulla crittanalisi di PEP, migliorando alcuni degli attacchi esistenti e dimostrando come, in alcuni casi (quando i codici sono definiti su campi finiti non primi), istanze di PEP ritenute difficili possono invece essere risolte in tempo polinomiale. I risultati ottenuti sono giustificati tramite analisi teoriche e sono stati verificati sperimentalmente tramite simulazioni intensive (utilizzando Sagemath e Python). Come primo contributo, è stato migliorato Support Splitting Algorithm (SSA), trovando una nuova modalità per calcolare la funzione di signature (usata come discriminante per ricostruire l’azione della permutazione). Rispetto alla funzione usata originariamente in SSA, la nuova funzione proposta in questa tesi mantiene la stessa complessità computazionale ma è più discriminante. Questo rende SSA globalmente più efficiente, poichè riduce il numero di step necessari per ricostruire la permutazione. I test effettuati confermano l’efficacia della funzione proposta. Come secondo contributo della tesi, sono state proposte e studiate due modalità per trasformare istanze di PEP ritenute difficili in istanze di PEP che, invece, possono essere risolte in tempo polinomiale grazie a SSA o ad un risolutore per Graph Isomorphism Problem (GIP). Le trasformazioni considerate valgono solamente per codici su campi finiti di dimensione non prima. L’ idea è quella di considerare PEP sui sottocodici di sottocampo, che mantengono la struttura della permutazione. Pur partendo da codici difficili da attaccare (chiamati self-dual), grazie alle trasformazioni proposte si riescono ad ottenere codici per cui PEP può essere risolto facilmente (con algoritmi il cui costo è polinomiale). Questi risultati mostrano come istanze di PEP ritenute difficili siano in realtà risolvibili in tempo polinomiale. Questo significa che per LESS, così come per altri schemi crittografici, esistono scelte di parametri che rendono il problema vulnerabile. In particolare, grazie ai risultati presentati in questa tesi, si può concludere che lavorare su campi non primi è una scelta non sicura. Per questo motivo, si raccomanda fortemente di evitare di utilizzare codici di questo tipo per applicazioni crittografiche, poichè sono facili da attaccare.