International Association for Cryptologic Research

International Association
for Cryptologic Research


John Wagner


Cryptanalysis of Rational Multivariate Public Key Cryptosystems
Jintai Ding John Wagner
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\cite{Tsujii-Fujioka:89}. 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 extremely fast to perform the computation to derive an equivalent private key, and it requires only a few seconds on a standard PC.
High Order Linearization Equation (HOLE) Attack on Multivariate Public Key Cryptosystems
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}}$-operations, after performing once for any 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.


Jintai Ding (3)
Lei Hu (2)
Jianyu Li (2)
Xuyun Nie (2)