Geodesic
On a probabilistic approach to the estimation of reliability of the Hellman method
Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 1, pp. 83-114 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The evaluation of the reliability of the Hellman method reduces to estimating the mean value of a random number $\xi(m, t, N)$ of different elements of the set $X$ in a table containing $m$ records of $t$ iterations of function $F : X \to X$. We suggest a probabilistic model, within which estimates of the deviation of the mean value of $\xi(m, t, N)/(mt)$ from its approximation are obtained. The properties of the $F$ function that significantly affect the reliability of the method are revealed. The estimation of the mean value of $\xi(m, t, N)$ is carried out using the appropriate Galton–Watson process. 
@article{MVK_2019_10_1_a5,
     author = {D. V. Pil'shchikov},
     title = {On a probabilistic approach to the estimation of reliability of the {Hellman} method},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {83--114},
     year = {2019},
     volume = {10},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2019_10_1_a5/}
}
TY  - JOUR
AU  - D. V. Pil'shchikov
TI  - On a probabilistic approach to the estimation of reliability of the Hellman method
JO  - Matematičeskie voprosy kriptografii
PY  - 2019
SP  - 83
EP  - 114
VL  - 10
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MVK_2019_10_1_a5/
LA  - ru
ID  - MVK_2019_10_1_a5
ER  - 
%0 Journal Article
%A D. V. Pil'shchikov
%T On a probabilistic approach to the estimation of reliability of the Hellman method
%J Matematičeskie voprosy kriptografii
%D 2019
%P 83-114
%V 10
%N 1
%U http://geodesic.mathdoc.fr/item/MVK_2019_10_1_a5/
%G ru
%F MVK_2019_10_1_a5
D. V. Pil'shchikov. On a probabilistic approach to the estimation of reliability of the Hellman method. Matematičeskie voprosy kriptografii, Tome 10 (2019) no. 1, pp. 83-114. http://geodesic.mathdoc.fr/item/MVK_2019_10_1_a5/

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

[2] Denning D., Cryptography and Data Security, Addison-Wesley, Boston, Massachusetts, USA, 1982, 100 pp. | MR | Zbl

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

[4] Biryukov A., Shamir A., Wagner D., “Real time cryptanalysis of A5/1 on a PC”, FSE 2000, Lect. Notes Comput. Sci., 1978, 2001, 1–18 | DOI | Zbl

[5] Saarinen M.-J. O., “A time-memory tradeoff attack against LILI-128”, FSE 2002, Lect. Notes Comput. Sci., 2365, 2002, 231–236 | DOI | Zbl

[6] Mentens N., Batina L., Preneel B., Verbauwhede I., “Cracking Unix passwords using FPGA platforms”, SHARCS'05 - Special Purpose Hardware for Attacking Cryptographic Systems (2005), 20–25

[7] Bono S., Green M., Stubblefield A., Juels A., Rubin A., Szydlo M., “Security analysis of a cryptographically-enabled RFID device”, 14th USENIX Security Symp., 2005, 1–16 | Zbl

[8] Kusuda K., Matsumoto T., “Optimization of time-memory trade-off cryptanalysis and its application to DES, FEAL-32, and Skipjack”, IEICE Trans. Fund. Electr., Commun. and Comput. Sci., E79-A:1 (1996), 35–48 | MR

[9] Saran N., Doganaksoy A., “Choosing parameters to achieve a higher success rate for Hellman time memory trade off attack”, Int. Conf. on Availability, Reliability and Security, 2009, 504–509

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

[11] Sevastyanov B. A., Vetvyaschiesya protsessy, Nauka, M., 1971, 436 pp.

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

[13] Vatutin V. A., Sagitov S. M., “Razlozhimyi kriticheskii vetvyaschiisya protsess s dvumya tipami chastits”, Trudy Matem. in-ta AN SSSR, 177, 1986, 3–20 | Zbl

[14] Pilshchikov D. V., “Estimation of the characteristics of time-memory-data tradeoff methods via generating functions of the number particles and the total number of particles in the Galton–Watson process”, Matematicheskie voprosy kriptografii, 5:2 (2014), 103–108 | DOI

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

[16] Pilschikov D. V., “Analiz slozhnosti algoritma parallelnogo poiska «zolotoi» kollizii”, Matematicheskie voprosy kriptografii, 6:4 (2015), 77–98 | DOI

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

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