2
$\begingroup$

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.

$\endgroup$

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.