Let $K$ and $M$ and be two finite sets.
Let $(G,\circ)$ be the group of permutations over $M$ under composition.
Let a (implicitly: block) cipher with key in $K$ and message in $M$ be any application $C:K\mapsto G$.
Let a commutative cipher be one verifying $\forall k\in K,\forall k'\in K, C(k)\circ C(k')=C(k')\circ C(k)$.

How many commutative ciphers are there, as a function of $|M|$ and $|K|$?

Of these, how many are injective? What's the maximum $|K|$ for an injective commutative cipher to exist, as a function of $|M|$?

There are $(|M|!)^{|K|}$ ciphers. Of these, $|M|!!\over(|M|!-|K|)!$ are injective, or none if $|K|>|M|!$.

We know explicit examples of commutative ciphers: with $n$ prime, $M=\{m\in\mathbb N, m<n\}$, $K=\{k\in\mathbb N, 0<k<n,\gcd(k,n-1)=1\}$, the application $C$ with $C(k)(m)=m^k\bmod n$, known as the Pohlig-Hellman Exponentiation Cipher, is commutative and injective; that follows from $C(k)\circ C(k')=C(k\cdot k'\small{\bmod(n-1)})$, itself following from Fermat's little theorem [as well as $C(k)$ being a permutation in the first place]. This can be extended to any squarefree $n$ by replacing $n-1$ with $\lambda(n)$ [the reduced totient function], and the cipher becomes SRA or RSA. We can remove or add from the message space $M$ any number of fixed points for all keys, including the existing $m=0$, $m=1$ and $m=n-1$. There's also the variation $C(k)(m)=\min(m^k\bmod n,\small(-m^k\small)\bmod n)$, restricting to $m\le n/2$.

If $C$ is a commutative cipher, then $\forall P\in G$, the cipher noted $P(C)$ and defined by $P(C)(k)=P^{-1}\circ C(k)\circ P$ is commutative; it is injective if and only if $C$ is.

Here's a related question, investigating the security of commutative (block) ciphers.

Update: For any commutative subgroup $H$ of $(G,\circ)$, we can construct $|H|^{|K|}$ distinct commutative ciphers by mapping any element of $K$ to any element of $H$. Of these, $|H|!\over(|H|-|K|)!$ are injective, or none if $|K|>|H|$. However I'm uncertain about if we can build a canonical commutative subgroup $H$ for every commutative cipher. If that was the case, then the maximum $|K|$ for which an injective commutative cipher exists would be the maximum size of a commutative subgroup of $(G,\circ)$; and I conjecture that the then part holds.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.