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

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

Paper 2017/1181

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

Ruben Niederhagen, 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.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published elsewhere. PQCrypto 2018
Keywords: Post-quantum cryptography multivariate quadratic systems parallel implementation GPU.
Contact author(s): ruben @ polycephaly org
History: 2018-02-12: last of 2 revisions; 2017-12-08: received; See all versions
Short URL: https://ia.cr/2017/1181
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1181,
      author = {Ruben Niederhagen and Kai-Chun Ning and Bo-Yin Yang},
      title = {Implementing Joux-Vitse's Crossbred Algorithm for Solving {MQ} Systems over {GF}(2) on {GPUs}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1181},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1181}
}