<p>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$.)</p>

<p>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:</p>

<p>$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)&lt;1/poly(n)$$</p>

<p>where $A$ is the adversary.</p>

<p>In fact, I'm going to strength our assumption a bit:</p>

<p>$$\forall x\in_{\mathcal{u}}: \mathbb{P}(A(f(x))=x)\leq 1/2^l$$</p>

<p>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?</p>

<p>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:</p>

<p>$$\forall x'\in L_{I,x}: \forall i_j\in I, f(x')[i_j]=f(x)[i_j]$$</p>

<p>where $f(x)[i_j]$ denotes the $i_j$th bit of $f(x)$ (and similar for $f(x')[i_j]$),</p>

<p>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}$?</p>

<p>Answers are great, but pointers to existing literature that studies this kind of problem are warmly welcome as well!</p>

<p>Thanks in advance! </p>

CC BY-SA 3.0
2013-11-02T07:04:00.783Z
Or it could try a polynomial number of fixed inputs, say the first $l^k$.
Yuval Filmus
<permutations><one-way-function>
"Partial" invert a one-way permutation
vistb
# "Partial" invert a one-way permutation

(Asked by: username_0 on 2013-11-01)

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!

**Tags:** permutations, one-way-function
> **Comments:**
> **username_1**: Or it could try a polynomial number of fixed inputs, say the first $l^k$.  

---

## 0 answers

