How to Subvert Backdoored Encryption: Security Against Adversaries that Decrypt All Ciphertexts.

We study secure and undetectable communication in a world where governmentscan read all encrypted communications of citizens. We consider a world wherethe only permitted communication method is via a government-mandated encryptionscheme, using government-mandated keys. Citizens caught trying to communicateotherwise (e.g., by encrypting strings which do not appear to be naturallanguage plaintexts) will be arrested. The one guarantee we suppose is that thegovernment-mandated encryption scheme is semantically secure against outsiders:a perhaps advantageous feature to secure communication against foreignentities. But what good is semantic security against an adversary that has thepower to decrypt?

Even in this pessimistic scenario, we show citizens can communicate securelyand undetectably. Informally, there is a protocol between Alice and Bob wherethey exchange ciphertexts that look innocuous even to someone who knows thesecret keys and thus sees the corresponding plaintexts. And yet, in the end,Alice will have transmitted her secret message to Bob. Our security definitionrequires indistinguishability between unmodified use of the mandated encryptionscheme, and conversations using the mandated encryption scheme in a modifiedway for subliminal communication.

Our topics may be thought to fall broadly within the realm of steganography:the science of hiding secret communication in innocent-looking messages, orcover objects. However, we deal with the non-standard setting of adversarialcover object distributions (i.e., a stronger-than-usual adversary). We leveragethat our cover objects are ciphertexts of a secure encryption scheme to bypassimpossibility results which we show for broader classes of steganographicschemes. We give several constructions of subliminal communication schemesbased on any key exchange protocol with random messages (e.g., Diffie-Hellman).