Next: Simple Constructions of Almost
Up: The Technion Period (1986-94)
Previous: A Quantitative Approach to
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
- Proc. of the 31st FOCS, pp. 318-326, 1990.
Oded Goldreich
2003-07-30