Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1988

AUTHORS

Tsutomu Matsumoto , Hideki Imai

ABSTRACT

This paper discusses an asymmetric cryptosystem C* which consists of public transformations of complexity O(m 2 n 3) and secret transformations of complexity O((mn)2(m + logn)), where each complexity is measured in the total number of bit-operations for processing an mn-bit message block. Each public key of C* is an n-tuple of quadratic n-variate polynomials over GF(2m) and can be used for both verifying signatures and encrypting plaintexts. This paper also shows that for C* it is practically infeasible to extract the n-tuple of n-variate polynomials representing the inverse of the corresponding public key. More... »

PAGES

419-453

References to SciGraph publications

  • 1986. Analysis of a Public Key Approach Based on Polynomial Substitution in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
  • Book

    TITLE

    Advances in Cryptology — EUROCRYPT ’88

    ISBN

    978-3-540-50251-7

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45961-8_39

    DOI

    http://dx.doi.org/10.1007/3-540-45961-8_39

    DIMENSIONS

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


    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": "Yokohama National University", 
              "id": "https://www.grid.ac/institutes/grid.268446.a", 
              "name": [
                "Division of Electrical and Computer Engineering, Yokohama National University, 156 Tokiwadai, Hodogaya, Yokohama\u00a0240, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Matsumoto", 
            "givenName": "Tsutomu", 
            "id": "sg:person.014347421531.49", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014347421531.49"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Yokohama National University", 
              "id": "https://www.grid.ac/institutes/grid.268446.a", 
              "name": [
                "Division of Electrical and Computer Engineering, Yokohama National University, 156 Tokiwadai, Hodogaya, Yokohama\u00a0240, Japan"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Imai", 
            "givenName": "Hideki", 
            "id": "sg:person.015036512317.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015036512317.70"
            ], 
            "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": "https://doi.org/10.1145/359340.359342", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013337011"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0019-9958(81)90629-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048394162"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1976.1055638", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061647862"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "1988", 
        "datePublishedReg": "1988-01-01", 
        "description": "This paper discusses an asymmetric cryptosystem C* which consists of public transformations of complexity O(m 2 n 3) and secret transformations of complexity O((mn)2(m + logn)), where each complexity is measured in the total number of bit-operations for processing an mn-bit message block. Each public key of C* is an n-tuple of quadratic n-variate polynomials over GF(2m) and can be used for both verifying signatures and encrypting plaintexts. This paper also shows that for C* it is practically infeasible to extract the n-tuple of n-variate polynomials representing the inverse of the corresponding public key.", 
        "editor": [
          {
            "familyName": "Barstow", 
            "givenName": "D.", 
            "type": "Person"
          }, 
          {
            "familyName": "Brauer", 
            "givenName": "W.", 
            "type": "Person"
          }, 
          {
            "familyName": "Brinch Hansen", 
            "givenName": "P.", 
            "type": "Person"
          }, 
          {
            "familyName": "Gries", 
            "givenName": "D.", 
            "type": "Person"
          }, 
          {
            "familyName": "Luckham", 
            "givenName": "D.", 
            "type": "Person"
          }, 
          {
            "familyName": "Moler", 
            "givenName": "C.", 
            "type": "Person"
          }, 
          {
            "familyName": "Pnueli", 
            "givenName": "A.", 
            "type": "Person"
          }, 
          {
            "familyName": "Seegm\u00fcller", 
            "givenName": "G.", 
            "type": "Person"
          }, 
          {
            "familyName": "Stoer", 
            "givenName": "J.", 
            "type": "Person"
          }, 
          {
            "familyName": "Wirth", 
            "givenName": "N.", 
            "type": "Person"
          }, 
          {
            "familyName": "G\u00fcnther", 
            "givenName": "Christoph G.", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45961-8_39", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-50251-7"
          ], 
          "name": "Advances in Cryptology \u2014 EUROCRYPT \u201988", 
          "type": "Book"
        }, 
        "name": "Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption", 
        "pagination": "419-453", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45961-8_39"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "a9977921ec6434dbc3bf2a50bb28beaa3a5c54f66c427916a8a2834e6b297f75"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035601256"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45961-8_39", 
          "https://app.dimensions.ai/details/publication/pub.1035601256"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T20:07", 
        "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_8687_00000265.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45961-8_39"
      }
    ]
     

    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-45961-8_39'

    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-45961-8_39'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45961-8_39'

    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-45961-8_39'


     

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

    134 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45961-8_39 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N434191ae96cc48118bf593c71541b60e
    4 schema:citation sg:pub.10.1007/3-540-39799-x_24
    5 https://doi.org/10.1016/s0019-9958(81)90629-x
    6 https://doi.org/10.1109/tit.1976.1055638
    7 https://doi.org/10.1145/359340.359342
    8 schema:datePublished 1988
    9 schema:datePublishedReg 1988-01-01
    10 schema:description This paper discusses an asymmetric cryptosystem C* which consists of public transformations of complexity O(m 2 n 3) and secret transformations of complexity O((mn)2(m + logn)), where each complexity is measured in the total number of bit-operations for processing an mn-bit message block. Each public key of C* is an n-tuple of quadratic n-variate polynomials over GF(2m) and can be used for both verifying signatures and encrypting plaintexts. This paper also shows that for C* it is practically infeasible to extract the n-tuple of n-variate polynomials representing the inverse of the corresponding public key.
    11 schema:editor Nfaf1be556711419c944162ccfacd32af
    12 schema:genre chapter
    13 schema:inLanguage en
    14 schema:isAccessibleForFree true
    15 schema:isPartOf Neef69305f64e4173b2b50c8bea83133e
    16 schema:name Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption
    17 schema:pagination 419-453
    18 schema:productId N0565b6b9284c40b2a0f5e11b806d7505
    19 N3c9f7723096443f3bf478d9adb4c0c17
    20 N4ac24ddb7b184f35a75e66812604e861
    21 schema:publisher N8d6f868ac92846618741e2c8a7d9994c
    22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035601256
    23 https://doi.org/10.1007/3-540-45961-8_39
    24 schema:sdDatePublished 2019-04-15T20:07
    25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    26 schema:sdPublisher N84028d09176441aea72d86dc80983d7c
    27 schema:url http://link.springer.com/10.1007/3-540-45961-8_39
    28 sgo:license sg:explorer/license/
    29 sgo:sdDataset chapters
    30 rdf:type schema:Chapter
    31 N0565b6b9284c40b2a0f5e11b806d7505 schema:name readcube_id
    32 schema:value a9977921ec6434dbc3bf2a50bb28beaa3a5c54f66c427916a8a2834e6b297f75
    33 rdf:type schema:PropertyValue
    34 N05e39e40d3ba4438aed42c5164c591d9 schema:familyName Moler
    35 schema:givenName C.
    36 rdf:type schema:Person
    37 N072841ab5a9442b2aa6565ec47a8266c rdf:first N79c2ce3485d548daa1e073572f0857af
    38 rdf:rest N7a987d82ef3840c080a05ef491bf543d
    39 N268627e0c7254fb8bec7a131e8eb2398 rdf:first Nb0099c98168d4d5c97835ff5682066f6
    40 rdf:rest Nf73c1824263541d4963b18c4c81f1ecd
    41 N377cbf04f08b48f9868f5a418f5a524f schema:familyName Gries
    42 schema:givenName D.
    43 rdf:type schema:Person
    44 N38eab556e457453c8d97aae92a4b72d1 schema:familyName Günther
    45 schema:givenName Christoph G.
    46 rdf:type schema:Person
    47 N3c9f7723096443f3bf478d9adb4c0c17 schema:name dimensions_id
    48 schema:value pub.1035601256
    49 rdf:type schema:PropertyValue
    50 N434191ae96cc48118bf593c71541b60e rdf:first sg:person.014347421531.49
    51 rdf:rest Nc443f9a52c0a4c11aace4f8c90542894
    52 N47ab69769e6a456e8f83a0ff3e21c220 rdf:first Ne9c9a392deff4adda67fd0c467dbd4b1
    53 rdf:rest N072841ab5a9442b2aa6565ec47a8266c
    54 N4ac24ddb7b184f35a75e66812604e861 schema:name doi
    55 schema:value 10.1007/3-540-45961-8_39
    56 rdf:type schema:PropertyValue
    57 N6221e77f46f8409bb2c47bc5fcf771df schema:familyName Barstow
    58 schema:givenName D.
    59 rdf:type schema:Person
    60 N6f3bca2af1f24a12a9e12a3791c1b9e5 schema:familyName Seegmüller
    61 schema:givenName G.
    62 rdf:type schema:Person
    63 N79c2ce3485d548daa1e073572f0857af schema:familyName Wirth
    64 schema:givenName N.
    65 rdf:type schema:Person
    66 N7a987d82ef3840c080a05ef491bf543d rdf:first N38eab556e457453c8d97aae92a4b72d1
    67 rdf:rest rdf:nil
    68 N84028d09176441aea72d86dc80983d7c schema:name Springer Nature - SN SciGraph project
    69 rdf:type schema:Organization
    70 N8ca13d93e1df488ba1239068c4a8d47b rdf:first N6f3bca2af1f24a12a9e12a3791c1b9e5
    71 rdf:rest N47ab69769e6a456e8f83a0ff3e21c220
    72 N8d6f868ac92846618741e2c8a7d9994c schema:location Berlin, Heidelberg
    73 schema:name Springer Berlin Heidelberg
    74 rdf:type schema:Organisation
    75 N9e11241e24224aa0b299fde323f7ec0a rdf:first N377cbf04f08b48f9868f5a418f5a524f
    76 rdf:rest N268627e0c7254fb8bec7a131e8eb2398
    77 Nb0099c98168d4d5c97835ff5682066f6 schema:familyName Luckham
    78 schema:givenName D.
    79 rdf:type schema:Person
    80 Nb00a71e71643451f8c2fdde7e817f6ff schema:familyName Brinch Hansen
    81 schema:givenName P.
    82 rdf:type schema:Person
    83 Nb28edc2452634f55ac6d780ff962693b rdf:first Nbabfe5069024448abeb2b4ba61987058
    84 rdf:rest Necb238212cb4492e919564da63a5ace1
    85 Nbabfe5069024448abeb2b4ba61987058 schema:familyName Brauer
    86 schema:givenName W.
    87 rdf:type schema:Person
    88 Nbca6bc6f70c44eb7a71a2e3b6bdeaf8b schema:familyName Pnueli
    89 schema:givenName A.
    90 rdf:type schema:Person
    91 Nc443f9a52c0a4c11aace4f8c90542894 rdf:first sg:person.015036512317.70
    92 rdf:rest rdf:nil
    93 Nd0aea1896e18432681480cea51f34bc9 rdf:first Nbca6bc6f70c44eb7a71a2e3b6bdeaf8b
    94 rdf:rest N8ca13d93e1df488ba1239068c4a8d47b
    95 Ne9c9a392deff4adda67fd0c467dbd4b1 schema:familyName Stoer
    96 schema:givenName J.
    97 rdf:type schema:Person
    98 Necb238212cb4492e919564da63a5ace1 rdf:first Nb00a71e71643451f8c2fdde7e817f6ff
    99 rdf:rest N9e11241e24224aa0b299fde323f7ec0a
    100 Neef69305f64e4173b2b50c8bea83133e schema:isbn 978-3-540-50251-7
    101 schema:name Advances in Cryptology — EUROCRYPT ’88
    102 rdf:type schema:Book
    103 Nf73c1824263541d4963b18c4c81f1ecd rdf:first N05e39e40d3ba4438aed42c5164c591d9
    104 rdf:rest Nd0aea1896e18432681480cea51f34bc9
    105 Nfaf1be556711419c944162ccfacd32af rdf:first N6221e77f46f8409bb2c47bc5fcf771df
    106 rdf:rest Nb28edc2452634f55ac6d780ff962693b
    107 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    108 schema:name Information and Computing Sciences
    109 rdf:type schema:DefinedTerm
    110 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    111 schema:name Data Format
    112 rdf:type schema:DefinedTerm
    113 sg:person.014347421531.49 schema:affiliation https://www.grid.ac/institutes/grid.268446.a
    114 schema:familyName Matsumoto
    115 schema:givenName Tsutomu
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014347421531.49
    117 rdf:type schema:Person
    118 sg:person.015036512317.70 schema:affiliation https://www.grid.ac/institutes/grid.268446.a
    119 schema:familyName Imai
    120 schema:givenName Hideki
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015036512317.70
    122 rdf:type schema:Person
    123 sg:pub.10.1007/3-540-39799-x_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009274988
    124 https://doi.org/10.1007/3-540-39799-x_24
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1016/s0019-9958(81)90629-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048394162
    127 rdf:type schema:CreativeWork
    128 https://doi.org/10.1109/tit.1976.1055638 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061647862
    129 rdf:type schema:CreativeWork
    130 https://doi.org/10.1145/359340.359342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013337011
    131 rdf:type schema:CreativeWork
    132 https://www.grid.ac/institutes/grid.268446.a schema:alternateName Yokohama National University
    133 schema:name Division of Electrical and Computer Engineering, Yokohama National University, 156 Tokiwadai, Hodogaya, Yokohama 240, Japan
    134 rdf:type schema:Organization
     




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


    ...