Unbalanced Oil and Vinegar Signature Schemes View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1999-04-15

AUTHORS

Aviad Kipnis , Jacques Patarin , Louis Goubin

ABSTRACT

In [16], J. Patarin designed a new scheme, called “Oil and Vinegar”, for computing asymmetric signatures. It is very simple, can be computed very fast (both in secret and public key) and requires very little RAM in smartcard implementations. The idea consists in hiding quadratic equations in n unknowns called “oil” and v = n unknowns called “vinegar” over a finite field K, with linear secret functions. This original scheme was broken in [10] by A. Kipnis and A. Shamir. In this paper, we study some very simple variations of the original scheme where v > n (instead of v = n). These schemes are called “Unbalanced Oil and Vinegar” (UOV), since we have more “vinegar” unknowns than “oil” unknowns. We show that, when v ⋍ n, the attack of [10] can be extended, but when v ≥ 2n for example, the security of the scheme is still an open problem. Moreover, when , the security of the scheme is exactly equivalent (if we accept a very natural but not proved property) to the problem of solving a random set of n quadratic equations in unknowns (with no trapdoor). However, we show that (in characteristic 2) when v ≥ n2, finding a solution is generally easy. Then we will see that it is very easy to combine the Oil and Vinegar idea and the HFE schemes of [14]. The resulting scheme, called HFEV, looks at the present also very interesting both from a practical and theoretical point of view. The length of a UOV signature can be as short as 192 bits and for HFEV it can be as short as 80 bits. More... »

PAGES

206-222

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-48910-x_15

DOI

http://dx.doi.org/10.1007/3-540-48910-x_15

DIMENSIONS

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


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": "NDS Technologies, 5 Hamarpe St., Har Hotzvim, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "NDS Technologies, 5 Hamarpe St., Har Hotzvim, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kipnis", 
        "givenName": "Aviad", 
        "id": "sg:person.016464474377.73", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464474377.73"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "id": "sg:person.012254315647.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012254315647.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goubin", 
        "givenName": "Louis", 
        "type": "Person"
      }
    ], 
    "datePublished": "1999-04-15", 
    "datePublishedReg": "1999-04-15", 
    "description": "In [16], J. Patarin designed a new scheme, called \u201cOil and Vinegar\u201d, for computing asymmetric signatures. It is very simple, can be computed very fast (both in secret and public key) and requires very little RAM in smartcard implementations. The idea consists in hiding quadratic equations in n unknowns called \u201coil\u201d and v = n unknowns called \u201cvinegar\u201d over a finite field K, with linear secret functions. This original scheme was broken in [10] by A. Kipnis and A. Shamir. In this paper, we study some very simple variations of the original scheme where v > n (instead of v = n). These schemes are called \u201cUnbalanced Oil and Vinegar\u201d (UOV), since we have more \u201cvinegar\u201d unknowns than \u201coil\u201d unknowns. We show that, when v \u22cd n, the attack of [10] can be extended, but when v \u2265 2n for example, the security of the scheme is still an open problem. Moreover, when , the security of the scheme is exactly equivalent (if we accept a very natural but not proved property) to the problem of solving a random set of n quadratic equations in unknowns (with no trapdoor). However, we show that (in characteristic 2) when v \u2265 n2, finding a solution is generally easy. Then we will see that it is very easy to combine the Oil and Vinegar idea and the HFE schemes of [14]. The resulting scheme, called HFEV, looks at the present also very interesting both from a practical and theoretical point of view. The length of a UOV signature can be as short as 192 bits and for HFEV it can be as short as 80 bits.", 
    "editor": [
      {
        "familyName": "Stern", 
        "givenName": "Jacques", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-48910-x_15", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65889-4", 
        "978-3-540-48910-8"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT \u201999", 
      "type": "Book"
    }, 
    "keywords": [
      "quadratic equation", 
      "Unbalanced Oil", 
      "finite field k", 
      "Vinegar (UOV) signature scheme", 
      "HFE scheme", 
      "field K", 
      "original scheme", 
      "random set", 
      "UOV signature", 
      "open problem", 
      "little RAM", 
      "unknowns", 
      "secret function", 
      "equations", 
      "smartcard implementations", 
      "scheme", 
      "new scheme", 
      "HFEv", 
      "theoretical point", 
      "problem", 
      "asymmetric signature", 
      "Patarin", 
      "Kipnis", 
      "idea", 
      "solution", 
      "set", 
      "simple variation", 
      "bits", 
      "function", 
      "point", 
      "implementation", 
      "Shamir", 
      "security", 
      "view", 
      "signature scheme", 
      "variation", 
      "signatures", 
      "length", 
      "rams", 
      "attacks", 
      "present", 
      "oil", 
      "vinegar", 
      "N2", 
      "example", 
      "paper", 
      "linear secret functions", 
      "Vinegar idea"
    ], 
    "name": "Unbalanced Oil and Vinegar Signature Schemes", 
    "pagination": "206-222", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1020614953"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-48910-x_15"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-48910-x_15", 
      "https://app.dimensions.ai/details/publication/pub.1020614953"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:07", 
    "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_377.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-48910-x_15"
  }
]
 

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/3-540-48910-x_15'

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-48910-x_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-48910-x_15'

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-48910-x_15'


 

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

