Psuedo-Private Key (eJazeera)

[Peter Fairbrother]

Tyler Durden wrote:
[...]
> Let's say I've been coerced into revealing the private key to a certain
> encrypted message. And now, of course, the authorities use that key and open
> the message, and see the contents (let's assume they are picture of a
> demonstration or whatever).
> 
> WOULDN'T IT BE NICE...If the original encrypted message actually had TWO
> messages inside it, both very similar. In this example, one of the messages
> is the "incriminating" pictures of the demonstration, the other is pictures
> of Pam Anderson or whatever.
> 
> AND, this double message has two private keys associated with it: one
> corresponds to the Pam Anderson photos, the other corresponds to the
> Demonstration photos. When coerced, I give up the key that opens the Pam
> Anderson photos (while hopefully annhilating the Incriminating photos).
> 
> Of course, there's no way the authorities know that there was another
> message (not if done very cleverly...Pam Anderson photos might be a little
> obvious) that they destroyed when they used the fake Private Key.
> 
> Does this exist? Would it be difficult?

Yes it exists. It's called deniable encryption. Two-level deniable
encryption is not hard, but it usually involves increases in data size.
There is some stuff about this in Crypto and Eurocrypt reports.

Steganography and steganogaphic filing systems can do something similar, but
the increase in message size tends to be larger.


I am developing a form of deniable encryption (as part of m-o-o-t) that
works slightly differently and does not involve message-size increases - in
fact it it decreases message size.

It's grammer-based and works a bit like this: A sentence is parsed, and eg
a noun is encoded as a number relating to one of a publicly shared
dictionary of nouns. This number is then encrypted. Decrypting with a random
key will give a noun in that position in the sentence in all possible
decryptions, and a good proportion of all randomly keyed decryptions will
apparently make sense.

There is a lot more involved, so eg both parties can give out the same false
key, and so eg the same nouns used more than once in a message will decrypt
to identical nouns in decryptions, as well as notions of closeness in the
words used in a typical message, but I have done both the theoretical
unicity calculations and some practical tests, and it works for email-length
messages. 

The main implementation problems I have are coding time and that the only
parser that works well enough is proprietary. If anyone else is working on
something similar I would like to know. I'm probably not a cypherpunk, more
a privacy avocate, but I do write code.

:)

-- 
Peter Fairbrother