MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy

Mohamed Saied Emam Mohamed; Wael Said Abd Elmageed Mohamed; Jintai Ding; Johannes Buchmann

doi:10.1007/978-3-540-88403-3_14

MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy

Mohamed Saied Emam Mohamed, Wael Said Abd Elmageed Mohamed, Jintai Ding, Johannes Buchmann

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

37 Citations (Scopus)

Abstract

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 ₄. 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 ₄ implementation.

Original language	English
Title of host publication	Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings
Publisher	Springer Verlag
Pages	203-215
Number of pages	13
ISBN (Print)	3540884025, 9783540884026
DOIs	https://doi.org/10.1007/978-3-540-88403-3_14
Publication status	Published - 2008
Externally published	Yes
Event	2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008 - Cincinnati, OH, United States Duration: 17 Oct 2008 → 19 Oct 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5299 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008
Country/Territory	United States
City	Cincinnati, OH
Period	17/10/08 → 19/10/08

Access to Document

10.1007/978-3-540-88403-3_14

Cite this

Mohamed, M. S. E., Mohamed, W. S. A. E., Ding, J., & Buchmann, J. (2008). MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy. In Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings (pp. 203-215). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5299 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-540-88403-3_14

Mohamed, Mohamed Saied Emam ; Mohamed, Wael Said Abd Elmageed ; Ding, Jintai et al. / MXL2 : Solving polynomial equations over GF(2) Using an improved mutant strategy. Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Springer Verlag, 2008. pp. 203-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{620472d694e54b0c9216231b105adfb1,

title = "MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy",

abstract = "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.",

author = "Mohamed, {Mohamed Saied Emam} and Mohamed, {Wael Said Abd Elmageed} and Jintai Ding and Johannes Buchmann",

year = "2008",

doi = "10.1007/978-3-540-88403-3_14",

language = "English",

isbn = "3540884025",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "203--215",

booktitle = "Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings",

note = "2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008 ; Conference date: 17-10-2008 Through 19-10-2008",

}

Mohamed, MSE, Mohamed, WSAE, Ding, J & Buchmann, J 2008, MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy. in Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5299 LNCS, Springer Verlag, pp. 203-215, 2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008, Cincinnati, OH, United States, 17/10/08. https://doi.org/10.1007/978-3-540-88403-3_14

MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy. / Mohamed, Mohamed Saied Emam; Mohamed, Wael Said Abd Elmageed; Ding, Jintai et al.
Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Springer Verlag, 2008. p. 203-215 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5299 LNCS).

Research output: Chapter in Book or Report/Conference proceeding › Conference Proceeding › peer-review

TY - GEN

T1 - MXL2

T2 - 2nd International Workshop on Post-Quantum Cryptography, PQCrypto 2008

AU - Mohamed, Mohamed Saied Emam

AU - Mohamed, Wael Said Abd Elmageed

AU - Ding, Jintai

AU - Buchmann, Johannes

PY - 2008

Y1 - 2008

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=56749170583&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-88403-3_14

DO - 10.1007/978-3-540-88403-3_14

M3 - Conference Proceeding

AN - SCOPUS:56749170583

SN - 3540884025

SN - 9783540884026

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 203

EP - 215

BT - Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings

PB - Springer Verlag

Y2 - 17 October 2008 through 19 October 2008

ER -

Mohamed MSE, Mohamed WSAE, Ding J, Buchmann J. MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy. In Post-Quantum Cryptography - Second International Workshop, PQCrypto 2008, Proceedings. Springer Verlag. 2008. p. 203-215. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-88403-3_14

MXL2: Solving polynomial equations over GF(2) Using an improved mutant strategy

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this