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!

We combine the method of searching for an invariant subspace of the unbalanced Oil and Vinegar signature scheme and the Minrank method to defeat the new TTS signature scheme, which was suggested for low-cost smart card applications at CHES 2004. We show that the attack complexity is less than 2^{50}.

In 2004, the inventors of TTM cryptosystems proposed a new scheme that could resist the existing attacks, in particular, the Goubin-Courtois attack [GC00] and the Ding-Schmidt attack [DS03]. In this paper, we show the new version is still insecure, and we find that the polynomial components of the cipher (F_i) satisfy nontrivial equations of the special form ∑_{i=0}^{n−1} a_i x_i + ∑_{0≤j≤k≤m−1} b_{jk} F_j F_k + ∑_{j=0}^{m−1} c_j F_j + d = 0, which could be found with 2^{38} computations. From these equations and consequently the linear equations we derive from these equations for any given ciphertext, we can eliminate some of the variables x_i by restricting the functions to an affine subspace, such that, on this subspace, we can trivialize the "lock" polynomials, which are the key structure to ensure its security in this new instance of TTM. Then with method similar to Ding-Schmidt [DS03], we can find the corresponding plaintext for any given ciphertext. The total computational complexity of the attack is less than 2^{39} operations over a finite field of size 2^8. Our results are further confirmed by computer experiments.

We propose a new basic trapdoor ℓIC (ℓ-Invertible Cycles) of the mixed field type for Multivariate Quadratic public key cryptosystems. This is the first new basic trapdoor since the invention of Unbalanced Oil and Vinegar in 1997. ℓIC can be considered an extended form of the well-known Matsumoto-Imai Scheme A (also MIA or C^∗), and share some features of stagewise triangular systems. However ℓIC has very distinctive properties of its own. In practice, ℓIC is much faster than MIA, and can even match the speed of single-field MQ schemes.