Even though there are existing claims as to superiority of one tradeoff algorithm over another algorithm, the algorithm performance comparisons provided by the current and preceding papers are of more practical value. Comparisons that take both the cost of pre-computation and the efficiency of the online phase into account, at parameters that achieve a common success rate, can now be carried out with ease. Comparisons can be based on the expected execution complexities rather than the worst case complexities, and details such as the effects of false alarms and various storage optimization techniques need no longer be ignored.
A large portion of this paper is allocated to accurately analyzing the execution behavior of the perfect table distinguished point method. In particular, we obtain a closed-form formula for the average length of chains associated with a perfect distinguished point table.Category / Keywords: secret-key cryptography / time memory tradeoff, distinguished point, rainbow table, perfect table, algorithm complexity Date: received 13 Sep 2012, last revised 6 Feb 2013 Contact author: jinhong at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20130206:073504 (All versions of this report) Discussion forum: Show discussion | Start new discussion