Memory-Efficient Algorithms for Finding Needles in Haystacks
Memory-Efficient Algorithms for Finding Needles in Haystacks
复制标题
大海捞针的内存高效算法
DOI：
10.1007/978-3-662-53008-5_7
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
A. Shamir
中科院分区：
文献类型：
--
作者：
Itai Dinur;O. Dunkelman;Nathan Keller;A. Shamir
密码学和密码分析中最常见的任务之一是在一个由N=2^n$$可能事件组成的指数级大集合中找到一些有趣的事件，或者证明不可能存在这样的事件。特别是，我们有兴趣找到针被定义为事件发生的概率异常高的$$p \gg 1/N$$在一个干草堆，这是一个几乎均匀分布的N个可能的事件。当搜索算法只能从该分布中采样值时，在给定OM内存的情况下，查找此类事件的最佳已知时间/内存权衡需要$$O1/Mp^2$$时间。
在本文中，我们开发了更快的针搜索算法，在常见的密码设置中，分布定义通过应用一些确定性函数f的随机输入。这样的分布可以通过具有N个顶点的随机有向图来建模，其中几乎所有的顶点都有O 1前导，而我们正在寻找的顶点具有异常大量的OpN前导。当我们只有一个恒定的内存量，我们提出了一个新的搜索方法，我们称之为NestedRho。随着p的增加，这样的随机图经历了几个微妙的相变，因此时间复杂度T对p的对数-对数依赖性变成了一条弯曲四次的分段线性曲线。我们的新算法在$$1/N<p<1$$的整个范围内比以前最好的算法的$$O1/p^2$$时间复杂度更快，特别是对于范围$$N^{-0.75}<p< N^{-0.5}$$中的任何p，它将以前的时间复杂度提高了$$\sqrt{N}$$。当我们有更多的内存，我们展示了如何结合联合收割机的NestedRho技术与并行碰撞搜索技术，以进一步降低其时间复杂度。最后，我们展示了如何将我们的新搜索技术应用于更复杂的多峰分布，当我们想要找到概率高于p的所有峰时。
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 $$N=2^n$$ 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 $$p \gg 1/N$$ in a haystack which is an almost uniform distribution on N 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 $$O1/Mp^2$$ time given OM 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 f to random inputs. Such a distribution can be modelled by a random directed graph with N vertices in which almost all the vertices have O1 predecessors while the vertex we are looking for has an unusually large number of OpN predecessors. When we are given only a constant amount of memory, we propose a new search methodology which we call NestedRho. As p increases, such random graphs undergo several subtle phase transitions, and thus the log-log dependence of the time complexity T on p becomes a piecewise linear curve which bends four times. Our new algorithm is faster than the $$O1/p^2$$ time complexity of the best previous algorithm in the full range of $$1/N<p<1$$, and in particular it improves the previous time complexity by a significant factor of $$\sqrt{N}$$ for any p in the range $$N^{-0.75}<p< N^{-0.5}$$. When we are given more memory, we show how to combine the 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 p.