Lamport-Diffie + Security Proof

Question

I am studying Lamport-Diffie signature scheme. In the lecture present the algorithm $A'$ for attempting to invert the one way function $f$, where $f$ is used to compute the public key. My question is Why to use this algorithm $A'$ to prove the Theorem 1?, Why I cann't use other any algorithm (for example Grover, or Brute Force)?

Answer 1

Well, $f$ is assumed to be a one-way function. That means, there cannot exist an efficient algorithm for finding preimages under $f$. The algorithm $A'$ is what we call a reduction.

We are trying to show that an efficient algorithm for attacking the signature scheme does not exist. To do that, we assume the contrary, i.e. we assume an efficient algorithm $A$ exists that successfully forges a signature. We then use this algorithm $A$ as blackbox (i.e. we do not assume anything about it beyond the fact that it works) to construct a second algorithm $A'$. This algorithm can efficiently compute preimages under $f$, if $A$ works as specified. Because we assumed that $f$ is one-way, this a contradiction, as no such algorithm can exist if $f$ is one-way.

Now, because the existence of $A$ implies existence of $A'$, but $A'$ cannot exist, we can conclude that $A$ cannot exist either. This proves that no efficient adversary against the one-time signature scheme exists and the scheme is, therefore, secure.

Some algorithm for inverting $f$ that does not use the adversary against the signature scheme (besides not being efficient) would not allow you to conclude anything about the security of the scheme.