Solving Underdefined Systems of Multivariate Quadratic Equations View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002

AUTHORS

Nicolas Courtois , Louis Goubin , Willi Meier , Jean-Daniel Tacier

ABSTRACT

The security of several recent digital signature schemes is based on the difficulty of solving large systems of quadratic multivariate polynomial equations over a finite field F. This problem, sometimes called MQ, is known to be NP-hard. When the number m of equations is equal to the number n of variables, and if n < 15, Gröbner base algorithms have been applied to solve MQ. In the overdefined case n 《 m, the techniques of relinearization and XL, due to A. Shamir et. al., have shown to be successful for solving MQ. In signature schemes, we usually have n 》 m. For example signature schemes Flash and Sflash submitted to Nessie call for primitives or the UOV scheme published at Eurocrypt 1999. Little is known about the security of such underdefined systems. In this paper, three new and different methods are presented for solving underdefined multivariate systems of quadratic equations. As already shown at Eurocrypt 1999, the problem MQ becomes polynomial when n ≥ m(m+1) for fields F of characteristic 2. We show that for any field, for about n ≥ 2 m/7(m + 1), exponential but quite small in practice, the problem becomes polynomial in n. When n → m the complexity of all our 3 algorithms tends to q m. However for practical instances of cryptosystems with n ≈ O(m), we show how to achieve complexities significantly lower than exhaustive search. For example we are able break Unbalanced Oil and Vinegar signature schemes for some “bad” choices of the parameters (but not for the parameters proposed in [4]). More... »

PAGES

211-227

