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


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2008

AUTHORS

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

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 F4. 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 F4 implementation. More... »

PAGES

203-215

Book

TITLE

Post-Quantum Cryptography

ISBN

978-3-540-88402-6
978-3-540-88403-3

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14

DOI

http://dx.doi.org/10.1007/978-3-540-88403-3_14

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1000585614


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohamed", 
        "givenName": "Mohamed Saied Emam", 
        "id": "sg:person.010070273144.20", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mohamed", 
        "givenName": "Wael Said Abd Elmageed", 
        "id": "sg:person.013634073236.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati", 
          "id": "https://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, OH 45220, Cincinnati, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ding", 
        "givenName": "Jintai", 
        "id": "sg:person.010723403013.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Buchmann", 
        "givenName": "Johannes", 
        "id": "sg:person.016400723075.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-45539-6_27", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000285811", 
          "https://doi.org/10.1007/3-540-45539-6_27"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/00927879908826559", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008867318"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-24632-9_22", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028117877", 
          "https://doi.org/10.1007/978-3-540-24632-9_22"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45961-8_39", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035601256", 
          "https://doi.org/10.1007/3-540-45961-8_39"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49649-1_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038271412", 
          "https://doi.org/10.1007/3-540-49649-1_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-49649-1_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038271412", 
          "https://doi.org/10.1007/3-540-49649-1_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2008", 
    "datePublishedReg": "2008-01-01", 
    "description": "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\u2019s implementation of F4. 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\u2019s F4 implementation.", 
    "editor": [
      {
        "familyName": "Buchmann", 
        "givenName": "Johannes", 
        "type": "Person"
      }, 
      {
        "familyName": "Ding", 
        "givenName": "Jintai", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-88402-6", 
        "978-3-540-88403-3"
      ], 
      "name": "Post-Quantum Cryptography", 
      "type": "Book"
    }, 
    "name": "MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy", 
    "pagination": "203-215", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-88403-3_14"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "02c9e6fde289aa84375e24f5211970256bd76bd846c543bb1ec558f583a3101b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000585614"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-88403-3_14", 
      "https://app.dimensions.ai/details/publication/pub.1000585614"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T06:11", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000350_0000000350/records_77581_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-88403-3_14"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-88403-3_14'


 

This table displays all metadata directly associated to this object as RDF triples.

