Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'98 View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2000-06

AUTHORS

Jacques Patarin

ABSTRACT

In 1 Matsumoto and Imai developed a new public key scheme, called C*, for enciphering or signing. (This scheme is completely different from and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 in 7 and broken in 1984 in 8). No attacks have been published as yet for this scheme. However, in this paper, we will see that—for almost all keys—almost every cleartext can be found from its ciphertext after only approximately m2n4 log n computations, where m is the degree of the chosen field K and mn is the number of bits of text. Moreover, for absolutely all keys that give a practical size for the messages, it will be possible to find almost all cleartexts from the corresponding ciphertexts after a feasible computation. Thus the algorithm of 1 is insecure. More... »

PAGES

175-209

Identifiers

URI

http://scigraph.springernature.com/pub.10.1023/a:1008341625464

DOI

http://dx.doi.org/10.1023/a:1008341625464

DIMENSIONS

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


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": [
            "Bull SC&T - 68, route de Versailles -, 78431, Louveciennes Cedex -, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0747-7171(08)80013-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1033876399"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tit.1979.1056010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061648209"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2000-06", 
    "datePublishedReg": "2000-06-01", 
    "description": "In 1 Matsumoto and Imai developed a new public key scheme, called C*, for enciphering or signing. (This scheme is completely different from and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 in 7 and broken in 1984 in 8). No attacks have been published as yet for this scheme. However, in this paper, we will see that\u2014for almost all keys\u2014almost every cleartext can be found from its ciphertext after only approximately m2n4 log n computations, where m is the degree of the chosen field K and mn is the number of bits of text. Moreover, for absolutely all keys that give a practical size for the messages, it will be possible to find almost all cleartexts from the corresponding ciphertexts after a feasible computation. Thus the algorithm of 1 is insecure.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1023/a:1008341625464", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136552", 
        "issn": [
          "0925-1022", 
          "1573-7586"
        ], 
        "name": "Designs, Codes and Cryptography", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "20"
      }
    ], 
    "name": "Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'98", 
    "pagination": "175-209", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d4faa397b175fa6483e80c53d35a8c6a03ca6a900614cf9fd60be670eb22d16d"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1023/a:1008341625464"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1044711662"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1023/a:1008341625464", 
      "https://app.dimensions.ai/details/publication/pub.1044711662"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-10T19:06", 
    "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_8678_00000501.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "http://link.springer.com/10.1023/A:1008341625464"
  }
]
 

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.1023/a:1008341625464'

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.1023/a:1008341625464'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1008341625464'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1008341625464'


 

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

65 TRIPLES      21 PREDICATES      29 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1023/a:1008341625464 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nf17c7e0717f44550bba71f06ac4526fc
4 schema:citation https://doi.org/10.1016/s0747-7171(08)80013-2
5 https://doi.org/10.1109/tit.1979.1056010
6 schema:datePublished 2000-06
7 schema:datePublishedReg 2000-06-01
8 schema:description In 1 Matsumoto and Imai developed a new public key scheme, called C*, for enciphering or signing. (This scheme is completely different from and should not be mistaken with another scheme of Matsumoto and Imai developed in 1983 in 7 and broken in 1984 in 8). No attacks have been published as yet for this scheme. However, in this paper, we will see that—for almost all keys—almost every cleartext can be found from its ciphertext after only approximately m2n4 log n computations, where m is the degree of the chosen field K and mn is the number of bits of text. Moreover, for absolutely all keys that give a practical size for the messages, it will be possible to find almost all cleartexts from the corresponding ciphertexts after a feasible computation. Thus the algorithm of 1 is insecure.
9 schema:genre research_article
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N5e8acdea343a4aa28c53abd66030c5ab
13 Nf8582c3e92794b42b40d557da818aecb
14 sg:journal.1136552
15 schema:name Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt'98
16 schema:pagination 175-209
17 schema:productId N4bf6d9deee8345bc93cfba76b45f5b0d
18 N6891e0e956a149468760ed08fe889daa
19 N7c6bf5907ca040d8864e24b14be0fcf6
20 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044711662
21 https://doi.org/10.1023/a:1008341625464
22 schema:sdDatePublished 2019-04-10T19:06
23 schema:sdLicense https://scigraph.springernature.com/explorer/license/
24 schema:sdPublisher N7e96bc01730e47bfac84b01b3d5a271f
25 schema:url http://link.springer.com/10.1023/A:1008341625464
26 sgo:license sg:explorer/license/
27 sgo:sdDataset articles
28 rdf:type schema:ScholarlyArticle
29 N4bf6d9deee8345bc93cfba76b45f5b0d schema:name doi
30 schema:value 10.1023/a:1008341625464
31 rdf:type schema:PropertyValue
32 N5e8acdea343a4aa28c53abd66030c5ab schema:volumeNumber 20
33 rdf:type schema:PublicationVolume
34 N6891e0e956a149468760ed08fe889daa schema:name dimensions_id
35 schema:value pub.1044711662
36 rdf:type schema:PropertyValue
37 N7c6bf5907ca040d8864e24b14be0fcf6 schema:name readcube_id
38 schema:value d4faa397b175fa6483e80c53d35a8c6a03ca6a900614cf9fd60be670eb22d16d
39 rdf:type schema:PropertyValue
40 N7e96bc01730e47bfac84b01b3d5a271f schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N8ef2378b2e5b455faf174a9e56400fb4 schema:name Bull SC&T - 68, route de Versailles -, 78431, Louveciennes Cedex -, France
43 rdf:type schema:Organization
44 Nc84727450f204d7380402d1bc80955ac schema:affiliation N8ef2378b2e5b455faf174a9e56400fb4
45 schema:familyName Patarin
46 schema:givenName Jacques
47 rdf:type schema:Person
48 Nf17c7e0717f44550bba71f06ac4526fc rdf:first Nc84727450f204d7380402d1bc80955ac
49 rdf:rest rdf:nil
50 Nf8582c3e92794b42b40d557da818aecb schema:issueNumber 2
51 rdf:type schema:PublicationIssue
52 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
53 schema:name Information and Computing Sciences
54 rdf:type schema:DefinedTerm
55 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
56 schema:name Computation Theory and Mathematics
57 rdf:type schema:DefinedTerm
58 sg:journal.1136552 schema:issn 0925-1022
59 1573-7586
60 schema:name Designs, Codes and Cryptography
61 rdf:type schema:Periodical
62 https://doi.org/10.1016/s0747-7171(08)80013-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033876399
63 rdf:type schema:CreativeWork
64 https://doi.org/10.1109/tit.1979.1056010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061648209
65 rdf:type schema:CreativeWork
 




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


...