Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F2on GPUs

Ruben Niederhagen; Kai Chun Ning; Bo Yin Yang

doi:10.1007/978-3-319-79063-3_6

Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs

Ruben Niederhagen, Kai Chun Ning, Bo Yin Yang

Mathematics and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

7 Citations (Scopus)

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 F₂. 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.

Original language	English
Title of host publication	Post-Quantum Cryptography
Subtitle of host publication	9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings
Editors	T. Lange, R. Steinwandt
Place of Publication	Dordrecht
Publisher	Springer
Pages	121-141
Number of pages	21
ISBN (Electronic)	978-3-319-79063-3
ISBN (Print)	978-3-319-79062-6
DOIs	https://doi.org/10.1007/978-3-319-79063-3_6
Publication status	Published - 1 Jan 2018
Event	Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018 - Fort Lauderdale, United States Duration: 9 Apr 2018 → 11 Apr 2018 Conference number: 9

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10786 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Post-Quantum Cryptography
Abbreviated title	PQCrypto 2018
Country/Territory	United States
City	Fort Lauderdale
Period	9/04/18 → 11/04/18

Funding

Acknowledgments. We would like to thank Daniel J. Bernstein for granting us access to his Saber GPU clusters at Eindhoven University of Technology and the University of Illinois at Chicago. This research was partially supported by the project MOST105-2923-E-001-003-MY3 of the Ministry of Science and Technology, Taiwan.

Keywords

GPU
Multivariate quadratic systems
Parallel implementation
Post-quantum cryptography

Access to Document

10.1007/978-3-319-79063-3_6

Cite this

Niederhagen, R., Ning, K. C., & Yang, B. Y. (2018). Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs. In T. Lange, & R. Steinwandt (Eds.), Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings (pp. 121-141). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS). Springer. https://doi.org/10.1007/978-3-319-79063-3_6

Niederhagen, Ruben ; Ning, Kai Chun ; Yang, Bo Yin. / Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs. Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. editor / T. Lange ; R. Steinwandt. Dordrecht : Springer, 2018. pp. 121-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{8190263ef1ac4c1389dd91e9f404e95b,

title = "Implementing joux-vitse{\textquoteright}s crossbred algorithm for solving MQ Systems over F2on GPUs",

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 F2. 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.",

keywords = "GPU, Multivariate quadratic systems, Parallel implementation, Post-quantum cryptography",

author = "Ruben Niederhagen and Ning, {Kai Chun} and Yang, {Bo Yin}",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-319-79063-3_6",

language = "English",

isbn = "978-3-319-79062-6",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "121--141",

editor = "T. Lange and R. Steinwandt",

booktitle = "Post-Quantum Cryptography",

address = "Germany",

note = "Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, PQCrypto 2018 ; Conference date: 09-04-2018 Through 11-04-2018",

}

Niederhagen, R, Ning, KC & Yang, BY 2018, Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs. in T Lange & R Steinwandt (eds), Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10786 LNCS, Springer, Dordrecht, pp. 121-141, Post-Quantum Cryptography , Fort Lauderdale, Florida, United States, 9/04/18. https://doi.org/10.1007/978-3-319-79063-3_6

Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs. / Niederhagen, Ruben; Ning, Kai Chun; Yang, Bo Yin.
Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. ed. / T. Lange; R. Steinwandt. Dordrecht: Springer, 2018. p. 121-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F2on GPUs

AU - Niederhagen, Ruben

AU - Ning, Kai Chun

AU - Yang, Bo Yin

N1 - Conference code: 9

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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 F2. 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.

AB - 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 F2. 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.

KW - GPU

KW - Multivariate quadratic systems

KW - Parallel implementation

KW - Post-quantum cryptography

UR - http://www.scopus.com/inward/record.url?scp=85045397203&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-79063-3_6

DO - 10.1007/978-3-319-79063-3_6

M3 - Conference contribution

AN - SCOPUS:85045397203

SN - 978-3-319-79062-6

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 121

EP - 141

BT - Post-Quantum Cryptography

A2 - Lange, T.

A2 - Steinwandt, R.

PB - Springer

CY - Dordrecht

T2 - Post-Quantum Cryptography

Y2 - 9 April 2018 through 11 April 2018

ER -

Niederhagen R, Ning KC, Yang BY. Implementing joux-vitse’s crossbred algorithm for solving MQ Systems over F₂on GPUs. In Lange T, Steinwandt R, editors, Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. Dordrecht: Springer. 2018. p. 121-141. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-79063-3_6