Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Johannes Buchmann , Daniel Cabarcas , Jintai Ding , Mohamed Saied Emam Mohamed

ABSTRACT

Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic applications. In this paper we present a strategy for computing Gröbner basis that challenges those complexity estimates. It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements–mutants. This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gröbner basis computation. The new proposed algorithm computed a Gröbner basis of a degree 2 random system with 32 variables and 32 equations using 30 GB which was never done before by any known Gröbner bases solver. More... »

PAGES

69-81

References to SciGraph publications

Book

TITLE

Progress in Cryptology – AFRICACRYPT 2010

ISBN

978-3-642-12677-2
978-3-642-12678-9

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-12678-9_5

DOI

http://dx.doi.org/10.1007/978-3-642-12678-9_5

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Technical University of Darmstadt", 
          "id": "https://www.grid.ac/institutes/grid.6546.1", 
          "name": [
            "FB Informatik, TU Darmstadt, 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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati", 
          "id": "https://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cabarcas", 
        "givenName": "Daniel", 
        "id": "sg:person.015423657271.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423657271.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, South China University of Technology"
          ], 
          "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": [
            "FB Informatik, TU Darmstadt, 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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-88403-3_14", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000585614", 
          "https://doi.org/10.1007/978-3-540-88403-3_14"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040947089"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041918753", 
          "https://doi.org/10.1007/978-3-642-14423-3_7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14423-3_7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041918753", 
          "https://doi.org/10.1007/978-3-642-14423-3_7"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic applications. In this paper we present a strategy for computing Gr\u00f6bner basis that challenges those complexity estimates. It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements\u2013mutants. This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gr\u00f6bner basis computation. The new proposed algorithm computed a Gr\u00f6bner basis of a degree 2 random system with 32 variables and 32 equations using 30 GB which was never done before by any known Gr\u00f6bner bases solver.", 
    "editor": [
      {
        "familyName": "Bernstein", 
        "givenName": "Daniel J.", 
        "type": "Person"
      }, 
      {
        "familyName": "Lange", 
        "givenName": "Tanja", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-12678-9_5", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-12677-2", 
        "978-3-642-12678-9"
      ], 
      "name": "Progress in Cryptology \u2013 AFRICACRYPT 2010", 
      "type": "Book"
    }, 
    "name": "Flexible Partial Enlargement to Accelerate Gr\u00f6bner Basis Computation over", 
    "pagination": "69-81", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1017552658"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-12678-9_5"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "53a0bbe8a4667bd28cda48d679bc51c810407303c2adac3f40858d8e9f72d0be"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-12678-9_5", 
      "https://app.dimensions.ai/details/publication/pub.1017552658"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T07:38", 
    "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/0000000357_0000000357/records_99328_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-12678-9_5"
  }
]
 

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-642-12678-9_5'

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-642-12678-9_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-12678-9_5'

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-642-12678-9_5'


 

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

