Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On the complexity of some cryptographic problems based on the general decoding problem

Johansson, Thomas LU orcid and Jönsson, Fredrik LU (2002) In IEEE Transactions on Information Theory 48(10). p.2669-2678
Abstract
A new probabilistic algorithm for decoding one received word from a set of many given received words, into a codeword such that the Hamming distance between the received word and the codeword is at most t, is proposed. The new algorithm is applicable to several cryptographic problems, such as the Stern identification scheme, the McEliece public-key cryptosystem, and in correlation attacks on stream ciphers. When applicable, it runs significantly faster than previous algorithms used for attacks on these cryptosystems.
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Stern identification system, cryptosystem, McEliece, decoding algorithms, complexity, correlation attack
in
IEEE Transactions on Information Theory
volume
48
issue
10
pages
2669 - 2678
publisher
IEEE - Institute of Electrical and Electronics Engineers Inc.
external identifiers
  • wos:000178163300003
  • scopus:0036794609
ISSN
0018-9448
DOI
10.1109/TIT.2002.802608
language
English
LU publication?
yes
id
50f8a328-0ba6-4ac8-8cb5-7cddbf2deb19 (old id 328377)
date added to LUP
2016-04-01 16:58:49
date last changed
2023-09-05 04:53:53
@article{50f8a328-0ba6-4ac8-8cb5-7cddbf2deb19,
  abstract     = {{A new probabilistic algorithm for decoding one received word from a set of many given received words, into a codeword such that the Hamming distance between the received word and the codeword is at most t, is proposed. The new algorithm is applicable to several cryptographic problems, such as the Stern identification scheme, the McEliece public-key cryptosystem, and in correlation attacks on stream ciphers. When applicable, it runs significantly faster than previous algorithms used for attacks on these cryptosystems.}},
  author       = {{Johansson, Thomas and Jönsson, Fredrik}},
  issn         = {{0018-9448}},
  keywords     = {{Stern identification system; cryptosystem; McEliece; decoding algorithms; complexity; correlation attack}},
  language     = {{eng}},
  number       = {{10}},
  pages        = {{2669--2678}},
  publisher    = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}},
  series       = {{IEEE Transactions on Information Theory}},
  title        = {{On the complexity of some cryptographic problems based on the general decoding problem}},
  url          = {{http://dx.doi.org/10.1109/TIT.2002.802608}},
  doi          = {{10.1109/TIT.2002.802608}},
  volume       = {{48}},
  year         = {{2002}},
}