Distinguish messages Since i cannot comment on questions, I give my own:

If a secret key encrypt algorithm can encrypt messages of arbitrary length and the encrypt algorithm is probabilistic then: suppose the adversary selects two messages of different length, $||m_0||=n$, $||m_1||=l$ and $n&lt;l$. She gets back a ciphertext $c$. How can she tell which message was encrypted? Cause I thought that since the encryption is probabilistic the length of $c$ might as well be $n$ (which is not likely, but just to show that $c$ can have any length), while message $m_1$ was the one encrypted. Right? or very wrong?
The encryption algorithm is probabilistic but the length (or better the entropy) of the ciphertext must be at least the length of the message. If the length of the ciphertext is shorter than the length of the plaintext, then you loose information about the plaintext while encryption process and you cannot decrypt it correctly. And the encryption algorithm is memoryless and does not know anything about older or other messages.

Now, suppose you have the two messages $||m_0|| = l_0$, $||m_1|| = l_1$ and $l_0 &lt;&lt; l_1$ (say $l_0 = 1 \, bit$ and $l_1$ is very large $&gt;10G \, bits$). If you receive a ciphertext shorter than $l_1$ you know that $m_0$ was encrypted. I think you can see, that an encryption algorithm, that produces ciphertexts longer than $l_1$ when you only encrypt a single bit, is very inefficient.

The only way to cancel this effect is to restrict the length of the plaintext messages and produce ciphertexts equal or longer than this maximum input length. But in this case, the plaintext of a single bit will be padded and you can directly define the security with equal length messages.