International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Cost of False Alarms in Hellman and Rainbow Tradeoffs

Authors:
Jin Hong
Download:
URL: http://eprint.iacr.org/2008/362
Search ePrint
Search Google
Abstract: With any cryptanalytic time memory tradeoff algorithm, false alarms pose a major obstacle in accurate assessment of its online time complexity. We study the size of pre-image set under function iterations and use the obtained theory 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. The effect of checkpoints in reducing the cost of false alarms is also quantified.
BibTeX
@misc{eprint-2008-18039,
  title={The Cost of False Alarms in Hellman and Rainbow Tradeoffs},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / time memory trade-off},
  url={http://eprint.iacr.org/2008/362},
  note={ jinhong@snu.ac.kr 14112 received 21 Aug 2008},
  author={Jin Hong},
  year=2008
}