A NP-Complete Problem in Coding Theory with Application to Code Based Cryptography

摘要

It is easy to determine if a given code C is a subcode of another known code D. For most of occurrences, it is easy to determine if two codes C and D are equivalent by permutation. In this paper, we show that determining if a code C is equivalent to a subcode of D is a NP-complete problem. We give also some arguments to show why this problem seems much harder to solve in practice than the Equivalence Punctured Code problem or the Punctured Code problem proposed by Wieschebrink [21]. For one application of this problem we propose an improvement of the three-pass identification scheme of Girault and discuss on its performance.