Complexity aspects of guessing prefix codes (Q1336967)

This paper deals with the complexity aspects of guessing prefix codes used as an encryption method, proposed for applications which do not require the absolute secrecy. The authors describe conditions under which the potential profits of ``breaking the code'' are less than costs of the decryption effort. They prove that various decoding problems involving variable -- length prefix codes, e.g. Huffman codes, that also optimise the text compression, are NP-complete. This means that in the case of storing, for instance a data base on a CD-ROM, in an encrypted form, there is no polynomial algorithm for ``breaking the code''.