MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy

Mohamed Saied Emam Mohamed TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany Wael Said Abd Elmageed Mohamed TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany Jintai Ding Department of Mathematical Sciences, University of Cincinnati, Cincinnati OH 45220, USA Johannes Buchmann TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289 Darmstadt, Germany

TBD mathscidoc:2207.43032

PQCrypto 2008, 203-215, 2008.10
MutantXL is an algorithm for solving systems of polynomial equations that was proposed at SCC 2008. This paper proposes two substantial improvements to this algorithm over GF(2) that result in significantly reduced memory usage. We present experimental results comparing MXL2 to the XL algorithm, the MutantXL algorithm and Magma’s implementation of F_4. For this comparison we have chosen small, randomly generated instances of the MQ problem and quadratic systems derived from HFE instances. In both cases, the largest matrices produced by MXL2 are substantially smaller than the ones produced by MutantXL and XL. Moreover, for a significant number of cases we even see a reduction of the size of the largest matrix when we compare MXL2 against Magma’s F_4 implementation.
No keywords uploaded!
[ Download ] [ 2022-07-12 09:59:47 uploaded by dingjt ] [ 265 downloads ] [ 0 comments ]
@inproceedings{mohamed2008mxl2:,
  title={MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy},
  author={Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding, and Johannes Buchmann},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220712095947439564609},
  booktitle={PQCrypto 2008},
  pages={203-215},
  year={2008},
}
Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding, and Johannes Buchmann. MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy. 2008. In PQCrypto 2008. pp.203-215. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20220712095947439564609.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved