Criteria for Markov block ciphers

We study probabilistic models of block ciphers with random independent identically distributed round keys. We call they by Markov ciphers if sequence of round differentials is a simple homogeneous Markov chain. Criteria and sufficient condition for this property are adjusted and generalized. Particularly, we prove that, for an iterative $r$-round block cipher with group operation on the set $\mathcal X$ of blocks and round function $g$, the following four conditions are equivalent: 1) for any plaintext of two blocks $(X,X^*)$, the sequence of random round differentials $\Delta X=X^*X^{-1}$, $\Delta X(1)=X^*(1)X(1)^{-1},\ldots,\Delta X(r)=X^*(r)X(r)^{-1}$ is a homogeneous Markov chain under any distribution of $(X,X^*)$; 2) for all $a\in\mathcal X\setminus\{e\}$, the distribution of $g(ax)g(x)^{-1}$ doesn't depend on $x\in\mathcal X$; 3) $\forall a\in\mathcal X\setminus\{e\}$, $x\in\mathcal X$ $(g(ax)g(x)^{-1}\sim g(aX)g(X)^{-1})$ under any distribution of $X$; 4) $\forall x\in\mathcal X$ $(g(\Delta X\, x)g(x)^{-1}\sim g(\Delta X\,X)g(X)^{-1})$ under any distribution of $(X,\Delta X)$. The class of Markov ciphers constructed in Lai's dissertation is expanded. We give sufficient conditions under which formula for the transition probabilities matrix of the expanded class contains tensor product of S-box transition probabilities matrices.