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

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 N8752a40aadab4ffe8ca76635be9c17ed
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 N866bc0da1a524f3bbe70b7b40a211f38
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf N6e29d2d477204e97bf2c48f0ad066842
16 schema:name Public Quadratic Polynomial-Tuples for Efficient Signature-Verification and Message-Encryption
17 schema:pagination 419-453
18 schema:productId N45d5fe2bcb5d4e64af28bd10b19b5517
19 N9da0f5369f8e4e90a8ab8433dcfdc92f
20 Nf348cb4610e0402d87a87a5fa9d8bbdd
21 schema:publisher N235437fba3114249b56d346414353cd6
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 N21f1dacdfe8846fab1642de489e2494e
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 N026f43a1fd994266950fc5414b0bef02 schema:familyName Gries
32 schema:givenName D.
33 rdf:type schema:Person
34 N067db89337324f29be4313e031ac583a schema:familyName Stoer
35 schema:givenName J.
36 rdf:type schema:Person
37 N145a1589b87549289aed12a73c5c8cc0 schema:familyName Günther
38 schema:givenName Christoph G.
39 rdf:type schema:Person
40 N180023c8ef694242b2402c37ad4c4410 rdf:first sg:person.015036512317.70
41 rdf:rest rdf:nil
42 N1e26e97c1b7d49b1a9e6facd4bb8132b rdf:first N458eca232ddc4fcc905affe27c93d0da
43 rdf:rest N2a917c2c814c4b5a9aace48a7ff45ab5
44 N21f1dacdfe8846fab1642de489e2494e schema:name Springer Nature - SN SciGraph project
45 rdf:type schema:Organization
46 N235437fba3114249b56d346414353cd6 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 N2a917c2c814c4b5a9aace48a7ff45ab5 rdf:first N067db89337324f29be4313e031ac583a
50 rdf:rest Ncf996f35931340ba9487c038e8a0f24a
51 N458eca232ddc4fcc905affe27c93d0da schema:familyName Seegmüller
52 schema:givenName G.
53 rdf:type schema:Person
54 N45d5fe2bcb5d4e64af28bd10b19b5517 schema:name doi
55 schema:value 10.1007/3-540-45961-8_39
56 rdf:type schema:PropertyValue
57 N61502113609a43cf89a86908f26e6fe1 rdf:first N026f43a1fd994266950fc5414b0bef02
58 rdf:rest Nbe441ad45e0e4c558ef60c4aaf1b429c
59 N626b240439c64f69915db946ab7936f8 rdf:first N145a1589b87549289aed12a73c5c8cc0
60 rdf:rest rdf:nil
61 N66baae9db5db47f5af00a37b694ab246 rdf:first Nf2b835a548f5426d97ae1ca23a69456b
62 rdf:rest N61502113609a43cf89a86908f26e6fe1
63 N6e29d2d477204e97bf2c48f0ad066842 schema:isbn 978-3-540-50251-7
64 schema:name Advances in Cryptology — EUROCRYPT ’88
65 rdf:type schema:Book
66 N6fbd9b90e1ce4ad5ad580d081b5c0b66 rdf:first Nc26d2e9bf3544fdf9df22d299301ca82
67 rdf:rest N66baae9db5db47f5af00a37b694ab246
68 N866bc0da1a524f3bbe70b7b40a211f38 rdf:first Ne827cc5a002242039543ff6c2fcdffe5
69 rdf:rest N6fbd9b90e1ce4ad5ad580d081b5c0b66
70 N8752a40aadab4ffe8ca76635be9c17ed rdf:first sg:person.014347421531.49
71 rdf:rest N180023c8ef694242b2402c37ad4c4410
72 N92764847aedc4ee2a28b82baf6af16ad schema:familyName Wirth
73 schema:givenName N.
74 rdf:type schema:Person
75 N9333eb4d4c2245f18623bca7241ba26a rdf:first Ne4dcb11c0e6447329d8c115e42c6b6d2
76 rdf:rest Nbcd50a6d6a194c2aa7b21ec06e8e3467
77 N9da0f5369f8e4e90a8ab8433dcfdc92f schema:name readcube_id
78 schema:value a9977921ec6434dbc3bf2a50bb28beaa3a5c54f66c427916a8a2834e6b297f75
79 rdf:type schema:PropertyValue
80 Nb07dca3e164c4ced92b4b33deb216f41 schema:familyName Luckham
81 schema:givenName D.
82 rdf:type schema:Person
83 Nbcd50a6d6a194c2aa7b21ec06e8e3467 rdf:first Ne3daed3777814ac18efa01f2508f21e3
84 rdf:rest N1e26e97c1b7d49b1a9e6facd4bb8132b
85 Nbe441ad45e0e4c558ef60c4aaf1b429c rdf:first Nb07dca3e164c4ced92b4b33deb216f41
86 rdf:rest N9333eb4d4c2245f18623bca7241ba26a
87 Nc26d2e9bf3544fdf9df22d299301ca82 schema:familyName Brauer
88 schema:givenName W.
89 rdf:type schema:Person
90 Ncf996f35931340ba9487c038e8a0f24a rdf:first N92764847aedc4ee2a28b82baf6af16ad
91 rdf:rest N626b240439c64f69915db946ab7936f8
92 Ne3daed3777814ac18efa01f2508f21e3 schema:familyName Pnueli
93 schema:givenName A.
94 rdf:type schema:Person
95 Ne4dcb11c0e6447329d8c115e42c6b6d2 schema:familyName Moler
96 schema:givenName C.
97 rdf:type schema:Person
98 Ne827cc5a002242039543ff6c2fcdffe5 schema:familyName Barstow
99 schema:givenName D.
100 rdf:type schema:Person
101 Nf2b835a548f5426d97ae1ca23a69456b schema:familyName Brinch Hansen
102 schema:givenName P.
103 rdf:type schema:Person
104 Nf348cb4610e0402d87a87a5fa9d8bbdd schema:name dimensions_id
105 schema:value pub.1035601256
106 rdf:type schema:PropertyValue
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)


...