The definition of the one way function says:

  1. it must be verifiable in polynomial time
  2. probability of inverting it less or equal to negligible

Now, I am not sure I fully understand one way functions.

  • Can I say that $f(x) = x$ is a one way function?
  • Do we assume that we know how $f$ is defined?
  • if $x$ is of length $l$, then the probability of guessing it is: $(1/2)^l$ which is negligible.

I am pretty sure that my reasoning is wrong, any hint?

  • 1
    $\begingroup$ We always assume to know the function, otherwise everything would be secure. $\endgroup$
    – SEJPM
    Feb 21 '16 at 20:24

It is not one-way because there is an efficient algorithm which inverts it with probability $1$; namely an algorithm which simply outputs its input.

The fact that we "know the function" is implicit in that no restriction is placed on how the algorithm is "devised", it is only required that such an algorithm exists.


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.