[eadmund]

Wouldn't this scheme still be semantically secure, while defending against the steganography in the paper?

1. encrypt plaintext | 128-bit random value 2. if last cyphertext was greater than its predecessor but less than this cyphertext, go to step 1 3. if last cyphertext was less than its predecessor but greater than this cyphertext, go to step 1

[thorel]

This is an interesting point, but note that the scheme you are suggesting is "stateful" (you need to remember the last ciphertext to be able to generate the next one). The standard definition of an encryption scheme (and the one used in this paper) is stateless (once you have generated the key, you can produce ciphertexts without keeping track of any state). Stateful encryption schemes lead to all kind of complications and for this reason tend to be studied way less from the theoretical perspective. But it would be an interesting question to see if the results from this paper extend to the stateful setting (and I agree that because of the example you provide, some adaptation would have to be made).

[eadmund]

Drat, I must have misunderstood the paper, then, because it seemed (to me) to require keeping the old cyphertext in order to determine the GT relation.

Any chance you have a more-plain-English (e.g. like in a NIST pub) description of the paper's proposed system.