Geodesic
On mixing properties of non-stationary shift register
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 80-83.

Voir la notice de l'article provenant de la source Math-Net.Ru

In this paper, we examine mixing properties of a non-stationary shift register, i.e., a binary non-linear $n$-stage shift register with feedback function depending on a binary sign of a control sequence. One of two register transformations is implemented at every clock cycle. We evaluate the minimal number $\gamma$ of register clock cycles after which the complete mixing is achieved, that is, each coordinate function of the transformation composition essentially depends on all variables. Mixing properties are rated by means of the set $\hat{\Gamma}$ of mixing $n$-vertex digraph with a common Hamiltonian cycle. An exponent bound allowing to estimate $\gamma$ from below is given for a primitive set $\hat{\Gamma}$. A computational experiment was carried out for $n=6$ and $10$ to calculate the exact value of $\gamma$, taking into account the control sequence. We have established that the complete mixing is possible in a number of cycles, which is less than double exponent. These results can be used for constructing cryptographic algorithms based on a composition of shift register transformations.
Keywords: primitivity of digraphs set, exponent of digraph, exponent of digraphs set. 
@article{PDMA_2019_12_a24,
     author = {Ya. E. Avezova},
     title = {On mixing properties of non-stationary shift register},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {80--83},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a24/}
}
TY  - JOUR
AU  - Ya. E. Avezova
TI  - On mixing properties of non-stationary shift register
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 80
EP  - 83
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a24/
LA  - ru
ID  - PDMA_2019_12_a24
ER  - 
%0 Journal Article
%A Ya. E. Avezova
%T On mixing properties of non-stationary shift register
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 80-83
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a24/
%G ru
%F PDMA_2019_12_a24
Ya. E. Avezova. On mixing properties of non-stationary shift register. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 80-83. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a24/

[1] Shannon C. E., “Communication theory of secrecy systems”, Bell System Technical J., 28 (1949), 656–715 | DOI | MR | Zbl

[2] Fomichev V. M., Melnikov D. A., Kriptograficheskie metody zaschity informatsii, V 2 ch., v. 1, Matematicheskie aspekty, Yurait, M., 2016, 209 pp.

[3] Avezova Ya. E., “Svoistva primitivnykh mnozhestv orientirovannykh grafov s obschim mnozhestvom konturov”, Prikladnaya diskretnaya matematika, 2019, no. 43, 101–114 | MR