Deniable data storage

[John Kelsey]

At 06:58 PM 11/5/03 -0800, James A. Donald wrote:
>I want to store information deniably.
...
>This would contain various items of information that one could
>extract by supplyin a secret, symmetric, key.   A random key would
>extract a block of gibberish of random length   There would be no
>indication as to how many bits of meaningful data were stored in the
>block, though obviously they would have to add up to less than the
>size of the block.

I believe one of Ross Anderson's students did something like this a few 
years ago, basically using error-correcting codes with a lot of 
redundancy.  The basic idea is that you use some kind of massive error 
correction and use a different sequence of bits with each key, so that 
you're very unlikely to have enough of your message bits clobbered by 
another message to make it impossible to decode correctly.  (It seems like 
there'd be a problem with information leakage about number of channels 
here, if you had a message encoded in that block of bits, because you would 
know when you decoded it how often you'd had bits flipped, but maybe they 
resolved that somehow.)

--John Kelsey, kelsey.j at ix.netcom.com
PGP: FA48 3237 9AD5 30AC EEDD  BBC8 2A80 6948 4CAA F259