| I gave a first pass summary in another comment but had a question based on my reading of the paper. I feel I understand it better now and can provide a better summary. TLDR: You can formally encrypt conversations using strings (or language phrases) such that even if they're communicated over a "compromised" channel, your encrypted conversation retains its confidentiality assuming that the compromised channel hasn't been fundamentally broken (e.g. the snooping party has the keys to the channel, not a universal lock pick that breaks the algorithm). The proposed scheme requires a channel with "strong" encryption capabilities, it won't work otherwise. For those wondering why that's a big deal: The paper is using public key encryption to enable subliminal messaging using normal everyday phrasing/conversations. You could have any conversation you wanted to (e.g. a non-forced or agreed upon previously conversation) and still communicate covertly (e.g. your talk carries extra meaning that an observer with access to the plain text wouldn't be able to discern). The two parties don't have to plan or strategize before the meeting takes place. In fact, as long as they both understand what public key cryptography is, they can use the technique proposed in this paper to communicate without ever having met before! I feel like that statement is what throws a lot people off, or wonder why they should care. For those wondering how it works that know some cryptographic stuff: The paper uses rejection sampling. They assume that the encryption of any given message will produce a string with desirable entropy. Meaning encrypting "hello" five times should result in 5 different encrypted cipher texts. They then select a desirable encryption of "hello" according to their extraction function f (which they defined in their subliminal messaging scheme and extracts the subliminal message but is also an entropy extractor). What the paper does is actually fairly straightforward scheme wise (though the math is different and takes a fair background to follow rigorously). Hand-waving again: Algorithm steps:
1. Establish a random key seed and perform a key exchange; you must be communicating over a semantically secure channel for this. Seed generation works by producing d cipher texts for each party, exchanging them, then using the greater than function on each cipher text to create a shared seed. They acknowledge that the seed is public to anyone that has decryption access to the government mandated encryption channel.
1.1 Do a key exchange, described as: "Let Ext be a strong seeded extractor, and let S serve as its seed. By rejection-sampling ciphertexts c until ExtS(c) = str, either party can embed a random string str of their choice in the conversation. By embedding in this manner the messages of a pseudorandom key-exchange protocol, both parties establish a shared secret sk∗." So they essentially use the rejection sampling to provide a cover for the key-exchange protocol. Pretty neat! 2. Using the seed and keys, do public key crypto like normal with the exception that transmitting cipher texts will be done on a single bit at a time by selectively choosing what cipher texts of cover messages are actually sent (that efficiency is very poor and I think they provide better techniques). The encrypted messages will thus be communicated by using an extractor function over a set of encrypted strings. The encrypted strings from step 2 can be generated from any conversation, without restriction, as long as the encryption function is strong. You do this by using a rejection sampling strategy to produce cipher texts with desirable characteristics. Example of step 2: Suppose you want to communicate "hello" as your cover text but you want to use the bit value 1 for your subliminal message. To do so, a scheme to encrypt the single bit value could be to ensure whatever cryptographic text you produce has an integer value greater than the last one you received. So, you encrypt your "hello" message repeatedly until it gives a value that, if represented as an integer, is larger numerically than the previous cipher text message. You then transmit this cryptographic text. Similarly, if you want to transmit 0 you generate a cipher text that will be less than the integer representation of the previous cipher text. Mathematically this scheme is as strong as the underlying government mandated encryption scheme (it uses the underlying cryptographic scheme as a source of entropy). Hope you found that intelligible and correct me if you see any mistakes! |