Crittografia multivariata: il problema dell'isomorfismo di polinomi e la sua applicazione a schemi di firma con delega

Un crittosistema a chiave pubblica multivariata (MPKC in breve) è uno schema asimmetrico in cui la funzione unidirezionale è rappresentata da una mappa polinomiale multivariata (in genere quadratica) su un campo finito. La sua sicurezza si basa sul fatto che la risoluzione di equazioni polinomiali multivariate su un campo finito è un problema NP-arduo. Questo ramo della crittografia è stato introdotto intorno alla fine degli anni '80 a causa del bisogno di trovare un'alternativa valida agli schemi basati su concetti numerici, come nell'RSA, non più computazionalmente efficienti contro gli attacchi dei potenti computer quantici. Sembra infatti che, a differenza degli schemi basati sulla fattorizzazione di numeri grandi o sulla ricerca del logaritmo discreto, non esiste alcun algoritmo che un computer quantico possa eseguire in tempo polinomiale per rompere un MPKC. I crittosistemi basati sul Problema dell'Isomorfismo di Polinomi (IP) formano una categoria di MPKC basata sulla difficoltà di ricoprire una particolare trasformazione tra due insiemi di polinomi multivariati. Il problema è il seguente: dati due insiemi di polinomi multivariati a e b, trovare due mappe invertibili lineari (o affini) S e T tali che b = T ◦ a ◦S. L'obiettivo di questo lavoro di tesi è quello di fornire una visione globale degli schemi IP andando ad analizzare nel dettaglio la sicurezza di questi crittosistemi e fare chiarezza sull'efficienza computazionale in relazione alla scelta dei parametri. A questo scopo sono stati ricercati e classificati i diversi attacchi forniti in questi anni, osservando come alcuni di questi sfruttino differenti risultati nel campo della geometria algebrica, come il calcolo delle basi di Grobner, altri usino concetti di probabilità, come il paradosso dei compleanni, ed altri ancora proprietà differenziali. Dal confronto di questi algoritmi è emerso come un'accurata scelta dei parametri possa portare a schemi resistenti, ovvero a problemi IP la cui risoluzione richiede un tempo esponenziale. Il problema dell'Isomorfismo di Polinomi è principalmente impiegato in schemi di autenticazione e nella firma asimmetrica. In questo lavoro l'attenzione è focalizzata principalmente su una recente applicazione su uno schema di firma con delega (proxy signature scheme), ovvero un protocollo nel cui il firmatario originale, o ¿delegator¿, può delegare un utente, detto ¿proxy signer¿, a firmare dei messaggi a favore del firmatario originale. Con tutta probabilità si tratta del primo ¿proxy signature scheme¿ basato su un crittosistema a chiave pubblica multivariata ed il principale vantaggio che lo distingue dagli altri schemi è la resistenza agli attacchi dei computer quantici, resa possibile proprio dall'uso di tali tipi di crittosistemi.

A Multivariate Public Key Cryptosystem (MPKC for short) is an asymmetric scheme where the trapdoor one-way function is a multivariate (usually quadratic) polynomial map over a finite field. Its security assumptions are based on the knowledge that solving a set of multivariate polynomial equations over a finite field is proven to be NP-hard. This area of cryptography began to be developed at the end of the '80s because of the need of a valid alternative to number theoretic-based schemes, such as RSA, no more computationally efficient against the attack of powerful quantum computers. Indeed it seems that, unlike schemes based on factorization of large integers or on finding a discrete logarithm, there is no known polynomial time algorithm that a quantum computer could perform to break a MPKC. Cryptosystems based on the Problem of Isomorphism of Polynomials (IP) form a major class of MPKC, based on the hardness of recovering a particular transformation between two sets of multivariate polynomials. The problem is the following: given two sets of multivariate polynomials a and b, find two invertible linear (or affine) maps S and T such that b = T ◦ a ◦S. The aim of this thesis work is to provide a global vision of the IP schemes, by deeply analyzing the security of these cryptosystems and explicating how the computational efficiency is related to the parameters chosen. To do so the past years attacks have been researched and classified, observing how they exploited different results, for instance in the algebraic geometry field (like the Grobner basis computation) or in the probability field (like the birthday paradox) and some more used differential properties. By comparing these algorithms, it was pointed out how a proper choice of parameters can lead to a stronger scheme and in particular to an IP problem solvable only in exponential time. The IP problem is mainly employed in authentication schemes and asymmetric signatures. In this work the main focus is on a recent application in a proxy signature scheme. It consists in a protocol in which the original signer, or delegator , can delegate a user, called proxy signer, to sign messages on his behalf. In all likelihood, this proxy signature scheme has been the first based on a Multivariate Public Key Cryptosystem and its main advantage over other proxy schemes is the resistance to the quantum computing attacks, made possible just by the use of such a kind of cryptosystem. ¬