Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, either made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We...

The multivariate scheme HFEv- used to be considered a promising candidate for a post-quantum signature system. First suggested in the early 2000s, a version of the scheme made it to the third round of the ongoing NIST post-quantum standardization process. In late 2020, the system suffered from an efficient rank attack due to Tao, Petzoldt, and Ding. In this paper, we inspect how this recent rank attack is affected by the projection modification. This modification was introduced to secure the...

The HFEv- signature scheme is a twenty year old multivariate public key signature scheme. It uses the Minus and the Vinegar modifier on the original HFE scheme. An instance of the HFEv- signature scheme called GeMSS is 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. We show that the Minus modification does not enhance the...

In this paper, we study and construct multivariate schemes with “ultra-short” signatures. We focus on the classic case where the public key is a set of multivariate polynomials of degree 2. To design ultra-short signature schemes, we consider that signing a message and verifying a signature could require up to 1 minute of computation on a modern personal computer. Shorter time could be considered but at the cost of a few additional bits in the signatures, more generally, a...

In this paper we consider several methods for an efficient extraction of roots of a polynomial over large finite fields. The problem of computing such roots is often the performance bottleneck for some multivariate quantum-immune cryptosystems, such as HFEv-based Quartz, Gui, etc. We also discuss a number of techniques for fast computation of traces as part of the factorization process. These optimization methods could significantly improve the performance of cryptosystems where roots...

The HFEv- signature scheme is one of the most studied multivariate schemes and one of the major candidates for the upcoming standardization of post-quantum digital signature schemes. In this paper, we propose three new attack strategies against HFEv-, each of them using the idea of projection. Especially our third attack is very effective and is, for some parameter sets, the most efficient known attack against HFEv-. Furthermore, our attack requires much less memory than direct and rank...

The HFEv- signature scheme is one of the most promising candidates for post-quantum digital signatures. Most notably here is the short signature size of the scheme. It has long been known that direct attacks against HFEv- systems work more efficiently than against random systems. The reason for this was found by Jintai Ding et al., who proved an upper bound on the degree of regularity of these systems. However, not much is known about the efficiency of the hybrid approach against the HFEv-...

(Sequential) Aggregate signature schemes enable a group of users $u_1, \dots, u_k$ with messages $m_1, \dots, m_k$ to produce a single signature $\Sigma$ which states the integrity and authenticity of all the messages $m_1, \dots, m_k$. The length of the signature $\Sigma$ is thereby significantly shorter than a concatenation of individual signatures. Therefore, aggregate signatures can improve the efficiency of numerous applications, e.g. the BGPsec protocol of Internet routing and the...

In this paper, we propose a new multivariate signature scheme named MI-T-HFE as a competitor of QUARTZ. The core map of MI-T-HFE is of an HFEv type but more importantly has a specially designed trapdoor. This special trapdoor makes MI-T-HFE have several attractive advantages over QUARTZ. First of all, the core map and the public map of MI-T-HFE are both surjective. This surjectivity property is important for signature schemes because any message should always have valid signatures; otherwise...

In this paper, we design a novel one-way trapdoor function, and then propose a new multivariate public key cryptosystem called $\rm TOT$, which can be used for encryption, signature and authentication. Through analysis, we declare that $\rm TOT$ is secure, because it can resist current known algebraic attacks if its parameters are properly chosen. Some practical implementations for $\rm TOT$ are also given, and whose security level is at least $2^{90}$. The comparison shows that $\rm TOT$ is...

Many efficient attacks have appeared in recent years, which have led to serious blow for the traditional multivariate public key cryptosystems. For example, the signature scheme SFLASH was broken by Dubois et al. at CRYPTO'07, and the Square signature (or encryption) scheme by Billet et al. at ASIACRYPTO'09. Most multivariate schemes known so far are insecure, except maybe the sigature schemes UOV and HFEv-. Following these new developments, it seems that the general design principle of...

This thesis gives an overview of Multivariate Quadratic polynomial equations and their use in public key cryptography. In the first chapter, some general terms of cryptography are introduced. In particular, the need for public key cryptography and alternative schemes is motivated, i.e., systems which neither use factoring (like RSA, Rivest-Shamir-Adleman) nor the discrete logarithm (like ECC, elliptic curve cryptography). This is followed by a brief introduction of finite fields and a...

In this article, we investigate the question of equivalent keys for two $\mathcal{M}$ultivariate $\mathcal{Q}$uadratic public key schemes HFE and C$^{*--}$ and improve over a previously known result, to appear at PKC 2005. Moreover, we show a new non-trivial extension of these results to the classes HFE-, HFEv, HFEv-, and C$^{*--}$, which are cryptographically stronger variants of the original HFE and C$^*$ schemes. In particular, we are able to reduce the size of the private --- and hence...

The most popular public key cryptosystems rely on assumptions from algebraic number theory, e.g., the difficulty of factorisation or the discrete logarithm. The set of problems on which secure public key systems can be based is therefore very small: e.g., a breakthrough in factorisation would make RSA insecure and hence affect our digital economy quite dramatically. This would be the case if quantum-computer with a large number of qbits were available. Therefore, a wider range of candidate...

Quartz is a signature scheme based on an HFEv- trapdoor function published at Eurocrypt 1996. In this paper we study "inversion" attacks for Quartz, i.e. attacks that solve the system of multivariate equations used in Quartz. We do not cover some special attacks that forge signatures without inversion. We are interested in methods to invert the HFEv- trapdoor function or at least to distinguish it from a random system of the same size. There are 4 types of attacks known on HFE:...

In a paper published at Asiacrypt 2000 a signature scheme that (apparently) cannot be abused for encryption is published. The problem is highly non-trivial and every solution should be looked upon with caution. What is especially hard to achieve is to avoid that the public key should leak some information, to be used as a possible "shadow" secondary public key. In the present paper we argument that the problem has many natural solutions within the framework of the multivariate...