Problem $1$: On leaking, or hiding, the message length

Consider encryption scheme Gen, Enc, Dec$)$ that is EAV$-$secure w$.$r$.$t$.$ the definition in Figure $1.$

Figure $1$: Indistinguishability of encryptions in the presence of an eavesdropper.

$(1)$ What does the condition $|m_0|=|m_1|$ capture? Does it weaken or strengthen $\text{'}$s security?

$(2)$ Let PrivK$-$EAV $2_{A,{}^{\text{'}}}(n)$ be the game in Figure $1$ where $A$ is allowed to choose challenge messages

of arbitrary length for breaking encryption scheme ${}^{\text{'}}=(Ge{n}^{\text{'}},En{c}^{\text{'}},De{c}^{\text{'}}),$ and consider the security

notion derived by this modified game: Intuitively, ${}^{\text{'}}$ is EAV$2-$secure$,$ if no efficient A can determine

$c_b$ better than guessing, even when $|m_0||m_1|.$ Show that no EAV$2-$secure scheme ${}^{\text{'}}$ exists.

Hint: First, note that ${}^{\text{'}}$ is defined over message space $M=\{0,1{\}}^{**},$ i$.$e$.,$ messages of

arbitrary length. Then, assume that polynomial $p(n)$ is an upper bound on the time

spent by Enc' for encrypting a single bit, and consider what happens when A chooses

$m_{0}in\{0,1\}$ and a random $m_{1}in\{0,1{\}}^{p(n)+c},$ where $c1$ a positive integer.

$(3)$ Show that EAV$2-$security can be achieved by encryption schemes defined over messages up to

a given maximum length, i$.$e$.,$ by schemes ${}^{\text{'}}$ such that for kin$\{0,1{\}}^n,$ algorithm $En{c}_k^{\text{'}}$ is defined

over message space $M^{\text{'}}=\{m$:$|m|l\},$ where $ll(n)$ for some given polynomial $l(*).$

Hint: Construct a scheme ${}^{\text{'}}=(Ge{n}^{\text{'}},En{c}^{\text{'}},Dec{e}^{\text{'}})$ that encrypts messages in $M^{\text{'}}$ by

employing a EAV$-$secure scheme Gen, Enc, Dec$)$ with message space $M.$ Consider

an algorithm Enc ${?}^{\text{'}}$ that on input message $m^{\text{'}}in{M}^{\text{'}},$ merely applies Enc on a unique

and inversible encoding $m=E(m^{\text{'}})inM$ of $m^{\text{'}}$ in a way that "compensates" for the

absence of the restriction $|m_0|=|m_1|$ in game $Priv{K}^{-\text{E}\text{A}\text{V}}{2}_{A,{}^{\text{'}}}(n).$ Then, prove that ${}^{\text{'}}$

is EAV$2-$secure via a proof by reduction.

$*****$ Please answer question number $3$