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 Nef170255990d4d77a8be6ad91c7e3fa1
    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 N8ba4b21ffd164dbea7e01a2aaa57b25f
    10 schema:genre chapter
    11 schema:inLanguage en
    12 schema:isAccessibleForFree true
    13 schema:isPartOf N9a4bc77a60d2413fbeb15f1eb9a01564
    14 schema:name Solving Underdefined Systems of Multivariate Quadratic Equations
    15 schema:pagination 211-227
    16 schema:productId N25de9efc84c447cbaa0964ea0b632788
    17 N64ad9f54dc314df4a4a9e85d1b2425e2
    18 Nf2c559a35d674171827cbde09c0038d3
    19 schema:publisher N9189c09ec6834d04a296ef82e26d9453
    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 N1bd6d3c13f184604bc2c1f9460289672
    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 N1bd6d3c13f184604bc2c1f9460289672 schema:name Springer Nature - SN SciGraph project
    30 rdf:type schema:Organization
    31 N25de9efc84c447cbaa0964ea0b632788 schema:name readcube_id
    32 schema:value 231ce8236bf5bda30da375f0b1eb7185557b9475c9224f1e601d85931301c2c1
    33 rdf:type schema:PropertyValue
    34 N375f72a00e1f4384b5c12c3adea49a48 rdf:first N61eae62dc0c94fe683955bf8d91c464d
    35 rdf:rest rdf:nil
    36 N3ab7497815dd46b88d577faaf4d7d05d schema:familyName Paillier
    37 schema:givenName Pascal
    38 rdf:type schema:Person
    39 N55d0afabbcd74cba84f9b58ff78c65e0 schema:name FH Aargau, CH-5210 Windisch
    40 rdf:type schema:Organization
    41 N5e35be053944468ba56f9969479b4575 schema:name CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430 Louveciennes Cedex, France
    42 rdf:type schema:Organization
    43 N61eae62dc0c94fe683955bf8d91c464d schema:affiliation N83dea9dfc8c7428d97b2def3f9a2bd6f
    44 schema:familyName Tacier
    45 schema:givenName Jean-Daniel
    46 rdf:type schema:Person
    47 N64ad9f54dc314df4a4a9e85d1b2425e2 schema:name dimensions_id
    48 schema:value pub.1007371554
    49 rdf:type schema:PropertyValue
    50 N7fbf7d7a864f4f03baf7cdd684478ad2 rdf:first N3ab7497815dd46b88d577faaf4d7d05d
    51 rdf:rest rdf:nil
    52 N83dea9dfc8c7428d97b2def3f9a2bd6f schema:name FH Aargau, CH-5210 Windisch
    53 rdf:type schema:Organization
    54 N8ba4b21ffd164dbea7e01a2aaa57b25f rdf:first Nb353cae7658743b5aa84b656a2c0c990
    55 rdf:rest N7fbf7d7a864f4f03baf7cdd684478ad2
    56 N9189c09ec6834d04a296ef82e26d9453 schema:location Berlin, Heidelberg
    57 schema:name Springer Berlin Heidelberg
    58 rdf:type schema:Organisation
    59 N95c47530132d4b61a487595a2cd4f806 schema:name CP8 Crypto Lab, SchlumbergerSema, 36-38 rue de la Princesse, BP45, F-78430 Louveciennes Cedex, France
    60 rdf:type schema:Organization
    61 N9a4bc77a60d2413fbeb15f1eb9a01564 schema:isbn 978-3-540-43168-8
    62 978-3-540-45664-3
    63 schema:name Public Key Cryptography
    64 rdf:type schema:Book
    65 Na75c669eb225440986e6297b6d5d35a1 rdf:first sg:person.07653531142.18
    66 rdf:rest N375f72a00e1f4384b5c12c3adea49a48
    67 Nb353cae7658743b5aa84b656a2c0c990 schema:familyName Naccache
    68 schema:givenName David
    69 rdf:type schema:Person
    70 Ncb69c483cd3f4b61aed253d7c5450981 rdf:first sg:person.015370711241.32
    71 rdf:rest Na75c669eb225440986e6297b6d5d35a1
    72 Nef170255990d4d77a8be6ad91c7e3fa1 rdf:first sg:person.013151403707.45
    73 rdf:rest Ncb69c483cd3f4b61aed253d7c5450981
    74 Nf2c559a35d674171827cbde09c0038d3 schema:name doi
    75 schema:value 10.1007/3-540-45664-3_15
    76 rdf:type schema:PropertyValue
    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 N95c47530132d4b61a487595a2cd4f806
    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 N5e35be053944468ba56f9969479b4575
    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 N55d0afabbcd74cba84f9b58ff78c65e0
    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)


    ...