Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2016-02-04

AUTHORS

Alan Szepieniec , Jintai Ding , Bart Preneel

ABSTRACT

This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms. More... »

PAGES

182-196

Book

TITLE

Post-Quantum Cryptography

ISBN

978-3-319-29359-2
978-3-319-29360-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-29360-8_12

DOI

http://dx.doi.org/10.1007/978-3-319-29360-8_12

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "iMinds, Ghent, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.56912.39", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "iMinds, Ghent, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Szepieniec", 
        "givenName": "Alan", 
        "id": "sg:person.013013776035.00", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati, Cincinnati, OH, USA", 
          "id": "http://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "University of Cincinnati, Cincinnati, OH, USA"
          ], 
          "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": "iMinds, Ghent, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.56912.39", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium", 
            "iMinds, Ghent, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-02-04", 
    "datePublishedReg": "2016-02-04", 
    "description": "This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.", 
    "editor": [
      {
        "familyName": "Takagi", 
        "givenName": "Tsuyoshi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-29360-8_12", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-29359-2", 
        "978-3-319-29360-8"
      ], 
      "name": "Post-Quantum Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "multivariate quadratic systems", 
      "Hidden Field Equations", 
      "multivariate quadratic public-key cryptosystems", 
      "field equations", 
      "linear systems", 
      "quadratic systems", 
      "simple polynomials", 
      "extension field", 
      "Unbalanced Oil", 
      "field polynomials", 
      "polynomials", 
      "public key cryptosystem", 
      "public key algorithms", 
      "scheme", 
      "concise description", 
      "equations", 
      "key algorithms", 
      "efficient operation", 
      "commutativity", 
      "algorithm", 
      "system", 
      "field", 
      "complexity", 
      "description", 
      "cryptosystem", 
      "primitives", 
      "transformation", 
      "construction", 
      "public key", 
      "implementation", 
      "operation", 
      "signatures", 
      "plaintext", 
      "trapdoor", 
      "private key", 
      "key", 
      "minus", 
      "encryption", 
      "users", 
      "attacks", 
      "reduction", 
      "contrast", 
      "oil", 
      "modifiers", 
      "vinegar", 
      "paper"
    ], 
    "name": "Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems", 
    "pagination": "182-196", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009369753"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-29360-8_12"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-29360-8_12", 
      "https://app.dimensions.ai/details/publication/pub.1009369753"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T06:59", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_453.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-29360-8_12"
  }
]
 

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-319-29360-8_12'

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-319-29360-8_12'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-29360-8_12'

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-319-29360-8_12'


 

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

