# “Partial” invert a one-way permutation

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!

• Your strengthened assumption cannot hold. $\:$ $A$ could just try two inputs chosen at random. $\hspace{.6 in}$ – user6973 Nov 1 '13 at 18:46
• Or it could try a polynomial number of fixed inputs, say the first $l^k$. – Yuval Filmus Nov 2 '13 at 7:04