Paper 2005/214

TMTO With Multiple Data: Analysis and New Single Table Trade-offs

Sourav Mukhopadhyay and Palash Sarkar

Abstract

Time/memory trade-off (TMTO) was introduced by Hellman and later studied by many other authors. The effect of multiple data in Hellman TMTO was studied by Biryukov and Shamir (BS). We continue the analysis of the general multiple data TMTO started in BS. The trade-offs of Babbage and Golic (BG) and Biryukov-Shamir are obtained as special cases. Further, the general analysis is carried out under different conditions including that of Hellman optimality (online time equal to memory). Our main contribution is to identify a new class of single table multiple data trade-offs which cannot be obtained either as BG or BS trade-off. In certain cases, these new trade-offs can provide more desirable parameters than the BG or the BS methods. We consider the analysis of the rainbow method of Oechslin and show that for multiple data, the TMTO curve of the rainbow method is inferior to the TMTO curve of the Hellman method. The costs of the rainbow method and the Hellman+DP method can be comparable if the size of the search space is small and the cost of one table look-up is relatively high.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
timememory trade-offone-way function.
Contact author(s)
sourav_t @ isical ac in
History
2005-07-05: received
Short URL
https://ia.cr/2005/214
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2005/214,
      author = {Sourav Mukhopadhyay and Palash Sarkar},
      title = {TMTO With Multiple Data: Analysis and New Single Table Trade-offs},
      howpublished = {Cryptology ePrint Archive, Paper 2005/214},
      year = {2005},
      note = {\url{https://eprint.iacr.org/2005/214}},
      url = {https://eprint.iacr.org/2005/214}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.