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

Thomas Johansson; Fredrik Jönsson

doi:10.1109/TIT.2002.802608

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

Thomas Johansson, Fredrik Jönsson

Research output: Contribution to journal › Article › peer-review

28 Citations (Scopus)

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.

Original language	English
Pages (from-to)	2669-2678
Number of pages	10
Journal	IEEE Transactions on Information Theory
Volume	48
Issue number	10
DOIs	https://doi.org/10.1109/TIT.2002.802608
Publication status	Published - 2002-Oct
Externally published	Yes

Keywords

Complexity
Correlation attack
Decoding algorithms
McEliece cryptosystem
Stern identification scheme

Access to Document

10.1109/TIT.2002.802608

Cite this

@article{f9451143352b404caac31e293d2d1c94,

title = "On the complexity of some cryptographic problems based on the general decoding problem",

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.",

keywords = "Complexity, Correlation attack, Decoding algorithms, McEliece cryptosystem, Stern identification scheme",

author = "Thomas Johansson and Fredrik J{\"o}nsson",

note = "Funding Information: Manuscript received February 8, 2001; revised May 24, 2001. This work was supported by the Foundation for Strategic Research–PCC under Grant 9706-09. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, MIT, Cambridge, MA, August 1998.",

year = "2002",

month = oct,

doi = "10.1109/TIT.2002.802608",

language = "English",

volume = "48",

pages = "2669--2678",

journal = "IEEE Transactions on Information Theory",

issn = "0018-9448",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

number = "10",

}

TY - JOUR

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

AU - Johansson, Thomas

AU - Jönsson, Fredrik

N1 - Funding Information: Manuscript received February 8, 2001; revised May 24, 2001. This work was supported by the Foundation for Strategic Research–PCC under Grant 9706-09. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, MIT, Cambridge, MA, August 1998.

PY - 2002/10

Y1 - 2002/10

N2 - 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.

AB - 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.

KW - Complexity

KW - Correlation attack

KW - Decoding algorithms

KW - McEliece cryptosystem

KW - Stern identification scheme

UR - http://www.scopus.com/inward/record.url?scp=0036794609&partnerID=8YFLogxK

U2 - 10.1109/TIT.2002.802608

DO - 10.1109/TIT.2002.802608

M3 - Article

AN - SCOPUS:0036794609

SN - 0018-9448

VL - 48

SP - 2669

EP - 2678

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

IS - 10

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this