Block cipher fixed points (plaintext equal to ciphertext) A block cipher is a bijective map from the set of possible plaintexts to the set of ciphertexts, which are the same size and might as well be considered the same thing: $\theta: S\to S$. In this there must exist a fixed point m $\in S$ such that $\theta(m) = m$ (alternatively you could consider encryption to be a binary operator acting on the set $S$ then you could write encryption under key $k$ as $m \odot k = m$, with $m,k \in S$. Unfortunately this cannot form a group since there is no unit $e$ that makes $e \odot k = e$ for all $k \in S$).

It is clear that when the block size is equal to the key size a single fixed point will exist when you hold the plaintext message constant and permute the key. The key allows you to select one of all the possible possible unique mappings, of which one must surely be a fixed point (am I right about my use of the word unique here?).

What I don't understand is how a key that is longer than a block size provides any extra security. From what I understand this would suggest the existence of many fixed points, or equivalently many different keys that will decrypt a ciphertext.

Note: I would also be interested to see articles that apply algebra to the study of block ciphers. Specifically constructing groups to aid analysis that also consider the fact that a block cipher is a composition of several round functions.
The question makes a number of statements that are incorrect.  It is not correct that a fixed point is guaranteed to exist.  It is not correct that if you hold the plaintext constant and vary the key, then a fixed point is guaranteed to exist.  Moreover, the existence of fixed points has only an extremely tenuous connection to security.

Assume $E$ is a secure block cipher.  A reminder of standard notation: $E_k(x)$ denotes the encryption of plaintext $x$ under key $k$ using this block cipher.

Here are some results on the number of fixed points, for different mappings derived from the block cipher $E$:


If we fix a key $k$ and look at the mapping $x \mapsto E_k(x)$, then we expect this to look like a random permutation.  The expected number of fixed points in a random permutation is 1, but this number varies from permutation to permutation.  The probability that a random permutation has no fixed points is $1/e \approx 0.37$.  For more facts on fixed points of a random permutation, see Random permutation statistics.
If we fix a plaintext $x$ and look at the mapping $k \mapsto E_k(x)$, then for most modern block ciphers we'd expect this to look like a random function.  If the key has the same size as the ciphertext, then the expected number of fixed points (treating it as a random function) is again 1.  The probability that a random function has no fixed points is again $1/e \approx 0.37$.


See also Does AES have any fixed-points?, and also The Ideal Cipher Model (wonky) on Matt Green's excellent blog.

The reason a longer key provides extra security has nothing to do with fixed points.  It has to do with the fact that a longer key provides better resistance against certain other attacks (e.g., brute-force keysearch).

In short: I think you are laboring under some misconceptions about the existence of fixed points in block ciphers, and their relevance to security.