Complexity aspects of guessing prefix codes

DOI10.1007/BF01185434MaRDI QIDQ1336967zbMATH OpenFDO

Authors Aviezri S. Fraenkel, Shmuel T. Klein

Publication date 13 October 1997

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01185434

complexity encryption Huffman codes NP-completeness prefix codes

Data encryption (aspects in computer science) (68P25) Analysis of algorithms and problem complexity (68Q25) Prefix, length-variable, comma-free codes (94A45) Cryptography (94A60)

Review text

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.

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Complexity aspects of guessing prefix codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1336967)