Post-Quantum Multivariate Cryptography - A Study of Gui and GeMSS Signature Schemes using Gröbner Bases

Abstract

The main goal of this thesis is to analyze and compare the two signature schemes Gui and GeMSS, both submitted to the Post-Quantum Cryptography Standardization Process initiated by the National Institute of Standards and Technology. Both schemes are based on the hardness of solving a system of multivariate polynomial equations, using the construction known as Hidden Field Equations (HFE). HFE together with its modifications have been extensively studied for over 20 years and has withstood the test of time. Today's most promising attacks on HFE-based schemes are Gröbner basis algorithms, both in the quantum and classical setting. Gui and GeMSS will be analyzed with regards to a Gröbner basis approach, as well as some other notable attacks. One instance of Gui and its proposed security level is broken using a generic Meet-in-the-middle attack. The authors of Gui suggest a tweak of parameters to counter this attack, resulting in reduced efficiency of the scheme. The authors claim the run time of signature generation will increase by approximately 50%, while both analytical and experimental results presented in this thesis suggest an increase by a factor of e, Euler's number.