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

Author

Johansson, Thomas ; Jönsson, Fredrik

Author_Institution

Dept. of Inf. Technol., Lund Univ., Sweden

Volume

48

Issue

10

fYear

2002

fDate

10/1/2002 12:00:00 AM

Firstpage

2669

Lastpage

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 (1989, 1994) identification scheme, the McEliece (1978) 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

computational complexity; decoding; public key cryptography; Hamming distance; McEliece public-key cryptosystem; NP-complete problem; Stern identification scheme; codeword; correlation attacks; cryptographic problems complexity; general decoding problem; probabilistic algorithm; received word; stream ciphers; Binary codes; Decoding; Galois fields; Hamming distance; Helium; Information technology; Information theory; Polynomials; Public key cryptography;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.2002.802608

Filename

1035119