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?

My answers were:

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}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.