Are any block ciphers provably free of equivalent keys?

Question

There are $2^n!$ possible permutations of an $n$-bit block cipher $E_k:\{0,1\}^n \rightarrow \{0,1\}^n$, and any given key $k$ selects one of these permutations at random. Define equivalent keys as a pair of keys $k \neq k^\prime$ where $\forall P:E_k(P) = E_{k^\prime}(P)$ and $P\in\{0,1\}^n$. The probability that such a pair exists for realistic cipher parameters is very low. Can a block cipher be proven to be free of equivalent keys?

Answer 1

Yes, some block ciphers provably have no equivalent keys.

For a start, it's very easy to exhibit such a block cipher, by restricting the key and message spaces to something enumerable. Granted, that makes the cipher insecure.

But we can also construct such a block cipher secure under chosen-plaintext attack. Assume a secure block cipher with the same key and block space (e.g. AES-128). Note $E_k(x)$ (resp. $D_k(x)$) for the encryption (resp. decryption) of $x$ under key $k$. And define $$E'_k(x)=\begin{cases} 0,&\text{if }x=k\\ E_k(k),&\text{if }x\ne k\text{ and }x=D_k(0)\\ E_k(x),&\text{otherwise} \end{cases}$$ In other words, $E'_k$ is the same function as $E_k$, except possibly for inputs $k$ and $D_k(0)$, which outputs are swapped.

Notice that for any fixed $k$, the function $E'_k$ is well-defined and a permutation of the block space, including in the rare case $E_k(k)=0$, which degenerates in $E'_k=E_k$. Hence $E'$ is a block cipher. And it is demonstrably secure under chosen-plaintext attack if $E$ is, because access to an encryption oracle gives no efficient way to query for $k$ or $D_k(0)$.

The corresponding decryption is $$D'_k(x)=\begin{cases} k,&\text{if }x=0\\ D_k(0),&\text{if }x\ne0\text{ and }x=E_k(k)\\ D_k(x),&\text{otherwise} \end{cases}$$ And since $k=D'_k(0)$, there can't be equivalent keys. For if keys $k_0$ and $k_1$ yielded the same bijections $E′_{k_0}$ and $E′_{k_1}$, then the reverse bijections $D′_{k_0}$ and $D′_{k_1}$ would be the same, hence we would have $D'_{k_0}(0)=D'_{k_1}(0)$, hence $k_0=k_1$; now by contraposition, different keys must yield different bijections, Q.E.D.