Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88 View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1995

AUTHORS

Jacques Patarin

ABSTRACT

In [1] Matsumoto and Imai have developed a new public key scheme for enciphering or signing. (This scheme is completely different and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 and broken at Eurocrypt’84). No attacks have been published as yet for this scheme. However we will see in this paper that for almost all the keys almost each cleartext can be found from his ciphertext after only about m 2 n 4 log n computations where m is the degree of the field K chosen, and where mn is the number of bits of the text. Moreover for absolutely all the keys that give a practical size for the messages it will be possible to find almost all the cleartexts from the corresponding ciphertexts after a feasible computation. So the algorithm of [1] is insecure. More... »

PAGES

248-261

Book

TITLE

Advances in Cryptology — CRYPT0’ 95

ISBN

978-3-540-60221-7
978-3-540-44750-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-44750-4_20

DOI

http://dx.doi.org/10.1007/3-540-44750-4_20

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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 TRANSAC, 68 route de Versailles, BP 45, 78430\u00a0Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "type": "Person"
      }
    ], 
    "datePublished": "1995", 
    "datePublishedReg": "1995-01-01", 
    "description": "In [1] Matsumoto and Imai have developed a new public key scheme for enciphering or signing. (This scheme is completely different and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 and broken at Eurocrypt\u201984). No attacks have been published as yet for this scheme. However we will see in this paper that for almost all the keys almost each cleartext can be found from his ciphertext after only about m 2 n 4 log n computations where m is the degree of the field K chosen, and where mn is the number of bits of the text. Moreover for absolutely all the keys that give a practical size for the messages it will be possible to find almost all the cleartexts from the corresponding ciphertexts after a feasible computation. So the algorithm of [1] is insecure.", 
    "editor": [
      {
        "familyName": "Coppersmith", 
        "givenName": "Don", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44750-4_20", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-60221-7", 
        "978-3-540-44750-4"
      ], 
      "name": "Advances in Cryptology \u2014 CRYPT0\u2019 95", 
      "type": "Book"
    }, 
    "name": "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt\u201988", 
    "pagination": "248-261", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44750-4_20"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "f5c0ebac4a8f038ad92f5a5cdf3e4aa2962076895203fa7ec144820b835f885c"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1051590862"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44750-4_20", 
      "https://app.dimensions.ai/details/publication/pub.1051590862"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:01", 
    "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_8664_00000554.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-44750-4_20"
  }
]
 

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-44750-4_20'

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-44750-4_20'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44750-4_20'

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-44750-4_20'


 

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

63 TRIPLES      22 PREDICATES      27 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44750-4_20 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N9c461410891c4bb2bf796acef5755a79
4 schema:datePublished 1995
5 schema:datePublishedReg 1995-01-01
6 schema:description In [1] Matsumoto and Imai have developed a new public key scheme for enciphering or signing. (This scheme is completely different and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 and broken at Eurocrypt’84). No attacks have been published as yet for this scheme. However we will see in this paper that for almost all the keys almost each cleartext can be found from his ciphertext after only about m 2 n 4 log n computations where m is the degree of the field K chosen, and where mn is the number of bits of the text. Moreover for absolutely all the keys that give a practical size for the messages it will be possible to find almost all the cleartexts from the corresponding ciphertexts after a feasible computation. So the algorithm of [1] is insecure.
7 schema:editor N0cf7fe49b55b42979609475a88896cda
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N0b281aa534814c00a569e53a4ed416ad
12 schema:name Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt’88
13 schema:pagination 248-261
14 schema:productId N66d82bbbfd524437924fe58cb2b80d27
15 N960f2041a5a54b959937daebda904779
16 Nd32f393f1bd74dd0be2b8ad5cd9c7edb
17 schema:publisher Nae33661776524518937f37cbf471318d
18 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051590862
19 https://doi.org/10.1007/3-540-44750-4_20
20 schema:sdDatePublished 2019-04-15T14:01
21 schema:sdLicense https://scigraph.springernature.com/explorer/license/
22 schema:sdPublisher N0f22cdb2d736455c946af1e05fee77b9
23 schema:url http://link.springer.com/10.1007/3-540-44750-4_20
24 sgo:license sg:explorer/license/
25 sgo:sdDataset chapters
26 rdf:type schema:Chapter
27 N0b281aa534814c00a569e53a4ed416ad schema:isbn 978-3-540-44750-4
28 978-3-540-60221-7
29 schema:name Advances in Cryptology — CRYPT0’ 95
30 rdf:type schema:Book
31 N0cf7fe49b55b42979609475a88896cda rdf:first Ne2cdd6e1237d478fa13f71885e8f1499
32 rdf:rest rdf:nil
33 N0f22cdb2d736455c946af1e05fee77b9 schema:name Springer Nature - SN SciGraph project
34 rdf:type schema:Organization
35 N51f513109a944224826925ee592dc390 schema:affiliation Nfecf4ec19f4248d9801712ab925c1560
36 schema:familyName Patarin
37 schema:givenName Jacques
38 rdf:type schema:Person
39 N66d82bbbfd524437924fe58cb2b80d27 schema:name doi
40 schema:value 10.1007/3-540-44750-4_20
41 rdf:type schema:PropertyValue
42 N960f2041a5a54b959937daebda904779 schema:name dimensions_id
43 schema:value pub.1051590862
44 rdf:type schema:PropertyValue
45 N9c461410891c4bb2bf796acef5755a79 rdf:first N51f513109a944224826925ee592dc390
46 rdf:rest rdf:nil
47 Nae33661776524518937f37cbf471318d schema:location Berlin, Heidelberg
48 schema:name Springer Berlin Heidelberg
49 rdf:type schema:Organisation
50 Nd32f393f1bd74dd0be2b8ad5cd9c7edb schema:name readcube_id
51 schema:value f5c0ebac4a8f038ad92f5a5cdf3e4aa2962076895203fa7ec144820b835f885c
52 rdf:type schema:PropertyValue
53 Ne2cdd6e1237d478fa13f71885e8f1499 schema:familyName Coppersmith
54 schema:givenName Don
55 rdf:type schema:Person
56 Nfecf4ec19f4248d9801712ab925c1560 schema:name CP8 TRANSAC, 68 route de Versailles, BP 45, 78430 Louveciennes Cedex, France
57 rdf:type schema:Organization
58 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
59 schema:name Information and Computing Sciences
60 rdf:type schema:DefinedTerm
61 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
62 schema:name Computation Theory and Mathematics
63 rdf:type schema:DefinedTerm
 




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


...