Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I cannot understand why a one-way function $f$ is defined in this way
$\text{Pr}(f(A(f(x))) = f(x)) < \frac{1}{p(n)}$
and not
$\text{Pr}(A(f(x)) = x) < \frac{1}{p(n)}$
where $A$ is a randomized algorithm.
Where is the difference? Is the second one weaker?
The two conditions indeed represent different things. Consider the function that, given an $n$-bit input, returns $n$ zeroes. This clearly meets the second definition (if you have $n$ zeroes, a randomized algorithm has just a $1/2^n$ chance of guessing the input, because any $n$-bit input returns that output), but it also clearly fails the first ($A$ is just "return $0^n$"). So the first condition is not weaker than the second; in fact, anything failing the second clearly fails the first (you just use the same algorithm $A$, and use $A(f(x))=x$ and so $f(A(f(x)))=f(x)$). So the first is in fact stronger than the second.
The key difference between the two is that the second is just about finding the exact input we fed into the function. If a function meets this condition, then it means an attacker who knows the output isn't going to figure out our actual input. But that's often not what we're concerned about. In many schemes, it's a problem if the attacker can find any input to get a given output, whether or not it's the actual input we used. Condition 2 asks for the inverse; condition 1 just ask for an inverse, and if the function isn't one-to-one there's a difference between the two. In crypto, one-way functions tend to be used where finding an inverse is a problem.
To use a password hash as an example, suppose my password is swordfish, which hashes to ABCDE1234, and the hash function meets condition 2 but not condition 1. Because of (2) you can't efficiently figure out that my password is swordfish, but because it fails (1) you can find something that hashes to ABCDE1234 (say, letmein12). Sure, you didn't get my password, but you found some inverse of ABCDE1234, and it doesn't help me that you didn't get my password - letmein12 works just as well for your purposes.
The difference is that one of them is useful, and the other is trivial to achieve. $\:$ The second one is weaker because all constant functions with super-polynomially growing domains satisfy it.