123 TRIPLES      22 PREDICATES      70 URIs      63 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-29360-8_12 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nbc348a219f674ce195a50a121b820002
4 schema:datePublished 2016-02-04
5 schema:datePublishedReg 2016-02-04
6 schema:description This paper introduces a new central trapdoor for multivariate quadratic (MQ) public-key cryptosystems that allows for encryption, in contrast to time-tested MQ primitives such as Unbalanced Oil and Vinegar or Hidden Field Equations which only allow for signatures. Our construction is a mixed-field scheme that exploits the commutativity of the extension field to dramatically reduce the complexity of the extension field polynomial implicitly present in the public key. However, this reduction can only be performed by the user who knows concise descriptions of two simple polynomials, which constitute the private key. After applying this transformation, the plaintext can be recovered by solving a linear system. We use the minus and projection modifiers to inoculate our scheme against known attacks. A straightforward C++ implementation confirms the efficient operation of the public key algorithms.
7 schema:editor N52885ac9fa054d13992d5a3db840a81b
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N076451eda64f448fbe2a900d292ea93f
11 schema:keywords Hidden Field Equations
12 Unbalanced Oil
13 algorithm
14 attacks
15 commutativity
16 complexity
17 concise description
18 construction
19 contrast
20 cryptosystem
21 description
22 efficient operation
23 encryption
24 equations
25 extension field
26 field
27 field equations
28 field polynomials
29 implementation
30 key
31 key algorithms
32 linear systems
33 minus
34 modifiers
35 multivariate quadratic public-key cryptosystems
36 multivariate quadratic systems
37 oil
38 operation
39 paper
40 plaintext
41 polynomials
42 primitives
43 private key
44 public key
45 public key algorithms
46 public key cryptosystem
47 quadratic systems
48 reduction
49 scheme
50 signatures
51 simple polynomials
52 system
53 transformation
54 trapdoor
55 users
56 vinegar
57 schema:name Extension Field Cancellation: A New Central Trapdoor for Multivariate Quadratic Systems
58 schema:pagination 182-196
59 schema:productId N3bb30f23a5234b3daf983d6ebe0a6c91
60 N6479021632ef439f9331fa869fe25282
61 schema:publisher Nf9a69a11e20b493cb7b176e4154202ff
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009369753
63 https://doi.org/10.1007/978-3-319-29360-8_12
64 schema:sdDatePublished 2022-10-01T06:59
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher N3bd529932d2644cc80210e1e17417b8f
67 schema:url https://doi.org/10.1007/978-3-319-29360-8_12
68 sgo:license sg:explorer/license/
69 sgo:sdDataset chapters
70 rdf:type schema:Chapter
71 N076451eda64f448fbe2a900d292ea93f schema:isbn 978-3-319-29359-2
72 978-3-319-29360-8
73 schema:name Post-Quantum Cryptography
74 rdf:type schema:Book
75 N3bb30f23a5234b3daf983d6ebe0a6c91 schema:name dimensions_id
76 schema:value pub.1009369753
77 rdf:type schema:PropertyValue
78 N3bd529932d2644cc80210e1e17417b8f schema:name Springer Nature - SN SciGraph project
79 rdf:type schema:Organization
80 N52885ac9fa054d13992d5a3db840a81b rdf:first N9797f537d6ef4cbcaa83108ec144bf38
81 rdf:rest rdf:nil
82 N6479021632ef439f9331fa869fe25282 schema:name doi
83 schema:value 10.1007/978-3-319-29360-8_12
84 rdf:type schema:PropertyValue
85 N9797f537d6ef4cbcaa83108ec144bf38 schema:familyName Takagi
86 schema:givenName Tsuyoshi
87 rdf:type schema:Person
88 Nbc348a219f674ce195a50a121b820002 rdf:first sg:person.013013776035.00
89 rdf:rest Ne32a04e1002447a5b8dd7ab2560a54a6
90 Nbf10a7ee345c463ea9ebaf7e2f040cf2 rdf:first sg:person.011115044357.39
91 rdf:rest rdf:nil
92 Ne32a04e1002447a5b8dd7ab2560a54a6 rdf:first sg:person.010723403013.04
93 rdf:rest Nbf10a7ee345c463ea9ebaf7e2f040cf2
94 Nf9a69a11e20b493cb7b176e4154202ff schema:name Springer Nature
95 rdf:type schema:Organisation
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
100 schema:name Data Format
101 rdf:type schema:DefinedTerm
102 sg:person.010723403013.04 schema:affiliation grid-institutes:grid.24827.3b
103 schema:familyName Ding
104 schema:givenName Jintai
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
106 rdf:type schema:Person
107 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.56912.39
108 schema:familyName Preneel
109 schema:givenName Bart
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
111 rdf:type schema:Person
112 sg:person.013013776035.00 schema:affiliation grid-institutes:grid.56912.39
113 schema:familyName Szepieniec
114 schema:givenName Alan
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013013776035.00
116 rdf:type schema:Person
117 grid-institutes:grid.24827.3b schema:alternateName University of Cincinnati, Cincinnati, OH, USA
118 schema:name University of Cincinnati, Cincinnati, OH, USA
119 rdf:type schema:Organization
120 grid-institutes:grid.56912.39 schema:alternateName iMinds, Ghent, Belgium
121 schema:name Department of Electrical Engineering, ESAT/COSIC, KU Leuven, Leuven, Belgium
122 iMinds, Ghent, Belgium
123 rdf:type schema:Organization
 




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


...