DocumentCode
2946797
Title
Two NP-complete Problems in Coding Theory with an Application in Code Based Cryptography
Author
Wieschebrink, Christian
Author_Institution
Federal Office for Inf. Security, Bonn
fYear
2006
fDate
9-14 July 2006
Firstpage
1733
Lastpage
1737
Abstract
In this paper it is shown that the reconstruction of a punctured code from a given code is an NP-complete problem. Based on this observation a modification of code-based cryptosystems such as the Niederreiter scheme is suggested. In particular the modification is resistant to the Sidelnikov-Shestakov attack. Some other possible attacks are reviewed, and secure key parameters are estimated
Keywords
codes; computational complexity; cryptography; NP-complete problems; Niederreiter scheme; Sidelnikov-Shestakov attack; code based cryptography; coding theory; punctured code; Binary codes; Decoding; Galois fields; Information security; Linear code; NP-complete problem; Parameter estimation; Polynomials; Public key cryptography; Reed-Solomon codes;
fLanguage
English
Publisher
ieee
Conference_Titel
Information Theory, 2006 IEEE International Symposium on
Conference_Location
Seattle, WA
Print_ISBN
1-4244-0505-X
Electronic_ISBN
1-4244-0504-1
Type
conf
DOI
10.1109/ISIT.2006.261651
Filename
4036264
Link To Document