Complexity analysis of the method of rainbow tables with fingerprints

The probabilistic model of the operative stage of the rainbow tables with fingerprints method is introduced. It is used to compute the mean time complexity of the complete processing of one table. Two-sided estimates of this complexity are obtained and computational approach to the construction of the optimal fingerprint is suggested. Our probabilistic model as opposed to other models permits to account for the impact of the variance of the preimages number of random uniformly chosen element of a finite set with respect to the one-way function.