We show that, under parameters and assumptions that are typically considered in theoretic discussions of the tradeoff algorithms, Hellman and distinguished point tradeoffs perform very close to each other and that the rainbow table method performs somewhat better than the other two algorithms. Our method of comparison can easily be applied to other situations, where the conclusions could be different.
The analysis of tradeoff efficiency presented in this paper does not ignore the effects of false alarms and also covers techniques for reducing storage, such as ending point truncations and index tables. Our comparison of algorithms takes the success probabilities and pre-computation efforts fully into account.Category / Keywords: secret-key cryptography / time memory tradeoff, Hellman, distinguished point, rainbow table, random function Publication Info: Journal of Cryptology. http://dx.doi.org/10.1007/s00145-012-9128-3 Date: received 2 Apr 2010, last revised 13 Sep 2012 Contact author: jinhong at snu ac kr Available format(s): PDF | BibTeX Citation Version: 20120913:091213 (All versions of this report) Short URL: ia.cr/2010/176 Discussion forum: Show discussion | Start new discussion