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

References to SciGraph publications

  • 2001-07-13. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’96
  • 1997. Trapdoor one-way permutations and multivariate polynomials in INFORMATION AND COMMUNICATIONS SECURITY
  • 2002-09-24. C−+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai in ADVANCES IN CRYPTOLOGY — ASIACRYPT’98
  • 1988. Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’88
  • 1995. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 in ADVANCES IN CRYPTOLOGY — CRYPT0’ 95
  • 1998. Cryptanalysis of the oil and vinegar signature scheme in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 1986. Analysis of a Public Key Approach Based on Polynomial Substitution in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
  • 2001-07-13. Asymmetric Cryptography with a Hidden Monomial in ADVANCES IN CRYPTOLOGY — CRYPTO ’96
  • 1998. Improved algorithms for isomorphisms of polynomials in ADVANCES IN CRYPTOLOGY — EUROCRYPT'98
  • Book

    TITLE

    Advances in Cryptology — EUROCRYPT ’99

    ISBN

    978-3-540-65889-4
    978-3-540-48910-8

    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/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": {
              "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": {
              "name": [
                "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Patarin", 
            "givenName": "Jacques", 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goubin", 
            "givenName": "Louis", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-39799-x_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009274988", 
              "https://doi.org/10.1007/3-540-39799-x_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0028491", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014519443", 
              "https://doi.org/10.1007/bfb0028491"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0055733", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016241801", 
              "https://doi.org/10.1007/bfb0055733"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0054126", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035038711", 
              "https://doi.org/10.1007/bfb0054126"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45961-8_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035601256", 
              "https://doi.org/10.1007/3-540-45961-8_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49649-1_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038271412", 
              "https://doi.org/10.1007/3-540-49649-1_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-49649-1_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038271412", 
              "https://doi.org/10.1007/3-540-49649-1_4"
            ], 
            "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": "sg:pub.10.1007/3-540-68339-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051894160", 
              "https://doi.org/10.1007/3-540-68339-9_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68339-9_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051894160", 
              "https://doi.org/10.1007/3-540-68339-9_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68697-5_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053126301", 
              "https://doi.org/10.1007/3-540-68697-5_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68697-5_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053126301", 
              "https://doi.org/10.1007/3-540-68697-5_4"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "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"
        }, 
        "name": "Unbalanced Oil and Vinegar Signature Schemes", 
        "pagination": "206-222", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-48910-x_15"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "623a09d0d5d5ae28ce52ee43c55cbca5108165167ace74e10821ae20af2fc6f1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1020614953"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-48910-x_15", 
          "https://app.dimensions.ai/details/publication/pub.1020614953"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T05:37", 
        "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/0000000346_0000000346/records_99839_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F3-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.

    116 TRIPLES      23 PREDICATES      35 URIs      19 LITERALS      8 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 N4f035b63565441579a24ab583aa96bea
    4 schema:citation sg:pub.10.1007/3-540-39799-x_24
    5 sg:pub.10.1007/3-540-44750-4_20
    6 sg:pub.10.1007/3-540-45961-8_39
    7 sg:pub.10.1007/3-540-49649-1_4
    8 sg:pub.10.1007/3-540-68339-9_4
    9 sg:pub.10.1007/3-540-68697-5_4
    10 sg:pub.10.1007/bfb0028491
    11 sg:pub.10.1007/bfb0054126
    12 sg:pub.10.1007/bfb0055733
    13 schema:datePublished 1999-04-15
    14 schema:datePublishedReg 1999-04-15
    15 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.
    16 schema:editor Nd41d9a39fa7848bdaf358aea3c3ac32f
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N3028bf7d8ab347e78cea925f95cd7f59
    21 schema:name Unbalanced Oil and Vinegar Signature Schemes
    22 schema:pagination 206-222
    23 schema:productId Nb948d4ac875a4629a758028137c0a906
    24 Ndccd8fb8cf7b4ab59253ba302eb11bd0
    25 Nf44b79579ce74115bf1bb8ec65813f9f
    26 schema:publisher Na471f80712574b4b9c6c085f73759010
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020614953
    28 https://doi.org/10.1007/3-540-48910-x_15
    29 schema:sdDatePublished 2019-04-16T05:37
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher Nd1ca421c19294a30967bbef9c03d2baf
    32 schema:url https://link.springer.com/10.1007%2F3-540-48910-X_15
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N0b7e31d8a1ea4e149444b52fec0bb809 schema:affiliation Na354f5a83b4040939e6f3149e8663f4d
    37 schema:familyName Goubin
    38 schema:givenName Louis
    39 rdf:type schema:Person
    40 N1c313e5ee17449cd889d76da6b4f499f schema:name Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France
    41 rdf:type schema:Organization
    42 N3028bf7d8ab347e78cea925f95cd7f59 schema:isbn 978-3-540-48910-8
    43 978-3-540-65889-4
    44 schema:name Advances in Cryptology — EUROCRYPT ’99
    45 rdf:type schema:Book
    46 N39f584f4b63e41b2961daf7f51abd836 rdf:first N0b7e31d8a1ea4e149444b52fec0bb809
    47 rdf:rest rdf:nil
    48 N4f035b63565441579a24ab583aa96bea rdf:first sg:person.016464474377.73
    49 rdf:rest N5379ecd2faf34c4185083cdba8e9ff4c
    50 N5379ecd2faf34c4185083cdba8e9ff4c rdf:first N8d7805e5953f46e3bb07a33949a9347f
    51 rdf:rest N39f584f4b63e41b2961daf7f51abd836
    52 N8d7805e5953f46e3bb07a33949a9347f schema:affiliation N1c313e5ee17449cd889d76da6b4f499f
    53 schema:familyName Patarin
    54 schema:givenName Jacques
    55 rdf:type schema:Person
    56 Na354f5a83b4040939e6f3149e8663f4d schema:name Bull SmartCards and Terminals, 68 route de Versailles - BP45, 78431, Louveciennes Cedex, France
    57 rdf:type schema:Organization
    58 Na471f80712574b4b9c6c085f73759010 schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 Nb948d4ac875a4629a758028137c0a906 schema:name doi
    62 schema:value 10.1007/3-540-48910-x_15
    63 rdf:type schema:PropertyValue
    64 Ncb9fb54fcfbc47b89b976ad84147b5c5 schema:name NDS Technologies, 5 Hamarpe St., Har Hotzvim, Jerusalem, Israel
    65 rdf:type schema:Organization
    66 Nd1ca421c19294a30967bbef9c03d2baf schema:name Springer Nature - SN SciGraph project
    67 rdf:type schema:Organization
    68 Nd41d9a39fa7848bdaf358aea3c3ac32f rdf:first Ne4d9846b31f141e6b90f3e8d283f993d
    69 rdf:rest rdf:nil
    70 Ndccd8fb8cf7b4ab59253ba302eb11bd0 schema:name readcube_id
    71 schema:value 623a09d0d5d5ae28ce52ee43c55cbca5108165167ace74e10821ae20af2fc6f1
    72 rdf:type schema:PropertyValue
    73 Ne4d9846b31f141e6b90f3e8d283f993d schema:familyName Stern
    74 schema:givenName Jacques
    75 rdf:type schema:Person
    76 Nf44b79579ce74115bf1bb8ec65813f9f schema:name dimensions_id
    77 schema:value pub.1020614953
    78 rdf:type schema:PropertyValue
    79 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    80 schema:name Information and Computing Sciences
    81 rdf:type schema:DefinedTerm
    82 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    83 schema:name Data Format
    84 rdf:type schema:DefinedTerm
    85 sg:person.016464474377.73 schema:affiliation Ncb9fb54fcfbc47b89b976ad84147b5c5
    86 schema:familyName Kipnis
    87 schema:givenName Aviad
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016464474377.73
    89 rdf:type schema:Person
    90 sg:pub.10.1007/3-540-39799-x_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009274988
    91 https://doi.org/10.1007/3-540-39799-x_24
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/3-540-44750-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051590862
    94 https://doi.org/10.1007/3-540-44750-4_20
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
    97 https://doi.org/10.1007/3-540-45961-8_39
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/3-540-49649-1_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038271412
    100 https://doi.org/10.1007/3-540-49649-1_4
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
    103 https://doi.org/10.1007/3-540-68339-9_4
    104 rdf:type schema:CreativeWork
    105 sg:pub.10.1007/3-540-68697-5_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053126301
    106 https://doi.org/10.1007/3-540-68697-5_4
    107 rdf:type schema:CreativeWork
    108 sg:pub.10.1007/bfb0028491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014519443
    109 https://doi.org/10.1007/bfb0028491
    110 rdf:type schema:CreativeWork
    111 sg:pub.10.1007/bfb0054126 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035038711
    112 https://doi.org/10.1007/bfb0054126
    113 rdf:type schema:CreativeWork
    114 sg:pub.10.1007/bfb0055733 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016241801
    115 https://doi.org/10.1007/bfb0055733
    116 rdf:type schema:CreativeWork
     




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


    ...