Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000

AUTHORS

Nicolas Courtois , Alexander Klimov , Jacques Patarin , Adi Shamir

ABSTRACT

The security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. This problem is NP-hard over any field. When the number of equations m is the same as the number of unknowns n the best known algorithms are exhaustive search for small fields, and a Gröbner base algorithm for large fields. Gröbner base algorithms have large exponential complexity and cannot solve in practice systems with n ≥ 15. Kipnis and Shamir [9] have recently introduced a new algorithm called “relinearization”. The exact complexity of this algorithm is not known, but for sufficiently overdefined systems it was expected to run in polynomial time. In this paper we analyze the theoretical and practical aspects of relinearization. We ran a large number of experiments for various values of n and m, and analysed which systems of equations were actually solvable. We show that many of the equations generated by relinearization are linearly dependent, and thus relinearization is less efficient that one could expect. We then develop an improved algorithm called XL which is both simpler and more powerful than relinearization. For all 0 < ε ≤ 1/2, and m ≥ εn 2, XL and relinearization are expected to run in polynomial time of approximately \( n^{\mathcal{O}(1/\sqrt \varepsilon )} \). Moreover, we provide strong evidence that relinearization and XL can solve randomly generated systems of polynomial equations in subexponential time when m exceeds n by a number that increases slowly with n. More... »

PAGES

392-407

Book

TITLE

Advances in Cryptology — EUROCRYPT 2000

ISBN

978-3-540-67517-4
978-3-540-45539-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-45539-6_27

DOI

http://dx.doi.org/10.1007/3-540-45539-6_27

