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 from 2017 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 3600 GTX 980 graphics cards. These parameters have been proposed for 80-bit security by, e.g., Sakumoto, Shirai, and Hiwatari at Crypto 2011.

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

Original Publication (in the same form): PQCrypto 2018

Date: received 4 Dec 2017, last revised 12 Feb 2018

Contact author: ruben at polycephaly org

Available format(s): PDF | BibTeX Citation

Version: 20180212:151832 (All versions of this report)

Short URL: ia.cr/2017/1181

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]