References to SciGraph publications

  • 2001. FLASH, a Fast Multivariate Signature Algorithm in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • Book

    TITLE

    Public Key Cryptography

    ISBN

    978-3-540-43168-8
    978-3-540-45664-3

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45664-3_15

    DOI

    http://dx.doi.org/10.1007/3-540-45664-3_15

    DIMENSIONS

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


    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": [
                "CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430\u00a0Louveciennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Courtois", 
            "givenName": "Nicolas", 
            "id": "sg:person.013151403707.45", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430\u00a0Louveciennes Cedex, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goubin", 
            "givenName": "Louis", 
            "id": "sg:person.015370711241.32", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015370711241.32"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "FH Aargau, CH-5210\u00a0Windisch"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Meier", 
            "givenName": "Willi", 
            "id": "sg:person.07653531142.18", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "FH Aargau, CH-5210\u00a0Windisch"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tacier", 
            "givenName": "Jean-Daniel", 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45353-9_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006045667", 
              "https://doi.org/10.1007/3-540-45353-9_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0022-4049(99)00005-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040947089"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002", 
        "datePublishedReg": "2002-01-01", 
        "description": "The security of several recent digital signature schemes is based on the difficulty of solving large systems of quadratic multivariate polynomial equations over a finite field F. This problem, sometimes called MQ, is known to be NP-hard. When the number m of equations is equal to the number n of variables, and if n < 15, Gr\u00f6bner base algorithms have been applied to solve MQ. In the overdefined case n \u300a m, the techniques of relinearization and XL, due to A. Shamir et. al., have shown to be successful for solving MQ. In signature schemes, we usually have n \u300b m. For example signature schemes Flash and Sflash submitted to Nessie call for primitives or the UOV scheme published at Eurocrypt 1999. Little is known about the security of such underdefined systems. In this paper, three new and different methods are presented for solving underdefined multivariate systems of quadratic equations. As already shown at Eurocrypt 1999, the problem MQ becomes polynomial when n \u2265 m(m+1) for fields F of characteristic 2. We show that for any field, for about n \u2265 2 m/7(m + 1), exponential but quite small in practice, the problem becomes polynomial in n. When n \u2192 m the complexity of all our 3 algorithms tends to q m. However for practical instances of cryptosystems with n \u2248 O(m), we show how to achieve complexities significantly lower than exhaustive search. For example we are able break Unbalanced Oil and Vinegar signature schemes for some \u201cbad\u201d choices of the parameters (but not for the parameters proposed in [4]).", 
        "editor": [
          {
            "familyName": "Naccache", 
            "givenName": "David", 
            "type": "Person"
          }, 
          {
            "familyName": "Paillier", 
            "givenName": "Pascal", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45664-3_15", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-43168-8", 
            "978-3-540-45664-3"
          ], 
          "name": "Public Key Cryptography", 
          "type": "Book"
        }, 
        "name": "Solving Underdefined Systems of Multivariate Quadratic Equations", 
        "pagination": "211-227", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45664-3_15"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "231ce8236bf5bda30da375f0b1eb7185557b9475c9224f1e601d85931301c2c1"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1007371554"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45664-3_15", 
          "https://app.dimensions.ai/details/publication/pub.1007371554"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T12:29", 
        "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/0000000001_0000000264/records_8663_00000247.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45664-3_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-45664-3_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-45664-3_15'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45664-3_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-45664-3_15'


     

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

    102 TRIPLES      23 PREDICATES      29 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45664-3_15 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author Ne5e1de4762da447f85d77a23f2cae816
    4 schema:citation sg:pub.10.1007/3-540-45353-9_22
    5 https://doi.org/10.1016/s0022-4049(99)00005-5
    6 schema:datePublished 2002
    7 schema:datePublishedReg 2002-01-01
    8 schema:description The security of several recent digital signature schemes is based on the difficulty of solving large systems of quadratic multivariate polynomial equations over a finite field F. This problem, sometimes called MQ, is known to be NP-hard. When the number m of equations is equal to the number n of variables, and if n < 15, Gröbner base algorithms have been applied to solve MQ. In the overdefined case n 《 m, the techniques of relinearization and XL, due to A. Shamir et. al., have shown to be successful for solving MQ. In signature schemes, we usually have n 》 m. For example signature schemes Flash and Sflash submitted to Nessie call for primitives or the UOV scheme published at Eurocrypt 1999. Little is known about the security of such underdefined systems. In this paper, three new and different methods are presented for solving underdefined multivariate systems of quadratic equations. As already shown at Eurocrypt 1999, the problem MQ becomes polynomial when n ≥ m(m+1) for fields F of characteristic 2. We show that for any field, for about n ≥ 2 m/7(m + 1), exponential but quite small in practice, the problem becomes polynomial in n. When n → m the complexity of all our 3 algorithms tends to q m. However for practical instances of cryptosystems with n ≈ O(m), we show how to achieve complexities significantly lower than exhaustive search. For example we are able break Unbalanced Oil and Vinegar signature schemes for some “bad” choices of the parameters (but not for the parameters proposed in [4]).
    9 schema:editor N8a9de00778f64c89b64aeb62c2509a07
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf Nef31a7886bca4bba9bd31e04c95d34a6
    14 schema:name Solving Underdefined Systems of Multivariate Quadratic Equations
    15 schema:pagination 211-227
    16 schema:productId N80ba1f64d7844d0897745b3ecd0ecca0
    17 Na5c80fabb45d46cab5f49ddcd1f3b1f8
    18 Nd1852ba679d14efb8f28b94d0364394e
    19 schema:publisher Nc25a46efdfaa41bb88cd3dff361fe356
    20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007371554
    21 https://doi.org/10.1007/3-540-45664-3_15
    22 schema:sdDatePublished 2019-04-15T12:29
    23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    24 schema:sdPublisher N418ab8726d06433cbe253c4059cbae79
    25 schema:url http://link.springer.com/10.1007/3-540-45664-3_15
    26 sgo:license sg:explorer/license/
    27 sgo:sdDataset chapters
    28 rdf:type schema:Chapter
    29 N074a6210e55843aa8d0fdbeeeb084e52 schema:name FH Aargau, CH-5210 Windisch
    30 rdf:type schema:Organization
    31 N0ae107e450744b34bfc4b7ade2b2c15e schema:affiliation Ne99caf6f5955485e98a2f68adbfd9b94
    32 schema:familyName Tacier
    33 schema:givenName Jean-Daniel
    34 rdf:type schema:Person
    35 N3fd09394502541d2a7b9db3a11c249f8 rdf:first sg:person.07653531142.18
    36 rdf:rest Na8de5246ade54985a5cf6a26ac615cdc
    37 N418ab8726d06433cbe253c4059cbae79 schema:name Springer Nature - SN SciGraph project
    38 rdf:type schema:Organization
    39 N5459eacb82c8434eabebe63e12416724 rdf:first Nd81383e7cc91422a9cc922eb459b2528
    40 rdf:rest rdf:nil
    41 N692f263172b34097b169b790ba95fd04 rdf:first sg:person.015370711241.32
    42 rdf:rest N3fd09394502541d2a7b9db3a11c249f8
    43 N80ba1f64d7844d0897745b3ecd0ecca0 schema:name dimensions_id
    44 schema:value pub.1007371554
    45 rdf:type schema:PropertyValue
    46 N8a9de00778f64c89b64aeb62c2509a07 rdf:first Ne495908a0e6e44b6be551fcb6474649c
    47 rdf:rest N5459eacb82c8434eabebe63e12416724
    48 Na5c80fabb45d46cab5f49ddcd1f3b1f8 schema:name doi
    49 schema:value 10.1007/3-540-45664-3_15
    50 rdf:type schema:PropertyValue
    51 Na8de5246ade54985a5cf6a26ac615cdc rdf:first N0ae107e450744b34bfc4b7ade2b2c15e
    52 rdf:rest rdf:nil
    53 Nc25a46efdfaa41bb88cd3dff361fe356 schema:location Berlin, Heidelberg
    54 schema:name Springer Berlin Heidelberg
    55 rdf:type schema:Organisation
    56 Nd1852ba679d14efb8f28b94d0364394e schema:name readcube_id
    57 schema:value 231ce8236bf5bda30da375f0b1eb7185557b9475c9224f1e601d85931301c2c1
    58 rdf:type schema:PropertyValue
    59 Nd81383e7cc91422a9cc922eb459b2528 schema:familyName Paillier
    60 schema:givenName Pascal
    61 rdf:type schema:Person
    62 Ne40ab5e005c3461aaae8f52968286c69 schema:name CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430 Louveciennes Cedex, France
    63 rdf:type schema:Organization
    64 Ne495908a0e6e44b6be551fcb6474649c schema:familyName Naccache
    65 schema:givenName David
    66 rdf:type schema:Person
    67 Ne5e1de4762da447f85d77a23f2cae816 rdf:first sg:person.013151403707.45
    68 rdf:rest N692f263172b34097b169b790ba95fd04
    69 Ne99caf6f5955485e98a2f68adbfd9b94 schema:name FH Aargau, CH-5210 Windisch
    70 rdf:type schema:Organization
    71 Nef31a7886bca4bba9bd31e04c95d34a6 schema:isbn 978-3-540-43168-8
    72 978-3-540-45664-3
    73 schema:name Public Key Cryptography
    74 rdf:type schema:Book
    75 Nf5fdb80cdaf84c08a3a7eeaff14faa85 schema:name CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430 Louveciennes Cedex, France
    76 rdf:type schema:Organization
    77 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    78 schema:name Information and Computing Sciences
    79 rdf:type schema:DefinedTerm
    80 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    81 schema:name Data Format
    82 rdf:type schema:DefinedTerm
    83 sg:person.013151403707.45 schema:affiliation Ne40ab5e005c3461aaae8f52968286c69
    84 schema:familyName Courtois
    85 schema:givenName Nicolas
    86 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45
    87 rdf:type schema:Person
    88 sg:person.015370711241.32 schema:affiliation Nf5fdb80cdaf84c08a3a7eeaff14faa85
    89 schema:familyName Goubin
    90 schema:givenName Louis
    91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015370711241.32
    92 rdf:type schema:Person
    93 sg:person.07653531142.18 schema:affiliation N074a6210e55843aa8d0fdbeeeb084e52
    94 schema:familyName Meier
    95 schema:givenName Willi
    96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
    97 rdf:type schema:Person
    98 sg:pub.10.1007/3-540-45353-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006045667
    99 https://doi.org/10.1007/3-540-45353-9_22
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/s0022-4049(99)00005-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040947089
    102 rdf:type schema:CreativeWork
     




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


    ...