News

2023/11/14
Type VI of n=33 and m=22 was solved by Kosuke Sakata and Tsuyoshi Takagi.

2023/10/23
Type VI of n=31 and m=21 was solved by Kosuke Sakata and Tsuyoshi Takagi.

2023/09/16
Type I of n=83 and m=166 was solved by Charles Bouillaguet and Julia Sauvage.

2023/08/22
Type V of n=30 and m=20 was solved by Ting Li and Yao Sun.

2023/07/10
Type V of n=25 and m=17 was solved by Ziyu Zhao and Jintai Ding.

2023/07/09
Type V of n=24 and m=16 was solved by Ziyu Zhao and Jintai Ding.

Introduction

Welcome to the Fukuoka MQ challenge project.

Multivariate Quadratic polynomial (MQ) problem is the basis of security for potentially post-quantum crypto systems. The hardness of solving MQ problem depends on a number of parameters, most importantly the number of variables, as well as the number of equations, the size of the base field etc.

MQ Challenge:

For quadratic polynomials fi (i=1,2,...,m) of n variables over a finite field F, consider the following polynomial system:

equations

The goal is to find an answer v=[v1,…,vn] in Fn of the above system.
In this challenge, we build up six types of systems: three of them are related to an encryption scheme with three different base fields, and other three are related to a signature scheme.

Type I: Encryption, m=2n, F=GF(2)
Type II: Encryption, m=2n, F=GF(28)
Type III: Encryption, m=2n, F=GF(31)
Type IV: Signature, n≈1.5m, F=GF(2)
Type V: Signature, n≈1.5m, F=GF(28)
Type VI: Signature, n≈1.5m, F=GF(31)

You are welcome to download and solve any challenge and submit the answer to us. We would be glad to see harder problems with larger parameters to be solved. We invite you sincerely to join this challenge and leave your name in the hall of fame.

Reference:
Takanori Yasuda, Xavier Dahan, Yun-Ju Huang, Tsuyoshi Takagi and Kouichi Sakurai,
"MQ Challenge: Hardness Evaluation of Solving Multivariate Quadratic Problems",
presented at the NIST Workshop on Cybersecurity in a Post-Quantum World held in Washington, D.C. on April 2-3, 2015.

Hall of Fame

  • Type I
  • Type II
  • Type III
  • Type IV
  • Type V
  • Type VI
  Number of
Variables (n)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
83 0 2023/09/16 Charles Bouillaguet and Julia Sauvage https://gitlab.lip6.fr/almasty/hpXbred, 3488 AMD EPYC 7J13 cores on the Oracle public cloud Details
80 0 2023/07/07 Charles Bouillaguet and Julia Sauvage https://gitlab.lip6.fr/almasty/hpXbred, 2048 AMD EPYC 7J13 cores on the Oracle public cloud Details
77 0 2023/06/26 Charles Bouillaguet and Julia Sauvage https://gitlab.lip6.fr/almasty/hpXbred, 1024 AMD EPYC 7J13 cores on the Oracle public cloud Details
76 0 2023/06/24 Charles Bouillaguet and Julia Sauvage https://gitlab.lip6.fr/almasty/hpXbred, 1024 AMD EPYC 7J13 cores on the Oracle public cloud Details
75 0 2023/06/20 Charles Bouillaguet and Julia Sauvage https://gitlab.lip6.fr/almasty/hpXbred, 1024 AMD EPYC 7J13 cores on the Oracle public cloud Details
  Number of
Variables (n)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
37 2 2019/04/10 Takuma Ito, Naoyuki Shinohara, Shigenori Uchiyama F4-style based algorithm to solve MQ problems, 4 x Intel(R) Xeon(R) CPU E5-4669 v4, 2.20GHz, 1TB RAM Details
36 0 2019/04/10 Takuma Ito, Naoyuki Shinohara, Shigenori Uchiyama F4-style based algorithm to solve MQ problems, 4 x Intel(R) Xeon(R) CPU E5-4669 v4, 2.20GHz, 1TB RAM Details
35 2 2016/09/09 Takuma Ito, Shigenori Uchiyama modified F4 algorithm, Intel(R) Xeon(R) CPU E5-2620 v4, 2.10GHz, 256GB RAM Details
Ex. 20 0 2015/3/20 Yun-Ju Huang Magma F4, Intel(R) Xeon(R) CPU E5-4617, 2.90GHz, 1T RAM Details
  Number of
Variables (n)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
38 3 2020/08/03 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 2x AMD EPYC 7742 Details
37 1 2019/06/27 Takuma Ito, Naoyuki Shinohara, Shigenori Uchiyama F4-style based algorithm to solve MQ problems, 4 x Intel(R) Xeon(R) CPU E5-4669 v4, 2.20GHz, 1TB RAM Details
37 0 2020/07/03 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 2x AMD EPYC 7742 Details
36 0 2016/07/13 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 4 x AMD Opteron 6282 SE Details
35 0 2015/09/30 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 4 x AMD Opteron 6282 SE Details
  Number of
