1
$\begingroup$

It is well-known that a One-Way Function is hard to invert on uniformly random inputs. As per Wikipedia,

for [sic] all randomized algorithms $F$, all positive integers $c$ and all sufficiently large $n = \mathsf{length}(x)$, $$\Pr[f(F(f(x))) = f(x)]\leq\mathsf{negl}(n)$$ where the probability is over the choice of $x$ from the uniform distribution on $\{0,1\}^n$ and the randomness of $F$.

Some basic facts about what happens in the case of non-uniform inputs can be easily ascertained: given, for instance, a pseudorandom distribution as input, the function is also hard to invert lest the existence of a distinguisher for the input distribution. It should be similarly easy to prove the hardness of inverting given an input distribution with a non-negligible amount of min-entropy.

What is the state-of-the-art on invertibility guarantees with non-uniform input distributions?

$\endgroup$
1
  • 2
    $\begingroup$ "It should be similarly easy to prove the hardness of inverting given an input distribution with a non-negligible amount of min-entropy." that's not true. Let $f : \{0,1\}^n \to \{0,1\}^n$ be a OWF. Define $g : \{0,1\}^{2n} \to \{0,1\}^n$ as $g(x\Vert y) := \begin{cases}y&\text{if } x=0^n\\f(y)&\text{otherwise}\end{cases}$. This remains one-way, with a uniform input distribution, but is trivial to invert relative to the distribution with $x=0^n$ and $y$ uniform. $\endgroup$
    – Maeher
    Mar 27 at 9:54

0

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.