Geodesic
On the ergodicity of difference distribution tables of random permutations
Trudy Instituta matematiki, Tome 14 (2006) no. 2, pp. 86-94 
A. S. Maslov. On the ergodicity of difference distribution tables of random permutations. Trudy Instituta matematiki, Tome 14 (2006) no. 2, pp. 86-94. http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a10/
@article{TIMB_2006_14_2_a10,
     author = {A. S. Maslov},
     title = {On the ergodicity of difference distribution tables of random permutations},
     journal = {Trudy Instituta matematiki},
     pages = {86--94},
     year = {2006},
     volume = {14},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a10/}
}
TY  - JOUR
AU  - A. S. Maslov
TI  - On the ergodicity of difference distribution tables of random permutations
JO  - Trudy Instituta matematiki
PY  - 2006
SP  - 86
EP  - 94
VL  - 14
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a10/
LA  - ru
ID  - TIMB_2006_14_2_a10
ER  - 
%0 Journal Article
%A A. S. Maslov
%T On the ergodicity of difference distribution tables of random permutations
%J Trudy Instituta matematiki
%D 2006
%P 86-94
%V 14
%N 2
%U http://geodesic.mathdoc.fr/item/TIMB_2006_14_2_a10/
%G ru
%F TIMB_2006_14_2_a10

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

Properties of the Markov chain induced by the difference distribution table of a random permutation acting on a finite group $G$ are considered. The ergodicity probability and the convergence rate of this Markov chain are estimated. It is proved that the group generated by permutations $x\mapsto s(xa)$, $x,a\in G$, is $2$-transitive for almost all permutations $s$ from the permutation group of $G$.

[1] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, Journal of Cryptology, 4 (1991), 3–72 | DOI | MR | Zbl

[2] Biham E., Shamir A., “Differential cryptanalysis of the full 16-round DES”, Advances in Cryptology, CRYPTO'92, Proceedings, 1993, 487–496 | Zbl

[3] Lai X., Massey J., Murphy S., “Markov Ciphers and Differential Cryptanalysis”, Advances in Cryptology, EUROCRYPT'91, Proceedings, 1991, 17–38 | MR | Zbl

[4] O'Connor L., Golić J., “A Unified Markov Approach to Differential and Linear Cryptanalysis”, Advances in Cryptology, ASIACRYPT'94, Proceedings, 1995, 387–397 | MR

[5] O'Connor L., “Designing product ciphers using Markov Chains”, Proceedings of the Workshop on Selected Areas in Cryptography, SAC'94, 1994, 2–13

[6] O'Connor L., “Convergence in Differential Distributions ”, Advances in Cryptology, EUROCRYPT'95, Proceedings, 1996, 13–23 | MR

[7] Dobrushin R.L., “Tsentralnaya predelnaya teorema dlya neodnorodnykh tsepei Markova. II”, Teoriya veroyatnostei i ee primeneniya, 1:4 (1956), 365–425 | Zbl

[8] Hoeffding W., “Probability inequalities for sums of bounded random variables”, J. Amer. Statist. Assoc., 58:301 (1963), 13–30 | DOI | MR | Zbl

[9] Petrov V.V., Summy nezavisimykh sluchainykh velichin, M., 1972 | MR

[10] Feller V., Vvedenie v teoriyu veroyatnostei i ee prilozheniya, M., 1964