Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Weiwei Cao , Lei Hu , Jintai Ding , Zhijun Yin

ABSTRACT

The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m + n variables over a finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document}. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d = n − m = 0 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0 < d < m and d is small with a complexity of O(qd − 1m4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al’s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(qd + 1m4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2. More... »

PAGES

168-180

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-21031-0_13

DOI

http://dx.doi.org/10.1007/978-3-642-21031-0_13

DIMENSIONS

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


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": "State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, 100049, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.9227.e", 
          "name": [
            "State Key Laboratory of Information Security, Graduate School 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": "State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, 100049, Beijing, China", 
          "id": "http://www.grid.ac/institutes/grid.9227.e", 
          "name": [
            "State Key Laboratory of Information Security, Graduate School 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, 510640, Guangzhou, China", 
          "id": "http://www.grid.ac/institutes/grid.79703.3a", 
          "name": [
            "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"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Cincinnati, 45221, OH, USA", 
          "id": "http://www.grid.ac/institutes/grid.24827.3b", 
          "name": [
            "University of Cincinnati, 45221, OH, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yin", 
        "givenName": "Zhijun", 
        "id": "sg:person.015543205727.71", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015543205727.71"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2011", 
    "datePublishedReg": "2011-01-01", 
    "description": "The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m\u2009+\u2009n variables over a finite field \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$\\mathbb{F}_q$\\end{document}. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d\u2009=\u2009n\u2009\u2212\u2009m\u2009=\u20090 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0\u2009<\u2009d\u2009<\u2009m and d is small with a complexity of O(qd\u2009\u2212\u20091m4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al\u2019s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(qd\u2009+\u20091m4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2.", 
    "editor": [
      {
        "familyName": "Bao", 
        "givenName": "Feng", 
        "type": "Person"
      }, 
      {
        "familyName": "Weng", 
        "givenName": "Jian", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-21031-0_13", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-642-21030-3", 
        "978-3-642-21031-0"
      ], 
      "name": "Information Security Practice and Experience", 
      "type": "Book"
    }, 
    "keywords": [
      "Kipnis-Shamir attack", 
      "finite field", 
      "Kipnis et al", 
      "quadratic equation", 
      "quadratic polynomial", 
      "small odd number", 
      "search method", 
      "Ding et al", 
      "scheme", 
      "equivalent keys", 
      "et al", 
      "unbalanced case", 
      "polynomials", 
      "equations", 
      "complexity", 
      "odd number", 
      "Kipnis", 
      "original work", 
      "alternative method", 
      "set", 
      "variables", 
      "cryptosytem", 
      "matrix", 
      "field", 
      "situation", 
      "Shamir", 
      "al", 
      "cases", 
      "key recovery attack", 
      "experimental observations", 
      "public key", 
      "field characteristics", 
      "number", 
      "key", 
      "attacks", 
      "work", 
      "recovery attack", 
      "observations", 
      "characteristics", 
      "method", 
      "paper", 
      "Oil-Vinegar scheme", 
      "balanced Oil-Vinegar scheme", 
      "Kipnis el al\u2019s attack", 
      "el al\u2019s attack", 
      "al\u2019s attack", 
      "Kipnis-Shamir method", 
      "equivalent key recovery attack", 
      "important experimental observations", 
      "Unbalanced Oil-Vinegar Scheme"
    ], 
    "name": "Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme", 
    "pagination": "168-180", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1009997768"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-21031-0_13"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-21031-0_13", 
      "https://app.dimensions.ai/details/publication/pub.1009997768"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:03", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_283.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-21031-0_13"
  }
]
 

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-21031-0_13'

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-21031-0_13'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-21031-0_13'

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-21031-0_13'


 

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

143 TRIPLES      23 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-21031-0_13 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N6a840cc175c34efea62eff989e05e7d1
4 schema:datePublished 2011
5 schema:datePublishedReg 2011-01-01
6 schema:description The public key of the Oil-Vinegar scheme consists of a set of m quadratic equations in m + n variables over a finite field \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$\mathbb{F}_q$\end{document}. Kipnis and Shamir broke the balanced Oil-Vinegar scheme where d = n − m = 0 by finding equivalent keys of the cryptosytem. Later their method was extended by Kipnis et al to attack the unbalanced case where 0 < d < m and d is small with a complexity of O(qd − 1m4). This method uses the matrices associated with the quadratic polynomials in the public key, which needs to be symmetric and invertible. In this paper, we give an optimized search method for Kipnis el al’s attack. Moreover, for the case that the finite field is of characteristic 2, we find the situation becomes very subtle, which, however, was totally neglected in the original work of Kipnis et al. We show that the Kipnis-Shamir method does not work if the field characteristic is 2 and d is a small odd number, and we fix the situation by proposing an alternative method and give an equivalent key recovery attack of complexity O(qd + 1m4). We also prove an important experimental observation by Ding et al for the Kipnis-Shamir attack on balanced Oil-Vinegar schemes in characteristic 2.
7 schema:editor N6199113a190d47fbbc596a2365bdadd2
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N1cbc112e464d46e5b0e6e481c8e56ea9
12 schema:keywords Ding et al
13 Kipnis
14 Kipnis el al’s attack
15 Kipnis et al
16 Kipnis-Shamir attack
17 Kipnis-Shamir method
18 Oil-Vinegar scheme
19 Shamir
20 Unbalanced Oil-Vinegar Scheme
21 al
22 alternative method
23 al’s attack
24 attacks
25 balanced Oil-Vinegar scheme
26 cases
27 characteristics
28 complexity
29 cryptosytem
30 el al’s attack
31 equations
32 equivalent key recovery attack
33 equivalent keys
34 et al
35 experimental observations
36 field
37 field characteristics
38 finite field
39 important experimental observations
40 key
41 key recovery attack
42 matrix
43 method
44 number
45 observations
46 odd number
47 original work
48 paper
49 polynomials
50 public key
51 quadratic equation
52 quadratic polynomial
53 recovery attack
54 scheme
55 search method
56 set
57 situation
58 small odd number
59 unbalanced case
60 variables
61 work
62 schema:name Kipnis-Shamir Attack on Unbalanced Oil-Vinegar Scheme
63 schema:pagination 168-180
64 schema:productId Ne0e1159a45fc4a4383fdcbf5b3fdcd96
65 Nfc93ba9d32b04517a8c869e8a36b5552
66 schema:publisher N67eedd94e2504a60b66633666895a153
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009997768
68 https://doi.org/10.1007/978-3-642-21031-0_13
69 schema:sdDatePublished 2021-12-01T20:03
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N11bbdf1202fa4f829b33195ad469a5b0
72 schema:url https://doi.org/10.1007/978-3-642-21031-0_13
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N11bbdf1202fa4f829b33195ad469a5b0 schema:name Springer Nature - SN SciGraph project
77 rdf:type schema:Organization
78 N1cbc112e464d46e5b0e6e481c8e56ea9 schema:isbn 978-3-642-21030-3
79 978-3-642-21031-0
80 schema:name Information Security Practice and Experience
81 rdf:type schema:Book
82 N4290ba95f99c4ac08d36234385727a57 rdf:first Nf794c113a4e64d1e84e3d2cf5d46a5ff
83 rdf:rest rdf:nil
84 N6199113a190d47fbbc596a2365bdadd2 rdf:first N7bacff404539447bb77c7c257872ac50
85 rdf:rest N4290ba95f99c4ac08d36234385727a57
86 N67eedd94e2504a60b66633666895a153 schema:name Springer Nature
87 rdf:type schema:Organisation
88 N686533bf91aa4632a77c3e534035aa28 rdf:first sg:person.010723403013.04
89 rdf:rest N7894d2deab4042c891845415eaea7037
90 N6a840cc175c34efea62eff989e05e7d1 rdf:first sg:person.014327515441.03
91 rdf:rest Ncf8d21f7e8f843d797455e16b57481db
92 N7894d2deab4042c891845415eaea7037 rdf:first sg:person.015543205727.71
93 rdf:rest rdf:nil
94 N7bacff404539447bb77c7c257872ac50 schema:familyName Bao
95 schema:givenName Feng
96 rdf:type schema:Person
97 Ncf8d21f7e8f843d797455e16b57481db rdf:first sg:person.011566074635.42
98 rdf:rest N686533bf91aa4632a77c3e534035aa28
99 Ne0e1159a45fc4a4383fdcbf5b3fdcd96 schema:name doi
100 schema:value 10.1007/978-3-642-21031-0_13
101 rdf:type schema:PropertyValue
102 Nf794c113a4e64d1e84e3d2cf5d46a5ff schema:familyName Weng
103 schema:givenName Jian
104 rdf:type schema:Person
105 Nfc93ba9d32b04517a8c869e8a36b5552 schema:name dimensions_id
106 schema:value pub.1009997768
107 rdf:type schema:PropertyValue
108 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information and Computing Sciences
110 rdf:type schema:DefinedTerm
111 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
112 schema:name Data Format
113 rdf:type schema:DefinedTerm
114 sg:person.010723403013.04 schema:affiliation grid-institutes:grid.79703.3a
115 schema:familyName Ding
116 schema:givenName Jintai
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010723403013.04
118 rdf:type schema:Person
119 sg:person.011566074635.42 schema:affiliation grid-institutes:grid.9227.e
120 schema:familyName Hu
121 schema:givenName Lei
122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011566074635.42
123 rdf:type schema:Person
124 sg:person.014327515441.03 schema:affiliation grid-institutes:grid.9227.e
125 schema:familyName Cao
126 schema:givenName Weiwei
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014327515441.03
128 rdf:type schema:Person
129 sg:person.015543205727.71 schema:affiliation grid-institutes:grid.24827.3b
130 schema:familyName Yin
131 schema:givenName Zhijun
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015543205727.71
133 rdf:type schema:Person
134 grid-institutes:grid.24827.3b schema:alternateName University of Cincinnati, 45221, OH, USA
135 schema:name University of Cincinnati, 45221, OH, USA
136 rdf:type schema:Organization
137 grid-institutes:grid.79703.3a schema:alternateName South China University of Technology, 510640, Guangzhou, China
138 schema:name South China University of Technology, 510640, Guangzhou, China
139 University of Cincinnati, 45221, OH, USA
140 rdf:type schema:Organization
141 grid-institutes:grid.9227.e schema:alternateName State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, 100049, Beijing, China
142 schema:name State Key Laboratory of Information Security, Graduate School of Chinese Academy of Sciences, 100049, Beijing, China
143 rdf:type schema:Organization
 




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


...