Time Space Tradeoffs for Attacks against One-Way Functions and PRGs

Time Space Tradeoffs for Attacks against One-Way Functions and PRGs
复制标题

针对单向函数和 PRG 的攻击的时空权衡

DOI：
--
复制
发表时间：
2010
期刊：
Annual International Cryptology Conference
影响因子：
--
通讯作者：
Madhur Tulsiani
Madhur Tulsiani
中科院分区：
--
文献类型：
--
作者：
Anindya De;L. Trevisan;Madhur Tulsiani

文献摘要

被引文献

相似文献

我们研究了针对单向功能和伪随机发电机的攻击的复杂性的时间空间权衡。 Fiat和Naor [7]表明，对于每个函数f：[n]→[n]，有一种算法可以在大多数N3/4的时间，空间和建议中无处不在（忽略较低级数）。 我们表明，最多使用时间，空间和建议的算法{持有，使我们的结果在e≤3√1/n的“低端”中紧密。 菲亚特和NAOR的结果以及我们的结果都是在算法的时间和空间和建议长度之间进行的更一般的权衡。になったんです。英语：您可以做的第一件事就是找到最好的方法。 我们还表明，对于每个长度增长的发电机G：[n]→[2n]都有一种算法可以在G和均匀分布的输出和均匀分布之间实现区别概率E，并且可以在多项式（在log n）时间中实现并使用建议和空间o（e2ċNlog n）。当杰出程序具有Oracle访问G时。 对于单向排列和伪随机发电机的家族，我们证明了更强的下限。
We study time space tradeoffs in the complexity of attacks against one-way functions and pseudorandom generators. Fiat and Naor [7] show that for every function f: [N] → [N], there is an algorithm that inverts f everywhere using (ignoring lower order factors) time, space and advice at most N3/4. We show that an algorithm using time, space and advice at most max{e 5/4 N 3/4, √eN} exists that inverts f on at least an e fraction of inputs. A lower bound of Ω(√eN) also holds, making our result tight in the "low end" of e ≤ 3√1/N. Both the results of Fiat and Naor and ours are formulated as more general trade-offs between the time and the space and advice length of the algorithm. The results quoted above correspond to the interesting special case in which time equals space and advice length.) We also show that for every length-increasing generator G: [N] → [2N] there is a algorithm that achieves distinguishing probability e between the output of G and the uniform distribution and that can be implemented in polynomial (in log N) time and with advice and space O(e2 ċ N log N). We prove a lower bound of S ċ T ≥ Ω(e2N) where T is the time used by the algorithm and S is the amount of advice. This lower bound applies even when the distinguisher has oracle access to G. We prove stronger lower bounds in the common random string model, for families of one-way permutations and of pseudorandom generators.