Geodesic
A complexity analysis of algorithm of parallel search of the “gold” collision
Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 4, pp. 77-97 
D. V. Pilshchikov. A complexity analysis of algorithm of parallel search of the “gold” collision. Matematičeskie voprosy kriptografii, Tome 6 (2015) no. 4, pp. 77-97. http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a4/
@article{MVK_2015_6_4_a4,
     author = {D. V. Pilshchikov},
     title = {A complexity analysis of algorithm of parallel search of the {\textquotedblleft}gold{\textquotedblright} collision},
     journal = {Matemati\v{c}eskie voprosy kriptografii},
     pages = {77--97},
     year = {2015},
     volume = {6},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a4/}
}
TY  - JOUR
AU  - D. V. Pilshchikov
TI  - A complexity analysis of algorithm of parallel search of the “gold” collision
JO  - Matematičeskie voprosy kriptografii
PY  - 2015
SP  - 77
EP  - 97
VL  - 6
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a4/
LA  - ru
ID  - MVK_2015_6_4_a4
ER  - 
%0 Journal Article
%A D. V. Pilshchikov
%T A complexity analysis of algorithm of parallel search of the “gold” collision
%J Matematičeskie voprosy kriptografii
%D 2015
%P 77-97
%V 6
%N 4
%U http://geodesic.mathdoc.fr/item/MVK_2015_6_4_a4/
%G ru
%F MVK_2015_6_4_a4

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

The paper refines known estimates of time and memory complexities of Oorschot and Wiener algorithm for the “gold” collision searching. We use results related to the computation of characteristics of time-memory-data tradeoff method with distinguished points. Probabilistic approximations of the algorithm characteristics by random variables depending on the number of particles and the total number of particles in a subcritical Galton–Watson process are described.The limits of expectations of these random variables are found.

[1] Oorschot P. C., Wiener M. J., “Parallel collision search with cryptanalytic applications”, J. Cryptology, 12 (1999), 1–28 | DOI | MR | Zbl

[2] Oorschot P. C., Wiener M. J., “Parallel collision search with application to hash functions and discrete logarithms”, 2nd ACM Conf. on Computer and Commun. Security, Fairfax, Virginia, 1994, 210–218

[3] Oorschot P. C., Wiener M. J., “Improving implementable meet-in-the-middle attacks by orders of magnitude”, CRYPTO' 96, Lect. Notes Comput. Sci., 1109, 1996, 229–236 | DOI | MR

[4] 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, Veldhoven, Netherlands, 1998, 111–118

[5] 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, 2003, 596–611

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

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