Say $\Pi=[Gen,Enc,Dec]$ private key encryption scheme, such that for $k \in \text{{0,1}}^n$, $Enc_k$ is only defined for message of length at most $p(n)$. (for some polynomial)
I need to construct a scheme for eavesdrop indistinguishability test where the eavesdrop isn't restricted to output equal-length message.
I saw a paper (last question) where given plaintext $m$ of length at most $p(n)$, they first padded $m$ from the left side with $0^{p(n)-|m|-1}1$ to get a message of length $p(n)$, and then applied $Enc_k(.)$ on the result. For decryption, they first used $Dec_k(.)$ on the ciphertext, and then parsed $0^t1$ to leave only $m$.
But what if for example, I want to encrypt the messages $0^t10^{p(n)-t-1}$ and $0^{p(n)-t-1}$ for some $1 \leq t \lt p(n)-1$, won't they be encrypted to the same cipher text?
2 Answers
That homework assignment is not entirely precise: If you allow $|m| = p(n)$, the padding doesn't make sense: $0^{-1}1$. Therefore, you would have to limit $|m| \leq p(n)-1$ to avoid that case.
For your example and question: You're right, if you consider that a prefix $0^{-1}1$ actually is the empty string (no padding). Then your strings are equal. However, that case is actually undefined and should be fixed with reducing the message length by $1$.
From an information theoretic point of view: There are $2^{n}$ messages of length (exactly) $n$. And there are $\sum_{k=0}^{n}2^k = 2^{n+1} - 1$ messages of length $n$ or less. So if you consider the set of all messages of length $n$ or less, and consider those shorter messages as different messages, then you actually have $n+1$ bits of entropy (rounded to the next integer) and need at least a message of $n+1$ bits length to encode that information.
As you correctly observe, the solution given in the notes you've linked to doesn't work for messages of length exactly $|m| = \ell(n)$, since the given procedure would try to pad such messages with the prefix $0^{\ell(n)-|m|-1}1 = 0^{-1}1$ (which is obviously impossible, as no actual bitstring can have a negative length). Indeed, trying to add any non-empty padding to such a message would increase its length above the limit $\ell(n)$, whereas leaving such message unpadded would, as you note, introduce ambiguity.
However, there's a seemingly simple fix: we can generate longer keys. Specifically, instead of just having ${\sf Gen'} = {\sf Gen}$ as in the answer proposed in your linked notes, we can define ${\sf Gen'}(1^n) = {\sf Gen}(1^n1)$, giving us a key of length at least $n+1$ (by the assumption, given in Definition 3.7, that ${\sf Gen}(1^n)$ outputs a key of length at least $n$) and thus the ability to encrypt messages of length up to $\ell(n+1)$.
Of course, this only fix works if the polynomial $\ell$ satisfies the additional requirement that $\ell(n+1) \ge \ell(n)+1$. More generally, by suitably modifying the definition of ${\sf Gen'}$, we could make this work for any polynomial $\ell$ that is asymptotically strictly increasing (i.e. of positive order, and having a positive leading coefficient). However, I don't see any obvious way to deal with degenerate cases like $\ell(n) = c$ for some constant $c$; the fact that this possibility is not excluded might just be a mistake in the textbook. (Indeed, it seems to me that simply restricting the exercise to the special case of $\ell(n) = n$ would fix this issue and generally simplify the exercise, without hurting its educational value in any obvious way.)
Or perhaps the textbook authors had some other, less obvious solution in mind. Yehuda Lindell does read this site, so if that's the case, perhaps he can clarify the issue. :)
Addendum: While reading the original exercise more carefully, it occurred to me that there's an alternative way to interpret it: namely that, instead of having to use a specific given encryption scheme $\Pi = [{\sf Gen}, {\sf Enc}, {\sf Dec}]$ to construct a new scheme $\Pi' = [{\sf Gen}', {\sf Enc}', {\sf Dec}']$, we might simply be meant to construct a scheme $\Pi = [{\sf Gen}, {\sf Enc}, {\sf Dec}]$ with the stated properties (i.e. only capable of encrypting messages of length $\ell(|k|)$, but eavesdropper indistinguishable even if the adversary outputs messages of unequal length) from scratch by any reasonable means available.
If so, there are plenty of easy ways to solve this exercise. For example, we can just use the padding scheme suggested in the linked notes to unambiguously pad all the input messages to length $\ell(|k|)+1$, and then use any of the constructions of eavesdropper indistinguishable encryption schemes given earlier in the chapter, possibly with minor modifications, to encrypt the padded messages. (It's easiest if we choose a construction that can already encrypt messages of arbitrary length, since then we don't need to worry about whether our key is long enough.)
