Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic applications. In this paper we present a strategy for computing Gröbner basis that challenges those complexity estimates. It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements–mutants. This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gröbner basis computation. The new proposed algorithm computed a Gröbner basis of a degree 2 random system with 32 variables and 32 equations using 30 GB which was never done before by any known Gröbner bases solver.

Recently, the Little Dragon Two and Poly-Dragon multivariate based public-key cryptosystems were proposed as efficient and secure schemes. In particular, the inventors of the two schemes claim that Little Dragon Two and Poly-Dragon resist algebraic cryptanalysis. In this paper, we show that MXL2, an algebraic attack method based on the XL algorithm and Ding’s concept of Mutants, is able to break Little Dragon Two with keys of length up to 229 bits and Poly-Dragon with keys of length up to 299. This contradicts the security claim for the proposed schemes and demonstrates the strength of MXL2 and the Mutant concept. This strength is further supported by experiments that show that in attacks on both schemes the MXL2 algorithm outperforms the Magma’s implementation of F4.

We give exact formulas for the growth of the ideal Aλ for λ a quadratic element of the algebra of Boolean functions over the Galois field GF(2). That is, we calculate dim A_k λ where A_k is the subspace of elements of degree less than or equal to k. These results clarify some of the assertions made in the article of Yang, Chen and Courtois [22,23] concerning the efficiency of the XL algorithm.

In this paper we present a new variant of the Zhuang-Zi algorithm, which solves multivariate polynomial equations over a finite field by converting it into a single variable problem over a large extension field. The improvement is based on the newly developed concept of mutant in solving multivariate equations.

MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity O((90r^2(15r+1)+180r^2+15r(15r+1)/2+27r+1)^w), where r is a small number denoting the degree of extension of finite fields and w ≈ 2.732. The computational complexity of deriving these equations is about 2^{37}. But to find the original plaintext, there still needs 240 times Gröbner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity O((15r+1)6r(12r+1)+180r^2+27r+1)^w. The complexity is 2^{36} for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems.

This paper discusses two encryption schemes to fix the Square scheme. Square+ uses the Plus modification of appending randomly chosen polynomials. Double-Layer Square uses a construction similar to some signature schemes, splitting the variables into two layers, one of which depends on the other.

In this paper, we present an efficient attack on the multivariate Quadratic Quasigroups (MQQ) public key cryptosystem. Our cryptanalysis breaks the MQQ cryptosystem by solving a system of multivariate quadratic polynomial equations using both the MutantXL algorithm and the F4 algorithm. We present the experimental results that show that MQQ systems is broken up to size n equal to 300. Based on these results we show also that MutantXL solves MQQ systems with much less memory than the F4 algorithm implemented in Magma.

Multivariate Public Key Cryptosystems (MPKCs) are often touted as future-proofing against Quantum Computers. It also has been known for efficiency compared to “traditional” alternatives. However, this advantage seems to erode with the increase of arithmetic resources in modern CPUs and improved algorithms, especially with respect to Elliptic Curve Cryptography (ECC). In this paper, we show that hardware advances do not just favor ECC. Modern commodity CPUs also have many small integer arithmetic/logic resources, embodied by SSE2 or other vector instruction sets, that are useful for MPKCs. In particular, Intel’s SSSE3 instructions can speed up both public and private maps over prior software implementations of Rainbow-type systems up to 4×. Furthermore, MPKCs over fields of relatively small odd prime characteristics can exploit SSE2 instructions, supported by most modern 64-bit Intel and AMD CPUs. For example, Rainbow over F_{31} can be up to 2× faster than prior implementations of similarly-sized systems over F_{16}. Here a key advance is in using Wiedemann (as opposed to Gauss) solvers to invert the small linear systems in the central maps. We explain the techniques and design choices in implementing our chosen MPKC instances over fields such as F_{31}, F_{16} and F_{256}. We believe that our results can easily carry over to modern FPGAs, which often contain a large number of small multipliers, usable by odd-field MPKCs.

We propose and analyze a multivariate encryption scheme that uses odd characteristic and an embedding in its construction. This system has a very simple core map F(X) = X^2, allowing for efficient decryption. We also discuss ways to make this decryption faster with specific parameter choices. We give heuristic arguments along with experimental data to show that this scheme resists all known attacks.

The SMS4 block cipher is part of the Chinese WAPI wireless standard. This paper describes the specification and offers a specification for a toy version called simplified SMS4 (S-SMS4). We explore algebraic attacks on SMS4 and S-SMS4 using Gröbner basis attacks on equation systems over GF(2) and GF(2^8), as well as attacks using a SAT solver derived from the GF(2) model. A comparison of SAT and Gröbner basis attacks is provided.

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.

