On estimations of distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping

V. O. Mironkin

Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 6-17

Résumé

Given $k,n\in\mathbb{N}$, $x_0\in S=\left\{1,\ldots,n\right\}$, and $ f:S\to S$, define $x_{i+1}=f^k(x_i)$ for every $i\in\{0,1,\ldots\}$ and $\tau_{f^k}(x_0)$ as the least integer $i$ such that $f^k(x_i)=x_j$ for some $j$, $j<i$. For the local probability $\mathsf{P}\left\{\tau_{f^k}\left(x_0\right)=z \right\}$ and for the distribution function $F_{\tau_{f^k}\left(x_0\right)}\left( z \right)$, the following estimates are obtained. If $kz<n$, then \begin{gather}\notag \mathsf{P}\left\{\tau_{f^k}\left(x_0\right){=}z \right\}>\frac 1n{\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}=z \\ \end{smallmatrix}}}{{\text{e}^{-\left( 1+\frac{m}{n} \right)\frac{{{m}^{2}}}{2n}}}}\;{+}{\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}<z \\ \end{smallmatrix}}}{\frac1{r+k}\text{e}^{-\left( 1+\frac{r}{n} \right)\frac{r^2}{2n}}\left( 1{-}{\left( 1{-}\frac{r+k}{n} \right)}^k \right)},\\ \notag \mathsf{P}\left\{\tau_{f^k}\left(x_0\right)=z \right\}<\frac1n{\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}=z \\ \end{smallmatrix}}}{\text{e}^{-\frac{{\left( m-1 \right)}^2}{2n}}}+{\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}<z \\ \end{smallmatrix}}}{\frac{1}{r}{\text{e}^{-\frac{{{\left( r-1 \right)}^{2}}}{2n}}}\left( 1-{{\left( 1-\frac{r}{n} \right)}^k} \right)}, \end{gather} where $r=m+\left( z-\dfrac{m}{(m,k)}-1 \right)k$. If $k^2z\leq n$, then \begin{equation}\notag \begin{gathered} \frac1n\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}=z \\ \end{smallmatrix}}{\text{e}^{-\left( 1+\frac{m}{n} \right)\frac{m^2}{2n}}}+\left( 1-\dfrac{k^2z}{2n} \right)\dfrac{k}{n}\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}<z \\ \end{smallmatrix}}{\text{e}^{-\left( 1+\frac{r}{n} \right)\frac{r^2}{2n}}}< \\ <\mathsf{P}\left\{\tau_{f^k}\left(x_0\right)=z \right\}<\frac1n\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}=z \\ \end{smallmatrix}}{\text{e}^{-\frac{{\left( m-1 \right)}^2}{2n}}}+\dfrac{k}{n}\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}<z \\ \end{smallmatrix}}{\text{e}^{-\frac{{\left( r-1 \right)}^2}{2n}}}, \end{gathered} \end{equation} which, for a prime $k$, is expressed in elementary functions and efficiently computable for used in practice values of $n$ ($2^{256}$ and more). Also, if $ kz\leq\sqrt{n}$, then $$\textstyle\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}\leq z \\ \end{smallmatrix}}{\dfrac{r}{n}\left( 1-\dfrac{r\left( m+r \right)}{2n} \right){\text{e}^{-\left( 1+\frac{m}{n} \right)\frac{m^2}{2n}}}}<F_{\tau_{f^k}\left(x_0\right)}(z)<\sum\limits_{\begin{smallmatrix} m\geq1, \\ \frac{m}{(m,k)}\leq z \\ \end{smallmatrix}}{\dfrac{r+1}{n}{\text{e}^{-\frac{{\left( m-1 \right)}^2}{2n}}}},$$ where $r=m+\left( z-\dfrac{m}{(m,k)} \right)k$. In some cases, the obtained results allow to estimate the allowable period of usage of the encryption keys generated by iterative algorithms and to build criteria for quality assessment of random sequences.

Détail

Keywords: equiprobable random mapping, iteration of random mapping, graph of a mapping, aperiodicity segment, local probability
Mots-clés : distribution.

Bibliographie

[1] Kolchin V. F., Random Mappings, Nauka Publ., M., 1984 (in Russian) | MR

[2] Harris B., “Probability distributions related to random mapping”, Ann. Math. Statist., 31:4 (1960), 1045–1062 | DOI | MR | Zbl

[3] Dalal A., Schmutz E., “Compositions of random functions on a finite set”, Electr. J. Comb., 9 (2002), R26 | MR | Zbl

[4] Flajolet P., Odlyzko A., “Random mapping statistics”, LNCS, 434, 1989, 329–354 | MR

[5] Zubkov A. M., Mironkin V. O., “Distribution of the length of aperiodicity segment in the graph of $k$-fold iteration of uniform random mapping”, Mat. Vopr. Kriptogr., 8:4 (2017), 63–74 (in Russian) | DOI | MR

[6] Mironkin V. O., Mikhailov V. G., “On the sets of images of $k$-fold iteration of uniform random mapping”, Mat. Vopr. Kriptogr., 9:3 (2018), 99–108 (in Russian) | DOI | MR

[7] Mironkin V. O., “Investigation of properties and characteristics of iteration of random mapping”, Obozrenie Prikladnoj i Promyshlennoj Matematiki, 21:1 (2014), 70–73 (in Russian)

[8] Mironkin V. O., “Probabilistic characteristics of layers in a random mapping draph”, Obozrenie Prikladnoj i Promyshlennoj Matematiki, 22:1 (2015), 80–82 (in Russian) | MR

[9] Mironkin V. O., “The joint probability of lengths of aperiodicity segments of two vertices in the graph of iteration of random mapping”, Obozrenie Prikladnoj i Promyshlennoj Matematiki, 22:4 (2015), 482–484 (in Russian)

[10] Mironkin V. O., “On singularities of the structure of the graph of iteration of random mapping”, Obozrenie Prikladnoj i Promyshlennoj Matematiki, 23:1 (2016), 57–62 (in Russian) | MR

[11] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, LNCS, 2729, 2003, 617–630 | MR | Zbl

[12] Pilshchikov D. V., “Estimation of the characteristics of time-memory-data tradeoff methods via generating functions of the number of particles and the total number of particles in the Galton-Watson process”, Mat. Vopr. Kriptogr., 5:2 (2014), 103–108 | DOI

[13] Pilshchikov D. V., “On the limiting mean values in probabilistic models of time-memory-data tradeoff methods”, Mat. Vopr. Kriptogr., 6:2 (2015), 59–65 | DOI | MR

[14] Mironkin V. O., “On some probabilistic characteristics of key derevation function “CRYPTOPRO KEY MESHING””, Problemy Informacionnoj Bezopasnosti. Komp'yuternye Sistemy, 2015, no. 4, 140–146 (in Russian)

[15] Tokareva N. N., Symmetric Cryptography, A Short Course: a Tutorial, NSU Publ., Novosibirsk, 2012 (in Russian)

[16] Sachkov V. N., Probabilistic Methods in Combinatorial Analysis, Nauka Publ., M., 1978 (in Russian)

[17] Zubkov A. M., Serov A. A., “Images of subset of finite set under iterations of random mappings”, Discr. Math., 26:4 (2014), 43–50 (in Russian) | DOI

[18] Pilshchikov D. V., “Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set”, Mat. Vopr. Kriptogr., 8:1 (2017), 95–106 (in Russian) | DOI