Welcome to the resource topic for 2006/127
Title:
A New Cryptanalytic Time/Memory/Data Trade-off Algorithm
Authors: Sourav Mukhopadhyay, Palash Sarkar
Abstract:In 1980, Hellman introduced a time/memory trade-off (TMTO) algorithm satisfying
the TMTO curve TM^2=N^2, where T is the online time, M is the memory and N is the size
of the search space. Later work by Biryukov-Shamir incorporated multiple data to
obtain the curve TM^2D^2=N^2, where D is the number of data points.
In this paper, we describe a new table structure obtained by combining Hellman’s
structure with a structure proposed by Oechslin. Using the new table structure, we
design a new multiple data TMTO algorithm both with and without the DP method.
The TMTO curve for the new algorithm is obtained to be T^3M^7D^8=N^7. This curve is
based on a conjecture on the number of distinct points covered by the new table. Support
for the conjecture has been obtained through some emperical observations. For D>N^{1/4},
we show that the trade-offs obtained by our method are better than the trade-offs
obtained by the BS method.
ePrint: https://eprint.iacr.org/2006/127
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 .