Cryptanalysis of Two Quartic Encryption Schemes and One Improved MFE Scheme View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2010

AUTHORS

Weiwei Cao , Xiuyun Nie , Lei Hu , Xiling Tang , Jintai Ding

ABSTRACT

MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity , where r is a small number denoting the degree of extension of finite fields and w ≈ 2.732. The computational complexity of deriving these equations is about 237. But to find the original plaintext, there still needs 240 times Gröbner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity . The complexity is 236 for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems. More... »

PAGES

41-60

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-12929-2_4

DOI

http://dx.doi.org/10.1007/978-3-642-12929-2_4

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "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": "University of Chinese Academy of Sciences", 
          "id": "https://www.grid.ac/institutes/grid.410726.6", 
          "name": [
            "State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, 100049, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Cao", 
        "givenName": "Weiwei", 
        "id": "sg:person.014327515441.03", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014327515441.03"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Electronic Science and Technology of China", 
          "id": "https://www.grid.ac/institutes/grid.54549.39", 
          "name": [
            "School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Nie", 
        "givenName": "Xiuyun", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Chinese Academy of Sciences", 
          "id": "https://www.grid.ac/institutes/grid.410726.6", 
          "name": [
            "State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, 100049, Beijing, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Hu", 
        "givenName": "Lei", 
        "id": "sg:person.011566074635.42", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011566074635.42"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "South China University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.79703.3a", 
          "name": [
            "South China University of Technology, 510640, Guangzhou, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tang", 
        "givenName": "Xiling", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "South China University of Technology", 
          "id": "https://www.grid.ac/institutes/grid.79703.3a", 
          "name": [
            "Department of Mathematical Sciences, University of Cincinnati, 45221, OH, USA", 
            "South China University of Technology, 510640, Guangzhou, China"
          ], 
          "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"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-71677-8_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002694957", 
          "https://doi.org/10.1007/978-3-540-71677-8_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11605805_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006462081", 
          "https://doi.org/10.1007/11605805_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11605805_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006462081", 
          "https://doi.org/10.1007/11605805_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-0-387-36946-4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026168664", 
          "https://doi.org/10.1007/978-0-387-36946-4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1026168664", 
        "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-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": "https://doi.org/10.1109/tit.1976.1055638", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061647862"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539795293172", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880065"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2010", 
    "datePublishedReg": "2010-01-01", 
    "description": "MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity , where r is a small number denoting the degree of extension of finite fields and w \u2248 2.732. The computational complexity of deriving these equations is about 237. But to find the original plaintext, there still needs 240 times Gr\u00f6bner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity . The complexity is 236 for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems.", 
    "editor": [
      {
        "familyName": "Sendrier", 
        "givenName": "Nicolas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-12929-2_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-12928-5", 
        "978-3-642-12929-2"
      ], 
      "name": "Post-Quantum Cryptography", 
      "type": "Book"
    }, 
    "name": "Cryptanalysis of Two Quartic Encryption Schemes and One Improved MFE Scheme", 
    "pagination": "41-60", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009903512"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-12929-2_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "2f2e0ef5f2aea1eb7433c91afa9f5d6bd96d1e67b3d2f387da83c3d141579d36"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-12929-2_4", 
      "https://app.dimensions.ai/details/publication/pub.1009903512"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:02", 
    "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/0000000359_0000000359/records_29203_00000000.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-642-12929-2_4"
  }
]
 

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-12929-2_4'

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-12929-2_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-12929-2_4'

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-12929-2_4'


 

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

125 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-12929-2_4 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N1be2425c70ef4a428039fde608136bee
4 schema:citation sg:pub.10.1007/11605805_9
5 sg:pub.10.1007/3-540-44750-4_20
6 sg:pub.10.1007/978-0-387-36946-4
7 sg:pub.10.1007/978-3-540-71677-8_16
8 https://app.dimensions.ai/details/publication/pub.1026168664
9 https://doi.org/10.1016/s0022-4049(99)00005-5
10 https://doi.org/10.1109/tit.1976.1055638
11 https://doi.org/10.1137/s0097539795293172
12 schema:datePublished 2010
13 schema:datePublishedReg 2010-01-01
14 schema:description MFE, a multivariate public key encryption scheme proposed by Wang et al in CT-RSA 2006, was conquered by second order linearization equation (SOLE) attack by Ding et al in PKC 2007. To resist this attack, many improved schemes were proposed. Wang et al in [WFW09 and Wang in [Wan07] both modified MFE and raised the public key from quadratic to quartic equations. We call the two quartic schemes Quartic-1 and Quartic-2 respectively for convenience. They are indeed immune to the SOLE attack. However, we find that there exist many quadratization equations (QEs), which are quadratic in plaintext variables and linear in ciphertext variables and can be derived from the public keys of Quartic-1 and Quartic-2. In this paper, we utilize QEs to recover the corresponding plaintext for a given ciphertext. For Quartic-1, we firstly find there are at least 2r SOLEs, which was regarded as impossible by the original authors, furthermore, we can find at least 35r QEs with a complexity , where r is a small number denoting the degree of extension of finite fields and w ≈ 2.732. The computational complexity of deriving these equations is about 237. But to find the original plaintext, there still needs 240 times Gröbner basis computations, which needs practically 1.328 seconds each time. For Quartic-2, we make a theoretical analysis and find 18r QEs with a computational complexity . The complexity is 236 for the parameter proposed in [Wan07], and we can break the scheme practically in 3110.734 seconds. Finally, we show that another improved version of MFE in [WZY07] is insecure against the linearization equation attack although its authors claimed it is secure against high order linearization equation attack. Our attack on the two quartic schemes illustrates that non-linearization equations like quadratization equations which are not degree one in plaintext variables can also be used efficiently to analyze multivariate cryptosystems.
15 schema:editor N71979ff1752c4731a1dce7fc3a6d5c6f
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree false
19 schema:isPartOf N1b02106ec7b64b69b339b09080cfc3b2
20 schema:name Cryptanalysis of Two Quartic Encryption Schemes and One Improved MFE Scheme
21 schema:pagination 41-60
22 schema:productId N0c496150044a493e87173d3a8571647d
23 N41717f77b7ff448dad16b2a7f1a4e09e
24 Ne794907c1db24f56bf657a56616d9ee3
25 schema:publisher N6e5779e4f221432e8a007a9467089599
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009903512
27 https://doi.org/10.1007/978-3-642-12929-2_4
28 schema:sdDatePublished 2019-04-16T08:02
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N915560324f9640b896637fb1b9d40e70
31 schema:url https://link.springer.com/10.1007%2F978-3-642-12929-2_4
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N0c496150044a493e87173d3a8571647d schema:name readcube_id
36 schema:value 2f2e0ef5f2aea1eb7433c91afa9f5d6bd96d1e67b3d2f387da83c3d141579d36
37 rdf:type schema:PropertyValue
38 N1b02106ec7b64b69b339b09080cfc3b2 schema:isbn 978-3-642-12928-5
39 978-3-642-12929-2
40 schema:name Post-Quantum Cryptography
41 rdf:type schema:Book
42 N1be2425c70ef4a428039fde608136bee rdf:first sg:person.014327515441.03
43 rdf:rest N357921ebca7c424d95db0556bcf88f9f
44 N357921ebca7c424d95db0556bcf88f9f rdf:first N42feaef2a0ec49348a8636942e0dad90
45 rdf:rest Na9ad3a79dedd497b9eaeeb39c9fe9de3
46 N40feedac3a6448faa28dbf253d1ef80e rdf:first sg:person.010723403013.04
47 rdf:rest rdf:nil
48 N41717f77b7ff448dad16b2a7f1a4e09e schema:name dimensions_id
49 schema:value pub.1009903512
50 rdf:type schema:PropertyValue
51 N42feaef2a0ec49348a8636942e0dad90 schema:affiliation https://www.grid.ac/institutes/grid.54549.39
52 schema:familyName Nie
53 schema:givenName Xiuyun
54 rdf:type schema:Person
55 N66be6d29baa14c7995beb6832c3c675f schema:familyName Sendrier
56 schema:givenName Nicolas
57 rdf:type schema:Person
58 N6e5779e4f221432e8a007a9467089599 schema:location Berlin, Heidelberg
59 schema:name Springer Berlin Heidelberg
60 rdf:type schema:Organisation
61 N71979ff1752c4731a1dce7fc3a6d5c6f rdf:first N66be6d29baa14c7995beb6832c3c675f
62 rdf:rest rdf:nil
63 N915560324f9640b896637fb1b9d40e70 schema:name Springer Nature - SN SciGraph project
64 rdf:type schema:Organization
65 Na9ad3a79dedd497b9eaeeb39c9fe9de3 rdf:first sg:person.011566074635.42
66 rdf:rest Nf7bf693e87bf4b52a216571b1fbfae1a
67 Ndfa3ad05c9da489991f8b1429921f31c schema:affiliation https://www.grid.ac/institutes/grid.79703.3a
68 schema:familyName Tang
69 schema:givenName Xiling
70 rdf:type schema:Person
71 Ne794907c1db24f56bf657a56616d9ee3 schema:name doi
72 schema:value 10.1007/978-3-642-12929-2_4
73 rdf:type schema:PropertyValue
74 Nf7bf693e87bf4b52a216571b1fbfae1a rdf:first Ndfa3ad05c9da489991f8b1429921f31c
75 rdf:rest N40feedac3a6448faa28dbf253d1ef80e
76 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
77 schema:name Information and Computing Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
80 schema:name Data Format
81 rdf:type schema:DefinedTerm
82 sg:person.010723403013.04 schema:affiliation https://www.grid.ac/institutes/grid.79703.3a
83 schema:familyName Ding
84 schema:givenName Jintai
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
86 rdf:type schema:Person
87 sg:person.011566074635.42 schema:affiliation https://www.grid.ac/institutes/grid.410726.6
88 schema:familyName Hu
89 schema:givenName Lei
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011566074635.42
91 rdf:type schema:Person
92 sg:person.014327515441.03 schema:affiliation https://www.grid.ac/institutes/grid.410726.6
93 schema:familyName Cao
94 schema:givenName Weiwei
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014327515441.03
96 rdf:type schema:Person
97 sg:pub.10.1007/11605805_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006462081
98 https://doi.org/10.1007/11605805_9
99 rdf:type schema:CreativeWork
100 sg:pub.10.1007/3-540-44750-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051590862
101 https://doi.org/10.1007/3-540-44750-4_20
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/978-0-387-36946-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026168664
104 https://doi.org/10.1007/978-0-387-36946-4
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-3-540-71677-8_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002694957
107 https://doi.org/10.1007/978-3-540-71677-8_16
108 rdf:type schema:CreativeWork
109 https://app.dimensions.ai/details/publication/pub.1026168664 schema:CreativeWork
110 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1109/tit.1976.1055638 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061647862
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1137/s0097539795293172 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880065
115 rdf:type schema:CreativeWork
116 https://www.grid.ac/institutes/grid.410726.6 schema:alternateName University of Chinese Academy of Sciences
117 schema:name State Key Laboratory of Information Security, Graduate University of Chinese Academy of Sciences, 100049, Beijing, China
118 rdf:type schema:Organization
119 https://www.grid.ac/institutes/grid.54549.39 schema:alternateName University of Electronic Science and Technology of China
120 schema:name School of Computer Science and Engineering, University of Electronic Science and Technology of China, 610054, Chengdu, China
121 rdf:type schema:Organization
122 https://www.grid.ac/institutes/grid.79703.3a schema:alternateName South China University of Technology
123 schema:name Department of Mathematical Sciences, University of Cincinnati, 45221, OH, USA
124 South China University of Technology, 510640, Guangzhou, China
125 rdf:type schema:Organization
 




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


...