Memory-Efficient Algorithms for Finding Needles in Haystacks
Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir
Abstract
One of the most common tasks in cryptography and cryptanalysis is to find
some interesting event (a needle) in an exponentially large collection (haystack) of
possible events, or to demonstrate that no such event is likely to
exist. In particular, we are interested in finding needles which are defined as events that
happen with an unusually high probability of in a haystack which is an almost uniform
distribution on possible events. When the search algorithm can
only sample values from this distribution, the best known time/memory
tradeoff for finding such an event requires time given
memory.
In this paper we develop much faster needle searching algorithms in the common
cryptographic setting in which the distribution is defined
by applying some deterministic function to random inputs.
Such a distribution can be modelled by a random directed graph with vertices in
which almost all the vertices have predecessors while
the vertex we are looking for has an unusually large number of predecessors.
When we are given only a constant amount of memory, we propose a new search methodology which we call
\textbf{NestedRho}. As increases, such random graphs undergo several subtle phase transitions,
and thus the log-log dependence of the time complexity on
becomes a piecewise linear curve which bends four times. Our new algorithm is faster than the
time complexity of the best previous algorithm in the full range of , and in particular
it improves the previous time complexity by a significant factor of for any in the range . When we are given more memory, we show how to combine the \textbf{NestedRho} technique with the parallel collision
search technique in order to further reduce its time complexity. Finally, we show how to apply our new search
technique to more complicated distributions with multiple peaks when we want to find all the peaks whose
probabilities are higher than .
@misc{cryptoeprint:2016/560,
author = {Itai Dinur and Orr Dunkelman and Nathan Keller and Adi Shamir},
title = {Memory-Efficient Algorithms for Finding Needles in Haystacks},
howpublished = {Cryptology {ePrint} Archive, Paper 2016/560},
year = {2016},
url = {https://eprint.iacr.org/2016/560}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.