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 cryptographymultivariate quadratic systemsparallel implementationGPU.
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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2017/1181}},
      url = {https://eprint.iacr.org/2017/1181}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.