Spectral probabilistic and statistical analysis of Markov ciphers

Let an Abelian group $(\mathcal{X},+)$ be the alphabet of $R$-round Markov block cipher with matrix $\mathcal{P}$ of transition probabilities of differentials; matrix size equals $M=|\mathcal{X}'|$, $\mathcal{X}'=\mathcal{X}\setminus\{0\}$. Suppose spectrum of $\mathcal{P}$ satisfies the condition $\lambda_1=1>|\lambda_2|>|\lambda_3|\ge\ldots\ge\lambda_M$.
1. Extremal transition probabilities $p_{ab}(R)$ and rows $\mathcal{P}^R$ for a large number of rounds. Let $\mathcal{P}$ be diagonalizable: $B\mathcal{P} C=D=\mathrm{diag}(1,\lambda_2,\ldots,\lambda_M)$, $B=C^{-1}$, and there exist $a,b\in\mathcal{X}'$ such that $|C_{a2}|>|C_{i2}|$, $|B_{2b}|>|B_{jb}|$ for all $i\ne a$, $j\ne b$. Then $\mathop{\operatorname{arg\,max}}\limits_{(i,j)\in\mathcal{X}'\times\mathcal{X}'} |p_{ij}(R)-\frac1{M}|=(a,b)$ and $\mathop{\operatorname{arg\,max}}\limits_{i\in\mathcal{X}'} |\mathbf{P}_i^{(R)}-\frac1{M} \mathbf{1}|=a$ for all sufficiently large $R$, $p_{ab}(R)-\frac1{M}\sim C_{a2}B_{2b}\lambda_2^R$ and $|\mathbf{P}_a(R)-\frac1{M} \mathbf{1}| \sim |C_{a2}| |\mathbf{B}_2| |\lambda_2|^R$ as $R\to\infty$.
2. Distinguishing attack by independent full codebooks. Let the cipher with alphabet $\mathcal{X}=\mathbb{Z}_2^n$ be Markovian (provided random uniformly distributed set of round keys $\mathbf{k}\sim U(\mathscr{K}^R)$) with matrix $\mathcal{P}$, $z_i=z_i(\mathbf{k})$ be the result of block $i\in\mathcal{X}$ transformation either by cipher (hypothesis $H_2$) or random uniformly distributed substitution $z(\mathbf{k})$ (hypothesis $H_1$). Let $(\lambda_2,u)$ or $(\lambda_2,v)$ be left or right eigenpair of $\mathcal{P}$, $|u|=|v|=1$, $\mu_2(R)=\mathbf{u} \mathcal{P}^R v\downarrow\ne0$, $S(\mathbf{k})=M \sum\limits_{\{i,j\}\subset \mathcal{X}} u_{j-i} v_{z_j-z_i}$. We prove that mean and variance of statistic $S(\mathbf{k})$ equal $0$ and $M^2 \frac{M+1}{2(M-2)}$ respectively under hypothesis $H_1$. If sets $\mathbf{k}(1),\ldots,\mathbf{k}(N_b)\sim U(\mathscr{K}^R)$ are independent, $N_b\to\infty$, then for all $0<\alpha<1$ criterion $d: S'(N_b) \mathrm{sign}(\mu_2(R)) > \kappa_{1-\alpha}\sqrt{\frac{NM}{M-2}} \Longrightarrow H_2$, where $N=\dbinom{M+1}2 N_b$, has error probability $\alpha_1(d)\to\alpha$. We show that $\alpha_2(d)\approx \beta$ for large values of $R$ and $N_b\approx \frac{2(\kappa_{1-\alpha}+\kappa_{1-\beta})^2 }{(2^n \mu_2(R))^2}$.