TTM (tame transformation method) is a type of multivariate public key cryptosystem. In 2007, the inventor of TTM proposed two new instances of TTM to resist the existing attacks, in particular, the Nie et al attack. The two instances are claimed to achieve a security of 2109 against Nie et al attack. Through computation, we found that the instance II satisfied First Order Linearization Equations. After finding all linearization equations, we can perform a ciphertext-only attack to break it.

In this paper, we study how the algebraic attack on the HFE multivariate public key cryptosystem works if we build an HFE cryptosystem on a finite field whose characteristic is not two. Using some very basic algebraic geometry we argue that when the characteristic is not two the algebraic attack should not be polynomial in the range of the parameters which are used in practical applications. We further support our claims with extensive experiments using the Magma implementation of F_4, which is currently the best publicly available implementation of the Gröbner basis algorithm. We present a new variant of the HFE cryptosystems, where we project the public key of HFE to a space of one dimension lower. This protects the system from the Kipnis-Shamir attack and makes the decryption process avoid multiple candidates for the plaintext. We propose an example for a practical application on GF(11) and suggest a test challenge on GF(7).

We explore ideas for speeding up HFE-based signature schemes. In particular, we propose an HFEv^− system with odd characteristic and a secret map of degree 2. Changing the characteristic of the system has a profound effect, which we attempt to explain and also demonstrate through experiment. We discuss known attacks which could possibly topple such systems, especially algebraic attacks. After testing the resilience of these schemes against F4, we suggest parameters that yield acceptable security levels.

In 1989, Tsujii, Fujioka, and Hirayama proposed a family of multivariate public key cryptosystems, where the public key is given as a set of multivariate rational functions of degree 4. These cryptosystems are constructed via composition of two quadratic rational maps. In this paper, we present the cryptanalysis of this family of cryptosystems. The key point of our attack is to transform a problem of decomposition of two rational maps into a problem of decomposition of two polynomial maps. We develop a new improved 2R decomposition method and other new techniques, which allows us to find an equivalent decomposition of the rational maps to break the system completely. For the example suggested for practical applications, it is very fast to derive an equivalent private key, and it requires only a few seconds on a standard PC.

MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008. This paper proposes two substantial improvements to this algorithm over GF(2) that result in significantly reduced memory usage. We present experimental results comparing MXL2 to the XL algorithm, the MutantXL algorithm and Magma’s implementation of F_4. For this comparison we have chosen small, randomly generated instances of the MQ problem and quadratic systems derived from HFE instances. In both cases, the largest matrices produced by MXL2 are substantially smaller than the ones produced by MutantXL and XL. Moreover, for a significant number of cases we even see a reduction of the size of the largest matrix when we compare MXL2 against Magma’s F_4 implementation.

SMS4 is a 128-bit block cipher used in the WAPI standard for providing data confidentiality in wireless networks. In this paper we investigate and explain the origin of the S-Box employed by the cipher, show that an embedded cipher similar to BES can be obtained for SMS4 and demonstrate the fragility of the cipher design by giving variants that exhibit 2^{64} weak keys. We also show attacks on reduced round versions of the cipher. The best practical attack we found is an integral attack that works on 10 rounds out of 32 rounds with a complexity of 2^{18} operations; it can be extended to 13 rounds using round key guesses, resulting in a complexity of 2^{114} operations and a data complexity of 2^{16} chosen pairs.

In 2006, the inventors of TRMC public key cryptosystem proposed a new variant of TRMC, TRMC-4, which can resist the existing attack, in particular, the Joux et al attack. In this paper, we show that the new version is vulnerable to attack via the linearization equations (LE) method. For any given valid ciphertext and its corresponding TRMC-4 public key, we can derive the corresponding plaintext within 2^{24} F_{2^8}-operations, after performing once for the public key a computation of complexity less than 2^{34}. Our results are confirmed by computer experiments.

We propose the idea of building a secure hash using quadratic or higher degree multivariate polynomials over a finite field as the compression function. We analyze some security properties and potential feasibility, where the compression functions are randomly chosen high-degree polynomials, and show that under some plausible assumptions, high-degree polynomials as compression functions has good properties. Next, we propose to improve on the efficiency of the system by using some specially designed polynomials generated by a small number of random parameters, where the security of the system would then relies on stronger assumptions, and we give empirical evidence for the validity of using such polynomials.

In this paper, we show the claims in the original Kipnis-Shamir attack on the HFE cryptosystems and the improved attack by Courtois that the complexity of the attacks is polynomial in terms of the number of variables are invalid. We present computer experiments and a theoretical argument using basic algebraic geometry to explain why it is so. Furthermore we show that even with the help of the powerful new Gröbner basis algorithm like F_4, the Kipnis-Shamir attack still should be exponential but not polynomial. This again is supported by our theoretical argument.

No abstract uploaded!