Geodesic
Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set
Matematičeskie voprosy kriptografii, Tome 8 (2017) no. 1, pp. 95-106 
D. V. Pilshchikov. Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set. Matematičeskie voprosy kriptografii, Tome 8 (2017) no. 1, pp. 95-106. http://geodesic.mathdoc.fr/item/MVK_2017_8_1_a7/
@article{MVK_2017_8_1_a7,
     author = {D. V. Pilshchikov},
     title = {Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {95--106},
     year = {2017},
     volume = {8},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2017_8_1_a7/}
}
TY  - JOUR
AU  - D. V. Pilshchikov
TI  - Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set
JO  - Matematičeskie voprosy kriptografii
PY  - 2017
SP  - 95
EP  - 106
VL  - 8
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2017_8_1_a7/
LA  - ru
ID  - MVK_2017_8_1_a7
ER  - 
%0 Journal Article
%A D. V. Pilshchikov
%T Asymptotic behaviour of the complete preimage cardinality for the image of a random set under iterations of mappings of a finite set
%J Matematičeskie voprosy kriptografii
%D 2017
%P 95-106
%V 8
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2017_8_1_a7/
%G ru
%F MVK_2017_8_1_a7

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

The estimation of complexity of time-memory-data tradeoff algorithms leads to the estimation problems of the complete preimage cardinality for the image of a random set under multiple iterations of mappings. We describe a probabilistic model allowing to estimate the cardinalities of the random sets considered via the number of particles and the total number of particles in the Galton–Watson process. The limits of mean values of these random variables are found.

[1] 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

[2] Borst J., Preneel B., Vandewalle J., “On the time-memory tradeoff between exhaustive key search and table precomputation”, Symp. Inf. Theory in the Benelux, 1998, 111–118

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

[4] Hong J., “The cost of false alarms in Hellman and rainbow tradeoffs”, Des., Codes and Cryptogr., 57:3 (2010), 293–327 | DOI | MR | Zbl

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

[6] Standaert F. X., Rouvroy G., Quisquater J. J., Legat J. D., “A time-memory tradeoff using distinguished points: New analysis FPGA results”, CHES 2002, Lect. Notes Comput. Sci., 2523, 2002, 593–609 | DOI | Zbl

[7] Hoch Y. Z., Security analysis of generic iterated hash functions, Ph.D. Thesis, Weizmann Inst. of Sci., 2009 | MR

[8] Hong J., Moon S., “A comparison of cryptanalytic tradeoff algorithms”, J. Cryptology, 26 (2013), 559–637 | DOI | MR | Zbl

[9] Pilshchikov D. V., “On the limiting mean values in probabilistic models of time-memory-data tradeoff methods”, Mathematical Aspects of Cryptography, 6:2 (2015), 59–65 | MR

[10] Sevastyanov B. A., Vetvyaschiesya protsessy, Nauka, M., 1971