Publica
Hier finden Sie wissenschaftliche Publikationen aus den FraunhoferInstituten. Implementing JouxVitse's crossbred algorithm for solving MQ systems over F2 on GPUs
 Lange, Tanja: PostQuantum Cryptography. 9th International Conference, PQCrypto 2018 : Fort Lauderdale, FL, USA, April 911, 2018, Proceedings Cham: Springer International Publishing, 2018 (Lecture Notes in Computer Science 10786) ISBN: 9783319790626 (Print) ISBN: 9783319790633 (Online) ISBN: 3319790625 pp.121141 
 International Conference on PostQuantum Cryptography (PQCrypto) <9, 2018, Fort Lauderdale/Fla.> 

 English 
 Conference Paper 
 Fraunhofer SIT () 
Abstract
The hardness of solving multivariate quadratic (MQ) systems is the underlying problem for multivariatebased schemes in the field of postquantum cryptography. The concrete, practical hardness of this problem needs to be measured by stateoftheart algorithms and highperformance 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 JouxVitse algorithm requires 6200 CPUhours for the same problem size. We used our implementation to solve all the Fukuoka TypeI 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 80bit security by, e.g., Sakumoto, Shirai, and Hiwatari at Crypto 2011.