This paper introduces a new efficient algorithm, called MXL_3, for computing Gröbner bases of zero-dimensional ideals. The MXL_3 is based on XL algorithm, mutant strategy, and a new sufficient condition for a set of polynomials to be a Gröbner basis. We present experimental results comparing the behavior of MXL_3 to F_4 on HFE and random generated instances of the MQ problem. In both cases the first implementation of the MXL_3 algorithm succeeds faster and uses less memory than Magma’s implementation of F_4.

This paper summarizes most of the main developments in the cryptanalysis of multivariate cryptosystems and discuss some problems that remain open. A strong emphasis is put on the symbolic computation tools that have been used to achieve these advances.

A recently proposed class of multivariate Public-Key Cryptosystems, the Rainbow-Like Digital Signature Schemes, in which successive sets of central variables are obtained from previous ones by solving linear equations, seem to lead to efficient schemes (TTS, TRMS, and Rainbow) that perform well on systems of low computational resources. Recently SFLASH (C^{∗−}) was broken by Dubois, Fouque, Shamir, and Stern via a differential attack. In this paper, we exhibit similar algebraic and diffential attacks, that will reduce published Rainbow-like schemes below their security levels. We will also discuss how parameters for Rainbow and TTS schemes should be chosen for practical applications.

This paper presents a time-area efficient hardware architecture for the multivariate signature scheme Rainbow. As a part of this architecture, a high-performance hardware optimized variant of the well-known Gaussian elimination over GF(2^l) and its efficient implementation are presented. The resulting signature generation core of Rainbow requires 63,593 gate equivalents and signs a message in just 804 clock cycles at 67 MHz using AMI 0.35μm CMOS technology. Thus, Rainbow provides significant performance improvements compared to RSA and ECDSA.

The SFLASH signature scheme stood for a decade as the most successful cryptosystem based on multivariate polynomials, before an efficient attack was finally found in 2007. In this paper, we review its recent cryptanalysis and we notice that its weaknesses can all be linked to the fact that the cryptosystem is built on the structure of a large field. As the attack demonstrates, this richer structure can be accessed by an attacker by using the specific symmetry of the core function being used. Then, we investigate the effect of restricting this large field to a purely linear subset and we find that the symmetries exploited by the attack are no longer present. At a purely defensive level, this defines a countermeasure which can be used at a moderate overhead. On the theoretical side, this informs us of limitations of the recent attack and raises interesting remarks about the design itself of multivariate schemes.