S-Space College of Natural Sciences (자연과학대학) Dept. of Mathematical Sciences (수리과학부) Theses (Master's Degree_수리과학부)
The Range of Reasonable Parameters for Cryptanalytic Tradeoff Algorithms: Focusing on the Rainbow Tradeoff Algorithm
- 자연과학대학 수리과학부
- Issue Date
- 서울대학교 대학원
- 학위논문 (석사)-- 서울대학교 대학원 : 수리과학부, 2013. 2. 홍진.
- 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.