What is 'key agility' in relation to symmetric-key encryption? I sometimes see, in discussions of symmetric ciphers, reference to the 'key agility' of a particular algorithm. It seems to be related to the difficulty of switching encryption keys, but I don't understand more than that.

Can anyone give a good explanation of 'key agility' and some contexts in which it is important?
Here's what I can say about the general meaning of it:


It means that the amount of preprocessing of a key is small. So the amount of time from generating/importing a new key to actually starting encrypting is neglegible.
It means that the amount of state a cipher uses is small. The state of a cipher generally is the key or preprocessed key schedule plus the actual block. If this is small it means that you can potentially fit many keys in the CPU cache.


Note that if you have either an extreme of 1 or 2 you can live with just one. If preprocessing takes a long time but the generated key schedule is small you can simply do it once and store it with the key. If preprocessing is very cheap but the state is very large you can do it on-the-fly.

To give an example of the key agility of my own cipher (broken link to pdf), here's why:


The key schedule only consists of permutations of the key - this means it's just memory loads and can be done on the fly.
The full state is only twice the block size - so 128 bytes.


As for why it's important, an example would be a busy HTTPS server. It has to handle many connections at once, and (if everything is done right) each connection has it's own associated keys. Being able to use many keys at once, and preferably to generate and use keys on the fly (ephemeral keys) is a huge bonus in performance and security.