Cryptanalysis of the Bisectional MQ Equations System

The security of many recently proposed cryptosystems is mainly based on the difficulty of solving large multivariate quadratic equations systems. Apart from UOV schemes with proper parameter values, the basic types of these schemes can be broken without great difficulty. Moreover, there are some shortages lying in some of these examined schemes. This paper proposes a bisectional multivariate quadratic equation (BMQE) system over a finite field of degree q (denoted as F_q). The BMQE system is analyzed by Kipnis & Shamir´s relinearization, and it is shown that the number of the variables n, together with the number of the equations m and the number of the degree q of F_q, have a great impact on the complexity of the BMQE system. If they are properly set, relinearization cannot be used to solve this system.