Welcome to the resource topic for 2005/214
Title:
TMTO With Multiple Data: Analysis and New Single Table Trade-offs
Authors: Sourav Mukhopadhyay, 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.
ePrint: https://eprint.iacr.org/2005/214
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .