1
$\begingroup$

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?

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.