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

  • 1
    $\begingroup$ It would probably be best if you formulated your post as an actual question. $\endgroup$
    – Maeher
    Feb 3 '19 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.

Of course, this is just a sketch, and some additional work is required to formally prove that everything works out fine, but it should not be too hard.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.