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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

7 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Post-Quantum Cryptography
Subtitel	9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings
Redacteuren	T. Lange, R. Steinwandt
Plaats van productie	Dordrecht
Uitgeverij	Springer
Pagina's	121-141
Aantal pagina's	21
ISBN van elektronische versie	978-3-319-79063-3
ISBN van geprinte versie	978-3-319-79062-6
DOI's	https://doi.org/10.1007/978-3-319-79063-3_6
Status	Gepubliceerd - 1 jan. 2018
Evenement	Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018 - Fort Lauderdale, Verenigde Staten van Amerika Duur: 9 apr. 2018 → 11 apr. 2018 Congresnummer: 9

Publicatie series

Naam	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10786 LNCS
ISSN van geprinte versie	0302-9743
ISSN van elektronische versie	1611-3349

Congres

Congres	Post-Quantum Cryptography
Verkorte titel	PQCrypto 2018
Land/Regio	Verenigde Staten van Amerika
Stad	Fort Lauderdale
Periode	9/04/18 → 11/04/18

Financiering

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.

Toegang tot document

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

Andere bestanden en links

Link to publication in Scopus

Citeer dit

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 (editors), Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings (blz. 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. redacteur / T. Lange ; R. Steinwandt. Dordrecht : Springer, 2018. blz. 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 (uitgave), 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, blz. 121-141, Post-Quantum Cryptography , Fort Lauderdale, Florida, Verenigde Staten van Amerika, 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. uitgave / T. Lange; R. Steinwandt. Dordrecht: Springer, 2018. blz. 121-141 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10786 LNCS).

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › 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, redacteurs, Post-Quantum Cryptography : 9th International Conference, PQCrypto 2018, Fort Lauderdale, FL, USA, April 9-11, 2018, Proceedings. Dordrecht: Springer. 2018. blz. 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