I am studying hash functions. I can understand why collision resistance implies second preimage resistance, but I don't get why second preimage resistance should imply first preimage resistance.
Could anybody be help me with this argument from Introduction to Modern Cryptography by Katz & Lindell, please?
Collision resistance: This is the strongest notion and the one we have considered so far.
Second pre-image resistance: Informally speaking, a hash function is second pre-image resistant if given $s$ and $x$ it is infeasible for a probabilistic polynomial-time adversary to find $x' \ne x$ such that $H^s(x') = H^s(s)$.
Pre-image resistance: Informally, a hash function is pre-image resistant if given $s$ and $y = H^s(x)$ (but not $x$ itself) for a randomly chosen $x$, it is infeasible for a probabilistic polynomial-time adversary to find a value $x'$ such that $H^s(x') = y$. (Looking ahead to later chapters in the book, this essentially means that $H^s$ is one-way.)
[...] Likewise, any hash function that is second pre-image resistant is also pre-image resistant. This is due to the fact that if it is possible to invert $y$ and find an $x^\prime$ such that $H^s (x^\prime ) = y$ then it is possible to take $x$, compute $y = H^s (x)$ and invert it again obtaining $x^\prime$. Since the domain of $H$ is infinite, it follows that with good probability $x \neq x^\prime$. We conclude that the above three security requirements form a hierarchy with each definition implying the one below it.