107 TRIPLES      23 PREDICATES      30 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-12678-9_5 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nff1ca36d962d44d18ebc5c5ff2518424
4 schema:citation sg:pub.10.1007/978-3-540-88403-3_14
5 sg:pub.10.1007/978-3-642-14423-3_7
6 https://doi.org/10.1016/s0022-4049(99)00005-5
7 schema:datePublished 2010
8 schema:datePublishedReg 2010-01-01
9 schema:description Recent developments in multivariate polynomial solving algorithms have made algebraic cryptanalysis a plausible threat to many cryptosystems. However, theoretical complexity estimates have shown this kind of attack unfeasible for most realistic applications. In this paper we present a strategy for computing Gröbner basis that challenges those complexity estimates. It uses a flexible partial enlargement technique together with reduced row echelon forms to generate lower degree elements–mutants. This new strategy surpasses old boundaries and obligates us to think of new paradigms for estimating complexity of Gröbner basis computation. The new proposed algorithm computed a Gröbner basis of a degree 2 random system with 32 variables and 32 equations using 30 GB which was never done before by any known Gröbner bases solver.
10 schema:editor N9d03a071878d437392a69633d8955979
11 schema:genre chapter
12 schema:inLanguage en
13 schema:isAccessibleForFree false
14 schema:isPartOf N3e6b19e599b74d5d9eee10286083c1fc
15 schema:name Flexible Partial Enlargement to Accelerate Gröbner Basis Computation over
16 schema:pagination 69-81
17 schema:productId N7b8a65a5382644bb8351f2e49ffedc4d
18 N99d48026384c4c89ab47e2309e06fa74
19 Ncb69e0d0a7184f6a86d507ed9eadafdf
20 schema:publisher Nda09c50edd1d46689b48d12bd01c47b5
21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017552658
22 https://doi.org/10.1007/978-3-642-12678-9_5
23 schema:sdDatePublished 2019-04-16T07:38
24 schema:sdLicense https://scigraph.springernature.com/explorer/license/
25 schema:sdPublisher N4ed9784d2d0f405f80f8f0ca953904a3
26 schema:url https://link.springer.com/10.1007%2F978-3-642-12678-9_5
27 sgo:license sg:explorer/license/
28 sgo:sdDataset chapters
29 rdf:type schema:Chapter
30 N0a6a7294c5e443b3bd89330cbe68f1bd schema:name Department of Mathematical Sciences, University of Cincinnati, South China University of Technology
31 rdf:type schema:Organization
32 N1a47dc3fa05f4fe59e7f61a86488df4d schema:familyName Bernstein
33 schema:givenName Daniel J.
34 rdf:type schema:Person
35 N3e6b19e599b74d5d9eee10286083c1fc schema:isbn 978-3-642-12677-2
36 978-3-642-12678-9
37 schema:name Progress in Cryptology – AFRICACRYPT 2010
38 rdf:type schema:Book
39 N4ed9784d2d0f405f80f8f0ca953904a3 schema:name Springer Nature - SN SciGraph project
40 rdf:type schema:Organization
41 N7b8a65a5382644bb8351f2e49ffedc4d schema:name doi
42 schema:value 10.1007/978-3-642-12678-9_5
43 rdf:type schema:PropertyValue
44 N99d48026384c4c89ab47e2309e06fa74 schema:name readcube_id
45 schema:value 53a0bbe8a4667bd28cda48d679bc51c810407303c2adac3f40858d8e9f72d0be
46 rdf:type schema:PropertyValue
47 N9d03a071878d437392a69633d8955979 rdf:first N1a47dc3fa05f4fe59e7f61a86488df4d
48 rdf:rest Naae80b3a88a34d718d170c42937398e8
49 Naae80b3a88a34d718d170c42937398e8 rdf:first Naf919f61dfc747e2b68df5805d71a47b
50 rdf:rest rdf:nil
51 Naf919f61dfc747e2b68df5805d71a47b schema:familyName Lange
52 schema:givenName Tanja
53 rdf:type schema:Person
54 Nb35d2c1d5a184567bf155b8393803b30 rdf:first sg:person.010070273144.20
55 rdf:rest rdf:nil
56 Nb71f4af9041544f3939f2bba1f295673 rdf:first sg:person.015423657271.68
57 rdf:rest Nd5f2919ee17f45498b95674e14da470b
58 Ncb69e0d0a7184f6a86d507ed9eadafdf schema:name dimensions_id
59 schema:value pub.1017552658
60 rdf:type schema:PropertyValue
61 Nd5f2919ee17f45498b95674e14da470b rdf:first sg:person.010723403013.04
62 rdf:rest Nb35d2c1d5a184567bf155b8393803b30
63 Nda09c50edd1d46689b48d12bd01c47b5 schema:location Berlin, Heidelberg
64 schema:name Springer Berlin Heidelberg
65 rdf:type schema:Organisation
66 Nff1ca36d962d44d18ebc5c5ff2518424 rdf:first sg:person.016400723075.52
67 rdf:rest Nb71f4af9041544f3939f2bba1f295673
68 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
69 schema:name Information and Computing Sciences
70 rdf:type schema:DefinedTerm
71 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
72 schema:name Computation Theory and Mathematics
73 rdf:type schema:DefinedTerm
74 sg:person.010070273144.20 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
75 schema:familyName Mohamed
76 schema:givenName Mohamed Saied Emam
77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010070273144.20
78 rdf:type schema:Person
79 sg:person.010723403013.04 schema:affiliation N0a6a7294c5e443b3bd89330cbe68f1bd
80 schema:familyName Ding
81 schema:givenName Jintai
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
83 rdf:type schema:Person
84 sg:person.015423657271.68 schema:affiliation https://www.grid.ac/institutes/grid.24827.3b
85 schema:familyName Cabarcas
86 schema:givenName Daniel
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015423657271.68
88 rdf:type schema:Person
89 sg:person.016400723075.52 schema:affiliation https://www.grid.ac/institutes/grid.6546.1
90 schema:familyName Buchmann
91 schema:givenName Johannes
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016400723075.52
93 rdf:type schema:Person
94 sg:pub.10.1007/978-3-540-88403-3_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000585614
95 https://doi.org/10.1007/978-3-540-88403-3_14
96 rdf:type schema:CreativeWork
97 sg:pub.10.1007/978-3-642-14423-3_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041918753
98 https://doi.org/10.1007/978-3-642-14423-3_7
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
101 rdf:type schema:CreativeWork
102 https://www.grid.ac/institutes/grid.24827.3b schema:alternateName University of Cincinnati
103 schema:name Department of Mathematical Sciences, University of Cincinnati
104 rdf:type schema:Organization
105 https://www.grid.ac/institutes/grid.6546.1 schema:alternateName Technical University of Darmstadt
106 schema:name FB Informatik, TU Darmstadt, Hochschulstrasse 10, 64289, Darmstadt, Germany
107 rdf:type schema:Organization
 




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


...