Introduction

In April 2015, the Kyushu University and ISIT announced the Fukuoka MQ challenge as a challenge for solving multivariate polynomial systems. The challenge consists of 6 types of random systems, where each type is either overdetermined or underdetermined and over either F2, F31, or F256. In this project we try to solve as many of these systems as possible.

Results

The following table shows the largest systems (with m equations and n variables) we solved by January 22, 2016.

type field m n time machine algorithm
Ⅰ F2 132 66 7 days 19 hours 50 minutes Rivyera, 128 Spartan 6 FPGAs Gray-code enumeration
Ⅲ F31 70 35 48 days 23 hours 32 minutes 4 x AMD Opteron 6282 SE eXtended Linearization (XL)
Ⅳ F2 66 99 3 days 21 hours 9 minutes Rivyera, 128 Spartan 6 FPGAs Gray-code enumeration

Software

An implementation for the Gray-code enumeration algorithm is available here as an extension package for the Sage computer algebra system.
The FPGA code we actually used is available here.

Slides

The slides for the talk at the hot-topic session of PQCrypto 2016 can be found here.

Papers

Fast Exhaustive Search for Quadratic Systems in F2 on FPGAs.
Charles Bouillaguet, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Bo-Yin Yang. SAC 2013. [pdf]

Solving Quadratic Equations with XL on Parallel Architectures.
Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Bo-Yin Yang. CHES 2012. [pdf]

Fast Exhaustive Search for Polynomial Systems in F2.
Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, Bo-Yin Yang. CHES 2010. [pdf]

Contributors