2
$\begingroup$

If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision bits every time), is the function a one-way function?

$\endgroup$
  • $\begingroup$ It might just be that I know nothing about one-way functions but I can't work out what you're asking. In the context of computability, "recursive" and "computable" mean the same thing; in the context of programming, I don't see how the function being recursive (i.e., calling itself) is relevant. The title says the function is in P but the question body doesn't. What does it mean for a function to be "mapped onto a fixed size string system"? "With less predictability" than what? $\endgroup$ – David Richerby Sep 25 '15 at 9:38
  • 1
    $\begingroup$ We don't know if one-way functions exist at all. A function that maps to a finite domain is definitely not one-way, though. $\endgroup$ – Tom van der Zanden Sep 25 '15 at 9:47
4
$\begingroup$

A one-way function is a function which is easy to compute but hard to invert. More accurate, it is a polytime function $f$ such that given a random $y$, it is hard to find a preimage $x$ satisfying $f(x) = y$. The exact sense of hardness isn't important here.

Your function is not one-way since it fails the first requirement: it is not easy to compute. If you use your recursive definition, computing $f(x)$ takes $x$ applications of the function $g$, which is exponential time.

It also fails the second requirement, since its range is finite. You can hardcode one preimage for each possible value in the image, and so invert the function efficiently.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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