Perfect secrecy and block ciphers

Question

Consider a block cipher that encrypts bit strings of length $n$, where the key-space of the block cipher is of size $2^{kn}$, $k \geq 1$. My understanding of perfect secrecy is that a system is perfectly secret if (and only if?) the size of the key space is larger than the size of the message space. But then, if the stated block cipher was used to encrypt messages, is it not true that such a block cipher could encrypt $k$ messages of length $n$ with perfect secrecy? Would this be possible if, after each encrypted message, a nonce was used that changed the key in some way, so that every subsequent message had perfect secrecy?

Answer 1

It is helpful to first define what a perfectly secure block cipher is. In the ideal case there are n different keys where each key uniquitely indexes one of the permutations mapping {0,1}^k to {0,1}^k. In this case we have n=(2^k)! Possible permutations/keys.

Perfect security typically means that no information is revealed at all. Not even against an adversary that is computationally unbounded (ie brute force) .

Given such an ideal block cipher (random permutation), can you think of a situation where information is leaked after seeing more than one message. Keep in mind, brute force attacks are allowed here.

Hint, this is why we have block cipher modes.