RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Prikl. Diskr. Mat.: Year: Volume: Issue: Page: Find

 Prikl. Diskr. Mat., 2021, Number 53, Pages 12–31 (Mi pdm744)

Mathematical Methods of Cryptography

Spectral probabilistic and statistical analysis of Markov ciphers

O. V. Denisov

Innovative Telecommunication Technologies, LLC, Moscow, Russia

Abstract: 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}$.

Keywords: Markov block ciphers, distinguishing attack, matrix spectrum, transition probabilities of differentials, second dominant eigenvalue, independent full codebooks.

DOI: https://doi.org/10.17223/20710410/53/2

Full text: PDF file (753 kB)
References: PDF file   HTML file

Bibliographic databases:

UDC: 519.23

Citation: O. V. Denisov, “Spectral probabilistic and statistical analysis of Markov ciphers”, Prikl. Diskr. Mat., 2021, no. 53, 12–31

Citation in format AMSBIB
\Bibitem{Den21} \by O.~V.~Denisov \paper Spectral probabilistic and statistical analysis of~Markov ciphers \jour Prikl. Diskr. Mat. \yr 2021 \issue 53 \pages 12--31 \mathnet{http://mi.mathnet.ru/pdm744} \crossref{https://doi.org/10.17223/20710410/53/2}