How to participate

To participate in the MQ challenge, please look at the instructions below.

  1. There are six types of MQ challenge based on coefficient field F, number of variables n and number of equations m. We offer several different challenges for the same parameter n generated by different seeds (numbered 0, 1, 2, 3, 4).
    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)
    Choose the type and the parameter n of the challenges to solve.
  2. Download the input file of the challenges by clicking the type and the parameter n and the seed in the download corner. One can choose several challenges with the same number of variables n using different seeds (numbered 0, 1, 2, 3, 4).
  3. Solve the challenge using your own program. Please read carefully the format example. We also provide the magma code for reading MQ challenges.
  4. If you solve the MQ challenge, please submit it through the submission page.

According to our policy, we do not encourage people or teams to solve more than two challenges of the same number of variables n using different seeds. If you have solved one instance, please try the harder challenges.

We hope every one will have fun in this MQ challenge project.

Coefficient Verifier

The coefficients of the challenges are generated from the digits of PI. We provide two kinds of coefficient verifier to let participants check the correctness of the downloaded challenges. For encryption scheme (Type I, Type II, Type III), the encryption coefficient verifier can check all the coefficients except the constant term, which is generated by the secret answer of MQ challenge team. For signature scheme (Type IV, Type V, Type VI), the signature coefficient verifier can check all the coefficients including the constant terms.

Policy and Rules

Welcome to the Fukuoka MQ challenge project. 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.