An Observation on the Security of McEliece’s Public-Key Cryptosystem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1988

AUTHORS

P. J. Lee , E. F. Brickell

ABSTRACT

The best known cryptanalytic attack on McEliece’s public-key cryptosystem based on algebraic coding theory is to repeatedly select k bits at random from an n-bit ciphertext vector, which is corrupted by at most t errors, in hope that none of the selected k bits are in error until the cryptanalyst recovers the correct message. The method of determining whether the recovered message is the correct one has not been throughly investigated. In this paper, we suggest a systematic method of checking, and describe a generalized version of the cryptanalytic attack which reduces the work factor significantly (factor of 211 for the commonly used example of n=1024 Goppa code case). Some more improvements are also given. We also note that these cryptanalytic algorithms can be viewed as generalized probabilistic decoding algorithms for any linear error correcting codes. More... »

PAGES

275-280

Book

TITLE

Advances in Cryptology — EUROCRYPT ’88

ISBN

978-3-540-50251-7
978-3-540-45961-3

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lee", 
        "givenName": "P. J.", 
        "id": "sg:person.014752300537.85", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014752300537.85"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Bell Communications Research, 07960, Morristown, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.432790.b", 
          "name": [
            "Bell Communications Research, 07960, Morristown, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Brickell", 
        "givenName": "E. F.", 
        "id": "sg:person.016650302365.34", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016650302365.34"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1988", 
    "datePublishedReg": "1988-01-01", 
    "description": "The best known cryptanalytic attack on McEliece\u2019s public-key cryptosystem based on algebraic coding theory is to repeatedly select k bits at random from an n-bit ciphertext vector, which is corrupted by at most t errors, in hope that none of the selected k bits are in error until the cryptanalyst recovers the correct message. The method of determining whether the recovered message is the correct one has not been throughly investigated. In this paper, we suggest a systematic method of checking, and describe a generalized version of the cryptanalytic attack which reduces the work factor significantly (factor of 211 for the commonly used example of n=1024 Goppa code case). Some more improvements are also given. We also note that these cryptanalytic algorithms can be viewed as generalized probabilistic decoding algorithms for any linear error correcting codes.", 
    "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_25", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-50251-7", 
        "978-3-540-45961-3"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT \u201988", 
      "type": "Book"
    }, 
    "keywords": [
      "public-key cryptosystem", 
      "McEliece public-key cryptosystem", 
      "cryptanalytic attacks", 
      "probabilistic decoding algorithm", 
      "error correcting codes", 
      "linear error correcting codes", 
      "algebraic coding theory", 
      "ciphertext vector", 
      "decoding algorithm", 
      "correcting codes", 
      "recovered message", 
      "cryptanalytic algorithm", 
      "coding theory", 
      "correct message", 
      "cryptosystem", 
      "algorithm", 
      "correct ones", 
      "messages", 
      "bits", 
      "attacks", 
      "systematic method", 
      "security", 
      "cryptanalyst", 
      "generalized version", 
      "error", 
      "code", 
      "method", 
      "version", 
      "vector", 
      "more improvement", 
      "improvement", 
      "one", 
      "theory", 
      "work factors", 
      "hope", 
      "observations", 
      "factors", 
      "paper", 
      "bit ciphertext vector"
    ], 
    "name": "An Observation on the Security of McEliece\u2019s Public-Key Cryptosystem", 
    "pagination": "275-280", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018510260"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-45961-8_25"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-45961-8_25", 
      "https://app.dimensions.ai/details/publication/pub.1018510260"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T19:58", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_178.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-45961-8_25"
  }
]
 

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_25'

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_25'

Turtle is a human-readable linked data format.

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

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_25'


 

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

