Estimates of the mean size of the subset image under composition of random mappings. (English. Russian original) Zbl 1420.60038

Discrete Math. Appl. 28, No. 5, 331-338 (2018); translation from Diskretn. Mat. 30, No. 2, 27-36 (2018).
Summary: Let \(\mathcal{X}_N\) be a set of \(N\) elements and \(F_1,F_2,\dots\) be a sequence of random independent equiprobable mappings \(\mathcal{X}_N\rightarrow_N\). For a subset \(S_0 \subset \mathcal{X}_N\), \(|S_0|=m\), we consider a sequence of its images \(S_t=F_t(\dots F_2(F_1(S_0))\dots)\), \(t=1,2\dots\). An approach to the exact recurrent computation of distribution of \(|S_t|\) is described. Two-sided inequalities for \(\mathbf{M}\{|S_t|||S_0|=m\}\) such that the difference between the upper and lower bounds is \(o(m)\) for \(m,t,N\rightarrow\infty\), \(mt=o(N)\) are derived. The results are of interest for the analysis of time-memory tradeoff algorithms.


60F05 Central limit and other weak theorems
60E05 Probability distributions: general theory
Full Text: DOI


[1] Bonferroni C. E. “Teoria statistica delle classi e calcolo delle probabilità ”, Pubbl. d. R. Ist. Super. di Sci. Econom. e Commerciali di Firenze, 1936, No3-62 (in Italian). · Zbl 0016.41103
[2] Gantmacher F. R. The Theory of Matrices. vol. 1 and vol. 2, Chelsea Publishing Company, New York, 1959, vol. 1: x+374 pp. vol. 2: x+277 pp. · Zbl 0927.15001
[3] Kolchin V. F., Sevastyanov B. A., Chistyakov V. P. Random allocations, V. H. Winston & Sons, Washington, 1978, 262.
[4] Borovkov A. A. Probability Theory, New York: Gordon & Breach, 1998, 474. · Zbl 0918.60003
[5] Hellman M.E., “A cryptanalytic time-memory trade-off”, IEEE Trans. Inf. Theory, 1980, 401-406. · Zbl 0436.94016
[6] Flajolet P., Odlyzko A.M., “Random mapping statistics”, Advances in Cryptology – Eurocrypt’89, Lect. Notes Comput. Sci., 1990 434, 329-354.
[7] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, Lect. Notes Comput. Sci, 2729, 2003, 617-630. · Zbl 1122.94393
[8] Hong J. , “The cost of false alarms in Hellman and rainbow tradeoffs”, Designs, Codes and Cryptography, 57:3, 2010, 293-327. · Zbl 1197.94192
[9] Hong J., Moon S., “A comparison of cryptanalytic tradeoff algorithms”, J. Cryptology, 26 2013, 559-637. · Zbl 1283.94069
[10] 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”, Matematicheskie Voprosy Kriptografii, 5:2, 2014, 103-108.
[11] Zubkov A.M., Serov A.A. , “Images of subset of finite set under iterations of random mappings”, Discrete Math. Appl., 2015, 25 :3 , 179-185. · Zbl 1347.60105
[12] Serov A..A. , “Images of a finite set under iterations of two random dependent mappings”, Discrete Math. Appl., 2016, 26 :3 , 175-181. · Zbl 1347.60004
[13] Zubkov A.M., Serov A.A. , “Limit theorem for the size of an image of subset under compositions of random mappings”, Discrete Math. Appl., 2018, 28 :2 , 131-138. · Zbl 1397.60102
[14] Zubkov A.M., Mironkin V. O. , “The distribution of the length of the aperiodicity segment in the graph of a k-fold iteration of a random equiprobable mapping”, Mathematical Aspects of Cryptography,, 8 :4 , 63-74 (in Russian).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.