Equations (m)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
69 0 2020/06/08 Yao Sun, Ting Li Improved Parallel Crossbred, Intel i7 8700 (x 8), GeForce GTX 1080Ti (x 10) Details
68 0 2020/05/17 Yao Sun, Ting Li Improved Parallel Crossbred, Intel i7 8700 (x 8), GeForce GTX 1080Ti (x 10) Details
67 0 2017/11/14 Kai-Chun Ning, Ruben Niederhagen Parallel Crossbred, 54 GPUs in the Saber cluster Details
67 1 2019/11/15 Ximing Fu, Chenhao Wu, Tianshuo Cong, Xiaoyun Wang, Shenghao Yang A new algorithm, A cluster of Intel Xeon @ 2.6 Ghz Details
66 0 2015/07/13 Tung Chou, Ruben Niederhagen, Bo-Yin Yang Gray Code enumeration, Rivyera, 128 Spartan 6 FPGAs Details
  Number of
Equations (m)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
20 0 2023/08/22 Ting Li, Yao Sun 1 x AMD Ryzen Threadripper 3970X, 192GB RAM, 2 x GeForce RTX 3080Ti Details
19 4 2016/05/12 Wen-Ding Li, Yun-An Chang, Ming-Shing Chen, Chen-Mou Cheng, Bo-Yin Yang MiniGB-F4, AMD opteron 6376x4 512GB RAM, AMD opteron 6376x4 512GB RAM Details
19 0 2017/10/25 Rusydi Makarim, Marc Stevens M4GB, 2 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 256GiB RAM Details
18 0 2016/03/11 Rusydi Makarim, Marc Stevens M4GB, 2 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 256GiB RAM Details
18 4 2016/05/06 Wen-Ding Li, Yun-An Chang, Ming-Shing Chen, Chen-Mou Cheng, Bo-Yin Yang MiniGB-F4, Intel(R) Xeon(R) CPU E5620 x 8, Intel(R) Xeon(R) CPU E3-1230 v3, Intel(R) Xeon(R) CPU E3-1245 v3 Details
  Number of
Equations (m)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
22 0 2023/11/14 Kosuke Sakata, Tsuyoshi Takagi F4 based on Hilbert-driven algorithm, MD EPYC 7742, 2TB RAM Details
21 0 2023/10/23 Kosuke Sakata, Tsuyoshi Takagi F4 based on Hilbert-driven algorithm, MD EPYC 7742, 2TB RAM Details
20 0 2017/7/10 Rusydi Makarim, Marc Stevens M4GB, 2 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 256GiB RAM Details
19 0 2016/3/30 Rusydi Makarim, Marc Stevens M4GB, 2 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 256GiB RAM Details
18 0 2016/2/29 Rusydi Makarim, Marc Stevens M4GB, 1 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 128GiB RAM Details

The hall of fame lists the five highest positions for each type of systems based on the rules below. For each number of variables n, several seeds are proposed. A participant can choose a seed until he set a record, in which case she will not be able to set a record with the same number of variables n, even with another seed (see Rule 3 below). Here is the full list of all submission details.

Policy and Rules

The policy of this MQ challenge project is to encourage more people all over the world to join the research on solving the MQ problem as well as to motivate the development of the MQ system solvers. Based on this policy, we set up the following rules for the MQ challenge project.

  1. To encourage the participants, we set up a hall of fame to keep record of participants who could solve a system earlier, as well as for new contributors who could solve harder systems. The one who solved a system with the larger number of variables n will be ranked higher. For participants who solved systems with a same number of variables n (i.e with different seeds) the first one will be ranked higher.
  2. Concerning challenges with the same number of variables n, only the first five instances solved will be recorded. These five instances should be set up with different seeds.
  3. To encourage more participants, we allow the submissions of challenges with the same number of variables n (no matter which seed was used) at most once per participant. If one would like to solve more challenges, one should try to solve systems with a larger number of variables n.
  4. The coefficients of the challenges are generated from the PI digits. For encryption scheme (Type I, Type II, Type III), the MQ challenge team will provide one random answer to make sure the challenges of overdetermined polynomial system have one solution. Hence for, members of MQ challenge team will not participate in solving Type I, Type II and Type III. On the other hand, for signature scheme (Type IV, Type V, Type VI), there are always solutions for underdetermined system. Therefore, the coefficients are all chosen from PI digits, and the MQ challenge team do not know the answers.

Submission

Guide for Participants

Download Challenges

Encryption
(m=2n)

  • Type I
  • Type II
  • Type III

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Signature
(n≈1.5m)

  • Type IV
  • Type V
  • Type VI

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Challenges - seed 0

Challenges - seed 1

Challenges - seed 2

Challenges - seed 3

Challenges - seed 4

Related Links