Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
复制标题
来自指数硬单向函数的高效伪随机生成器
DOI：
10.1007/11787006_20
复制
发表时间：
2006
影响因子：
2.5
通讯作者：
Omer Reingold
中科院分区：
文献类型：
--
作者：
Iftach Haitner;Danny Harnik;Omer Reingold
在他们的开创性论文[HILL99]中，Hastad, Impagliazzo， Levin和Luby表明，伪随机生成器可以由任何单向函数构造。这个似是而非的结果是密码学中最基本的定理之一，有助于我们理解该领域的硬度和随机性。不幸的是，[HILL99]的缩减并不像人们希望的那样高效，也不像人们希望的那样安全。安全性恶化的主要原因是输入量的增大。特别地，给定n位上的单向函数，通过[HILL99]伪随机生成器获得种子长度为$\cal{O}$（n8）的伪随机函数。当假设单向函数具有一定的限制结构（例如排列或正则函数）时，存在更有效的替代结构。最近，Holenstein [Hol06]提出了一种不同类型的限制。在[Hol06]中证明，当考虑具有指数硬度的单向函数时，可以减少构造中的爆破。该结果推广了[HILL99]的原始构造，并从任何指数硬单向函数中获得一个生成器，该函数具有$\cal{O}$(n5)，甚至$\cal{O}$(n4 log2n)，如果所得到的伪随机生成器的安全性允许具有较弱（但超多项式）的安全性
In their seminal paper [HILL99], Hastad, Impagliazzo, Levin and Luby show that a pseudorandom generator can be constructed from any one-way function. This plausibility result is one of the most fundamental theorems in cryptography and helps shape our understanding of hardness and randomness in the field. Unfortunately, the reduction of [HILL99] is not nearly as efficient nor as security preserving as one may desire. The main reason for the security deterioration is the blowup to the size of the input. In particular, given one-way functions on n bits one obtains by [HILL99] pseudorandom generators with seed length $\cal{O}$(n8). Alternative constructions that are far more efficient exist when assuming the one-way function is of a certain restricted structure (e.g. a permutations or a regular function). Recently, Holenstein [Hol06] addressed a different type of restriction. It is demonstrated in [Hol06] that the blowup in the construction may be reduced when considering one-way functions that have exponential hardness. This result generalizes the original construction of [HILL99] and obtains a generator from any exponentially hard one-way function with a blowup of $\cal{O}$(n5), and even $\cal{O}$(n4 log2n) if the security of the resulting pseudorandom generator is allowed to have weaker (yet super-polynomial) security
In this work we show a construction of a pseudorandom generator from any exponentially hard one-way function with a blowup of only $\cal{O}$(n2) and respectively, only $\cal{O}$(n log2n) if the security of the resulting pseudorandom generator is allowed to have only super-polynomial security. Our technique does not take the path of the original [HILL99] methodology, but rather follows by using the tools recently presented in [HHR05] (for the setting of regular one-way functions) and further developing them