ECCC-Report TR05-135https://eccc.weizmann.ac.il/report/2005/135Comments and Revisions published for TR05-135en-usSat, 19 Nov 2005 11:29:19 +0200
Paper TR05-135
| On the Power of the Randomized Iterate |
Iftach Haitner,
Danny Harnik,
Omer Reingold
https://eccc.weizmann.ac.il/report/2005/135We consider two of the most fundamental theorems in Cryptography. The first, due to Haastad et. al. [HILL99], is that pseudorandom generators can be constructed from any one-way function. The second due to Yao [Yao82] states that the existence of weak one-way functions (i.e. functions on which every efficient algorithm fails to invert with some noticeable probability) implies the existence of full fledged one-way functions. These powerful plausibility results shape our understanding of hardness and randomness in Cryptography. Unfortunately, the reductions given in [HILL99,Yao82] are not as security preserving as one may desire. The main reason for the security deterioration is the input blow up in both of these constructions. For example, given one-way functions on n bits one obtains by [HILL99] pseudorandom generators with seed length Omega(n^8).
Sat, 19 Nov 2005 11:29:19 +0200https://eccc.weizmann.ac.il/report/2005/135