DIMENSIONS

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


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": "Universite De Toulon Et Du Var", 
          "id": "https://www.grid.ac/institutes/grid.12611.35", 
          "name": [
            "MS/LI, Toulon University, BP 132, F-83957\u00a0La Garde Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Courtois", 
        "givenName": "Nicolas", 
        "id": "sg:person.013151403707.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Moscow State University", 
          "id": "https://www.grid.ac/institutes/grid.14476.30", 
          "name": [
            "Dept. of Appl. Math. & Cybernetics, Moscow State University, Moscow, Russia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Klimov", 
        "givenName": "Alexander", 
        "id": "sg:person.012103040156.56", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012103040156.56"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Bull CP8, 68, route de Versailles, BP45, 78431\u00a0Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "id": "sg:person.011133025705.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011133025705.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Weizmann Institute of Science", 
          "id": "https://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Dept. of Applied Math., The Weizmann Institute of Science, Rehovot, 76100, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Shamir", 
        "givenName": "Adi", 
        "id": "sg:person.013052746407.28", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1040947089"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000", 
    "datePublishedReg": "2000-01-01", 
    "description": "The security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. This problem is NP-hard over any field. When the number of equations m is the same as the number of unknowns n the best known algorithms are exhaustive search for small fields, and a Gr\u00f6bner base algorithm for large fields. Gr\u00f6bner base algorithms have large exponential complexity and cannot solve in practice systems with n \u2265 15. Kipnis and Shamir [9] have recently introduced a new algorithm called \u201crelinearization\u201d. The exact complexity of this algorithm is not known, but for sufficiently overdefined systems it was expected to run in polynomial time. In this paper we analyze the theoretical and practical aspects of relinearization. We ran a large number of experiments for various values of n and m, and analysed which systems of equations were actually solvable. We show that many of the equations generated by relinearization are linearly dependent, and thus relinearization is less efficient that one could expect. We then develop an improved algorithm called XL which is both simpler and more powerful than relinearization. For all 0 < \u03b5 \u2264 1/2, and m \u2265 \u03b5n 2, XL and relinearization are expected to run in polynomial time of approximately \\( n^{\\mathcal{O}(1/\\sqrt \\varepsilon )} \\). Moreover, we provide strong evidence that relinearization and XL can solve randomly generated systems of polynomial equations in subexponential time when m exceeds n by a number that increases slowly with n.", 
    "editor": [
      {
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-45539-6_27", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-67517-4", 
        "978-3-540-45539-4"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT 2000", 
      "type": "Book"
    }, 
    "name": "Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations", 
    "pagination": "392-407", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45539-6_27"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "015bd38478b8faa2c7027dab06ca24deb5726efabbab42c77d78aae657a4b5ec"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1000285811"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45539-6_27", 
      "https://app.dimensions.ai/details/publication/pub.1000285811"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T15:18", 
    "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/0000000001_0000000264/records_8672_00000243.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-45539-6_27"
  }
]
 

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/3-540-45539-6_27'

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/3-540-45539-6_27'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45539-6_27'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45539-6_27'


 

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

97 TRIPLES      23 PREDICATES      28 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45539-6_27 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N73d3b349ed464cacb7ec4d6304065ee9
4 schema:citation https://doi.org/10.1016/s0022-4049(99)00005-5
5 schema:datePublished 2000
6 schema:datePublishedReg 2000-01-01
7 schema:description The security of many recently proposed cryptosystems is based on the difficulty of solving large systems of quadratic multivariate polynomial equations. This problem is NP-hard over any field. When the number of equations m is the same as the number of unknowns n the best known algorithms are exhaustive search for small fields, and a Gröbner base algorithm for large fields. Gröbner base algorithms have large exponential complexity and cannot solve in practice systems with n ≥ 15. Kipnis and Shamir [9] have recently introduced a new algorithm called “relinearization”. The exact complexity of this algorithm is not known, but for sufficiently overdefined systems it was expected to run in polynomial time. In this paper we analyze the theoretical and practical aspects of relinearization. We ran a large number of experiments for various values of n and m, and analysed which systems of equations were actually solvable. We show that many of the equations generated by relinearization are linearly dependent, and thus relinearization is less efficient that one could expect. We then develop an improved algorithm called XL which is both simpler and more powerful than relinearization. For all 0 < ε ≤ 1/2, and m ≥ εn 2, XL and relinearization are expected to run in polynomial time of approximately \( n^{\mathcal{O}(1/\sqrt \varepsilon )} \). Moreover, we provide strong evidence that relinearization and XL can solve randomly generated systems of polynomial equations in subexponential time when m exceeds n by a number that increases slowly with n.
8 schema:editor N8e07ac2e3ea24864b13818e7526cbf85
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
12 schema:isPartOf Nba1e2af0a56d473492ea1ec69c463152
13 schema:name Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations
14 schema:pagination 392-407
15 schema:productId Nd51a62d5e59e43eba7caa31c500486ce
16 Nf2d4f129bdf6403baacd3f6617c0eaaa
17 Nf842ae40edda493aa34863f68972a6c8
18 schema:publisher N8f743004a23f4f56adbce4c2e0c09992
19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
20 https://doi.org/10.1007/3-540-45539-6_27
21 schema:sdDatePublished 2019-04-15T15:18
22 schema:sdLicense https://scigraph.springernature.com/explorer/license/
23 schema:sdPublisher Nff95bda009464a588d8845c826b89a77
24 schema:url http://link.springer.com/10.1007/3-540-45539-6_27
25 sgo:license sg:explorer/license/
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N50b727006fde401fb15a699ac73c9fc2 schema:familyName Preneel
29 schema:givenName Bart
30 rdf:type schema:Person
31 N67f7b102b6f84a19bbfe53b89648263f rdf:first sg:person.013052746407.28
32 rdf:rest rdf:nil
33 N73d3b349ed464cacb7ec4d6304065ee9 rdf:first sg:person.013151403707.45
34 rdf:rest N74d680ee9add40268e1c57d04052694c
35 N74d680ee9add40268e1c57d04052694c rdf:first sg:person.012103040156.56
36 rdf:rest N77f675c640a446ca9e156b99f8f721b9
37 N77f675c640a446ca9e156b99f8f721b9 rdf:first sg:person.011133025705.92
38 rdf:rest N67f7b102b6f84a19bbfe53b89648263f
39 N8e07ac2e3ea24864b13818e7526cbf85 rdf:first N50b727006fde401fb15a699ac73c9fc2
40 rdf:rest rdf:nil
41 N8f743004a23f4f56adbce4c2e0c09992 schema:location Berlin, Heidelberg
42 schema:name Springer Berlin Heidelberg
43 rdf:type schema:Organisation
44 N96f2e9fc3d384fda85b8fd0d5856151e schema:name Bull CP8, 68, route de Versailles, BP45, 78431 Louveciennes Cedex, France
45 rdf:type schema:Organization
46 Nba1e2af0a56d473492ea1ec69c463152 schema:isbn 978-3-540-45539-4
47 978-3-540-67517-4
48 schema:name Advances in Cryptology — EUROCRYPT 2000
49 rdf:type schema:Book
50 Nd51a62d5e59e43eba7caa31c500486ce schema:name dimensions_id
51 schema:value pub.1000285811
52 rdf:type schema:PropertyValue
53 Nf2d4f129bdf6403baacd3f6617c0eaaa schema:name doi
54 schema:value 10.1007/3-540-45539-6_27
55 rdf:type schema:PropertyValue
56 Nf842ae40edda493aa34863f68972a6c8 schema:name readcube_id
57 schema:value 015bd38478b8faa2c7027dab06ca24deb5726efabbab42c77d78aae657a4b5ec
58 rdf:type schema:PropertyValue
59 Nff95bda009464a588d8845c826b89a77 schema:name Springer Nature - SN SciGraph project
60 rdf:type schema:Organization
61 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
62 schema:name Information and Computing Sciences
63 rdf:type schema:DefinedTerm
64 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
65 schema:name Computation Theory and Mathematics
66 rdf:type schema:DefinedTerm
67 sg:person.011133025705.92 schema:affiliation N96f2e9fc3d384fda85b8fd0d5856151e
68 schema:familyName Patarin
69 schema:givenName Jacques
70 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011133025705.92
71 rdf:type schema:Person
72 sg:person.012103040156.56 schema:affiliation https://www.grid.ac/institutes/grid.14476.30
73 schema:familyName Klimov
74 schema:givenName Alexander
75 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012103040156.56
76 rdf:type schema:Person
77 sg:person.013052746407.28 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
78 schema:familyName Shamir
79 schema:givenName Adi
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013052746407.28
81 rdf:type schema:Person
82 sg:person.013151403707.45 schema:affiliation https://www.grid.ac/institutes/grid.12611.35
83 schema:familyName Courtois
84 schema:givenName Nicolas
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45
86 rdf:type schema:Person
87 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
88 rdf:type schema:CreativeWork
89 https://www.grid.ac/institutes/grid.12611.35 schema:alternateName Universite De Toulon Et Du Var
90 schema:name MS/LI, Toulon University, BP 132, F-83957 La Garde Cedex, France
91 rdf:type schema:Organization
92 https://www.grid.ac/institutes/grid.13992.30 schema:alternateName Weizmann Institute of Science
93 schema:name Dept. of Applied Math., The Weizmann Institute of Science, Rehovot, 76100, Israel
94 rdf:type schema:Organization
95 https://www.grid.ac/institutes/grid.14476.30 schema:alternateName Moscow State University
96 schema:name Dept. of Appl. Math. & Cybernetics, Moscow State University, Moscow, Russia
97 rdf:type schema:Organization
 




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


...