The Range of Reasonable Parameters for Cryptanalytic Tradeoff Algorithms: Focusing on the Rainbow Tradeoff Algorithm

Abstract

We suggest a new terminology, reasonable tradeoff parameters in a fixed tradeoff algorithm. In brief, if there is no other set of parameters which is a comparative advantage in terms all of the tradeoff efficiency, the cost of pre-computation and the probability of success, we call it a reasonable set of parameters. And the criterion for tradeoff parameters being reasonable is also obtained.

As an additional corollary, it is showed that if one of the tradeoff efficiency, the cost of pre-computation and the probability of success is given with the table count $l$ in the rainbow tradeoff (instead, with the matrix stopping constant in the Hellman and the DP case), the remaining ones are uniquely determined and tradeoff parameters implementing these values always exist.

The concept of reasonable tradeoff parameters is extended to the case of comparing two sets of parameters from two different tradeoff algorithms respectively. Under assumptions typically considered in theoretical discussions, we conclude that in the range of the high value of the probability of success, we get reasonable tradeoff parameters by selecting the rainbow tradeoff only. And the method to get these reasonable tradeoff parameters is obtained.