MathSciDoc: An Archive for Mathematician ∫

In the CT-track of the 2006 RSA conference, a new multivariate public key cryptosystem, which is called the Medium Field Equation (MFE) multivariate public key cryptosystem, is proposed by Wang, Yang, Hu and Lai. We use the second order linearization equation attack method by Patarin to break MFE. Given a ciphertext, we can derive the plaintext within 2^{23} F_{2^16}-multiplications, after performing once for any given public key a computation of complexity less than 2^{52}. We also propose a high order linearization equation (HOLE) attack on multivariate public key cryptosystems, which is a further generalization of the (first and second order) linearization equation (LE). This method can be used to attack extensions of the current MFE.

We present the Zhuang-Zi algorithm, a new method for solving multivariate polynomial equations over a finite field. We describe the algorithm and present examples, some of which cannot be solved with the fastest known algorithms.

We prove that a random map drawn from any class \mathfrak{C} of polynomial maps from (F_q)^n to (F_q)^{n+r} that is (i) totally random in the affine terms, and (ii) has a negligible chance of being not strongly one-way, provides a secure PRNG (hence a secure stream cipher) for any q. Plausible choices for are semi-sparse (i.e., the affine terms are truly random) systems and other systems that are easy to evaluate from a small (compared to a generic map) number of parameters. To our knowledge, there are no other positive results for provable security of specialized polynomial systems, in particular sparse ones (which are natural candidates to investigate for speed). We can build a family of provably secure stream ciphers a rough implementation of which at the same security level can be more than twice faster than an optimized QUAD (and any other provably secure stream ciphers proposed so far), and uses much less storage. This may also help build faster provably secure hashes. We also examine the effects of recent results on specialization on security, e.g., Aumasson-Meier (ICISC 2007), which precludes Merkle-Damgaard compression using polynomials systems {uniformly very sparse in every degree} from being universally collision-free. We conclude that our ideas are consistent with and complements these new results. We think that we can build secure primitives based on specialized (versus generic) polynomial maps which are more efficient.

In 2006, Nie et al proposed an attack to break an instance of TTM cryptosystems. However, the inventor of TTM disputed this attack and he proposed two new instances of TTM to support his viewpoint. At this time, he did not give the detail of key construction --- the construction of the lock polynomials in these instances which would be used in decryption. The two instances are claimed to achieve a security of 2^{109} against Nie et al attack. In this paper, we show that these instances are both still insecure, and in fact, they do not achieve a better design in the sense that we can find a ciphertext-only attack utilizing the First Order Linearization Equations while for the previous version of TTM, only Second Order Linearization Equations can be used in the beginning stage of the previous attack. Different from previous attacks, we use an iterated linearization method to break these two instances. For any given valid ciphertext, we can find its corresponding plaintext within 2^{31} F_{2^8}-computations after performing once for any public key a computation of complexity less than 2^{44} . Our experiment result shows we have unlocked the lock polynomials after several iterations, though we do not know the detailed construction of lock polynomials.

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.

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 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}.

No abstract uploaded!

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.

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.