# How to prove that weak one way functions cannot have polynomial-sized ranges?

I figured how to show that strong OWFs cannot have polynomial sized ranges. But I am unable to prove the same for weak OWFs.

• It would probably be best if you formulated your post as an actual question. – Maeher Feb 3 at 13:54

Here is a sketch of the proof, I will let you figure out the details. Let $$n$$ be your security parameter. If the function $$f$$ has polynomial size range $$\{y_1, \cdots, y_{p(n)}\}$$, then its domain can be partitioned as the union of a polynomial $$p(n)$$ disjoint subsets $$S_i$$, where each $$S_i$$ contains all values $$x$$ such that $$f(x) = y_i$$. Now, the game is as follows: the challenger picks $$x$$ at random, and returns $$y = f(x)$$. The goal is to find a preimage $$x'$$.
I claim that, except with negligible probability, the set $$S_i$$ associated with $$y$$ has inverse-polynomial density over the set of all possible preimages; that is, it contains a fraction $$1/q(n)$$ of all preimages for some polynomial $$q$$. This is simply for the following reason: if it is not the case that $$S_i$$ has polynomial density, then the probability that the value $$x$$ sampled by the challenger belongs to $$S_i$$ is negligible, and there are only polynomially many sets.
Now, this suggests a simple algorithm for inverting the function: sample $$q(n)\cdot \omega(\log n)$$ random inputs $$x'$$ from the domain, and compute $$f(x)$$. Then, the probability that none of the sampled inputs belong to $$S_i$$ is negligible ($$2^{-\omega(\log n)}$$). Hence, except with negligible probability, this algorithm will invert the function $$f$$ successfully on $$y$$, contradicting the claim that $$f$$ is a weak one-way function.
A little remark on how this should be properly formalized: working with "negligible" versus "non-negligible" would not work, since there can be weird intermediate things between "negligible size" and "inverse polynomial size". The right approach is to start from a specific $$1/d(n)$$-weak OWF (where each algorithm fails at inverting $$f$$ on a random output with probability at least $$1/d(n)$$), and construct through the above approach an algorithm that succeeds with better than $$1-1/d(n)$$ probability at inverting the function. To do so, consider all sets $$S_i$$ with density at most $$1/(p(n)\cdot d^2(n))$$: the union of all those $$S_i$$ has density at most $$1/d^2(n)$$, hence the random input $$x$$ of the challenger will be in a set of density at least $$1/(p(n)\cdot d^2(n))$$, except with probability $$1/d^2(n)$$. When this happens, sampling $$p(n)d^2(n)\omega(\log n)$$ random inputs gives a preimage with overwhelming probability, hence our algorithm succeeds with probability at least $$1-1/d^2(n)-\mathsf{negl}(n)$$ ($$\mathsf{negl}(n)$$ denotes a negligible function), contradicting the $$1/d(n)$$-weak one-wayness.