In this work, we study the expected pre-image size for an iteration of functions and use the result to analyze the cost incurred by false alarms. We are able to present the expected online time complexities for the Hellman tradeoff and the rainbow table method in a manner that takes false alarms into account. We also analyze the effects of the checkpoint method in reducing false alarm costs.
The ability to accurately compute the online time complexities will allow one to choose their tradeoff parameters more optimally, before starting the expensive pre-computation process.
Category / Keywords: secret-key cryptography / time memory tradeoff, Hellman, rainbow table, checkpoint Date: received 21 Aug 2008, last revised 25 Feb 2009 Contact author: jinhong at snu ac kr Available format(s): PDF | BibTeX Citation Note: The current version extends the theory of the pervious version so that the analysis now closely fits experiments even for the checkpoint case. Version: 20090225:095315 (All versions of this report) Short URL: ia.cr/2008/362 Discussion forum: Show discussion | Start new discussion