New Insight into the Isomorphism of Polynomial Problem IP1S and Its Use in Cryptography View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Gilles Macario-Rat , Jérôme Plut , Henri Gilbert

ABSTRACT

This paper investigates the mathematical structure of the “Isomorphism of Polynomial with One Secret” problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.). We show that the structure of the equations is directly linked to a matrix derived from the polar form of the polynomials. We prove that in the likely case where this matrix is cyclic, the problem can be solved in polynomial time – using an algorithm that unlike previous solving techniques is not based upon Gröbner basis computation. More... »

PAGES

117-133

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-42033-7_7

DOI

http://dx.doi.org/10.1007/978-3-642-42033-7_7

DIMENSIONS

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


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/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Orange Labs, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux Cedex 9, France", 
          "id": "http://www.grid.ac/institutes/grid.89485.38", 
          "name": [
            "Orange Labs, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794, Issy-les-Moulineaux Cedex 9, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Macario-Rat", 
        "givenName": "Gilles", 
        "id": "sg:person.011046304613.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011046304613.50"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plut", 
        "givenName": "J\u00e9r\u00f4me", 
        "id": "sg:person.012162703636.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162703636.29"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gilbert", 
        "givenName": "Henri", 
        "id": "sg:person.012771236207.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "This paper investigates the mathematical structure of the \u201cIsomorphism of Polynomial with One Secret\u201d problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.). We show that the structure of the equations is directly linked to a matrix derived from the polar form of the polynomials. We prove that in the likely case where this matrix is cyclic, the problem can be solved in polynomial time \u2013 using an algorithm that unlike previous solving techniques is not based upon Gr\u00f6bner basis computation.", 
    "editor": [
      {
        "familyName": "Sako", 
        "givenName": "Kazue", 
        "type": "Person"
      }, 
      {
        "familyName": "Sarkar", 
        "givenName": "Palash", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-42033-7_7", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-42032-0", 
        "978-3-642-42033-7"
      ], 
      "name": "Advances in Cryptology - ASIACRYPT 2013", 
      "type": "Book"
    }, 
    "keywords": [
      "Isomorphism of Polynomials", 
      "Gr\u00f6bner basis computation", 
      "practical parameter values", 
      "mathematical structure", 
      "polynomial problem", 
      "random instances", 
      "basis computation", 
      "parameter values", 
      "solving techniques", 
      "polar form", 
      "polynomials", 
      "isomorphism", 
      "problem", 
      "equations", 
      "matrix", 
      "computation", 
      "algorithm", 
      "cryptography", 
      "structure", 
      "instances", 
      "technique", 
      "form", 
      "likely case", 
      "cases", 
      "values", 
      "new insights", 
      "purpose", 
      "use", 
      "insights", 
      "secrets", 
      "paper"
    ], 
    "name": "New Insight into the Isomorphism of Polynomial Problem IP1S and Its Use in Cryptography", 
    "pagination": "117-133", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019950830"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-42033-7_7"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-42033-7_7", 
      "https://app.dimensions.ai/details/publication/pub.1019950830"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:17", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_393.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-42033-7_7"
  }
]
 

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-42033-7_7'

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-42033-7_7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-42033-7_7'

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-42033-7_7'


 

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

