Commutative algebra techniques in post-quantum cryptography
Publisher
Neuchâtel : Université de Neuchâtel
Date issued
2024
Number of pages
63
Subjects
Post-quantum cryptography Post-quantum signatures Multivariate Cryptography MinRank Problem Random system Gröbner basis Macaulay Algorithm Cryptographie post-quantique Signatures post-quantiques Cryptographie multivariée Problème du MinRank Système aléatoire Base de Gröbner Algorithme de Macaulay
Abstract
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.
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.
Notes
Acceptée sur proposition du jury:
Prof. Elisa Gorla, Université de Neuchâtel, directeur de thèse
Prof. Alessio Caminata, Università di Genova, Expert externe
Prof. Jung Kyu Canci, Université de Neuchâtel & HSLU , membre interne
Dr. Carlo Matteotti, DDPS - Swiss Armed Forces, Cyber Command, expert externe
Dr. Lisa Seccia, Université de Neuchâtel, membre interne
Soutenue le 24 octobre 2024
No de thèse : 3145
Prof. Elisa Gorla, Université de Neuchâtel, directeur de thèse
Prof. Alessio Caminata, Università di Genova, Expert externe
Prof. Jung Kyu Canci, Université de Neuchâtel & HSLU , membre interne
Dr. Carlo Matteotti, DDPS - Swiss Armed Forces, Cyber Command, expert externe
Dr. Lisa Seccia, Université de Neuchâtel, membre interne
Soutenue le 24 octobre 2024
No de thèse : 3145
Publication type
doctoral thesis
File(s)