Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)?

share|improve this question
1  
@xag please, Could you help me with this question? –  juaninf Jul 5 '13 at 4:15
add comment

1 Answer

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.

share|improve this answer
    
When you say "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." Are you refer to Grover algorithm, for example ?. Which is a role of the classical and quantum algorithms to attempting invert $f$ in model attack CMA-secure?. –  juaninf Jul 5 '13 at 13:17
1  
The goal of the theorem is to show that algorithm A does not exist. The way to this goal is constructed via A' and basic logic: $A \rightarrow A'$ and $A'$ is a contradiction to the original assumption. If you do not use A to construct A', then .... you have no statement about A. –  tylo Jul 30 '13 at 14:10
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.