[woliveirajr]

If I understood correctly, as long as Alice and Bob can arrange some meeting and agree to some method, they'll be able to communicate over any channel, be it encrypted or not.

Example: Alice and Bob agree that the 5th letter of the n-th phrase from a conversation will mean '1' if it is the set ones={A, C , E} and '0'={B, D, F}. And that the set will be generated based on some characteristic from some headline from a newspaper.

That will be secure even if used over the GE-encryption method from the government, and won't attract attention, except if someone knows how to deal with it.

Isn't that? So, a kind of steganography: hide information in plain sight, as long as it was agreed before and was not leaked.

[tmpmov]

The paper targets an adversarially selected encryption scheme. Thus perhaps any would work, though I sort of doubt this based on my reading. In addition, the paper supposes that the two parties should be able to communicate using a normal-ish public/private key method.

Based on the quotes below I belive paper relies explicitly on the GE channel's hardness to break:

"On Our Modeling Assumptions. Our model considers a relatively powerful adversary that, for example, has the ability to choose the encryption scheme using which all parties must communicate, and to decrypt all such communications. We believe that this can be very realistic in certain scenarios, but it is also important to note the limitations that our model places on the adversary.

The most obvious limitation is that the encryption scheme chosen by the adversary must be semantically secure (against third parties that do not have the ability to decrypt)."

Later:

"All known constructions of such undetectable random string embedding rely on the sampling of a public random seed after the adversarial strategy is fixed. In this paper, however, we are interested in bootstrapping hidden communications from the very ground up, and we are not willing to assume that the parties start from a state where such a seed is already present."

" We begin with the following simple idea: for each consecutive pair of ciphertexts c and c0, a single hidden (random) bit b is defined by b = f(c, c0) where f is some two-source extractor. It is initially unclear why this should work because (1) c and c0 are encryptions of messages m and m0 which are potentially dependent, and two-source extractors are not guaranteed to work without independence; ..."

"We overcome difficulty (1) by relying on the semantic security of the ciphertexts of the adversarially chosen encryption scheme. Paradoxically, even though the adversary knows the decryption key, we exploit the fact that semantic security still holds against the extractor, which does not have the decryption key."

[thorel]

This is correct: if both parties have some pre-agreed secret, then it is much easier to secretly communicate over any channel and the method you are describing works and is similar in spirit to standard steganographic methods.

However, deriving the "secret" from "some headline from a newspaper" will not work because the adversary can also perform the same derivation and will be able to extract the secret conversation as easily as Alice or Bob.