Comparison Between XL and Gröbner Basis Algorithms View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Gwénolé Ars , Jean-Charles Faugère , Hideki Imai , Mitsuru Kawazoe , Makoto Sugita

ABSTRACT

This paper compares the XL algorithm with known Gröbner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Gröbner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Gröbner basis algorithm which can be represented as a redundant variant of a Gröbner basis algorithm F4. Then we compare these algorithms on semi-regular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields and with q ≫ n. We show that the size of the matrix constructed by XL is large compared to the ones of the F5 algorithm. Finally, we give an experimental study between XL and the Buchberger algorithm on the cryptosystem HFE and find that the Buchberger algorithm has a better behavior. More... »

PAGES

338-353

References to SciGraph publications

  • 2003. Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 2003. Higher Order Correlation Attacks, XL Algorithm and Cryptanalysis of Toyocrypt in INFORMATION SECURITY AND CRYPTOLOGY — ICISC 2002
  • 2003-05-13. Algebraic Attacks on Stream Ciphers with Linear Feedback in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2003
  • 1998. Using Algebraic Geometry in NONE
  • 2001-07-13. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’96
  • 2001. The Security of Hidden Field Equations (HFE) in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • 1995. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 in ADVANCES IN CRYPTOLOGY — CRYPT0’ 95
  • 1999-04-15. Unbalanced Oil and Vinegar Signature Schemes in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’99
  • 1993. Gröbner Bases, A Computational Approach to Commutative Algebra in NONE
  • 2003. Algebraic Attacks on Combiners with Memory in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 2003. Fast Algebraic Attacks on Stream Ciphers with Linear Feedback in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization in ADVANCES IN CRYPTOLOGY — CRYPTO’ 99
  • 1983. Gröbner bases, Gaussian elimination and resolution of systems of algebraic equations in COMPUTER ALGEBRA
  • 2002. Cryptanalysis of Block Ciphers with Overdefined Systems of Equations in ADVANCES IN CRYPTOLOGY — ASIACRYPT 2002
  • 2000. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2000
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-540-30539-2_24

    DOI

    http://dx.doi.org/10.1007/978-3-540-30539-2_24

    DIMENSIONS

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


    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": "Mathematics Research Institute of Rennes", 
              "id": "https://www.grid.ac/institutes/grid.469499.f", 
              "name": [
                "IRMAR, University of Rennes 1, Campus de Beaulieu, 35042, Rennes, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ars", 
            "givenName": "Gw\u00e9nol\u00e9", 
            "id": "sg:person.016233257170.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016233257170.21"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sorbonne University", 
              "id": "https://www.grid.ac/institutes/grid.462844.8", 
              "name": [
                "LIP6/CNRS/INRIA, University of Paris VI, 8 rue du Capitaine Scott Paris, 75015, Paris, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Faug\u00e8re", 
            "givenName": "Jean-Charles", 
            "id": "sg:person.015445232677.54", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015445232677.54"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Tokyo", 
              "id": "https://www.grid.ac/institutes/grid.26999.3d", 
              "name": [
                "Institute of Industrial Science, University of Tokyo, 4-6-1 Komaba, Meguro-ku, 153-8505, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Imai", 
            "givenName": "Hideki", 
            "id": "sg:person.015036512317.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015036512317.70"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Osaka Prefecture University", 
              "id": "https://www.grid.ac/institutes/grid.261455.1", 
              "name": [
                "Department of Mathematics and Information Sciences, Osaka Prefecture University, 1-1 Gakuen-cho, 599-8531, Sakai Osaka, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kawazoe", 
            "givenName": "Mitsuru", 
            "id": "sg:person.015626242511.23", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015626242511.23"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Information-Technology Promotion Agency", 
              "id": "https://www.grid.ac/institutes/grid.469365.b", 
              "name": [
                "IT Security Center, Information-technology Promotion Agency, Japan, 2-28-8 Honkomagome, Bunkyo-ku, 113-6591, Tokyo, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sugita", 
            "givenName": "Makoto", 
            "id": "sg:person.014550535711.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014550535711.45"
            ], 
            "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": "sg:pub.10.1007/3-540-45353-9_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003163768", 
              "https://doi.org/10.1007/3-540-45353-9_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/780506.780516", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007436250"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1011483333", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-6911-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011483333", 
              "https://doi.org/10.1007/978-1-4757-6911-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-6911-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011483333", 
              "https://doi.org/10.1007/978-1-4757-6911-1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://app.dimensions.ai/details/publication/pub.1015138233", 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0913-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015138233", 
              "https://doi.org/10.1007/978-1-4612-0913-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4612-0913-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015138233", 
              "https://doi.org/10.1007/978-1-4612-0913-3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48910-x_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020614953", 
              "https://doi.org/10.1007/3-540-48910-x_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48910-x_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020614953", 
              "https://doi.org/10.1007/3-540-48910-x_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020782332", 
              "https://doi.org/10.1007/978-3-540-45146-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020782332", 
              "https://doi.org/10.1007/978-3-540-45146-4_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jsco.1993.1051", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021494546"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-12868-9_99", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030833923", 
              "https://doi.org/10.1007/3-540-12868-9_99"
            ], 
            "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/3-540-39200-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043854228", 
              "https://doi.org/10.1007/3-540-39200-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39200-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043854228", 
              "https://doi.org/10.1007/3-540-39200-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48405-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045972569", 
              "https://doi.org/10.1007/3-540-48405-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36178-2_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046297994", 
              "https://doi.org/10.1007/3-540-36178-2_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049850905", 
              "https://doi.org/10.1007/978-3-540-45146-4_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049850905", 
              "https://doi.org/10.1007/978-3-540-45146-4_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-36552-4_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049921761", 
              "https://doi.org/10.1007/3-540-36552-4_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44750-4_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051590862", 
              "https://doi.org/10.1007/3-540-44750-4_20"
            ], 
            "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": "2004", 
        "datePublishedReg": "2004-01-01", 
        "description": "This paper compares the XL algorithm with known Gr\u00f6bner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Gr\u00f6bner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Gr\u00f6bner basis algorithm which can be represented as a redundant variant of a Gr\u00f6bner basis algorithm F4. Then we compare these algorithms on semi-regular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields and with q \u226b n. We show that the size of the matrix constructed by XL is large compared to the ones of the F5 algorithm. Finally, we give an experimental study between XL and the Buchberger algorithm on the cryptosystem HFE and find that the Buchberger algorithm has a better behavior.", 
        "editor": [
          {
            "familyName": "Lee", 
            "givenName": "Pil Joong", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-540-30539-2_24", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-23975-8", 
            "978-3-540-30539-2"
          ], 
          "name": "Advances in Cryptology - ASIACRYPT 2004", 
          "type": "Book"
        }, 
        "name": "Comparison Between XL and Gr\u00f6bner Basis Algorithms", 
        "pagination": "338-353", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1006829906"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-540-30539-2_24"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "2088ac939dad86158f3d13cab953015952d4cf5dc4a38093d3157110992b492c"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-540-30539-2_24", 
          "https://app.dimensions.ai/details/publication/pub.1006829906"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:29", 
        "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/0000000356_0000000356/records_57868_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-540-30539-2_24"
      }
    ]
     

    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-30539-2_24'

    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-30539-2_24'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30539-2_24'

    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-30539-2_24'


     

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

    178 TRIPLES      23 PREDICATES      47 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-540-30539-2_24 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4baa0aee84f2424eb9a668136a4daffc
    4 schema:citation sg:pub.10.1007/3-540-12868-9_99
    5 sg:pub.10.1007/3-540-36178-2_17
    6 sg:pub.10.1007/3-540-36552-4_13
    7 sg:pub.10.1007/3-540-39200-9_21
    8 sg:pub.10.1007/3-540-44750-4_20
    9 sg:pub.10.1007/3-540-45353-9_20
    10 sg:pub.10.1007/3-540-45539-6_27
    11 sg:pub.10.1007/3-540-48405-1_2
    12 sg:pub.10.1007/3-540-48910-x_15
    13 sg:pub.10.1007/3-540-68339-9_4
    14 sg:pub.10.1007/978-1-4612-0913-3
    15 sg:pub.10.1007/978-1-4757-6911-1
    16 sg:pub.10.1007/978-3-540-45146-4_10
    17 sg:pub.10.1007/978-3-540-45146-4_11
    18 sg:pub.10.1007/978-3-540-45146-4_3
    19 https://app.dimensions.ai/details/publication/pub.1011483333
    20 https://app.dimensions.ai/details/publication/pub.1015138233
    21 https://doi.org/10.1006/jsco.1993.1051
    22 https://doi.org/10.1016/s0022-4049(99)00005-5
    23 https://doi.org/10.1145/780506.780516
    24 schema:datePublished 2004
    25 schema:datePublishedReg 2004-01-01
    26 schema:description This paper compares the XL algorithm with known Gröbner basis algorithms. We show that to solve a system of algebraic equations via the XL algorithm is equivalent to calculate the reduced Gröbner basis of the ideal associated with the system. Moreover we show that the XL algorithm is also a Gröbner basis algorithm which can be represented as a redundant variant of a Gröbner basis algorithm F4. Then we compare these algorithms on semi-regular sequences, which correspond, in conjecture, to almost all polynomial systems in two cases: over the fields and with q ≫ n. We show that the size of the matrix constructed by XL is large compared to the ones of the F5 algorithm. Finally, we give an experimental study between XL and the Buchberger algorithm on the cryptosystem HFE and find that the Buchberger algorithm has a better behavior.
    27 schema:editor N1cf772de09834049b120a0dbc20ac585
    28 schema:genre chapter
    29 schema:inLanguage en
    30 schema:isAccessibleForFree true
    31 schema:isPartOf N4f85b603b4d34108b6fdd420700a1aed
    32 schema:name Comparison Between XL and Gröbner Basis Algorithms
    33 schema:pagination 338-353
    34 schema:productId N24a52d45df314873b3505a6b57a9fbbd
    35 N545d3d2c88ce4120bd782f7685441c5b
    36 Ne5f327785aca4513bc4704a1de2ad320
    37 schema:publisher N8ba8d38e809b4abcb4bd8a9734ed1eef
    38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006829906
    39 https://doi.org/10.1007/978-3-540-30539-2_24
    40 schema:sdDatePublished 2019-04-16T07:29
    41 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    42 schema:sdPublisher N7a9ac859ea7c4c09aae9ebf1f9c38181
    43 schema:url https://link.springer.com/10.1007%2F978-3-540-30539-2_24
    44 sgo:license sg:explorer/license/
    45 sgo:sdDataset chapters
    46 rdf:type schema:Chapter
    47 N00254e17672748a59f9303e10992ad87 rdf:first sg:person.015626242511.23
    48 rdf:rest Nd9e49e7cfe4143429285958356ccb3fc
    49 N1cf772de09834049b120a0dbc20ac585 rdf:first N60ff232e1b6d42cfa98756869ecede62
    50 rdf:rest rdf:nil
    51 N24a52d45df314873b3505a6b57a9fbbd schema:name readcube_id
    52 schema:value 2088ac939dad86158f3d13cab953015952d4cf5dc4a38093d3157110992b492c
    53 rdf:type schema:PropertyValue
    54 N4baa0aee84f2424eb9a668136a4daffc rdf:first sg:person.016233257170.21
    55 rdf:rest N921fe54076eb46a1b38fd9c92eca25f3
    56 N4f85b603b4d34108b6fdd420700a1aed schema:isbn 978-3-540-23975-8
    57 978-3-540-30539-2
    58 schema:name Advances in Cryptology - ASIACRYPT 2004
    59 rdf:type schema:Book
    60 N545d3d2c88ce4120bd782f7685441c5b schema:name doi
    61 schema:value 10.1007/978-3-540-30539-2_24
    62 rdf:type schema:PropertyValue
    63 N60ff232e1b6d42cfa98756869ecede62 schema:familyName Lee
    64 schema:givenName Pil Joong
    65 rdf:type schema:Person
    66 N7a9ac859ea7c4c09aae9ebf1f9c38181 schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 N8ba8d38e809b4abcb4bd8a9734ed1eef schema:location Berlin, Heidelberg
    69 schema:name Springer Berlin Heidelberg
    70 rdf:type schema:Organisation
    71 N921fe54076eb46a1b38fd9c92eca25f3 rdf:first sg:person.015445232677.54
    72 rdf:rest Nb109cd531b5148138e381fe7f5137b29
    73 Nb109cd531b5148138e381fe7f5137b29 rdf:first sg:person.015036512317.70
    74 rdf:rest N00254e17672748a59f9303e10992ad87
    75 Nd9e49e7cfe4143429285958356ccb3fc rdf:first sg:person.014550535711.45
    76 rdf:rest rdf:nil
    77 Ne5f327785aca4513bc4704a1de2ad320 schema:name dimensions_id
    78 schema:value pub.1006829906
    79 rdf:type schema:PropertyValue
    80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Information and Computing Sciences
    82 rdf:type schema:DefinedTerm
    83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    84 schema:name Computation Theory and Mathematics
    85 rdf:type schema:DefinedTerm
    86 sg:person.014550535711.45 schema:affiliation https://www.grid.ac/institutes/grid.469365.b
    87 schema:familyName Sugita
    88 schema:givenName Makoto
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014550535711.45
    90 rdf:type schema:Person
    91 sg:person.015036512317.70 schema:affiliation https://www.grid.ac/institutes/grid.26999.3d
    92 schema:familyName Imai
    93 schema:givenName Hideki
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015036512317.70
    95 rdf:type schema:Person
    96 sg:person.015445232677.54 schema:affiliation https://www.grid.ac/institutes/grid.462844.8
    97 schema:familyName Faugère
    98 schema:givenName Jean-Charles
    99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015445232677.54
    100 rdf:type schema:Person
    101 sg:person.015626242511.23 schema:affiliation https://www.grid.ac/institutes/grid.261455.1
    102 schema:familyName Kawazoe
    103 schema:givenName Mitsuru
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015626242511.23
    105 rdf:type schema:Person
    106 sg:person.016233257170.21 schema:affiliation https://www.grid.ac/institutes/grid.469499.f
    107 schema:familyName Ars
    108 schema:givenName Gwénolé
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016233257170.21
    110 rdf:type schema:Person
    111 sg:pub.10.1007/3-540-12868-9_99 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030833923
    112 https://doi.org/10.1007/3-540-12868-9_99
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/3-540-36178-2_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046297994
    115 https://doi.org/10.1007/3-540-36178-2_17
    116 rdf:type schema:CreativeWork
    117 sg:pub.10.1007/3-540-36552-4_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049921761
    118 https://doi.org/10.1007/3-540-36552-4_13
    119 rdf:type schema:CreativeWork
    120 sg:pub.10.1007/3-540-39200-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043854228
    121 https://doi.org/10.1007/3-540-39200-9_21
    122 rdf:type schema:CreativeWork
    123 sg:pub.10.1007/3-540-44750-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051590862
    124 https://doi.org/10.1007/3-540-44750-4_20
    125 rdf:type schema:CreativeWork
    126 sg:pub.10.1007/3-540-45353-9_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003163768
    127 https://doi.org/10.1007/3-540-45353-9_20
    128 rdf:type schema:CreativeWork
    129 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
    130 https://doi.org/10.1007/3-540-45539-6_27
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/3-540-48405-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
    133 https://doi.org/10.1007/3-540-48405-1_2
    134 rdf:type schema:CreativeWork
    135 sg:pub.10.1007/3-540-48910-x_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020614953
    136 https://doi.org/10.1007/3-540-48910-x_15
    137 rdf:type schema:CreativeWork
    138 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
    139 https://doi.org/10.1007/3-540-68339-9_4
    140 rdf:type schema:CreativeWork
    141 sg:pub.10.1007/978-1-4612-0913-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015138233
    142 https://doi.org/10.1007/978-1-4612-0913-3
    143 rdf:type schema:CreativeWork
    144 sg:pub.10.1007/978-1-4757-6911-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011483333
    145 https://doi.org/10.1007/978-1-4757-6911-1
    146 rdf:type schema:CreativeWork
    147 sg:pub.10.1007/978-3-540-45146-4_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049850905
    148 https://doi.org/10.1007/978-3-540-45146-4_10
    149 rdf:type schema:CreativeWork
    150 sg:pub.10.1007/978-3-540-45146-4_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020782332
    151 https://doi.org/10.1007/978-3-540-45146-4_11
    152 rdf:type schema:CreativeWork
    153 sg:pub.10.1007/978-3-540-45146-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049476263
    154 https://doi.org/10.1007/978-3-540-45146-4_3
    155 rdf:type schema:CreativeWork
    156 https://app.dimensions.ai/details/publication/pub.1011483333 schema:CreativeWork
    157 https://app.dimensions.ai/details/publication/pub.1015138233 schema:CreativeWork
    158 https://doi.org/10.1006/jsco.1993.1051 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021494546
    159 rdf:type schema:CreativeWork
    160 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
    161 rdf:type schema:CreativeWork
    162 https://doi.org/10.1145/780506.780516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007436250
    163 rdf:type schema:CreativeWork
    164 https://www.grid.ac/institutes/grid.261455.1 schema:alternateName Osaka Prefecture University
    165 schema:name Department of Mathematics and Information Sciences, Osaka Prefecture University, 1-1 Gakuen-cho, 599-8531, Sakai Osaka, Japan
    166 rdf:type schema:Organization
    167 https://www.grid.ac/institutes/grid.26999.3d schema:alternateName University of Tokyo
    168 schema:name Institute of Industrial Science, University of Tokyo, 4-6-1 Komaba, Meguro-ku, 153-8505, Tokyo, Japan
    169 rdf:type schema:Organization
    170 https://www.grid.ac/institutes/grid.462844.8 schema:alternateName Sorbonne University
    171 schema:name LIP6/CNRS/INRIA, University of Paris VI, 8 rue du Capitaine Scott Paris, 75015, Paris, France
    172 rdf:type schema:Organization
    173 https://www.grid.ac/institutes/grid.469365.b schema:alternateName Information-Technology Promotion Agency
    174 schema:name IT Security Center, Information-technology Promotion Agency, Japan, 2-28-8 Honkomagome, Bunkyo-ku, 113-6591, Tokyo, Japan
    175 rdf:type schema:Organization
    176 https://www.grid.ac/institutes/grid.469499.f schema:alternateName Mathematics Research Institute of Rennes
    177 schema:name IRMAR, University of Rennes 1, Campus de Beaulieu, 35042, Rennes, France
    178 rdf:type schema:Organization
     




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


    ...