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!

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.