# Using an Even-Mansour block cipher in a tweakable mode of operation

Assume that:

• $P(X): \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $Q(X): \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $E(K, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $D(K, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $\widetilde{E}(K, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $\widetilde{D}(K, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $E_{*}(K, IV, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{IV}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $D_{*}(K, IV, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{IV}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$.
• $\ell_{X}$, $\ell_{K}$, $\ell_{T}$, and $\ell_{IV}$ are equal.
• $P$ and $Q$ are each other's inverses.
• $E(K, X) = P(X \oplus K) \oplus K$.
• $D(K, X) = Q(X \oplus K) \oplus K$.
• $\widetilde{E}(K, T, X) = E(E(K, T), X)$.
• $\widetilde{D}(K, T, X) = D(E(K, T), X)$.
• $E_{*}(K, IV, T, X) = \widetilde{E}(E(K, IV), T, X)$.
• $D_{*}(K, IV, T, X) = \widetilde{D}(E(K, IV), T, X)$.

$P$ and $Q$ are inverses and are both publicly known pseudorandom permutations that form the core of a single-key Even-Mansour block cipher. $\widetilde{E}$/$\widetilde{D}$ and $E_{*}$/$D_{*}$ are two modes of operation that I've constructed from it. With the mode of operation built around $\widetilde{E}$/$\widetilde{D}$, $CT_{i} = \widetilde{E}(K, i, PT_{i})$ and $PT_{i} = \widetilde{D}(K, i, CT_{i})$. With the mode of operation built around $E_{*}$/$D_{*}$, $CT_{i} = E_{*}(K, IV, i, PT_{i})$ and $PT_{i} = D_{*}(K, IV, i, CT_{i})$.

As I understand the Even-Mansour scheme, an attacker who possesses $2^{0.5 \times \ell_{X}}$ pairs of plaintext and ciphertext blocks can break the security of it. In the case of the first mode of operation, the key used for each block is different and is derived by encrypting the block's index with $K$ as the key. In the case of the second, an instance vector (as opposed to "initialization vector") is encrypted with $K$ as the key and this new value is used as the key the same way as in the first mode of operation. In either mode of operation does the birthday bound apply? Does security disappear after knowing $2^{0.5 \times \ell_{X}}$ pairs of plaintexts and ciphertexts? Or does the security become optimal?