156 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-45961-8_25 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nfe66b5d583604cce960c247e00391236
4 schema:datePublished 1988
5 schema:datePublishedReg 1988-01-01
6 schema:description The best known cryptanalytic attack on McEliece’s public-key cryptosystem based on algebraic coding theory is to repeatedly select k bits at random from an n-bit ciphertext vector, which is corrupted by at most t errors, in hope that none of the selected k bits are in error until the cryptanalyst recovers the correct message. The method of determining whether the recovered message is the correct one has not been throughly investigated. In this paper, we suggest a systematic method of checking, and describe a generalized version of the cryptanalytic attack which reduces the work factor significantly (factor of 211 for the commonly used example of n=1024 Goppa code case). Some more improvements are also given. We also note that these cryptanalytic algorithms can be viewed as generalized probabilistic decoding algorithms for any linear error correcting codes.
7 schema:editor N9a7be50abced43ca96ca7f8f0221740e
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N9016dcab2b024106a37e474def424194
12 schema:keywords McEliece public-key cryptosystem
13 algebraic coding theory
14 algorithm
15 attacks
16 bit ciphertext vector
17 bits
18 ciphertext vector
19 code
20 coding theory
21 correct message
22 correct ones
23 correcting codes
24 cryptanalyst
25 cryptanalytic algorithm
26 cryptanalytic attacks
27 cryptosystem
28 decoding algorithm
29 error
30 error correcting codes
31 factors
32 generalized version
33 hope
34 improvement
35 linear error correcting codes
36 messages
37 method
38 more improvement
39 observations
40 one
41 paper
42 probabilistic decoding algorithm
43 public-key cryptosystem
44 recovered message
45 security
46 systematic method
47 theory
48 vector
49 version
50 work factors
51 schema:name An Observation on the Security of McEliece’s Public-Key Cryptosystem
52 schema:pagination 275-280
53 schema:productId N6fa1d8f312d84f16967ebfacb8b141c5
54 Ne0672e3872c847b78635a75750b3cd5c
55 schema:publisher N34ef5291164240d48537607304059f6d
56 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018510260
57 https://doi.org/10.1007/3-540-45961-8_25
58 schema:sdDatePublished 2021-12-01T19:58
59 schema:sdLicense https://scigraph.springernature.com/explorer/license/
60 schema:sdPublisher N6d8a5a4d540c44849c398a6be34be2cd
61 schema:url https://doi.org/10.1007/3-540-45961-8_25
62 sgo:license sg:explorer/license/
63 sgo:sdDataset chapters
64 rdf:type schema:Chapter
65 N005f07c22ee1433a91829ec30d91ab22 rdf:first Naae2f3b8f9de46f485de0cc6301a1d97
66 rdf:rest Nb4b6ff7eb2924ae99552a39cf2fb2072
67 N145f268e3876472dac044f67bc9b372c rdf:first sg:person.016650302365.34
68 rdf:rest rdf:nil
69 N147c3efe43bf44d0a255fba9ecb4c43a schema:familyName Wirth
70 schema:givenName N.
71 rdf:type schema:Person
72 N16442436b4014355a0ab1fdc8b358079 schema:familyName Barstow
73 schema:givenName D.
74 rdf:type schema:Person
75 N1af46358a8b74ce5bd354b2fa874b9d9 rdf:first N2a11a928ef494af7bc84bafd313ab988
76 rdf:rest N2a4e04b4c0fe4a9a9b0d913c6f661990
77 N2a11a928ef494af7bc84bafd313ab988 schema:familyName Moler
78 schema:givenName C.
79 rdf:type schema:Person
80 N2a4e04b4c0fe4a9a9b0d913c6f661990 rdf:first Nc06a9fda1a88487ab6a5ba8643d74a93
81 rdf:rest Nc543690ee56e4d808ffbda96e9381400
82 N34ef5291164240d48537607304059f6d schema:name Springer Nature
83 rdf:type schema:Organisation
84 N3ee685eea9eb4fdcbb20282b1c8a7fa8 rdf:first N147c3efe43bf44d0a255fba9ecb4c43a
85 rdf:rest Nf802be878e974893bf09bfb7b1499b38
86 N4699156d095b45c9a3c0a642cd0cb711 rdf:first Nf1fdabc5a1af4cf9b5d4842aceb8d495
87 rdf:rest N3ee685eea9eb4fdcbb20282b1c8a7fa8
88 N50ac83124edc4541b9d955891a52f841 rdf:first N915452f9f9e44e69b069187152c73f92
89 rdf:rest N005f07c22ee1433a91829ec30d91ab22
90 N6d8a5a4d540c44849c398a6be34be2cd schema:name Springer Nature - SN SciGraph project
91 rdf:type schema:Organization
92 N6fa1d8f312d84f16967ebfacb8b141c5 schema:name dimensions_id
93 schema:value pub.1018510260
94 rdf:type schema:PropertyValue
95 N72795cbab71648aeb91f9c50764e99a3 schema:familyName Gries
96 schema:givenName D.
97 rdf:type schema:Person
98 N9016dcab2b024106a37e474def424194 schema:isbn 978-3-540-45961-3
99 978-3-540-50251-7
100 schema:name Advances in Cryptology — EUROCRYPT ’88
101 rdf:type schema:Book
102 N915452f9f9e44e69b069187152c73f92 schema:familyName Brauer
103 schema:givenName W.
104 rdf:type schema:Person
105 N9a7be50abced43ca96ca7f8f0221740e rdf:first N16442436b4014355a0ab1fdc8b358079
106 rdf:rest N50ac83124edc4541b9d955891a52f841
107 Na9267e07dc2f41af823fc6da3336e0ab schema:familyName Luckham
108 schema:givenName D.
109 rdf:type schema:Person
110 Naae2f3b8f9de46f485de0cc6301a1d97 schema:familyName Brinch Hansen
111 schema:givenName P.
112 rdf:type schema:Person
113 Nb4b6ff7eb2924ae99552a39cf2fb2072 rdf:first N72795cbab71648aeb91f9c50764e99a3
114 rdf:rest Ne8a0aa1249874475bff0ecd03a5ef8ea
115 Nbeddd8e48ba7416199e803615d7edaf3 schema:familyName Günther
116 schema:givenName Christoph G.
117 rdf:type schema:Person
118 Nc06a9fda1a88487ab6a5ba8643d74a93 schema:familyName Pnueli
119 schema:givenName A.
120 rdf:type schema:Person
121 Nc543690ee56e4d808ffbda96e9381400 rdf:first Nd3cdc00b886d4044bd31674311b714dc
122 rdf:rest N4699156d095b45c9a3c0a642cd0cb711
123 Nd3cdc00b886d4044bd31674311b714dc schema:familyName Seegmüller
124 schema:givenName G.
125 rdf:type schema:Person
126 Ne0672e3872c847b78635a75750b3cd5c schema:name doi
127 schema:value 10.1007/3-540-45961-8_25
128 rdf:type schema:PropertyValue
129 Ne8a0aa1249874475bff0ecd03a5ef8ea rdf:first Na9267e07dc2f41af823fc6da3336e0ab
130 rdf:rest N1af46358a8b74ce5bd354b2fa874b9d9
131 Nf1fdabc5a1af4cf9b5d4842aceb8d495 schema:familyName Stoer
132 schema:givenName J.
133 rdf:type schema:Person
134 Nf802be878e974893bf09bfb7b1499b38 rdf:first Nbeddd8e48ba7416199e803615d7edaf3
135 rdf:rest rdf:nil
136 Nfe66b5d583604cce960c247e00391236 rdf:first sg:person.014752300537.85
137 rdf:rest N145f268e3876472dac044f67bc9b372c
138 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
139 schema:name Information and Computing Sciences
140 rdf:type schema:DefinedTerm
141 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
142 schema:name Data Format
143 rdf:type schema:DefinedTerm
144 sg:person.014752300537.85 schema:affiliation grid-institutes:grid.432790.b
145 schema:familyName Lee
146 schema:givenName P. J.
147 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014752300537.85
148 rdf:type schema:Person
149 sg:person.016650302365.34 schema:affiliation grid-institutes:grid.432790.b
150 schema:familyName Brickell
151 schema:givenName E. F.
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016650302365.34
153 rdf:type schema:Person
154 grid-institutes:grid.432790.b schema:alternateName Bell Communications Research, 07960, Morristown, NJ, USA
155 schema:name Bell Communications Research, 07960, Morristown, NJ, USA
156 rdf:type schema:Organization
 




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


...