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
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;
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
DOI :
10.1109/ISIT.2006.261651
