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

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.