# Block cipher mode of operation with beyond-birthday-bound security

I am looking for block cipher modes of operation that are secure even when the number of blocks encrypted exceeds the birthday bound.

• Hmm, would counter mode encryption work, provided you'd never repeat the counter? Just thinking out loud here. Feb 17, 2016 at 8:58
• @MaartenBodewes, security is still lost after the birthday bound, because ciphertext collisions give you information about what the plaintext cannot be.
– otus
Feb 17, 2016 at 11:56
• @otus Can we assume that this is then a property of the block cipher itself? Or could we construct a new cipher out of it with a higher bound? I'd presume that could be possible, but it would probably be rather complex / inefficient. I'm not sure that I would call that a "mode of operation". Feb 17, 2016 at 13:16
• @MaartenBodewes, it follows from block size and counter mode. You'd have to construct a larger cipher or use another mode to get better bounds.
– otus
Feb 17, 2016 at 14:24
• Some modes are presented here: cs.ru.nl/~bmennink/slides/croatia17b.pdf Jul 12, 2021 at 8:09

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$ rather than $O(2^{n/2})$. See The Sum of Two PRPs is a secure PRF.