Collisions and incidence of vertices and components in the graph of $k$-fold iteration of the uniform random mapping

V. O. Mironkin

Diskretnaya Matematika, Tome 31 (2019) no. 4, pp. 38-52.

Résumé

The probabilistic characteristics of the graph of $k$-fold iteration of uniform random mapping are studied. Formulas for the distribution of the length of the aperiodicity segment of an arbitrary vertex with some restrictions are calculated. We obtain exact expressions for the probabilities that two arbitrary vertices belong to the same connected component, that an arbitrary vertex belongs to the preimage set of another vertex and that there exists a collision in the considered graph.} \keywords{ uniform random mapping, iteration of random mapping, aperiodicity segment, graph of a mapping, connected component, preimage, collision

Détail

Keywords: uniform random mapping, iteration of random mapping, aperiodicity segment, graph of a mapping, connected component, preimage, collision.

Bibliographie

[1] Zubkov A. M., “Vychislenie raspredelenii kharakteristik chisel komponent i tsiklicheskikh tochek sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 1:2 (2010), 5–18 | DOI

[2] Zubkov A. M., Serov A. A., “Predelnaya teorema dlya moschnosti obraza podmnozhestva pri kompozitsii sluchainykh otobrazhenii”, Diskretnaya matematika, 29:1 (2017), 17–26 ; Zubkov A. M., Serov A. A., “Limit theorem for the size of an image of subset under compositions of random mappings”, Discrete Math. Appl., 28:2 (2018), 131–138 | DOI | DOI | MR | Zbl

[3] Zubkov A. M., Serov A. A., “Otsenki srednego razmera obraza podmnozhestva pri kompozitsii sluchainykh otobrazhenii”, Diskretnaya matematika, 30:2 (2018), 27–36 | DOI | Zbl

[4] Mikhailov V. G., “O povtoryaemosti sostoyanii datchika psevdosluchainykh chisel pri ego mnogokratnom ispolzovanii”, Teoriya veroyatn. i ee primen., 40:4 (1995), 786–797 | MR | Zbl

[5] Mikhailov V. G., “Issledovanie kombinatorno-veroyatnostnoi modeli avtomatov iz registrov s neravnomernym dvizheniem”, Trudy po diskretnoi matematike, 2002, 139–149

[6] Mikhailov V. G., “Issledovanie chisla tsiklicheskikh tochek avtomata iz registrov s neravnomernym dvizheniem”, Trudy po diskretnoi matematike, 2002, 167–172

[7] Pogorelov B. A., Sachkov V. N. (red.), Slovar kriptograficheskikh terminov, MTsNMO, M., 2006, 94 pp.

[8] Vasilenko O. N., Teoretiko-chislovye algoritmy v kriptografii, MTsNMO, M., 2003, 328 pp.

[9] Hellman M. E., “A cryptanalytic time-memory trade-off”, IEEE Trans. Inf. Theory, 1980, 401–406 | DOI | MR | Zbl

[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 | DOI

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

[12] Pilschikov D. V., “Issledovanie slozhnosti metoda raduzhnykh tablits s markerami tsepochek”, Matematicheskie voprosy kriptografii, 8:4 (2017), 99–116 | DOI | MR

[13] Avoine G., Junod P., Oechslin P., “Characterization and improvement of time-memory trade-off based on perfect tables”, Trans. Inf. Syst. Secur., 11:17 (2008), 1–17

[14] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, Lect. Notes Comput. Sci., 2729 (2003), 617–630 | DOI | MR | Zbl

[15] Zubkov A. M., Mironkin V. O., “Raspredelenie dliny otrezka aperiodichnosti v grafe $k$-kratnoi iteratsii sluchainogo ravnoveroyatnogo otobrazheniya”, Matematicheskie voprosy kriptografii, 8:4 (2017), 63–74 | DOI | MR

[16] Zubkov A. M., Serov A. A., “Sovokupnost obrazov podmnozhestva konechnogo mnozhestva pri iteratsiyakh sluchainykh otobrazhenii”, Diskretnaya matematika, 26:4 (2014), 43–50 ; Zubkov A. M., Serov A. A., “Images of subset of finite set under iterations of random mappings”, Discrete Math. Appl., 25:3 (2015), 179–185 | DOI | DOI | MR | Zbl

[17] Mironkin V. O., Mikhailov V. G., “O mnozhestve obrazov $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 9:3 (2018), 99–108 | DOI | MR

[18] Mironkin V. O., “Ob otsenkakh raspredeleniya dliny otrezka aperiodichnosti v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Prikladnaya diskretnaya matematika, 42 (2018), 6–17 | MR

[19] Pilschikov D. V., “Asimptoticheskoe povedenie moschnosti polnogo proobraza sluchainogo mnozhestva pri iteratsiyakh otobrazhenii konechnogo mnozhestva”, Matematicheskie voprosy kriptografii, 8:1 (2017), 95–106 | DOI

[20] Rubin H., Sitgreaves R., Probability distributions related to random transformations of a finite set, Tech. Rept. No19A, Appl. Math. and Statist. Lab., Stanford Univ., 1954, 50 pp.

[21] Mironkin V. O., “Sloi v grafe $k$-kratnoi iteratsii ravnoveroyatnogo sluchainogo otobrazheniya”, Matematicheskie voprosy kriptografii, 10:1 (2019), 73–82 | DOI | MR

[22] Mironkin V. O., “O nekotorykh veroyatnostnykh kharakteristikakh algoritma vyrabotki klyucha «CRYPTOPRO KEY MESHING»”, Problemy informatsionnoi bezopasnosti. Kompyuternye sistemy, 2015, no. 4, 140–146

[23] Chistyakov V. P., Kurs teorii veroyatnostei, 7-e izd., Drofa, M., 2007, 253 pp.

[24] Khalipov P. V., Veroyatnost pokrytiya konechnogo mnozhestva komponentoi sluchainogo otobrazheniya, Diplomnaya rabota, mekh-mat MGU im. M.V. Lomonosova, 2008

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

[26] Tokareva N. N., Simmetrichnaya kriptografiya, Kratkii kurs: uchebnoe posobie, Novosib. gos. un-t, Novosibirsk, 2012, 234 pp.