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
In this project we try to solve as many of these systems as possible.
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|
An implementation for the Gray-code enumeration algorithm is available
as an extension package for the
Sage computer algebra system.
The FPGA code we actually used is available
The slides for the talk at the hot-topic session of PQCrypto 2016 can be found
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]