Performance differences between different tradeoff algorithms are usually not very large, but even these small differences can be crucial in practice. So we take care not to ignore the side effects of false alarms in providing an online time complexity analysis of the parallel distinguished point tradeoff algorithm. Our complexity results are used to compare the parallel non-perfect distinguished point tradeoff against the non-perfect rainbow table method. The two algorithms are compared under identical success rate requirements and the pre-computation efforts are also taken into account. Contrary to our anticipation, we find that the rainbow table method is superior in typical situations, even though the parallelization did have a positive effect on the efficiency of the distinguished point tradeoff algorithm.
Category / Keywords: time memory tradeoff, parallel distinguished point, distinguished point, rainbow table Date: received 18 Jul 2011, last revised 29 Sep 2011 Contact author: gwlee87 at snu ac kr Available formats: PDF | BibTeX Citation Version: 20110929:112224 (All versions of this report) Discussion forum: Show discussion | Start new discussion