On nonabelian key addition groups and markovian block ciphers

In this paper, $(X,*)$ is an arbitrary key addition group, $\mathbf W=\{W_0,\dots,W_{r-1}\}$ is a partition of $X$, $S(X)$ is the symmetric group on $X$. In 1991, X. Lai, J. L. Massey and S. Murphy introduced markovian block ciphers. We investigate a markovian block cipher $\mathrm C_l(*,b)$ where $l$ is the round number, $b$ is a permutation on $X$, $g\colon X^2\to X$ is the round function defined by $g\colon (x,k)\mapsto b(x*k)$. In the previous paper, we introduced $*_\mathbf W$-markovian block ciphers, which are a generalization of markovian ciphers, and $*_\mathbf W$-markovian transformations. The block cipher $\mathrm C_l(*,b)$ is $*_\mathbf W$-markovian iff the permutation $b$ is $*_\mathbf W$-markovian. We have proved that if $g$ preserves $\mathbf W$, then $G=\langle b,X^*\rangle$ is an imprimitive group and $\mathbf W$ is an imprimitivity system where $X^*$ is the right permutation representation of $(X,*)$. Moreover, if $G$ is imprimitive, then there exists a canonical homomorphism $\varphi_\mathbf W\colon G\to S(\{0,\dots,r-1\})$. We have proved that in the case $(W_0,*)\triangleleft(X,*)$, the cipher $\mathrm C_l(*,b)$ is $*_\mathbf W$-markovian iff there exists a homomorphism $\varphi_\mathbf W$. For cryptographic applications, we are interested in groups of order $2^m$. In this paper, we consider all four nonabelian groups of order $2^m$ having a cyclic subgroup of index 2. These four groups include a dihedral group and a generalized quaternion group. For all four groups, we have described $*_\mathbf W$-markovian permutations such that $\mathbf W$ is the right coset space ($X\colon W_0=\mathbf W$), but $(W_0,*)\ntriangleleft(X,*)$.