The HFE cryptosystem is one of the most popular multi- variate schemes. Especially in the area of digital signatures, the HFEv- variant offers short signatures and high performance. Recently, an instance of the HFEv- signature scheme called GeMSS was selected as one of the alternative candidates for signature schemes in the third round of the NIST Post-Quantum Crypto (PQC) Standardization Project. In this paper, we propose a new key recovery attack on the HFEv- signature scheme. Our attack shows that both the Minus and the Vinegar modification do not enhance the security of the basic HFE scheme significantly. This shows that it is very difficult to build a secure and efficient signature scheme on the basis of HFE. In particular, we use our attack to show that the proposed parameters of the GeMSS scheme are not as secure as claimed.

In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar [3], which is a modification to the Unbalanced Oil and Vinegar Scheme by Patarin. Previously, Ding et al. proposed the Subfield Differential Attack [22] which prompted a change of parameters by the authors of LUOV for the second round of the NIST post quantum standardization competition [4]. In this paper we propose a modification to the Subfield Differential Attack called the Nested Subset Differential Attack which fully breaks half of the parameter sets put forward. We also show by experimentation that this attack is practically possible to do in under 210 min for the level I security parameters and not just a theoretical attack. The Nested Subset Differential attack is a large improvement of the Subfield differential attack which can be used in real world circumstances. Moreover, we will only use what is called the “lifted” structure of LUOV, and our attack can be thought as a development of solving “lifted” quadratic systems.

No abstract uploaded!

In this paper, we attack the recent NIST submission Giophantus, a public key encryption scheme. We find that the complicated structure of Giophantus's ciphertexts leaks information via a correspondence from a low dimensional lattice. This allows us to distinguish encrypted data from random data by the LLL algorithm. This is a more efficient attack than previous proposed attacks.

In 2017, Ward Beullens et al. submitted Lifted Unbalanced Oil and Vinegar (LUOV) [4], a signature scheme based on the famous multivariate public key cryptosystem (MPKC) called Unbalanced Oil and Vinegar (UOV), to NIST for the competition for post-quantum public key scheme standardization. The defining feature of LUOV is that, though the public key P works in the extension field of degree r of F_2, the coefficients of P come from F_2. This is done to significantly reduce the size of P. The LUOV scheme is now in the second round of the NIST PQC standardization process. In this paper we introduce a new attack on LUOV. It exploits the “lifted” structure of LUOV to reduce direct attacks on it to those over a subfield. We show that this reduces the complexity below the targeted security for the NIST post-quantum standardization competition.