112 TRIPLES      22 PREDICATES      56 URIs      49 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-42033-7_7 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nf6ab796ba06447ea8f50e6c5c17f49f1
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description This paper investigates the mathematical structure of the “Isomorphism of Polynomial with One Secret” problem (IP1S). Our purpose is to understand why for practical parameter values of IP1S most random instances are easily solvable (as first observed by Bouillaguet et al.). We show that the structure of the equations is directly linked to a matrix derived from the polar form of the polynomials. We prove that in the likely case where this matrix is cyclic, the problem can be solved in polynomial time – using an algorithm that unlike previous solving techniques is not based upon Gröbner basis computation.
7 schema:editor Nc8f9b393329b46e5b672f7c2f220b0a5
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N6c80dbfd3da8484497cd1ed55b80dbd8
11 schema:keywords Gröbner basis computation
12 Isomorphism of Polynomials
13 algorithm
14 basis computation
15 cases
16 computation
17 cryptography
18 equations
19 form
20 insights
21 instances
22 isomorphism
23 likely case
24 mathematical structure
25 matrix
26 new insights
27 paper
28 parameter values
29 polar form
30 polynomial problem
31 polynomials
32 practical parameter values
33 problem
34 purpose
35 random instances
36 secrets
37 solving techniques
38 structure
39 technique
40 use
41 values
42 schema:name New Insight into the Isomorphism of Polynomial Problem IP1S and Its Use in Cryptography
43 schema:pagination 117-133
44 schema:productId N43a0d9cbc6d142f38778eef1e610f2aa
45 Na2149579021645b5b26c3c29126b597b
46 schema:publisher N0e3fe84c44cf49d3abf873176e304c4e
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019950830
48 https://doi.org/10.1007/978-3-642-42033-7_7
49 schema:sdDatePublished 2022-11-24T21:17
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N836671c2234048eaa829b31a05d11871
52 schema:url https://doi.org/10.1007/978-3-642-42033-7_7
53 sgo:license sg:explorer/license/
54 sgo:sdDataset chapters
55 rdf:type schema:Chapter
56 N0e3fe84c44cf49d3abf873176e304c4e schema:name Springer Nature
57 rdf:type schema:Organisation
58 N43a0d9cbc6d142f38778eef1e610f2aa schema:name doi
59 schema:value 10.1007/978-3-642-42033-7_7
60 rdf:type schema:PropertyValue
61 N6c80dbfd3da8484497cd1ed55b80dbd8 schema:isbn 978-3-642-42032-0
62 978-3-642-42033-7
63 schema:name Advances in Cryptology - ASIACRYPT 2013
64 rdf:type schema:Book
65 N794ee03651384303bdda2236f2f8b4d5 rdf:first sg:person.012771236207.08
66 rdf:rest rdf:nil
67 N836671c2234048eaa829b31a05d11871 schema:name Springer Nature - SN SciGraph project
68 rdf:type schema:Organization
69 N83fde09615bd4162a0371c1370a89441 rdf:first Nf076e37cb29f42198b9d8480087e6dea
70 rdf:rest rdf:nil
71 Na2149579021645b5b26c3c29126b597b schema:name dimensions_id
72 schema:value pub.1019950830
73 rdf:type schema:PropertyValue
74 Nc8f9b393329b46e5b672f7c2f220b0a5 rdf:first Necc673260c2c45749b95169c70861e99
75 rdf:rest N83fde09615bd4162a0371c1370a89441
76 Nd7ceef96709341bbb8a72f6a105dd503 rdf:first sg:person.012162703636.29
77 rdf:rest N794ee03651384303bdda2236f2f8b4d5
78 Necc673260c2c45749b95169c70861e99 schema:familyName Sako
79 schema:givenName Kazue
80 rdf:type schema:Person
81 Nf076e37cb29f42198b9d8480087e6dea schema:familyName Sarkar
82 schema:givenName Palash
83 rdf:type schema:Person
84 Nf6ab796ba06447ea8f50e6c5c17f49f1 rdf:first sg:person.011046304613.50
85 rdf:rest Nd7ceef96709341bbb8a72f6a105dd503
86 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
87 schema:name Mathematical Sciences
88 rdf:type schema:DefinedTerm
89 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
90 schema:name Pure Mathematics
91 rdf:type schema:DefinedTerm
92 sg:person.011046304613.50 schema:affiliation grid-institutes:grid.89485.38
93 schema:familyName Macario-Rat
94 schema:givenName Gilles
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011046304613.50
96 rdf:type schema:Person
97 sg:person.012162703636.29 schema:affiliation grid-institutes:None
98 schema:familyName Plut
99 schema:givenName Jérôme
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162703636.29
101 rdf:type schema:Person
102 sg:person.012771236207.08 schema:affiliation grid-institutes:None
103 schema:familyName Gilbert
104 schema:givenName Henri
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08
106 rdf:type schema:Person
107 grid-institutes:None schema:alternateName ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France
108 schema:name ANSSI, 51 Boulevard de la Tour-Maubourg, 75007, Paris, France
109 rdf:type schema:Organization
110 grid-institutes:grid.89485.38 schema:alternateName Orange Labs, 38–40, rue du Général Leclerc, 92794, Issy-les-Moulineaux Cedex 9, France
111 schema:name Orange Labs, 38–40, rue du Général Leclerc, 92794, Issy-les-Moulineaux Cedex 9, France
112 rdf:type schema:Organization
 




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


...