2
$\begingroup$

In the proof of existence of length preserving one way functions assuming the existence of one way functions, see

Length-preserving one-way functions

We need $p(n)$ to be a function which can not only be computed in polynomial time, but also, its inverse should be polynomial time computable. How do we ensure that ? $p(n)$ can be chosen to be monotonically increasing. But is that sufficient ?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

$p(n)$ is just a polynomial that indicates the length of the output of the function $g$, as a function of the length of the input. Imagine that it's something like $27n$ or $2n^2$, and then read through the proof and you'll see how it works.

I didn't see any requirement to compute an inverse of $p(\cdot)$ in that proof. I'm not sure where you got that from. But anyway, if you wanted to invert it, any such polynomial is monotonic and can be easily inverted, e.g., by using binary search or using Newton's method.

Improve this answer
$\endgroup$
2
  • $\begingroup$ When we compute $f(x||y)$, (let the length of $x||y$ be $n+1$) we do not know where the partition is,so don't we need to find $p^{-1}(n)$, to get the prefix $x$ ? $\endgroup$
    – Gaganpreet
    Commented Apr 19, 2015 at 7:07
  • $\begingroup$ @user15338, in a non-uniform model of computation, it costs you nothing. You don't recompute that anew for each $x$. Instead, it's a one-time deal (which doesn't count in the running time for computing $f$, at least in a non-uniform complexity model, as the result can be hardcoded in the algorithm for $f$). Alternatively, if you wanted to compute the inverse of $p(\cdot)$, you could do it efficiently using the method described in my answer. $\endgroup$
    – D.W. ♦
    Commented Apr 19, 2015 at 7:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.