Having spent a couple of nights thinking about this question, it seems to me that:
- there is no commutative block cipher that could pass your test, and
- in any case, indistinguishability from a random commutative block cipher is probably not a good measure of cryptographic quality, since it turns out that a random commutative block cipher is, with overwhelming likelihood, a pretty useless thing for crypto.
Since this is an SE answer and not a research paper, the arguments I present below to support these claims are sketchy at best. Nonetheless, I at least find them personally convincing.
First, let me start by noting that the trick used in poncho's answer to your earlier question can be adapted to almost prove claim 1 above, except for a few minor conjectural gaps that I have not managed to rigorously bridge.
Specifically, assume that there exists a key $k \in K$ and a block $x \in S$ such that $E(k,x) \ne x$. (If no such $k$ and $x$ exist, then $E$ is the trivial "null cipher", and should be easily distinguishable from a random commutative block cipher — although, as noted below, perhaps not quite as easily as one might expect.) Let the adversary:
- compute $y = E(k,x)$, and query the oracle for $z = F(k,y)$;
- query the oracle for $y' = F(k,x)$ and compute $z' = E(k,y')$; and
- output "1" if $z = z'$, and "2" otherwise.
Clearly, in case 1, where $F$ is $E$ with a shuffled keyspace: $$z = E(P(k),E(k,x)) = E(k,E(P(k),x)) = z',$$ and so in this case the adversary will always guess correctly.
In case 2, where $F$ is a random commutative block cipher, the adversary will only guess wrong if either:
- a) $x$ and $y$ are both fixed points of the random permutation $F(k,\cdot)$, or
- b) neither $x$ nor $y$ is a fixed point of $F(k,\cdot)$ and it just happens that $F(k,y)$ is the image of $F(k,x)$ under $E(k,\cdot)$.
Both of these possibilities seem intuitively unlikely, although I will argue below that, for random commutative block ciphers, (a) may actually happen with a non-negligible probability. Still, as long as the probability that neither (a) nor (b) occurs is not negligible, the adversary described above will return the correct result with a non-negligible advantage. I have not proven this, but I would be quite surprised if it wasn't true.
Filling out the gaps in the proof sketch above would seem to require a closer examination of what a "random commutative block cipher" actually looks like. Such an examination turns out to yield some rather unexpected results, at least when contrasted with the behavior of random non-commutative block ciphers.
In particular, let me first state a few rather surprising conclusions, which I will attempt to justify below:
- For large $K$ and $S$, the probability that $F(k,x) = x$ for a random commutative block cipher $F: K \times S \to S$ is approximately $1/3$.
- Let $\mathcal{G}_F$ denote the (Abelian) group of permutations of $S$ generated by the permutations $\{x \mapsto F(k,x): k \in K\}$, and let $\mathcal{G}_F(x) \subset S$ denote the orbit of $x$ under $\mathcal{G}_F$. For reasonably large $K$ and $S$, the orbit $\mathcal{G}_F(x)$ of most points $x \in S$ should consist of 2 to 4 points, with 3-point orbits becoming the norm as $|K|$ grows.
To show how I came up with these conclusions, let me start by noting that, for any fixed message space $S$, we can iteratively construct all commutative $n$-key block ciphers over $S$.
Specifically, let us WLOG fix the keyspace $K_n = \{1,2,\dots,n\}$, and represent each block cipher $F: K_n \times S \to S$ by the corresponding sequence of permutations $f = (f_1, f_2, \dots, f_n)$, where $f_i = F(i,\cdot)$. Let $\mathcal{C}_n$ denote the set of such sequences corresponding to $n$-key commutative block ciphers, i.e. $n$-element sequences of mutually commuting permutations of $S$.
Clearly, $\mathcal{C}_1$ consists of the one-element sequences $(p)$ for every permutation $p$ of $S$.
To construct $\mathcal{C}_n$ for $n > 1$, we simply take each sequence $(f_1, \dots, f_{n-1}) \in \mathcal{C}_{n-1}$ and append to it every possible permutation $f_n$ of $S$ that commutes with all the permutations already in it:
$$
\mathcal{C}_n = \{
(f_1,\dots,f_n)
\mid
(f_1,\dots,f_{n-1}) \in \mathcal{C}_{n-1}
\land
\forall 1 \le i < n: f_i \circ f_n = f_n \circ f_i
\}.
$$
In particular, this construction should yield a recipe for reasonably efficient Monte Carlo importance sampling of the set of commutative block ciphers over any key and message space: simply start with a random permutation of $S$ and repeatedly append a new random permutation chosen so as to commute with all the previously chosen permutations, while also multiplying the relative weight of the sample by the fraction of all permutations eligible to be so chosen. As far as I can tell, it should be possible to select (and count) these eligible permutations efficiently by keeping track of the orbits on $S$ induced by the current set of permutations, and of the algebraic relations the hold between the permutations within each orbit, as described below.
I have not yet actually implemented the sampling algorithm described above. However, simply considering the process in an abstract way yields some useful insights.
First of all, we can consider the cycle structure of the first permutation $f_1$, and note that it imposes significant constraints on the second permutation $f_2$: namely, $f_2$ must map each cycle of $f_1$ either onto itself, or onto another cycle of the same size (which must then be mapped onto either the original cycle or yet another cycle of the same size, and so on). Furthermore, for each cycle of $f_1$, once we choose the image of one element of the cycle under $f_2$, this uniquely determines the corresponding images of all other elements of the cycle.
Thus, while for $f_1$ we have all $|S|!$ possible permutations to choose from, only $\prod_{k=1}^{|S|} k^{n_k}\, n_k!$ of those are eligible to be chosen as $f_2$, where $n_k$ denotes the number of $k$-element cycles of $f_1$. (The formula $k^{n_k}\, n_k!$ comes from the observation that, first, we have $n_k!$ ways to map the $n_k$ cycles onto each other, and then $k$ independent choices for how much to shift each of the $n_k$ cycles.)
For $f_3$ and higher, similar constraints apply, but with a further restriction: while we may always choose to map each orbit of the subgroup generated by $f_1$ and $f_2$ onto itself (and, again, choosing the image of any element of the orbit is enough to fix the images of all elements in the same orbit), we can only map two (or more) previously separate orbits onto each other if they are compatible, in the sense that the same algebraic relations between $f_1$ and $f_2$ must hold within each orbit. That is to say, if $x$ and $y$ are arbitrary elements of the two respective orbits, and if $f_1^{(a)}(x) = f_2^{(b)}(x)$ for some integers $a$ and $b$, then the same relation must also hold for $y$.
Now, an important (but, alas, not 100% rigorous) observation is that, as we keep adding new random permutations to the sequence $f$, its orbit structure will, with high probability, tend to very quickly (I suspect this happens in $O(\log |S|)$ steps on average) become "locked" so that no two orbits remain compatible with each other, either because any formerly compatible orbits get merged, or because they become incompatible due to new relations between the added permutations.
Once this happens, it is no longer possible for any further permutation in the sequence to connect two orbits, and so the number of eligible new permutations becomes fixed at $R = \prod_{k=1}^{|S|} k^{n_k}$, where, again, $n_k$ is the number of $k$-element orbits of the cipher.
Thus, once the orbit structure of a particular cipher becomes locked in this way, increasing $|K|$ by one simply splits this cipher into $R$ new variants, each with the same orbits (and thus the same splitting factor $R$) as their parent cipher had.
Thus, once we're past the initial steps, and the orbit structure of most ciphers has become locked, $\mathcal{C}_n(S)$ is effectively divided into "families" of ciphers with the same $R$ factor, with the size of each family growing in proportion to $R^n$.
The outcome should be obvious to anyone familiar with replicator dynamics in ecology: as $n$ grows, the "population" of ciphers becomes dominated by the family with the highest exponential growth rate $R$.
What does this family look like? First, as far as the size of the message space allows, all its orbits should have the same size, since otherwise we could increase $R$ by moving points from larger orbits into smaller ones. Now, if all the orbits have size $k$, then $R = k^{n/k}$; maximizing this is equivalent to maximizing $\log R = \frac nk \log k$. Dropping the constant factor $n$ leaves us with $\frac{\log k}{k}$, an expression that, for real $k > 0$, attains its maximum at $k = e$.
Over the positive integers, the maximum is attained at $k = 3 \approx e$, with $k = 2$ and $k = 4$ tied for second place. Thus, for a given $|S|$, one would expect the maximum growth factor $R$ to be attained by ciphers that divide $S$ into 3-element orbits, possibly with a single 2- or 4-element orbit if $|S|$ is not a multiple of 3.
Since all the permutations in a cipher must commute with each other, each permutation in the cipher must act one any given 3-element orbit by shifting the elements of the orbit forward by 0, 1 or 2 places, each with equal probability. In particular, this implies that, for any given element of $S$, a randomly chosen permutation in a maximal-$R$ cipher will leave that element untouched with probability approximately $1/3$.
Obviously, this is very much unlike the behavior of random block ciphers in general, and it's quite remarkable that the imposition of commutativity should have such a drastic effect. Yet, even though there are surely gaps and inaccuracies in my reasoning above, I don't believe that any of them should significantly affect the main conclusions.
A natural verification step would be to test these conclusions computationally, either using stochastic sampling as I suggest above, or by simply enumerating all the possible commutative block ciphers (modulo obvious symmetries to speed up the search) by brute force over sufficiently small key and message spaces to keep this feasible.
In any case, assuming I haven't made any really silly mistakes in what I've written above, this should clearly suggest that, insofar there may be any commutative block ciphers with useful cryptographic properties, they almost certainly will not look anything like uniformly random families of mutually commutative permutations.
