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 N6b0070cf33aa45ada8e628aa83ae38e3
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 Nfc6e7075ab7349018619f85a6a044732
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nf461fb743619422e847f227f5a83fb91
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 N329cdbe0b8bb4dd69386defbcc0d1eb7
54 N7d3e944e0c674a7499c98cdc98be2abf
55 schema:publisher N9703cd7826da4393976fb665c79d7efa
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 N5719f4bef7e74c7fa15c6308136ca1c8
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 N05397f350b214126a35b4d3dc0d6a705 rdf:first N718f34e3515e403fa56041ac21a18f69
66 rdf:rest N9983bbc8f32b4dd081a96935c381cdef
67 N07286b27d6df403ab6e25829b6835292 schema:familyName Brauer
68 schema:givenName W.
69 rdf:type schema:Person
70 N287b7a7f193a4698a0012804f07d26ad schema:familyName Seegmüller
71 schema:givenName G.
72 rdf:type schema:Person
73 N2a4cc9c9485f4bb7aaa93bcc2b4b0a93 rdf:first N753e7483aacd4f90a0d8bcb862494eeb
74 rdf:rest rdf:nil
75 N329cdbe0b8bb4dd69386defbcc0d1eb7 schema:name dimensions_id
76 schema:value pub.1018510260
77 rdf:type schema:PropertyValue
78 N55d1c56d05784b19af33d92c5609b517 rdf:first N07286b27d6df403ab6e25829b6835292
79 rdf:rest Nc1c4d7bc4c1a4771bcf0ec4cfeebb816
80 N5719f4bef7e74c7fa15c6308136ca1c8 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 N64e9ed71e282493ea7f17eb197e7ea8f schema:familyName Moler
83 schema:givenName C.
84 rdf:type schema:Person
85 N6b0070cf33aa45ada8e628aa83ae38e3 rdf:first sg:person.014752300537.85
86 rdf:rest Nd2208cdb0fa048288b972903a3c39c16
87 N718f34e3515e403fa56041ac21a18f69 schema:familyName Stoer
88 schema:givenName J.
89 rdf:type schema:Person
90 N753e7483aacd4f90a0d8bcb862494eeb schema:familyName Günther
91 schema:givenName Christoph G.
92 rdf:type schema:Person
93 N79f61ed706514c7398834447f75bf4fb schema:familyName Gries
94 schema:givenName D.
95 rdf:type schema:Person
96 N7cb4e0b4658d4fee876fa9e01a0dcbd7 rdf:first N64e9ed71e282493ea7f17eb197e7ea8f
97 rdf:rest Nea9cf7294a954ec596b28633676c1850
98 N7d3e944e0c674a7499c98cdc98be2abf schema:name doi
99 schema:value 10.1007/3-540-45961-8_25
100 rdf:type schema:PropertyValue
101 N82a9787cf60f4bbea7a8fb9bc304e22f schema:familyName Wirth
102 schema:givenName N.
103 rdf:type schema:Person
104 N94a45dbccd4f45d79d86f8cd608e3ad8 rdf:first N287b7a7f193a4698a0012804f07d26ad
105 rdf:rest N05397f350b214126a35b4d3dc0d6a705
106 N9703cd7826da4393976fb665c79d7efa schema:name Springer Nature
107 rdf:type schema:Organisation
108 N9983bbc8f32b4dd081a96935c381cdef rdf:first N82a9787cf60f4bbea7a8fb9bc304e22f
109 rdf:rest N2a4cc9c9485f4bb7aaa93bcc2b4b0a93
110 Na982f8b6dfa646ba8816e4fc4b784d7f schema:familyName Luckham
111 schema:givenName D.
112 rdf:type schema:Person
113 Naad3ca98e6cb4991965b06ff522651e2 rdf:first Na982f8b6dfa646ba8816e4fc4b784d7f
114 rdf:rest N7cb4e0b4658d4fee876fa9e01a0dcbd7
115 Nadd24a72ce144d8ca00bb4cb4503e700 schema:familyName Pnueli
116 schema:givenName A.
117 rdf:type schema:Person
118 Nc1c4d7bc4c1a4771bcf0ec4cfeebb816 rdf:first Ncd208b9c0abe4979aa15f21d922399de
119 rdf:rest Nc4ee0b1715b44f4c83fed930535fa010
120 Nc4ee0b1715b44f4c83fed930535fa010 rdf:first N79f61ed706514c7398834447f75bf4fb
121 rdf:rest Naad3ca98e6cb4991965b06ff522651e2
122 Nc706dfbd1a694fc7a5967677234f068d schema:familyName Barstow
123 schema:givenName D.
124 rdf:type schema:Person
125 Ncd208b9c0abe4979aa15f21d922399de schema:familyName Brinch Hansen
126 schema:givenName P.
127 rdf:type schema:Person
128 Nd2208cdb0fa048288b972903a3c39c16 rdf:first sg:person.016650302365.34
129 rdf:rest rdf:nil
130 Nea9cf7294a954ec596b28633676c1850 rdf:first Nadd24a72ce144d8ca00bb4cb4503e700
131 rdf:rest N94a45dbccd4f45d79d86f8cd608e3ad8
132 Nf461fb743619422e847f227f5a83fb91 schema:isbn 978-3-540-45961-3
133 978-3-540-50251-7
134 schema:name Advances in Cryptology — EUROCRYPT ’88
135 rdf:type schema:Book
136 Nfc6e7075ab7349018619f85a6a044732 rdf:first Nc706dfbd1a694fc7a5967677234f068d
137 rdf:rest N55d1c56d05784b19af33d92c5609b517
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)


...