Suppose Alice and Bob want to "secretly" communicate a message, we'll call the message LL for love-letter, but the government mandates an encryption scheme, we'll call it GE for government encryption. This encryption scheme allows the government to decrypt your correspondence as they know the keys that are necessary for its use.
Suppose also that GE is "secure": only Alice, Bob, and the government can decrypt an encrypted message. We consider this secure as the government already has the keys and hasn't fundamentally broken the algorithm.
The paper proposes that Alice and Bob can still communicate their LL and that the government won't understand it, even over a link that the government can decrypt. Further, the conversation between Alice and Bob will be encoded in such a way that it does not appear to the government that encryption on top of the mandated GE is taking place. In addition, even if the government knew that the conversation had subliminal meaning it wouldn't be capable of decrypting it/understanding it: the LL was encrypted using a method as hard as the GE. Thus the paper gives a good security guarantee for the subliminal messages.
I thought the important point they make in the paper is that the proposed scheme should not generate messages that are clearly encrypted: the government should see a normal conversation between Alice and Bob unrelated to the LL. They reference steganography as an example of sending encrypted information that doesn't appear to be encrypted (e.g. via a message encoding in the color bits of a picture such that the picture looks the same before and after encoding your message into it). We'll call this the normality constraint (NC). They then give an impossibility result for something known as local decoding. Metaphorically, I think local decoding translates to using the same picture to carry a conversation stegenographically. So using your favorite meme picture repeatedly for the stegenographic conversation isn't secure (again, my understanding is shallow here and the constraints may be even stricter). It would appear though that you could randomly select from a meme archive to have your private stegongraphic-like conversation (treating the pictures as strings of bits and randomly selecting among them for the purposes of the proposed algorithm, I explain more below)
The NC motivates them to use a probabilistic function over a set of strings as the alphabet/symbols of their encryption.
I think this means that the government would see a conversation that is syntactically correct and not outrageously meaningless, though I didn't see this quantified/addressed directly in the paper (correct me if I'm wrong).
Thus, as I didn't see the semantics of the encrypted subliminal conversation addressed I felt motivated to attempt a quick answer myself (again my shallow understanding of the paper may have overlooked how they addressed this).
Specifically: Wouldn't it become obvious if the government saw a syntactically wrong and semantically meaningless conversation?
My hair-brained scheme to address the question goes like this:
Use phrase indexes or phrasal pairs. A phrase index would be a string like "hey, how are you?". A phrasal pair might be pairs of related phrasal indexes. I could see this being mechanically generated via machine learning. Although this solution has its own pitfalls as you can probably guess and would need further fleshing out.
The semantic authenticity required by the NC seems to be hard to satisfy based on my reading. Would any care to enlighten me?
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).