123 TRIPLES      23 PREDICATES      73 URIs      66 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-48910-x_15 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Na53c6ccf71d74370b737d101468f3be7
4 schema:datePublished 1999-04-15
5 schema:datePublishedReg 1999-04-15
6 schema:description In [16], J. Patarin designed a new scheme, called “Oil and Vinegar”, for computing asymmetric signatures. It is very simple, can be computed very fast (both in secret and public key) and requires very little RAM in smartcard implementations. The idea consists in hiding quadratic equations in n unknowns called “oil” and v = n unknowns called “vinegar” over a finite field K, with linear secret functions. This original scheme was broken in [10] by A. Kipnis and A. Shamir. In this paper, we study some very simple variations of the original scheme where v > n (instead of v = n). These schemes are called “Unbalanced Oil and Vinegar” (UOV), since we have more “vinegar” unknowns than “oil” unknowns. We show that, when v ⋍ n, the attack of [10] can be extended, but when v ≥ 2n for example, the security of the scheme is still an open problem. Moreover, when , the security of the scheme is exactly equivalent (if we accept a very natural but not proved property) to the problem of solving a random set of n quadratic equations in unknowns (with no trapdoor). However, we show that (in characteristic 2) when v ≥ n2, finding a solution is generally easy. Then we will see that it is very easy to combine the Oil and Vinegar idea and the HFE schemes of [14]. The resulting scheme, called HFEV, looks at the present also very interesting both from a practical and theoretical point of view. The length of a UOV signature can be as short as 192 bits and for HFEV it can be as short as 80 bits.
7 schema:editor N126d947ea29f47fe9517aa4a80c71435
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nea016397342942de81bd529238c57264
12 schema:keywords HFE scheme
13 HFEv
14 Kipnis
15 N2
16 Patarin
17 Shamir
18 UOV signature
19 Unbalanced Oil
20 Vinegar (UOV) signature scheme
21 Vinegar idea
22 asymmetric signature
23 attacks
24 bits
25 equations
26 example
27 field K
28 finite field k
29 function
30 idea
31 implementation
32 length
33 linear secret functions
34 little RAM
35 new scheme
36 oil
37 open problem
38 original scheme
39 paper
40 point
41 present
42 problem
43 quadratic equation
44 rams
45 random set
46 scheme
47 secret function
48 security
49 set
50 signature scheme
51 signatures
52 simple variation
53 smartcard implementations
54 solution
55 theoretical point
56 unknowns
57 variation
58 view
59 vinegar
60 schema:name Unbalanced Oil and Vinegar Signature Schemes
61 schema:pagination 206-222
62 schema:productId Na1ce47e5b49c43f1906d3fa8cfd3db66
63 Ne9454f60bd754f21b5d94dbe85f2aec5
64 schema:publisher N05cb1e60f306421397e1a1199da8f690
65 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020614953
66 https://doi.org/10.1007/3-540-48910-x_15
67 schema:sdDatePublished 2021-12-01T20:07
68 schema:sdLicense https://scigraph.springernature.com/explorer/license/
69 schema:sdPublisher Ne80c09c4f5ec47579c8117ffe54b9786
70 schema:url https://doi.org/10.1007/3-540-48910-x_15
71 sgo:license sg:explorer/license/
72 sgo:sdDataset chapters
73 rdf:type schema:Chapter
74 N05cb1e60f306421397e1a1199da8f690 schema:name Springer Nature
75 rdf:type schema:Organisation
76 N0db6ebc7ed5140cbbc2dc2361e6cb267 schema:affiliation grid-institutes:None
77 schema:familyName Goubin
78 schema:givenName Louis
79 rdf:type schema:Person
80 N126d947ea29f47fe9517aa4a80c71435 rdf:first Nb9998fa17c6d4330bfc7a99b3a341787
81 rdf:rest rdf:nil
82 N2fa177e6b9bb410daeb9ff4564fb7956 rdf:first N0db6ebc7ed5140cbbc2dc2361e6cb267
83 rdf:rest rdf:nil
84 Na1ce47e5b49c43f1906d3fa8cfd3db66 schema:name doi
85 schema:value 10.1007/3-540-48910-x_15
86 rdf:type schema:PropertyValue
87 Na53c6ccf71d74370b737d101468f3be7 rdf:first sg:person.016464474377.73
88 rdf:rest Nf9b1730d5ba7460d914132c24adc4f41
89 Nb9998fa17c6d4330bfc7a99b3a341787 schema:familyName Stern
90 schema:givenName Jacques
91 rdf:type schema:Person
92 Ne80c09c4f5ec47579c8117ffe54b9786 schema:name Springer Nature - SN SciGraph project
93 rdf:type schema:Organization
94 Ne9454f60bd754f21b5d94dbe85f2aec5 schema:name dimensions_id
95 schema:value pub.1020614953
96 rdf:type schema:PropertyValue
97 Nea016397342942de81bd529238c57264 schema:isbn 978-3-540-48910-8
98 978-3-540-65889-4
99 schema:name Advances in Cryptology — EUROCRYPT ’99
100 rdf:type schema:Book
101 Nf9b1730d5ba7460d914132c24adc4f41 rdf:first sg:person.012254315647.07
102 rdf:rest N2fa177e6b9bb410daeb9ff4564fb7956
103 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
104 schema:name Information and Computing Sciences
105 rdf:type schema:DefinedTerm
106 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
107 schema:name Data Format
108 rdf:type schema:DefinedTerm
109 sg:person.012254315647.07 schema:affiliation grid-institutes:None
110 schema:familyName Patarin
111 schema:givenName Jacques
112 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012254315647.07
113 rdf:type schema:Person
114 sg:person.016464474377.73 schema:affiliation grid-institutes:None
115 schema:familyName Kipnis
116 schema:givenName Aviad
117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464474377.73
118 rdf:type schema:Person
119 grid-institutes:None schema:alternateName Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France
120 NDS Technologies, 5 Hamarpe St., Har Hotzvim, Jerusalem, Israel
121 schema:name Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France
122 NDS Technologies, 5 Hamarpe St., Har Hotzvim, Jerusalem, Israel
123 rdf:type schema:Organization
 




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


...