Cryptology ePrint Archive: Report 2017/1181

Implementing Joux-Vitse's Crossbred Algorithm for Solving MQ Systems over GF(2) on GPUs

Ruben Niederhagen and Kai-Chun Ning and Bo-Yin Yang

Abstract: The hardness of solving multivariate quadratic (MQ) systems is the underlying problem for multivariate-based schemes in the field of post-quantum cryptography. The concrete, practical hardness of this problem needs to be measured by state-of-the-art algorithms and high-performance implementations. We describe, implement, and evaluate an adaption of the Crossbred algorithm by Joux and Vitse for solving MQ systems over GF(2). Our adapted algorithm is highly parallelizable and is suitable for solving MQ systems on GPU architectures. Our implementation is able to solve an MQ system of 134 equations in 67 variables in 98.39 hours using one single commercial Nvidia GTX 980 graphics card, while the original Joux-Vitse algorithm requires 6200 CPU-hours for the same problem size. We used our implementation to solve all the Fukuoka Type-I MQ challenges for n = 55,...,74. Based on our implementation, we estimate that the expected computation time for solving an MQ system of 80 equations in 84 variables is about one year using a cluster of 3647 GTX 980 graphics cards. These parameters have been proposed for 80-bit security by, e.g., Sakumoto, Shirai, and Hiwatari in 2011.

Category / Keywords: implementation / Post-quantum cryptography, multivariate quadratic systems, parallel implementation, GPU.

Date: received 4 Dec 2017

Contact author: ruben at polycephaly org

Available format(s): PDF | BibTeX Citation

Version: 20171208:180145 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]