Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Bo-Yin Yang , Jiun-Ming Chen

ABSTRACT

Multivariate public-key cryptosystems (sometimes polynomial-based PKC’s or just multivariates) handle polynomials of many variables over relatively small fields instead of elements of a large ring or group. The “tame-like” or “sparse” class of multivariates are distinguished by the relatively few terms that they have per central equation. We explain how they differ from the “big-field” type of multivariates, represented by derivatives of C ∗ and HFE, how they are better, and give basic security criteria for them. The last is shown to be satisfied by efficient schemes called “Enhanced TTS” which is built on a combination of the Oil-and-Vinegar and Triangular ideas. Their security levels are estimated. In this process we summarize and in some cases, improve rank-based attacks, which seek linear combinations of certain matrices at given ranks. These attacks are responsible for breaking many prior multivariate designs. More... »

PAGES

518-531

References to SciGraph publications

  • 2005. A Study of the Security of Unbalanced Oil and Vinegar Signature Schemes in TOPICS IN CRYPTOLOGY – CT-RSA 2005
  • 2001. FLASH, a Fast Multivariate Signature Algorithm in TOPICS IN CRYPTOLOGY — CT-RSA 2001
  • 2005. Cryptanalysis of the Tractable Rational Map Cryptosystem in PUBLIC KEY CRYPTOGRAPHY - PKC 2005
  • 1999. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization in ADVANCES IN CRYPTOLOGY — CRYPTO’ 99
  • 2005. Rainbow, a New Multivariable Polynomial Signature Scheme in ROBOCUP 2005: ROBOT SOCCER WORLD CUP IX
  • 2004. A More Secure and Efficacious TTS Signature Scheme in INFORMATION SECURITY AND CRYPTOLOGY - ICISC 2003
  • 2000. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2000
  • 2002. Solving Underdefined Systems of Multivariate Quadratic Equations in PUBLIC KEY CRYPTOGRAPHY
  • 2003. Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gröbner Bases in ADVANCES IN CRYPTOLOGY - CRYPTO 2003
  • 2000. Cryptanalysis of the TTM Cryptosystem in ADVANCES IN CRYPTOLOGY — ASIACRYPT 2000
  • 1995. Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 in ADVANCES IN CRYPTOLOGY — CRYPT0’ 95
  • 2004. The XL-Algorithm and a Conjecture from Commutative Algebra in ADVANCES IN CRYPTOLOGY - ASIACRYPT 2004
  • 2005. Efficient Cryptanalysis of RSE(2)PKC and RSSE(2)PKC in SECURITY IN COMMUNICATION NETWORKS
  • 2005. All in the XL Family: Theory and Practice in INFORMATION SECURITY AND CRYPTOLOGY – ICISC 2004
  • 2005. Cryptanalysis of HFEv and Internal Perturbation of HFE in PUBLIC KEY CRYPTOGRAPHY - PKC 2005
  • 2005. Tractable Rational Map Signature in PUBLIC KEY CRYPTOGRAPHY - PKC 2005
  • 2001-07-13. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’96
  • 2004. TTS: High-Speed Signatures on a Low-Cost Smart Card in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2004
  • 2004. Strong Authentication for RFID Systems Using the AES Algorithm in CRYPTOGRAPHIC HARDWARE AND EMBEDDED SYSTEMS - CHES 2004
  • 1988. Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’88
  • 1994. Attacks on the Birational Permutation Signature Schemes in ADVANCES IN CRYPTOLOGY — CRYPTO’ 93
  • 1998. Cryptanalysis of the oil and vinegar signature scheme in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 1999-04-15. Unbalanced Oil and Vinegar Signature Schemes in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’99
  • Book

    TITLE

    Information Security and Privacy

    ISBN

    978-3-540-26547-4
    978-3-540-31684-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11506157_43

    DOI

    http://dx.doi.org/10.1007/11506157_43

    DIMENSIONS

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


    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": {
              "alternateName": "Tamkang University", 
              "id": "https://www.grid.ac/institutes/grid.264580.d", 
              "name": [
                "Dept. of Mathematics, Tamkang University, Tamsui, Taiwan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yang", 
            "givenName": "Bo-Yin", 
            "id": "sg:person.010017213117.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017213117.39"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Chinese Data Security, Inc., & Nat\u2019l Taiwan U., Taipei"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chen", 
            "givenName": "Jiun-Ming", 
            "id": "sg:person.010552153601.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010552153601.77"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45539-6_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000285811", 
              "https://doi.org/10.1007/3-540-45539-6_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30598-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003321122", 
              "https://doi.org/10.1007/978-3-540-30598-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30598-9_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003321122", 
              "https://doi.org/10.1007/978-3-540-30598-9_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11496618_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004218140", 
              "https://doi.org/10.1007/11496618_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11496618_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004218140", 
              "https://doi.org/10.1007/11496618_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "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": "sg:pub.10.1007/3-540-45664-3_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007371554", 
              "https://doi.org/10.1007/3-540-45664-3_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/780506.780516", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007436250"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/00927879908826559", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008867318"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24691-6_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013746886", 
              "https://doi.org/10.1007/978-3-540-24691-6_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014916110", 
              "https://doi.org/10.1007/978-3-540-28632-5_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014916110", 
              "https://doi.org/10.1007/978-3-540-28632-5_26"
            ], 
            "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/3-540-48910-x_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020614953", 
              "https://doi.org/10.1007/3-540-48910-x_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48910-x_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020614953", 
              "https://doi.org/10.1007/3-540-48910-x_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028452893", 
              "https://doi.org/10.1007/978-3-540-30580-4_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028452893", 
              "https://doi.org/10.1007/978-3-540-30580-4_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031254011", 
              "https://doi.org/10.1007/978-3-540-28632-5_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-28632-5_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031254011", 
              "https://doi.org/10.1007/978-3-540-28632-5_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032831457", 
              "https://doi.org/10.1007/978-3-540-30580-4_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_20", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032831457", 
              "https://doi.org/10.1007/978-3-540-30580-4_20"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11496137_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033985068", 
              "https://doi.org/10.1007/11496137_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11496137_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033985068", 
              "https://doi.org/10.1007/11496137_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11496137_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033985068", 
              "https://doi.org/10.1007/11496137_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034073611", 
              "https://doi.org/10.1007/978-3-540-30574-3_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034073611", 
              "https://doi.org/10.1007/978-3-540-30574-3_4"
            ], 
            "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/978-3-540-30580-4_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042849207", 
              "https://doi.org/10.1007/978-3-540-30580-4_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30580-4_18", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042849207", 
              "https://doi.org/10.1007/978-3-540-30580-4_18"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48405-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045972569", 
              "https://doi.org/10.1007/3-540-48405-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-45146-4_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049476263", 
              "https://doi.org/10.1007/978-3-540-45146-4_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48329-2_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049865404", 
              "https://doi.org/10.1007/3-540-48329-2_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30539-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050327206", 
              "https://doi.org/10.1007/978-3-540-30539-2_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30539-2_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050327206", 
              "https://doi.org/10.1007/978-3-540-30539-2_23"
            ], 
            "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-44448-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052740197", 
              "https://doi.org/10.1007/3-540-44448-3_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/237814.237866", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053319325"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1994.365700", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095740049"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "Multivariate public-key cryptosystems (sometimes polynomial-based PKC\u2019s or just multivariates) handle polynomials of many variables over relatively small fields instead of elements of a large ring or group. The \u201ctame-like\u201d or \u201csparse\u201d class of multivariates are distinguished by the relatively few terms that they have per central equation. We explain how they differ from the \u201cbig-field\u201d type of multivariates, represented by derivatives of C \u2217 and HFE, how they are better, and give basic security criteria for them. The last is shown to be satisfied by efficient schemes called \u201cEnhanced TTS\u201d which is built on a combination of the Oil-and-Vinegar and Triangular ideas. Their security levels are estimated. In this process we summarize and in some cases, improve rank-based attacks, which seek linear combinations of certain matrices at given ranks. These attacks are responsible for breaking many prior multivariate designs.", 
        "editor": [
          {
            "familyName": "Boyd", 
            "givenName": "Colin", 
            "type": "Person"
          }, 
          {
            "familyName": "Gonz\u00e1lez Nieto", 
            "givenName": "Juan Manuel", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11506157_43", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-26547-4", 
            "978-3-540-31684-8"
          ], 
          "name": "Information Security and Privacy", 
          "type": "Book"
        }, 
        "name": "Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS", 
        "pagination": "518-531", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033184328"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11506157_43"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9e1597d3e6520967af402980829c2809c3091bbbc5963c66d201b015a5561fc3"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11506157_43", 
          "https://app.dimensions.ai/details/publication/pub.1033184328"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:27", 
        "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/0000000363_0000000363/records_70061_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11506157_43"
      }
    ]
     

    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/11506157_43'

    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/11506157_43'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11506157_43'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11506157_43'


     

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

    183 TRIPLES      23 PREDICATES      54 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11506157_43 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author Nfd61f423376141d89ead59790a8ca9a4
    4 schema:citation sg:pub.10.1007/11496137_12
    5 sg:pub.10.1007/11496618_7
    6 sg:pub.10.1007/3-540-44448-3_4
    7 sg:pub.10.1007/3-540-44750-4_20
    8 sg:pub.10.1007/3-540-45353-9_22
    9 sg:pub.10.1007/3-540-45539-6_27
    10 sg:pub.10.1007/3-540-45664-3_15
    11 sg:pub.10.1007/3-540-45961-8_39
    12 sg:pub.10.1007/3-540-48329-2_37
    13 sg:pub.10.1007/3-540-48405-1_2
    14 sg:pub.10.1007/3-540-48910-x_15
    15 sg:pub.10.1007/3-540-68339-9_4
    16 sg:pub.10.1007/978-3-540-24691-6_24
    17 sg:pub.10.1007/978-3-540-28632-5_26
    18 sg:pub.10.1007/978-3-540-28632-5_27
    19 sg:pub.10.1007/978-3-540-30539-2_23
    20 sg:pub.10.1007/978-3-540-30574-3_4
    21 sg:pub.10.1007/978-3-540-30580-4_17
    22 sg:pub.10.1007/978-3-540-30580-4_18
    23 sg:pub.10.1007/978-3-540-30580-4_20
    24 sg:pub.10.1007/978-3-540-30598-9_21
    25 sg:pub.10.1007/978-3-540-45146-4_3
    26 sg:pub.10.1007/bfb0055733
    27 https://doi.org/10.1080/00927879908826559
    28 https://doi.org/10.1109/sfcs.1994.365700
    29 https://doi.org/10.1145/237814.237866
    30 https://doi.org/10.1145/780506.780516
    31 schema:datePublished 2005
    32 schema:datePublishedReg 2005-01-01
    33 schema:description Multivariate public-key cryptosystems (sometimes polynomial-based PKC’s or just multivariates) handle polynomials of many variables over relatively small fields instead of elements of a large ring or group. The “tame-like” or “sparse” class of multivariates are distinguished by the relatively few terms that they have per central equation. We explain how they differ from the “big-field” type of multivariates, represented by derivatives of C ∗ and HFE, how they are better, and give basic security criteria for them. The last is shown to be satisfied by efficient schemes called “Enhanced TTS” which is built on a combination of the Oil-and-Vinegar and Triangular ideas. Their security levels are estimated. In this process we summarize and in some cases, improve rank-based attacks, which seek linear combinations of certain matrices at given ranks. These attacks are responsible for breaking many prior multivariate designs.
    34 schema:editor N70447f468a514e38a5f20b4e4e942275
    35 schema:genre chapter
    36 schema:inLanguage en
    37 schema:isAccessibleForFree true
    38 schema:isPartOf N69635221ff5a4256a59f6451b15c9210
    39 schema:name Building Secure Tame-like Multivariate Public-Key Cryptosystems: The New TTS
    40 schema:pagination 518-531
    41 schema:productId N12b1ceddac1f4ee1ad06763f16c6663b
    42 N6b7aadbb36a246df8a5b21aa5cc7b5ce
    43 Nd4d5b2749ba749e5b61cd9796326d662
    44 schema:publisher Na6d10f9136ff4d4a96d52c313bcd26f0
    45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033184328
    46 https://doi.org/10.1007/11506157_43
    47 schema:sdDatePublished 2019-04-16T08:27
    48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    49 schema:sdPublisher N6706328e56ed467db76652bb7246a661
    50 schema:url https://link.springer.com/10.1007%2F11506157_43
    51 sgo:license sg:explorer/license/
    52 sgo:sdDataset chapters
    53 rdf:type schema:Chapter
    54 N12b1ceddac1f4ee1ad06763f16c6663b schema:name doi
    55 schema:value 10.1007/11506157_43
    56 rdf:type schema:PropertyValue
    57 N38851f897f1d44e68149cd862767c1be schema:familyName Boyd
    58 schema:givenName Colin
    59 rdf:type schema:Person
    60 N6706328e56ed467db76652bb7246a661 schema:name Springer Nature - SN SciGraph project
    61 rdf:type schema:Organization
    62 N69635221ff5a4256a59f6451b15c9210 schema:isbn 978-3-540-26547-4
    63 978-3-540-31684-8
    64 schema:name Information Security and Privacy
    65 rdf:type schema:Book
    66 N6b7aadbb36a246df8a5b21aa5cc7b5ce schema:name dimensions_id
    67 schema:value pub.1033184328
    68 rdf:type schema:PropertyValue
    69 N70447f468a514e38a5f20b4e4e942275 rdf:first N38851f897f1d44e68149cd862767c1be
    70 rdf:rest Ne7e71614a7894c1db7c02a2751ef5a2b
    71 N9dd1d08d9f57421b8ef3a6257ebd1e25 rdf:first sg:person.010552153601.77
    72 rdf:rest rdf:nil
    73 Na2f5a93a55264d5e91e0979de8df790e schema:familyName González Nieto
    74 schema:givenName Juan Manuel
    75 rdf:type schema:Person
    76 Na6d10f9136ff4d4a96d52c313bcd26f0 schema:location Berlin, Heidelberg
    77 schema:name Springer Berlin Heidelberg
    78 rdf:type schema:Organisation
    79 Nd4d5b2749ba749e5b61cd9796326d662 schema:name readcube_id
    80 schema:value 9e1597d3e6520967af402980829c2809c3091bbbc5963c66d201b015a5561fc3
    81 rdf:type schema:PropertyValue
    82 Ne7e71614a7894c1db7c02a2751ef5a2b rdf:first Na2f5a93a55264d5e91e0979de8df790e
    83 rdf:rest rdf:nil
    84 Ne9273bbe00c94078b92cbec5fc9bbc26 schema:name Chinese Data Security, Inc., & Nat’l Taiwan U., Taipei
    85 rdf:type schema:Organization
    86 Nfd61f423376141d89ead59790a8ca9a4 rdf:first sg:person.010017213117.39
    87 rdf:rest N9dd1d08d9f57421b8ef3a6257ebd1e25
    88 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    89 schema:name Information and Computing Sciences
    90 rdf:type schema:DefinedTerm
    91 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Data Format
    93 rdf:type schema:DefinedTerm
    94 sg:person.010017213117.39 schema:affiliation https://www.grid.ac/institutes/grid.264580.d
    95 schema:familyName Yang
    96 schema:givenName Bo-Yin
    97 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010017213117.39
    98 rdf:type schema:Person
    99 sg:person.010552153601.77 schema:affiliation Ne9273bbe00c94078b92cbec5fc9bbc26
    100 schema:familyName Chen
    101 schema:givenName Jiun-Ming
    102 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010552153601.77
    103 rdf:type schema:Person
    104 sg:pub.10.1007/11496137_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033985068
    105 https://doi.org/10.1007/11496137_12
    106 rdf:type schema:CreativeWork
    107 sg:pub.10.1007/11496618_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004218140
    108 https://doi.org/10.1007/11496618_7
    109 rdf:type schema:CreativeWork
    110 sg:pub.10.1007/3-540-44448-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052740197
    111 https://doi.org/10.1007/3-540-44448-3_4
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/3-540-44750-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051590862
    114 https://doi.org/10.1007/3-540-44750-4_20
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/3-540-45353-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006045667
    117 https://doi.org/10.1007/3-540-45353-9_22
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/3-540-45539-6_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000285811
    120 https://doi.org/10.1007/3-540-45539-6_27
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/3-540-45664-3_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007371554
    123 https://doi.org/10.1007/3-540-45664-3_15
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/3-540-45961-8_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
    126 https://doi.org/10.1007/3-540-45961-8_39
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/3-540-48329-2_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049865404
    129 https://doi.org/10.1007/3-540-48329-2_37
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/3-540-48405-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045972569
    132 https://doi.org/10.1007/3-540-48405-1_2
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-48910-x_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020614953
    135 https://doi.org/10.1007/3-540-48910-x_15
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
    138 https://doi.org/10.1007/3-540-68339-9_4
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-540-24691-6_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013746886
    141 https://doi.org/10.1007/978-3-540-24691-6_24
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-540-28632-5_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014916110
    144 https://doi.org/10.1007/978-3-540-28632-5_26
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-540-28632-5_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031254011
    147 https://doi.org/10.1007/978-3-540-28632-5_27
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/978-3-540-30539-2_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050327206
    150 https://doi.org/10.1007/978-3-540-30539-2_23
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/978-3-540-30574-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034073611
    153 https://doi.org/10.1007/978-3-540-30574-3_4
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/978-3-540-30580-4_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028452893
    156 https://doi.org/10.1007/978-3-540-30580-4_17
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/978-3-540-30580-4_18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042849207
    159 https://doi.org/10.1007/978-3-540-30580-4_18
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/978-3-540-30580-4_20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032831457
    162 https://doi.org/10.1007/978-3-540-30580-4_20
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/978-3-540-30598-9_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003321122
    165 https://doi.org/10.1007/978-3-540-30598-9_21
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/978-3-540-45146-4_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049476263
    168 https://doi.org/10.1007/978-3-540-45146-4_3
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/bfb0055733 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016241801
    171 https://doi.org/10.1007/bfb0055733
    172 rdf:type schema:CreativeWork
    173 https://doi.org/10.1080/00927879908826559 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008867318
    174 rdf:type schema:CreativeWork
    175 https://doi.org/10.1109/sfcs.1994.365700 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095740049
    176 rdf:type schema:CreativeWork
    177 https://doi.org/10.1145/237814.237866 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053319325
    178 rdf:type schema:CreativeWork
    179 https://doi.org/10.1145/780506.780516 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007436250
    180 rdf:type schema:CreativeWork
    181 https://www.grid.ac/institutes/grid.264580.d schema:alternateName Tamkang University
    182 schema:name Dept. of Mathematics, Tamkang University, Tamsui, Taiwan
    183 rdf:type schema:Organization
     




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


    ...