# Maximum number of blocks that can be safely encrypted using a block cipher with a counter

Assume that we have a block cipher with a key size of $\ell_{K}$ bits, a tweak size of $\ell_{T}$ bits, and a block size of $\ell_{X}$ bits. Formally, the encryption of a given block of data is $$E(K, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$$ and the decryption of the same is $$D(K, T, X): \{0, 1\}^{\ell_{K}} \times \{0, 1\}^{\ell_{T}} \times \{0, 1\}^{\ell_{X}} \rightarrow \{0, 1\}^{\ell_{X}}$$

The encryption and decryption schemes $\widetilde{E}$ and $\widetilde{D}$ operate on a stream of $s$ blocks $X$, where $$X = X_{0} \Vert X_{1} \Vert \ldots \Vert X_{s-2} \Vert X_{s-1}$$ If $Y$ denotes the output of either the encryption or decryption of $X$ with key $K$, then $Y_{i} = E(K, i, X_{i})$ or $Y_{i} = D(K, i, X_{i})$ and $$Y = Y_{0} \Vert Y_{1} \Vert \ldots \Vert Y_{s-2} \Vert Y_{s-1}$$

What is the maximum number of blocks that can be securely encrypted? Is it $2^{\ell_{X}}$? Is it $2^{0.5 \times \ell_{T}}$?

Is every use of a block cipher for encrypting data subject to the birthday bound? Or do optimal constructions exist?

• Your encryption scheme is length-preserving, and thus bound to be deterministic and unsafe under CPA when the same key and tweak is reused for several plaintext, contrary to the standard security definition of a cipher. Is that an intentional simplification? To avoid this, usual constructions of ciphers from block ciphers assume an IV (typically random or sequential), which is both an input of (or generated by) encryption, and an input of decryption (be it as a separate input or as part of the ciphertext), with that IV not used as tweak of the block cipher. – fgrieu Jan 2 '18 at 9:23
• Yeah, could you clarify which security definition you are considering if it is not the standard. – otus Jan 2 '18 at 10:11
• @fgrieu Since when is length preservation bad? As to your observation on the lack of an IV, I know those are commonly supported, but I didn't think leaving it out and using the key only once would be much different for the analysis. – Melab Jan 3 '18 at 3:22
• @otus I'm not sure, in that case. The toughest kind, so either CPA or CCA security, I suppose. – Melab Jan 3 '18 at 3:23
• Length preservation is not bad per se. But combined with the possibility to decipher, it implies that identical plaintexts always encipher to the same ciphertexts, and that is totally incompatible with CPA security. It gets even worse with usual block cipher modes, where identical beginnings of plaintexts is detectable from ciphertexts. – fgrieu Jan 3 '18 at 7:24