PPT eavesdroper able to output $m_{0}$ and $m_{1}$ of different lengths

Question

I've read the following two questions and their answers:

• Messages of different lengths and one-time computationally-secret
• Why is a non fixed-length encryption scheme worse than a fixed-length one?

I am still not convinced of what is the actual strategy of the adversary $A$. I understand that in case that the encryption scheme cipher depends on the length of the message to encrypt then $A$ could output $m_{0}$, $m_{1}$ of different lengths and would be able to tell which one was encrypted by the length of $Enc(m_{b})$ (where $b\gets\{0,1\}$).

Now, who promises that $|Enc(m)|$ depends on $|m|$?
Isn't it possible that $|Enc(m_{0})|=|Enc(m_{1})|$?

Answer 1

"Now, who promises that $|Enc(m)|$ depends on $|m|$?" $\:$ the protocol designers

"Isn't it possible that $|Enc(m_0)| = |Enc(m_1)|$?"
It is perfectly possible that $\:\:\big|\hspace{-0.03 in}\operatorname{Enc}(m_{\hspace{.02 in}0})\big| \:=\: \big|\hspace{-0.03 in}\operatorname{Enc}(m_1)\big|\;\;$.

I will use $k$ to denote the security parameter.
$1$ is polynomial in $k$, and a random message of length $1$ has probability half of being equal to "0".
Let $\hspace{.045 in}f$ be a polynomial such that for sufficiently large $k$, with probability greater than $\:1\hspace{-0.05 in}-\hspace{-0.04 in}\frac1{4\cdot \hspace{.02 in}k}\:$, $\:$ encrypting a random message whose length is $1$ will take at most $\hspace{.045 in}f(k)$ steps.
Combining the previous two sentences shows that for sufficiently large $k$, with probability
greater than $\:1\hspace{-0.05 in}-\hspace{-0.04 in}\frac1{2\cdot \hspace{.02 in}k}\:$, encrypting the message "0" will take at most $\hspace{.045 in}f(k)$ steps.
Since writing a bit takes a step, it is the case that for sufficiently large $k$, with probability greater
than $\:1\hspace{-0.05 in}-\hspace{-0.04 in}\frac1{2\cdot \hspace{.02 in}k}\:$, $\:$ encrypting the message "0" produces a ciphertext whose length is at most $\hspace{.045 in}f(k)$.
For each $k$, define "the $k$-th bad set" to be the set of plaintexts $m$ of
length $\:\hspace{.045 in}f(k)+k\:$ such that there exists a ciphertext $c$ of length at most
$\hspace{.045 in}f(k)$ such that the probability of $c$ decrypting to $m$ is not less than $\frac23$.
Observe that for each $k$, the $k$-th bad set has less than $\:2^{\hspace{.04 in}f(k)+1}\:$ elements.
Since there are $\:2^{\hspace{.04 in}f(k)+k}\:$ possible messages of length $\:\hspace{.045 in}f(k)+k\:$, $\:$ it is the case that for all $k$,
the probability that a random such message is in the $k$-th bad set is less than $\:1/\big(2^{k-1}\hspace{-0.03 in}\big)\;$.
It follows that for all $k$, the probability that encrypting and then decrypting a random
plaintext of length $\:\hspace{.045 in}f(k)+k\:$ does not result in the original plaintext is greater than
$\frac13 \cdot \left(1\hspace{-0.04 in}-\hspace{-0.03 in}\left(1/\big(2^{k-1}\hspace{-0.03 in}\big)\right)\right)\:\:$ times the probability that encrypting a random plaintext
of length $\:\hspace{.045 in}f(k)+k\:$ outputs a ciphertext whose length is at most $\hspace{.045 in}f(k)$.
Since $\hspace{.045 in}f(k)$ is polynomial in $k$, $\:\hspace{.045 in}f(k)+k\:$ is also polynomial in $k$, so for sufficiently large $k$,
the probability that encrypting and then decrypting a random plaintext of length
$\hspace{.045 in}f(k)+k\:$ does not result in the original plaintext is less than $\frac1{8\cdot \hspace{.02 in}k}$.
For all $k$, if $\:3< k\:$ then $\;\;\; \frac14 \:\: < \:\: \frac13 \cdot \left(1\hspace{-0.04 in}-\hspace{-0.03 in}\left(1/\big(2^{k-1}\hspace{-0.03 in}\big)\right)\right) \:\:\:\:$.
Combining the previous three sentences shows that for sufficiently large $k$,
the probability that encrypting a random plaintext of length $\:\hspace{.045 in}f(k)+k\:$ has
probability less than $\frac1{2\cdot \hspace{.02 in}k}$ of outputting a ciphertext whose length is at most $\hspace{.045 in}f(k)$.


