First of all, to my best understanding, traditionally, if $f$ is a one-way function that maps a length $l$ bit string to another length $l$ bit string (i.e., $f:\{0,1\}^l\rightarrow\{0,1\}^l$), then given a length $l$ bit string $x$ that is chosen uniformly at random from $\{0,1\}^l$, the probability that an adversary can invert it in poly time is at most $o(1/poly(l))$. (Notice, it is small $o$, not big $O$.)Now, further assume $f$ is a one-way permutation, that is, $f$ is bijective. Hence, according to discussion in first paragraph, I think it's safe to say:$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)<1/poly(n)$$where $A$ is the adversary.In fact, I'm going to strength our assumption a bit:$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)\leq 1/2^l$$Now, my question is, under above assumption, we give Eve a length $l$ string $x$ that is chosen uniformly at random, what is the probability that Eve found another string $y$ such that $f(y)$ and $f(x)$ has, say $l/4$ bits are the same?More formally, let $I=\{i_1,\cdots,i_{|I|}\}$ be a set of non-negative integers (indice), let $L_{I,x}$ be the set of length $l$ bit strings such that:$$\forall x'\in L_{I,x}: \forall i_j\in I, f(x')[i_j]=f(x)[i_j]$$where $f(x)[i_j]$ denotes the $i_j$th bit of $f(x)$ (and similar for $f(x')[i_j]$),and the question is: given $I$, when we choose $f(x)$ uniformly at random from $\{0,1\}^l$, what is the probability that Eve found any $x'$ that is in $L_{I,x}$?Answers are great, but pointers to existing literature that studies this kind of problem are warmly welcome as well!Thanks in advance! 
Partial invert a one-way permutation
permutations;one way function