Descrizione e crittanalisi algebrica dello schema di firma RYDE

Abstract

L'arrivo ormai imminente dei computer quantistici su larga scala rappresenta una seria minaccia per i protocolli crittografici a chiave pubblica attualmente in uso. In risposta al processo di standardizzazione per la crittografia post-quantum indetto dal NIST, è stato proposto lo schema di firma RYDE, la cui sicurezza si basa su una restrizione del problema di decodifica di sindrome di rango. Questo lavoro di tesi si concentra sullo studio della complessità computazionale della risoluzione di tale problema mediante l'uso delle basi di Gröbner. In particolare, si investiga il modello MaxMinors, che permette di tradurre il problema in un sistema polinomiale multivariato, per poi analizzare il costo di calcolo della base di Gröbner rispetto all'ordinamento DegRevLex al crescere dei parametri. Vengono confrontati due diversi approcci algebrici: una modellazione diretta e una basata sulla teoria delle relazioni di Plücker. I risultati sperimentali mostrano che la complessità del secondo approccio risulta più elevata, verosimilmente a causa del numero eccessivo di relazioni generate.

The advent of large-scale quantum computers represents a serious threat to currently deployed public-key cryptographic protocols. In response to the ongoing NIST standardization process for post-quantum cryptography, the RYDE signature scheme was introduced. The security of this scheme relies on the hardness of a specific restriction of the Rank Syndrome Decoding problem. This thesis focuses on the study of the computational complexity of solving this problem through the use of Gröbner bases. In particular, we investigate the MaxMinors modeling, which allows us to translate the problem into a multivariate polynomial system. We then analyze the cost of computing the Gröbner basis with respect to the DegRevLex ordering as the parameters increase. Two different algebraic approaches are compared: a direct modeling approach and one based on the theory of Plücker relations. The experimental results show that the complexity of the second approach is higher, likely due to the excessive number of generated relations.