Multivariate public key cryptosystem (MPKC) is one of the major post quantum cryptosystems (PQC), and the National Institute of Standards and Technology (NIST) recently selected four MPKCs as candidates of their PQC. The security of MPKC depends on the hardness of solving systems of algebraic equations over finite fields. In particular, the multivariate quadratic (MQ) problem is that of solving such a system consisting of quadratic polynomials and is regarded as an important research subject in cryptography. In the Fukuoka MQ challenge project, the hardness of the MQ problem is discussed, and algorithms for solving the MQ problem and the computational results obtained by these algorithms are reported. Algorithms for computing Gröbner basis are used as the main tools for solving the MQ problem. For example, the F4 algorithm and M4GB algorithm have succeeded in solving many instances of the MQ problem provided by the project. In this paper, based on the F4-style algorithm, we present an efficient algorithm to solve the MQ problems with dense polynomials generated in the Fukuoka MQ challenge project. We experimentally show that our algorithm requires less computational time and memory for these MQ problems than the F4 algorithm and M4GB algorithm. We succeeded in solving Type II and III problems of Fukuoka MQ challenge using our algorithm when the number of variables was 37 in both problems.

The MQ problem, which consists of solving a system of multivariate quadratic polynomials over a finite field, has attracted the attention of researchers for the development of public-key cryptosystems because (1) it is NP-complete, (2) there is no known polynomial-time algorithm for its solution, even in the quantum computational model, and (3) it enables cryptographic primitives of practical interest. In 2011, Sakumoto, Shirai and Hiwatari presented two new zero-knowledge identification protocols based exclusively on the MQ problem. The 3-pass identification protocol of Sakumoto et al. has impersonation probability 2/3. In this paper, we propose an improvement that reduces the impersonation probability to 1/2. The result is a protocol that reduces the total computation time, the total communication needed and requires a smaller number of rounds for the same security level. We also present a new extension that achieves an additional communication reduction with the use of some smaller hash commitments, but maintaining the same security level.