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 Ned971edc90dd40038e4b00de3d2f7fa1
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 N2ba08bfa0e3342489a481e38b8b9e9cb
13 Na6a42ce2f670419cb483298ed906ba12
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 N0e84bc6657f8422e8b84fe6e528143fe
18 N31759936e4d64f3fa0c640df8e900885
19 N7375554033a7467cab1954208a8adeb4
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 Na1ecfd553a294762abae9ed5851f5766
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 N0e84bc6657f8422e8b84fe6e528143fe schema:name dimensions_id
30 schema:value pub.1044711662
31 rdf:type schema:PropertyValue
32 N2ba08bfa0e3342489a481e38b8b9e9cb schema:volumeNumber 20
33 rdf:type schema:PublicationVolume
34 N31759936e4d64f3fa0c640df8e900885 schema:name readcube_id
35 schema:value d4faa397b175fa6483e80c53d35a8c6a03ca6a900614cf9fd60be670eb22d16d
36 rdf:type schema:PropertyValue
37 N433051b35154453cb6791a71902d4cc5 schema:name Bull SC&T - 68, route de Versailles -, 78431, Louveciennes Cedex -, France
38 rdf:type schema:Organization
39 N7375554033a7467cab1954208a8adeb4 schema:name doi
40 schema:value 10.1023/a:1008341625464
41 rdf:type schema:PropertyValue
42 Na1ecfd553a294762abae9ed5851f5766 schema:name Springer Nature - SN SciGraph project
43 rdf:type schema:Organization
44 Na6a42ce2f670419cb483298ed906ba12 schema:issueNumber 2
45 rdf:type schema:PublicationIssue
46 Nd03236ed71f640c2a4fd6a98bea5c440 schema:affiliation N433051b35154453cb6791a71902d4cc5
47 schema:familyName Patarin
48 schema:givenName Jacques
49 rdf:type schema:Person
50 Ned971edc90dd40038e4b00de3d2f7fa1 rdf:first Nd03236ed71f640c2a4fd6a98bea5c440
51 rdf:rest rdf:nil
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)


...