Cryptography Reference
In-Depth Information
on instances of the second task, induced by our reduction. In many cases the latter
distribution equals the distribution to which the hypothesis (regarding solvability of the
second task) refers, but other cases can be handled too (e.g., these distributions may
be “sufficiently close” for the specific purpose). In any case, a careful analysis of the
distribution induced by the reducibility argument is due.
2.3.3.2. The Information-Theoretic Analogue
Theorem 2.3.2 has a natural information-theoretic (or “probabilistic”) analogue that as-
serts that repeating an experiment that has a noticeable failure probability sufficiently
many times will yield some failure with very high probability. The reader is probably
convinced at this stage that the proof of Theorem 2.3.2 is much more complex than the
proof of the information-theoretic analogue. In the information-theoretic context, the
repeated events are independent by definition, whereas in our computational context no
such independence (which corresponds to the naive argument given at the beginning
of the proof of Theorem 2.3.2) can be guaranteed. Another indication of the difference
between the two settings follows. In the information-theoretic setting, the probability
that none of the failure events will occur decreases exponentially with the number of
repetitions. In contrast, in the computational setting we can reach only an unspecified
negligible bound on the inverting probabilities of polynomial-time algorithms. Further-
more, it may be the case that
g
constructed in the proof of Theorem 2.3.2 can be ef-
ficiently inverted on
g
(
U
n
2
p
(
n
)
) with success probability that is sub-exponentially de-
creasing (e.g., with probability 2
−
(log
2
n
)
3
), whereas the analogous information-theoretic
bound is exponentially decreasing (i.e.,
e
−
n
).
2.3.3.3. Weak One-Way Functions Versus Strong Ones: A Summary
By Theorem 2.3.2, whenever we assume the existence of one-way functions, there
is no need to specify whether we refer to weak or strong ones. That is, as far as the
mere existence of one-way function goes, the notions of weak and strong one-way
functions are equivalent. However, as far as efficiency considerations are concerned,
the two notions are not really equivalent, since the above transformation of weak one-
way functions into strong ones is not practical. An alternative transformation, which is
much more efficient, does exist for the case of one-way permutations and other specific
classes of one-way functions. The interested reader is referred to Section 2.6.
2.4. One-Way Functions: Variations
In this section we discuss several issues concerning one-way functions. In the first
subsection we present a function that is (strongly) one-way, provided that one-way
functions exist. The construction of this function is of strict abstract interest. In contrast,
the issues discussed in the other subsections are of practical importance. First, we
present an alternative formulation of one-way functions. This formulation is better
suited for describing many natural candidates for one-way functions, and indeed we use
it in order to describe some popular candidates for one-way functions. Next, we use this
51
