Prikladnaya Diskretnaya Matematika
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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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}


Linking options:
  • http://mi.mathnet.ru/eng/pdm744
  • http://mi.mathnet.ru/eng/pdm/y2021/i3/p12

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Прикладная дискретная математика
    Number of views:
    This page:37
    Full text:22

     
    Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2021