Thesis : The algebra of the MinRank problem in post-quantum cryptography: Gröbner bases, complexity, and implementations
PhD school thesis
The central issue which is at the genesis of this thesis is that polynomial systems coming from MinRank are not generic. Complexity studies of the F5 algorithm do not apply there. In , the authors present a preliminary study of the algebraic properties of the MinRank systems, and identify the largest size of the matrices considered during the Gröbner basis computation in order to deduce an upper complexity bound. Apart from this, only heuristic results are known, with no proved complexity upper bound. The goal of this PhD is to adapt the F5 algorithm to the MinRank systems, obtain the most accurate possible upper and lower bounds on the complexity, and apply the new derived algorithms to challenging instances coming from the future post-quantum standards.
This PhD research project has been submitted for a funding request to “Ecole Doctorale d‘Informatique, Télécommunication et d‘Electronique (EDITE)”. The PhD candidate selected by the project leader will therefore participate in the project selection process (including a file and an interview) to obtain funding.
More details here
Contact :Ludovic Perret, Vincent Neiger, Éric Schost