Therefore the adversary $\mathcal{A}^{\hspace{.03 in}f}$ defined by

let x be a string of f(k)+k random bits
send  [m0,m1] = ["0",x]  to the challenge oracle
if  len(c) <= f(k)  then  return 0  else  return  1

is efficient and such that for sufficiently large $k$, it distinguishes the two cases
$b=0\:$ and $\:b=1\:$ from each other by an amount greater than $\:1\hspace{-0.04 in}-\hspace{-0.03 in}\frac1k\;$.

Answer 2

Actually, every encryption algorithm has an associated message space which defines the maximum message size which can be encrypted and the ciphertext is always of size of the associated ciphertext space. If the message at hand is larger than the message space of the encryption algorithm, you have to encrypt the message "block by block" (where a block can also be a bit. For block ciphers there are various ways to realise this, e.g., CBC (see here), for stream ciphers viewing the message space as being a bit it should be obvious how the ciphertext size depends on the message size and for asymmetric schemes in practice this is typically not required since you use hybrid encryption and thus always only encrypt a single "block".

Now for achieving the weakest reasonable security, i.e., indistinguishability under chosen plaintext attacks (IND-CPA) where i'm talking about public key encryption schemes here (actually the argument is the same for one-time computationally-secret as in your referenced question), an adversary providing two challenge messages $m_0$ and $m_1$ and given back the ciphertext $c_b$ has to figure out which one has been encrypted (i.e., determine whether $b=0$ or $b=1$) (here it does not really matter that the adversary can then afterwards ask an encryption oracle for encryptions of messages different from the challenge messages). Clearly, if one of the challenge messages is out of the message space and the other is larger, i.e., requires $>1$ blocks, then it is trivial to distinguish the two ciphertexts.

Consequently, in the attack game one requires that if one message is larger, the second is padded to have the same length as the first to rule out this trivial attack. Then, if both messages are of the same length (and padded) both ciphertexts will be of the same length and then the adversary has to apply a non-trivial strategy to figure out which message has been encrypted as a challenge.

Edit: PrivK Game:

Ok, the PrivK game is defined as follows (I took the definition from this question):

An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$ is one-time computationally-secret if for any PPT adversary $\cal A$ it holds that $Pr[PrivK_{\cal A}^{eav}(n)=1]−1/2$ is negligible function, where $PrivK_{\cal A}^{eav}(n)$ denotes the output of the following experiment:

(a) The adversary $\cal A$ on input $1^n$ outputs a pair of messages $m_0,m_1$.

(b) Let $k\leftarrow Gen(1^n)$ and let $b\in \{0,1\}$ be chosen uniformly at random. Then a ciphertext $c\leftarrow Enc_k(m_b)$ is computed and given to $\cal A$.

(c) $\cal A$ on input $c$ outputs a bit $b'$.

(d) The output of the experiment is $1$ if $b'=b$ and $0$ otherwise.

Let us assume that we have a block cipher with block size $k$ bits and let the adversary now choose a message $m_0\in \{0,1\}^k$ and $m_1 \in \{0,1\}^{2k}$, i.e., message $m_0$ has one block and message $m_1$ has two blocks. Consequently, $c_0=Enc_k(m_0)$ will be of size $k$ bits and $c_1=Enc_k(m_1)$ will be of size $2k$ bits. Hence, the adversary will always output $1$ and thus $Pr[PrivK_{\cal A}^{eav}(n)=1]=1$ and $Pr[PrivK_{\cal A}^{eav}(n)=1]-1/2$ is $1/2$, which is non negligible. Consequently, we need to require that $|m_0|=|m_1|$ to rule out this strategy for $\cal A$.