Résultat de la recherche
Commutative algebra techniques in post-quantum cryptography
Post-quantum cryptography aims to find quantum-resistant public-key cryptographic schemes, that is, schemes which remain secure against both quantum and standard computers. In fact in 1994, Shor published an algorithm [85] breaking the nowadays used public-key cryptoschemes in polynomial time on a quantum computer. The security of public-key algorithms is based on computationally hard mathematical problems. Among the post-quantum proposals there is the Multivariate Problem: Solving a multivariate polynomial system over a finite field. The general and the most computationally efficient method for solving such systems is computing a Groöbner basis of the ideal they generate. In 2021, Beullens [22] used a strategy involving the MinRank Problem for breaching the most promising multivariate scheme at the time. All the details regarding public-key schemes and in particular the multivariate one can be found within the Introduction. The thesis is divided into three blocks. The goal of Chapter 1 is twofold. It is a collection of algebraic concepts and classical facts that are used through these pages, in particular, Section 1.1 serves this scope. In addition, the problem of solving polynomial systems via Gr¨bner basis is fully explained in Section 1.2. In Chapter 2 and Chapter 3, I present the two main works of my PhD, during which I mainly focused on the analysis of multivariate cryptoschemes twofolds. Firstly, together with my advisor Elisa Gorla, we propose a new definition of ‘random system’ using the concept of generality mutued from algebraic geometry. The details of this work are given in Chapter 2. On the other hand, with the help of Daniel Cabarcas (Universidad Nacional de Colombia), we investigated the SupportMinors Modeling, which is a method for modeling the MinRank Problem used by Beullens in his attack. The specifics of this work can be found in Chapter 3.