$next$ $up$ $previous$
Next: On the Theory of Up: The Technion Period (1986-94) Previous: On-line/Off-line Digital signatures

Hard-core Predicates for any One-Way Function

It is shown that any one-way function can be slightly modify to yield a one-way function that has a simple hard-core predicate. The transformation preseves many properties of the original function (e.g., being 1-1, length preserving, etc.). Implicit in the proof is a very efficient list-decoding algorithm for the Hadamard Code.

$\fbox{\begin{minipage}{40em} {\bf Abstract ({v.o.}):} {A central tool in constr... ...tion on the {\em x}'s for which {\em f}\/ is hard to invert.} \end{minipage}}$

Comments: Authored by O. Goldreich and L.A. Levin. Appeared in

Proc. of the 21st ACM Symp. on Theory of Computing (STOC), pp. 25-32, 1989.

Oded Goldreich
2003-07-30