# Proving a scheme's EAV-insecurity

EDIT: The instructor clarified that part (a) was wrong. He declined to indicate why. I can share more details of the prompt if need be.

I apologize again if this question is too low-level; it comes from a practice midterm in a course I'm taking. I was told by an instructor that my proposed solution was wrong, but not why. The notation is Katz's.

For the problem, $$F:\{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n$$ is a block cipher (or pseudorandom permutation). The scheme works as follows: to encrypt $$M = m_1 || \cdots || m_l$$, where each $$m_i \in \{0,1\}^n$$, we select a key $$k$$, choose a uniform $$\mathrm{ctr}$$, and output $$\mathrm{ctr}||F_k(\mathrm{ctr} + 1 + m_1)||\cdots||F_k(\mathrm{ctr} + l + m_l).$$ The question(s) were a) how do we decrypt, and b) how can the scheme be shown EAV-insecure?

a) $$F_k$$ is 1-1, so invertible; for each $$i$$th block we compute $$m_i = F_k^{-1}(c_i) - \mathrm{ctr} - i$$, and return $$m_1||\cdots||m_l$$.
b) Pick $$m_l' = m_{l-1}' + 1 = \cdots = m_1' + l - 1$$, and (towards an EAV attack) let $$m_0 = m_1'||\cdots||m_l'$$; choose $$m_1$$ at random. Let $$\mathcal{A}$$ output $$b' = 0$$ if $$c_1 = \cdots = c_l$$ and $$b' = 1$$ otherwise. Then $$\Pr[\mathrm{PrivK^{\mathrm{eav}}}_{\mathcal{A}}(n) = 1] = \frac{1}{2} \Pr[\mathcal{A}$$ outputs $$0|b = 0] + \frac{1}{2}\Pr[\mathcal{A}$$ outputs $$1|b = 1] = \frac{1}{2} \Pr[\mathcal{A}$$ outputs $$0|b = 0] + \frac{1}{2}(1 - \Pr[\mathcal{A}$$ outputs $$0|b = 1]) = \frac{1}{2}\cdot1 +$$ $$\frac{1}{2}\cdot(1 - \left(\frac{1}{2^n}\right)^{l-1}).$$ This is plainly greater than 1/2 + $$\epsilon(n)$$ for negligible $$\epsilon$$, so we see that the scheme is not EAV-secure against $$\mathcal{A}$$.