Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Why is Lamport-Diffie secure? I note that there is a demonstration based on onewayness (in the book postquantum cryptography). But a one way function is not sufficient to ensure that it can not infer some bits or any feature of the key signature.

share|improve this question
As far as we know, there there are collision resistant hashes (if necessary we can even weaken that to random prefix collision resistance) which resist quantum computers with slightly larger security parameter. – CodesInChaos Nov 30 '13 at 14:34

Lets assume an adversary knows one LD signature for message $M$ as well as public key $pk$ and can generate a forgery for an arbitrary different message $M'$. Clearly, there exists at least one bit position where the messages differ, i.e. $M_i \neq M'_i$, as $M \neq M'$. So, for simplicity assume there is only one bit difference. Then the adversary can take all signature values for the signature on $M'$ from the signature on $M$ besides the value for this single bit position. For the signature value of this bit it must hold that $f(sig_i) = pk_{i,M'_i}$ as otherwise verification would fail.

So if the adversary is able to generate a valid forgery it obviously is able to find a value $x$ that satisfies $f(x) = pk_{i,M'_i}$ for given $pk_{i,M'_i}$. This is per definition finding a preimage of $f$.

To get back to your question: The adversary might learn some information about $sk_{i,M'_i}$ from $pk_{i,M'_i}$. But that is not enough to produce a forgery as a forgery requires knowledge of a complete value $x$. Even more: it is not required that $x = sk_{i,M'_i}$ for the forgery to be valid.

share|improve this answer

Your Answer


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.