117 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-88403-3_14 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N9bafa354c3ec4e2c948875df4f0dcd79
4 schema:citation sg:pub.10.1007/3-540-45539-6_27
5 sg:pub.10.1007/3-540-45961-8_39
6 sg:pub.10.1007/3-540-49649-1_4
7 sg:pub.10.1007/3-540-68339-9_4
8 sg:pub.10.1007/978-3-540-24632-9_22
9 https://doi.org/10.1080/00927879908826559
10 schema:datePublished 2008
11 schema:datePublishedReg 2008-01-01
12 schema:description 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 F4. 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 F4 implementation.
13 schema:editor Ne02fc9adddf6430eb640e47d14b8c5f8
14 schema:genre chapter
15 schema:inLanguage en
16 schema:isAccessibleForFree true
17 schema:isPartOf N97598a2823cc4a0c912b6b3e283f27f7
18 schema:name MXL2: Solving Polynomial Equations over GF(2) Using an Improved Mutant Strategy
19 schema:pagination 203-215
20 schema:productId Na1ef4a43779f4a399156f1567c946d4e
21 Ncac6fb35af624477b12834e4a2ece926
22 Nd502c12769504aa5be184da70b8c1edf
23 schema:publisher N83e3aaee15ae4321adc4430dfeddbb39
24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
25 https://doi.org/10.1007/978-3-540-88403-3_14
26 schema:sdDatePublished 2019-04-16T06:11
27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
28 schema:sdPublisher N8052ca20418942219bfb7725011c88af
29 schema:url https://link.springer.com/10.1007%2F978-3-540-88403-3_14
30 sgo:license sg:explorer/license/
31 sgo:sdDataset chapters
32 rdf:type schema:Chapter
33 N023807b41336451dbe02dc6226c3a614 schema:familyName Buchmann
34 schema:givenName Johannes
35 rdf:type schema:Person
36 N802237885e944936ac849b2e505b7d6e rdf:first sg:person.016400723075.52
37 rdf:rest rdf:nil
38 N8052ca20418942219bfb7725011c88af schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N83e3aaee15ae4321adc4430dfeddbb39 schema:location Berlin, Heidelberg
41 schema:name Springer Berlin Heidelberg
42 rdf:type schema:Organisation
43 N97598a2823cc4a0c912b6b3e283f27f7 schema:isbn 978-3-540-88402-6
44 978-3-540-88403-3
45 schema:name Post-Quantum Cryptography
46 rdf:type schema:Book
47 N9bafa354c3ec4e2c948875df4f0dcd79 rdf:first sg:person.010070273144.20
48 rdf:rest Nd8b7713a3e8b4bad83005ec4924ddc41
49 Na1ef4a43779f4a399156f1567c946d4e schema:name doi
50 schema:value 10.1007/978-3-540-88403-3_14
51 rdf:type schema:PropertyValue
52 Nad92fd2c22384ffab9d19f0b9446d41d schema:familyName Ding
53 schema:givenName Jintai
54 rdf:type schema:Person
55 Ncac6fb35af624477b12834e4a2ece926 schema:name dimensions_id
56 schema:value pub.1000585614
57 rdf:type schema:PropertyValue
58 Nd0beafc3832c4afd988f72314638e39a rdf:first Nad92fd2c22384ffab9d19f0b9446d41d
59 rdf:rest rdf:nil
60 Nd502c12769504aa5be184da70b8c1edf schema:name readcube_id
61 schema:value 02c9e6fde289aa84375e24f5211970256bd76bd846c543bb1ec558f583a3101b
62 rdf:type schema:PropertyValue
63 Nd8b7713a3e8b4bad83005ec4924ddc41 rdf:first sg:person.013634073236.45
64 rdf:rest Nf4b28ae0b9514527b4b3e612359edbfb
65 Ne02fc9adddf6430eb640e47d14b8c5f8 rdf:first N023807b41336451dbe02dc6226c3a614
66 rdf:rest Nd0beafc3832c4afd988f72314638e39a
67 Nf4b28ae0b9514527b4b3e612359edbfb rdf:first sg:person.010723403013.04
68 rdf:rest N802237885e944936ac849b2e505b7d6e
69 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
70 schema:name Mathematical Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
73 schema:name Pure Mathematics
74 rdf:type schema:DefinedTerm
75 sg:person.010070273144.20 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
76 schema:familyName Mohamed
77 schema:givenName Mohamed Saied Emam
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20
79 rdf:type schema:Person
80 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
81 schema:familyName Ding
82 schema:givenName Jintai
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
84 rdf:type schema:Person
85 sg:person.013634073236.45 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
86 schema:familyName Mohamed
87 schema:givenName Wael Said Abd Elmageed
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013634073236.45
89 rdf:type schema:Person
90 sg:person.016400723075.52 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
91 schema:familyName Buchmann
92 schema:givenName Johannes
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52
94 rdf:type schema:Person
95 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
96 https://doi.org/10.1007/3-540-45539-6_27
97 rdf:type schema:CreativeWork
98 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
99 https://doi.org/10.1007/3-540-45961-8_39
100 rdf:type schema:CreativeWork
101 sg:pub.10.1007/3-540-49649-1_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038271412
102 https://doi.org/10.1007/3-540-49649-1_4
103 rdf:type schema:CreativeWork
104 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
105 https://doi.org/10.1007/3-540-68339-9_4
106 rdf:type schema:CreativeWork
107 sg:pub.10.1007/978-3-540-24632-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028117877
108 https://doi.org/10.1007/978-3-540-24632-9_22
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1080/00927879908826559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008867318
111 rdf:type schema:CreativeWork
112 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
113 schema:name Department of Mathematical Sciences, University of Cincinnati, OH 45220, Cincinnati, USA
114 rdf:type schema:Organization
115 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
116 schema:name TU Darmstadt, FB Informatik, Hochschulstrasse 10, 64289, Darmstadt, Germany
117 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...