Geodesic
On the limiting mean values in probabilistic models of time-memory-data tradeoff methods
Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 2, pp. 59-65 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Time-memory-data tradeoff methods are used to solve one-way function inversion problems. This work provides some mathematical results aimed to the complexity analysis of the most known methods. We introduce a set of random variables depending on the generation sizes and on the total number of particles in a Galton–Watson process considered as a model of the main characteristics of these methods. The limit behavior of their mean values is studied. This work develops the results presented by the author at the CTCrypt 2013 workshop. 
@article{MVK_2015_6_2_a6,
     author = {D. V. Pilshchikov},
     title = {On the limiting mean values in probabilistic models of time-memory-data tradeoff methods},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {59--65},
     year = {2015},
     volume = {6},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a6/}
}
TY  - JOUR
AU  - D. V. Pilshchikov
TI  - On the limiting mean values in probabilistic models of time-memory-data tradeoff methods
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 59
EP  - 65
VL  - 6
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a6/
LA  - en
ID  - MVK_2015_6_2_a6
ER  - 
%0 Journal Article
%A D. V. Pilshchikov
%T On the limiting mean values in probabilistic models of time-memory-data tradeoff methods
%J Matematičeskie voprosy kriptografii
%D 2015
%P 59-65
%V 6
%N 2
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a6/
%G en
%F MVK_2015_6_2_a6
D. V. Pilshchikov. On the limiting mean values in probabilistic models of time-memory-data tradeoff methods. Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 2, pp. 59-65. http://geodesic.mathdoc.fr/item/MVK_2015_6_2_a6/

[1] Vatutin V. A., Sagitov S. M., “A decomposable critical branching process with two types of particles”, Trudy Matem. in-ta im. V. A. Steklova, 177, 1986, 3–20 (in Russian) | MR | Zbl

[2] Aliev S. A., Shurenkov V. M., “Transitional phenomena and the convergence of Galton–Watson processes to Jirina processes”, Teoriya veroyatn. i ee primen., 27:3 (1982), 443–455 (in Russian) | MR | Zbl

[3] Avoine G., Junod P., Oechslin P., Time-memory trade-offs: False alarm detection using checkpoints (extended version), Tech. Rept LASEC-REPORT 2005-002, 2005 | MR

[4] Avoine G., Junod P., Oechslin P., “Characterization and improvement of timememory trade-off based on perfect tables”, ACM Trans. Inf. and Syst. Secur., 11:4 (2008), Article 17, 22 pp. | DOI | MR

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

[6] Matsumoto T., Kim I., Hara T., “Methods to reduce time and memory in timememory tradeoff”, ISEC, 1997, 97–100

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

[8] Hong J., “The cost of false alarms in Hellman and rainbow tradeoffs”, Des. Codes and 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, Lect. Notes Comput. Sci., 4991, Springer-Verlag, 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. Fundam. Electr., Communic. Comput. Sci., E82-A:1 (1999), 123–129

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

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

[13] 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, Lect. Notes. Comput. Sci., 2523, 2002, 593–609 | Zbl

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

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

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

[17] Lee G. W., Hong J., A comparison of perfect table cryptanalytic tradeoff algorithms, Cryptology ePrint Archive, Report 2012/540 | MR

[18] Pilshchikov D., “Estimation of the characteristics of time-memory-data tradeoff methods using the limits of generating function of the particle number and the total number of particles in the Galton-Watson process”, Matematicheskie voprosy kriptografii, 5:2 (2014), 103–108