Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The following paper interests me very much:

D. W. Gillman, M. Mohtashemi, R. I. Rivest, On breaking a Huffman code. IEEE Trans. Inf. Th. Vol.42 (1996), pp 972-976.

However, unfortunately due to my poor knowledge, my understanding of it can only be partial. Hence I should appreciate help of the experts:

(1) As far I could understand, i.e. if I don't err in reading, the conclusion/claim of the paper is that substitution with random prefix codes is highly secure (though no sentence exactly like this is to be found in the paper). I like to know whether this is indeed the claim of the authors. (In case the answer is no or not quite, what is the real conclusion/claim?)

(2) [Deleted corresponding to a suggestion of rath.]

[Addendum] (1) has been answered by D. W. Corresponding to a suggestion of him, I have posted a new question entitled "Any good means to enhance the security of encryption processing with random prefix codes?"

Thanks in advance.

share|improve this question

closed as unclear what you're asking by D.W., figlesquidge, e-sushi, AFS, archie Apr 9 '14 at 3:47

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

Oh, I should have replaced "claim" with "claim according to my interpretation", since I am not 100% sure of the correctness of my interpretation (as I said, my understanding of the article is only partial). If the real claim is not correct, then the other phrase of mine would make sense IMHO. – Mok-Kong Shen Mar 28 '14 at 5:23
@Mok-KongShen: Perhaps you could update the wording of your question to clarify this. – figlesquidge Mar 28 '14 at 10:45
@figlesquidge: Done. Thank you. – Mok-Kong Shen Mar 28 '14 at 17:42
Question 2 is a bit too much really. You may find someone willing to do it, but essentially you're asking for an in-depth evaluation of the paper, which is off-topic. On that basis I suggest you remove it. Moving on, it may further help the question if you point where in the document the claim is made/implied, as well as include a quote or some equations that demonstrate it. And don't worry about misinterpreting the paper; as you correctly note we all make mistakes. I hope this helps. – rath Apr 1 '14 at 21:27
@rath: I have deleted (2) corresponding to your suggestion. – Mok-Kong Shen Apr 2 '14 at 0:15

No. These codes are not secure. They are not secure against a known-plaintext attack or chosen-plaintext attack, if the cryptanalyst has enough known/chosen text.

Nowhere does the paper claim that these codes are secure enough for practical use. It appears that the paper looks only at ciphertext-only attacks, but security against ciphertext-only attacks is not enough to achieve a useful level of security. (In fact, it looks like the paper focuses on an even more restrictive attack model, where the attacker doesn't even know the probability distribution on plaintexts. Of course, in practice, this is even more unrealistic, so it further limits the applicability of the paper's results.)

Bottom line: No, the paper does not imply that it would be secure to use Huffman encoding for encryption.

share|improve this answer
But IMHO in crypto one rarely uses one single algorithm (in the narrow sense) but a combination of confusion and diffusion in the terms of Shannon. So if one appropriately combine prefix-coding with e.g. certain transpositions, would that be a good defense against known/chosen text attacks? (In fact I have attempted to do such a combination in a humble scheme of mine recently ( Actually, it was because I was not very sure whether prefix-coding is "self-sufficient" that I did the original posting in order to learn more about its real strength.) – Mok-Kong Shen Mar 28 '14 at 20:37
@Mok-KongShen, that's of course a different question, and of course the answer to that question will probably depend on the details. This is not a discussion forum: one question per question, please (so it's important to make sure that you frame your question well so it reflects what you really want answered). – D.W. Mar 28 '14 at 21:40
I understand you mean that one should limit the scope of a question to the least minimum possible. So I'll have to ask a new question in the present context. Thank you very much for the guidance. – Mok-Kong Shen Mar 29 '14 at 16:04
I have duly correspondingly formulated my new question with the best care I could manage to do to limit its scope to the least minimum and posted it under the title "Any good means to enhance the security of encryption processing with random prefix codes". – Mok-Kong Shen Mar 30 '14 at 10:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.