Computational Complexity

Monday, July 09, 2007

 
`Its Huffman coded!' does make sense!

Posted by GASARCH

On the post Math Terms used in Real Life- Good or Bad I mentioned the following:

On 24, season two, there was a line `we can't break in, its been Huffman coded!' This makes no sense mathematically but it raises awareness of security issues.

I had thought that Huffman Codes are just used to compress data and had nothing to do with hiding information. I was wrong! Yakov Nekrich pointed out the following to me:

Actually Huffman codes can be difficult to break, see for instance this article: On breaking a Huffman code by Gillman, D.W. Mohtashemi, M. Rivest, R.L.

I'm curious- did the writers of 24 know this or not? I would guess no, and they just lucked out. Unless Hillman or Mohtashemi is moonlightening as a writer for 24 (I doubt Rivest needs the money.)

4:17 PM #

1.  Nagesh Adluru says:  
   
   This is the second time I am pointing out a typo:), Bill.
   
   It's Gillman in the last sentence not Hillman.
   

   5:26 PM, July 09, 2007

2.  Bram Cohen says:  
   
   Compression in general does an okay job of obfuscating data. Not even vaguely cryptographically secure in the modern sense, but reasonable at making it look like line noise.
   

   6:16 PM, July 09, 2007

3.  Anonymous says:  
   
   Slate carries an interview with 24 writer Loeff, where he says he is "a mathematician and programmer by trade."
   
   I happen to play Go with another 24 writer. Methinks the writers of this show are more technologically savvy than one might otherwise expect.
   

   1:35 PM, July 20, 2007