TY - GEN
T1 - Evaluation of solving time for multivariate quadratic equation system using XL algorithm over small finite fields on GPU
AU - Tanaka, Satoshi
AU - Cheng, Chen Mou
AU - Sakurai, Kouichi
N1 - Funding Information:
This work is partly supported by “Study on Secure Cryptosystem using Multivariate polynomial,” No. 0159-0091, Strategic Information and Communications R&D Promotion Programme (SCOPE), the Ministry of Internal Affairs and Communications, Japan and Grant-in-Aid for Young Scientists (B), Grant number 24740078.
Publisher Copyright:
© Springer India 2015.
PY - 2015
Y1 - 2015
N2 - The security of multivariate public-key cryptography is largely determined by the complexity of solving multivariate quadratic equations over finite fields, a.k.a. the MQ problem. XL (eXtended Linearization) is an efficient algorithm for solving the MQ problem, so its running time is an important indicator for the complexity of solving the MQ problem. In this work, we implement XL on graphics processing unit (GPU) and evaluate its solving time for theMQ problem over several small finite fields, namely, GF(2), GF(3), GF(5), and GF(7). Our implementations can solve MQ instances of 74 equations in 37 unknowns over GF(2) in 36,972 s, 48 equations in 24 unknowns over GF(3) in 933 s, 42 equations in 21 unknowns over GF(5) in 347 s, as well as 42 equations in 21 unknowns over GF(7) in 387 s. Moreover, we can also solve the MQ instance of 48 equations in 24 unknowns over GF(7) in 34,882 s, whose complexity is about O(267) with exhaustive search.
AB - The security of multivariate public-key cryptography is largely determined by the complexity of solving multivariate quadratic equations over finite fields, a.k.a. the MQ problem. XL (eXtended Linearization) is an efficient algorithm for solving the MQ problem, so its running time is an important indicator for the complexity of solving the MQ problem. In this work, we implement XL on graphics processing unit (GPU) and evaluate its solving time for theMQ problem over several small finite fields, namely, GF(2), GF(3), GF(5), and GF(7). Our implementations can solve MQ instances of 74 equations in 37 unknowns over GF(2) in 36,972 s, 48 equations in 24 unknowns over GF(3) in 933 s, 42 equations in 21 unknowns over GF(5) in 347 s, as well as 42 equations in 21 unknowns over GF(7) in 387 s. Moreover, we can also solve the MQ instance of 48 equations in 24 unknowns over GF(7) in 34,882 s, whose complexity is about O(267) with exhaustive search.
UR - http://www.scopus.com/inward/record.url?scp=84947071086&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84947071086&partnerID=8YFLogxK
U2 - 10.1007/978-81-322-2452-5_24
DO - 10.1007/978-81-322-2452-5_24
M3 - Conference contribution
AN - SCOPUS:84947071086
SN - 9788132224518
T3 - Springer Proceedings in Mathematics and Statistics
SP - 349
EP - 361
BT - Mathematics and Computing - ICMC 2015
A2 - Giri, Debasis
A2 - Mohapatra, Ram N.
A2 - Chowdhury, Dipanwita Roy
PB - Springer New York LLC
T2 - 2nd International Conference on Mathematics and Computing, ICMC 2015
Y2 - 5 January 2015 through 10 January 2015
ER -