Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

2.2.1. Strong One-Way Functions > Further Discussion - Pg. 33

2.2. ONE-WAY FUNCTIONS: DEFINITIONS Definition 2.2.1 (Strong One-Way Functions): A function f : {0, 1} {0, 1} is called (strongly) one-way if the following two conditions hold: 1. Easy to compute: There exists a (deterministic) polynomial-time algorithm A such that on input x algorithm A outputs f (x) (i.e., A(x) = f (x)). 2. Hard to invert: For every probabilistic polynomial-time algorithm A , every positive polynomial p(·), and all sufficiently large n's, Pr[A ( f (U n ), 1 n ) f -1 ( f (U n ))] < 1 p(n) Recall that U n denotes a random variable uniformly distributed over {0, 1} n . Hence, the probability in the second condition is taken over all the possible values assigned to U n and all possible internal coin tosses of A , with uniform probability distribution. Note that A is not required to output a specific pre-image of f (x); any pre-image (i.e., element in the set f -1 ( f (x))) will do. (Indeed, in case f is 1-1, the string x is the only pre-image of f (x) under f ; but in general there may be other pre-images.) The Auxiliary Input 1 n . In addition to an input in the range of f , the inverting algorithm A is also given the length of the desired output (in unary notation). The main reason for this convention is to rule out the possibility that a function will be considered one-way merely because it drastically shrinks its input, and so the inverting algorithm just does not have enough time to print the desired output (i.e., the corresponding pre- image). Consider, for example, the function f len defined by f len (x) = y such that y is the binary representation of the length of x (i.e., f len (x) = |x|). Since | f len (x)| = log 2 |x|, no algorithm can invert f len on y in time polynomial in |y|; yet there exists an obvious algorithm that inverts f len on y = f len (x) in time polynomial in |x| (e.g., by |x| 0 |x| ). In general, the auxiliary input 1 |x| , provided in conjunction with the input f (x), allows the inverting algorithm to run in time polynomial in the total length of the main input and the desired output. Note that in the special case of length-preserving functions f (i.e.| f (x)| = |(x)| for all x's ), this auxiliary input is redundant. More generally, the auxiliary input is redundant if, given only f (x), one can generate 1 |x| in time polynomial in |x|. (See Exercise 4 and Section Further Discussion Hardness to invert is interpreted (by the foregoing definition) as an upper bound on the success probability of efficient inverting algorithms. The probability is measured with respect to both the random choices of the inverting algorithm and the distribution of the (main) input to this algorithm (i.e., f (x)). The input distribution to the inverting algorithm is obtained by applying f to a uniformly selected x {0, 1} n . If f induces a permutation on {0, 1} n , then the input to the inverting algorithm is uniformly distributed over {0, 1} n . However, in the general case where f is not necessarily a one-to-one function, the input distribution to the inverting algorithm may differ substantially from the uniform one. In any case, it is required that the success probability, defined over the aforementioned probability space, be negligible (as a function of the length of x). To 33