Loading...
Please wait, while we are loading the content...
Similar Documents
Evaluating Solving Time of Multivariate Quadratic Equation System using XL Algorithm over Small Finite Fields
| Content Provider | Semantic Scholar |
|---|---|
| Author | Tanaka, Satoshi Cheng, Chen-Mou Sakurai, Kouichi |
| Copyright Year | 2014 |
| Abstract | The security of multivariate public-key system is based on the problem of solving multivariate quadratic equation systems over finite fields (MQ problem). The XL (eXtended Linearization) is a aolving algorithm of MQ problem, and its running time is an important index of the complexity of MQ problem. In this work, we provide parallelized XL-Wiedeman algorithm on Graphics Processing Units (GPU). Our implementations solve MQ of 37 unknowns and 74 equations over GF(2) in 36,972 seconds, of 24 unknowns and 48 equations over GF(3) in 933 seconds, and of 21 unknowns and 42 equations over GF(5) in 347 seconds. Computer Security Symposium 2014 22 24 October 2014 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | https://ipsj.ixsq.nii.ac.jp/ej/index.php?action=pages_view_main&active_action=repository_action_common_download&attribute_id=1&block_id=8&file_no=1&item_id=106540&item_no=1&page_id=13 |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |