# Is it possible for this tweakable block cipher scheme to be secure for more than $2^\frac{n}{2}$ blocks? $2^{n}$ blocks?

In the title, $n$ is the block size in bits and will not be used to denote it in the body of this question unless otherwise stated. Imagine that we have $\mathbb{K} \in \{0, 1\}^{\ell_{K}}$, $\mathbb{T} \in \{0, 1\}^{\ell_{T}}$, and $\mathbb{X} \in \{0, 1\}^{\ell_{X}}$, $E(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$, and $D(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$. We have a tweakable block cipher where the encryption of a block of data is returned by $E(K, T, X)$, the decryption of a block of data is returned by $D(K, T, X)$, $K$ is the secret key, $T$ is the tweak, and $X$ is the block of data. Suppose that this tweakable block cipher is meant to be used in such a way that $T$ is equal to the block number. If $\ell_{T}$ is sufficiently large, then will the maximum number of blocks that can be encrypted under this scheme be equal to or possibly even greater than $2^{\frac{\ell_{X}}{2}}$ or even $2^{\ell_{X}}$?

Abstractly, there is no $2^{l_X/2}$ limit on the security of a block cipher. The security claim is that the block cipher is indistinguishable from a random permutation which it may remain even after the adversary has seen all its inputs and outputs (for a particular key). Similarly, there is no reason a tweakable block cipher needs to become insecure after a certain number of blocks are encrypted.
In practice the security of a block cipher depends on the mode of operation you use and most of those break down one way or another after $2^{l_X/2}$ blocks.
If you have a tweakable block cipher that is not constructed from another block cipher, its security claim may or may not depend on its block size. So using it like you describe may or may not be secure for more than $2^{l_X/2}$ blocks.
• Is every tweakable block cipher that is constructed from a normal block cipher going to be insecure for more than $2^{0.5 \times \ell_{X}}$ encryptions? – Melab Dec 28 '17 at 21:17
• @otus I would intuitively guess that it may not be possible to avoid the birthday bound, because you're trying to get $2^{\ell_T}$ independent choices of PRP out of a single PRP. Under a single key, there's only one permutation, not $2^{\ell_T}$ independent ones, and a lack of collisions in the outputs for different tweaks might reveal something; if you try to pick different subkeys for each tweak, the subkeys themselves might collide. (This is nowhere near a formal argument, of course, just a hazy intuition!) – Squeamish Ossifrage Dec 29 '17 at 4:50