# Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations

Ontology type: schema:Chapter      Open Access: True

### Chapter Info

DATE

2000

AUTHORS 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:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"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",
"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"
]
},
{
"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",
"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",
}
]

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'

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
2 anzsrc-for:0802
3 schema:author Nebeed979f68844549269d3f1b98f2d11
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 N7bd17096f34f47fa89b8107217bf4d02
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree true
13 schema:name Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations
14 schema:pagination 392-407
15 schema:productId N324486fa61d945c3b9c92e93ab2af70e
18 schema:publisher N7bc71b83d6be4952a0180c69c3f37950
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
23 schema:sdPublisher N5e92c0612edd40b2b4b9063242fc1199
26 sgo:sdDataset chapters
27 rdf:type schema:Chapter
28 N2033abe91f4f44bb9fcc5fbf77292eb4 rdf:first sg:person.012103040156.56
30 N324486fa61d945c3b9c92e93ab2af70e schema:name doi
31 schema:value 10.1007/3-540-45539-6_27
32 rdf:type schema:PropertyValue
33 N4265afa1b14e418e9e42b0b8709cfc2b schema:name Bull CP8, 68, route de Versailles, BP45, 78431 Louveciennes Cedex, France
34 rdf:type schema:Organization
36 schema:value 015bd38478b8faa2c7027dab06ca24deb5726efabbab42c77d78aae657a4b5ec
37 rdf:type schema:PropertyValue
38 N5e92c0612edd40b2b4b9063242fc1199 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N793970db1e6c42f3b971d9b2f64f999e schema:familyName Preneel
41 schema:givenName Bart
42 rdf:type schema:Person
43 N7bc71b83d6be4952a0180c69c3f37950 schema:location Berlin, Heidelberg
44 schema:name Springer Berlin Heidelberg
45 rdf:type schema:Organisation
46 N7bd17096f34f47fa89b8107217bf4d02 rdf:first N793970db1e6c42f3b971d9b2f64f999e
47 rdf:rest rdf:nil
48 N80c40d50f1e749c189df6d45e86eb807 rdf:first sg:person.013052746407.28
49 rdf:rest rdf:nil
51 rdf:rest N80c40d50f1e749c189df6d45e86eb807
53 978-3-540-67517-4
54 schema:name Advances in Cryptology — EUROCRYPT 2000
55 rdf:type schema:Book
56 Nebeed979f68844549269d3f1b98f2d11 rdf:first sg:person.013151403707.45
57 rdf:rest N2033abe91f4f44bb9fcc5fbf77292eb4
59 schema:value pub.1000285811
60 rdf:type schema:PropertyValue
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 N4265afa1b14e418e9e42b0b8709cfc2b
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
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