next up previous
Next: Simple Constructions of Almost Up: The Technion Period (1986-94) Previous: A Quantitative Approach to

Security Preserving Amplification of Hardness

It is shown how to transform weak one-way permutations into strong one-way permutations, while increasing the length of the argument only by a constant factor. This improves over Yao's construction that blows up the length by a factor inversely proportional to the fraction on which the original permutation is hard to invert. The construction consists of interating the original permutation, while interleaving succesive iterations with moves on an adequate expander graph.


Comments: Authored by O. Goldreich, R. Impagliazzo, L.A. Levin, R. Venkatesan and D. Zuckerman. Appeared in



Oded Goldreich
2003-07-30