News

2017/07/10
Type VI of n=30 and m=20 was solved by Rusydi Makarim, Marc Stevens.

2016/12/17
Type I of n=74 and m=148 was solved by Antoine Joux.

2016/12/17
Type I of n=73 and m=146 was solved by Antoine Joux.

2016/12/13
Type I of n=72 and m=144 was solved by Antoine Joux.

2016/12/13
Type I of n=71 and m=142 was solved by Antoine Joux.

2016/12/13
Type I of n=70 and m=140 was solved by Antoine Joux.

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
1 74 0 2016/12/17 Antoine Joux New hybridized XL related algorithm, Heterogeneous cluster of Intel Xeon @ 2.7-3.5 Ghz Details
2 73 0 2016/12/17 Antoine Joux New hybridized XL related algorithm, Heterogeneous cluster of Intel Xeon @ 2.7-3.5 Ghz Details
3 72 0 2016/12/13 Antoine Joux New hybridized XL related algorithm, Heterogeneous cluster of Intel Xeon @ 2.7-3.5 Ghz Details
4 71 0 2016/12/13 Antoine Joux New hybridized XL related algorithm, Heterogeneous cluster of Intel Xeon @ 2.7-3.5 Ghz Details
5 70 0 2016/12/13 Antoine Joux New hybridized XL related algorithm, Heterogeneous cluster of Intel Xeon @ 2.7-3.5 Ghz Details
  Number of
Variables (n)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
1 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
1 36 0 2016/07/13 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 4 x AMD Opteron 6282 SE Details
2 35 0 2015/09/30 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 4 x AMD Opteron 6282 SE Details
3 34 0 2015/08/04 Tung Chou, Ruben Niederhagen, Bo-Yin Yang XL with block Wiedemann, 4 x AMD Opteron 6282 SE Details
4 34 1 2016/08/13 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
Equations (m)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
1 66 0 2015/07/13 Tung Chou, Ruben Niederhagen, Bo-Yin Yang Gray Code enumeration, Rivyera, 128 Spartan 6 FPGAs Details
2 65 0 2015/07/08 Tung Chou, Ruben Niederhagen, Bo-Yin Yang Gray Code enumeration, Rivyera, 128 Spartan 6 FPGAs Details
3 64 0 2015/07/01 Tung Chou, Ruben Niederhagen, Bo-Yin Yang Gray Code enumeration, Rivyera, 128 Spartan 6 FPGAs Details
4 63 0 2015/06/01 Tung Chou, Ruben Niederhagen, Bo-Yin Yang Gray Code enumeration, Rivyera, 128 Spartan 6 FPGAs Details
5 62 0 2015/05/20 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
1 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
2 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
3 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
4 17 0 2016/02/28 Rusydi Makarim, Marc Stevens M4GB, 1 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 128GiB RAM Details
5 16 0 2015/04/03 JC Faugere F5 - FGb, Intel(R) Xeon(R) CPU E5-2670 v2 @ 2.50GHz Details
  Number of
Equations (m)
Seed (0,1,2,3,4) Date Contestants Computational
Resource
Data
1 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
2 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
3 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
4 17 0 2016/2/25 Rusydi Makarim, Marc Stevens M4GB, 1 x Intel(R) Xeon(R) CPU E5-2650 v3 @ 2.30GHz, 128GiB RAM Details
5 16 0 2015/4/1 JC Faugere F5 - FGb, Intel(R) Xeon(R) CPU E5-2670 v2 @ 2.50GHz 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