Geodesic
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
Matematičeskie voprosy kriptografii, Tome 5 (2014) no. 2, pp. 103-108 
D. V. Pilshchikov. 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. Matematičeskie voprosy kriptografii, Tome 5 (2014) no. 2, pp. 103-108. http://geodesic.mathdoc.fr/item/MVK_2014_5_2_a11/
@article{MVK_2014_5_2_a11,
     author = {D. V. Pilshchikov},
     title = {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{\textendash}Watson} process},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {103--108},
     year = {2014},
     volume = {5},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2014_5_2_a11/}
}
TY  - JOUR
AU  - D. V. Pilshchikov
TI  - 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
JO  - Matematičeskie voprosy kriptografii
PY  - 2014
SP  - 103
EP  - 108
VL  - 5
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2014_5_2_a11/
LA  - en
ID  - MVK_2014_5_2_a11
ER  - 
%0 Journal Article
%A D. V. Pilshchikov
%T 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
%J Matematičeskie voprosy kriptografii
%D 2014
%P 103-108
%V 5
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2014_5_2_a11/
%G en
%F MVK_2014_5_2_a11

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

Time-memory-data tradeoff algorithms are tools for inverting one-way functions. This work provides some mathematical results for an accurate complexity analysis of the most famous of them. We consider a probabilistic model which allows us to estimate the mean values of some characteristics by studying the asymptotic behavior of the generating function of the joint distribution of the number of particles and the total number of particles in the subcritical and critical Galton–Watson processes.

[1] Vatutin V. A., Sagitov S. M., “A decomposable critical branching process with two types of particles”, Proc. Steklov Inst. Math., 177, 1988, 1–19 | MR | Zbl

[2] Aliev S. A., Shurenkov V. M., “Transitional Phenomena and the Convergence of Galton–Watson Processes to Jirina Processes”, Theory Probab. Appl., 27:3 (1983), 472–485 | DOI | MR | Zbl

[3] Avoine G., Junod P., Oechslin P., Time-memory trade-offs: False alarm detection using checkpoints (extended version), Tech. Rep. LASEC-REPORT 2005-002, Swiss Federal Institute of Technology (EPFL), Security and Cryptography Laboratory (LASAC), Lausanne, Switzerland, September 2005 | MR

[4] Avoine G., Junod P., Oechslin P., “Characterization and improvement of Time-Memory Trade-Off based on perfect tables”, ACM Trans. Inf. Syst. Secur., 11:4, July (2008), Article No. 17, 22 pp. | DOI

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

[6] Matsumoto T., Kim I., Hara T., “Methods to reduce time and memory in time-memory tradeoff”, ISEC97-10, May 26, 1997

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

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

[9] Hong J., Jeong K. C., Kwon E. Y., Lee I.-S., Ma D., “Variants of the distinguished point method for cryptanalytic time memory trade-off”, ISPEC 2008, LNCS, 4991, 2008, 131–145

[10] Kim I.-J., Matsumoto T., “Achieving higher success probability in time-memory trade-off cryptanalysis without increasing memory size”, IEICE Trans. Fundamentals, E82-A (1999), 123–129

[11] Ma D., Hong J., “Success probability of the Hellman trade-off”, Inf. Process. Lett., 109:7 (2008), 347–351 | MR

[12] Oechslin P., “Making a faster cryptanalytic time-memory trade-off”, CRYPTO' 03, LNCS, 2729, 2003, 617–630 | MR | Zbl

[13] Pakes A. G., “Some limit theorems for the total progeny of a branching process”, Adv. Appl. Probab., 3:1 (1971), 176–192 | DOI | MR | Zbl

[14] Standaert F. X., Rouvroy G., Quisquater J. J., Legat J. D., “A time-memory tradeoff using distinguished points: New analysis FPGA results”, Proc. CHES 2002, LNCS, 2523, 2002, 596–611