In Lamport's one time signature scheme:

  • One way function to convert a pseudo random number private key to a public key takes $\{0,1\}^n$ and returns $\{0,1\}^n$.
  • Cryptographic hash function to convert message into message digest takes $\{0,1\}^*$ and returns $\{0,1\}^n$.

Why are these two not independent? Why do they need the same number of bits $n$?

  • $\begingroup$ Having them be independent makes the scheme take a little longer to describe. ​ ​ $\endgroup$ – user991 Apr 26 '16 at 4:38
  • $\begingroup$ But the security is same even if number of bits is different, right? We can have smaller signatures if number of bits in the message digest and each key is different. $\endgroup$ – Mithraasmi Apr 26 '16 at 4:56
  • $\begingroup$ No. ​ ​ ​ ​ ​ ​ $\endgroup$ – user991 Apr 26 '16 at 4:57
  • 1
    $\begingroup$ Can you please explain little elaborately? "little longer to describe" seems trivial. I would like to understand this before moving to winternitz. $\endgroup$ – Mithraasmi Apr 26 '16 at 5:01
  • $\begingroup$ An adversary could forge by finding a collision or breaking the candidate-OWF. ​ When your compression function is independent of your candidate-OWF, those two tasks will be independent of each other. ​ ​ ​ ​ $\endgroup$ – user991 Apr 26 '16 at 5:27

The security level of a hash function is determined by its output size. In general, a hash function is considered cryptographically secure when it is collision resistant and provides security level $b = n/2$. Hence, it is not wrong to describe Lamport's scheme that way. However, the description probably was done that way to abstract away some details:

If you want to get $b$ bits security and do a classical message digest, you will need a hash function with $m = 2b$ bit outputs for the digest. However, for the "internal" hash function used to map secret key elements to public key elements you are fine with $n = b$ bit outputs as you just need one-wayness for this function. Now, if you change the message digest to a randomized message digest using $h = H(R,M)$ for randomness $R$ and message $M$, you can get away with $m = n = b$ bit output length for the message digest (if you do everything correctly). This is more about the message digest than about the hash function used inside of Lamport and hence distracting from the actual topic: How does Lamport's scheme work.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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