Multivariate Quadratic Polynomials In Public Key Cryptography

The MFE cryptosystem proposed by Wang et al.[1]is insecure due to HOLEs attackby Ding et al.[2].In this paper we describe an improved MFE cryptosystem,which canresist the HOLEs attack.Meanwhile with well-chosen parameters it can also resist Rankattack and XL & Gr(o|¨)bner basis attack.The TTM cryptosystem is very fast in encryption and decryption due to its designand small underlying field.The success of this system relies on the construction of apolynomial Q_m(y1,…,yt)of degree m≥2 and a set of polynomails{q1,…,qt},all ofwhich have degree 2 in x₁,…,x_s,such that Q_m(q1,…,qt)is a polynomail of degree 2in x₁,…,x_s.We call Q_m(q1,…qt)Q_m-module.Chou et al.gave a systematic way toconstruct Q₂^k-module[3].In this paper we describe an implementation of TTM cryptosystem based on this Q₂^k-module,then with method similar to the one proposed byDing and Hodge[4],we break this implementation.