Talk:Lamport signature

Merkle signatures

I'm not clear on the differences between the system described under "Public key for multiple messages" and the system described in the article on "Merkle signature scheme", although the public key at least appears to be different. Can someone help? Also, I imagine there ought to be a link to the "Merkle signature scheme" article somewhere, but I'm not sure where yet. Doctorhook (talk) 23:21, 22 August 2010 (UTC)

It is the same system (although I did not proof read the description over at Merkle signature scheme). And just below the section title "Public key for multiple messages" there now is the text and link "Main article: Merkle signature scheme". --David Göthberg (talk) 11:18, 30 January 2023 (UTC)

Mistake under "Making the key pair" section

It is written 2x256x256 i.e., 256 pairs of each 256 bits. Then it says, we hash these 512 data each to 256 bits (Also 16KB). What kind of hash function is this that maps 256 bit input to 256 bit output??? —Preceding unsigned comment added by 213.233.170.69 (talk) 11:55, 14 October 2010 (UTC)

Most hash functions map arbitrary-sized input to fixed-sized output, so nearly any hash function that outputs 256 bits will suffice - SHA-256 being a common example. 142.167.200.150 (talk) 20:53, 8 May 2011 (UTC)

Error in Article--please correct

The algorithm described in the article is one that is described by Diffie & Hellman in their seminal 1976 paper "New Directions in Cryptography" and attributed to Lamport. The cited 1979 paper by Lamport describes an improvement to that algorithm that uses fewer bits. A discussion of the history and a copy of the 1979 paper can be found on Lamport's publication page:

  http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html#dig-sig

Would someone please correct the article.

Milkycow (talk) 18:27, 25 July 2011 (UTC)

Signing the message example

The Signing the message section uses the following example:

First she hashes the message to a 256-bit hash sum. Then for each bit in the hash sum she picks the corresponding number from her private key. If for instance the first bit in the hash sum is a 0, she picks the first number in the first pair. If instead it is a 1, she picks the first number in the second pair and so on.

As someone unfamiliar with the subject, this is unclear to me. I would expect the first bit being a 1 would mean she picks the second number in the first pair. This way provides a 1:1 mapping of the number of bits in the message hash to the number of pairs. If the text as written is correct, then there's no explanation of how the second number of any of the pairs would ever be used, or how the second bit of the message hash is handled.

Thorncp (talk) 02:40, 19 December 2013 (UTC)

That section has since been modified to read:

... If for instance the first bit in the hash sum is a 0, she picks the first number in the first pair. If instead it is a 1, she picks the second number in the first pair and so on.

I believe that the quote you provided is correct. She's iterating through every bit in the 256-bit hash sum. For each bit, if it is 0, she selects the corresponding hash (by array index) from the first set of 256 random numbers. If the bit is 1, she selects the corresponding hash from the second set of 256 random numbers.

For example, hash sum with binary "0011 ..." would generate the signature:

0 => 1st hash, first set

0 => 2nd hash, first set

1 => 3rd hash, second set

1 => 4th hash, second set

... so on

I'm not too familiar with Lamport signing. Can someone with more expertise verify before changes are made in the article?

Polemic Thoughts (talk) 22:26, 20 January 2014 (UTC)

You guys have understood it correctly. Thorncp: Yes, the old text was wrong. Polemic: Yes, the new text is correct and your explanation is spot on. --David Göthberg (talk) 11:29, 30 January 2023 (UTC)

Inconsistent description of the algorithm

The "signing the message" section and the "Hashing the message" seem inconsistent:

- Later Alice wants to sign a message. First she hashes the message to a 256-bit hash sum.

- Unlike some other signature schemes (e.g. RSA) the Lamport signature scheme does not require that the message m is hashed before it is signed.

In the Alice example it seems like the message needs to be hashed before it is signed. The Hashing the message section implies that you don't need to first hash the message, but that seems to contradict the algorithm above (which requires a hashed message so that there are exactly 256 bits to to use for finding keys). Maybe the Hashing The Message section could be extended to explain how exactly the algorithm works without first hashing the message. — Preceding unsigned comment added by 67.161.125.36 (talk) 16:44, 24 May 2015 (UTC)

I've removed that section because it didn't make any sense to me, either. TOGoS (talk) 01:22, 27 November 2015 (UTC)

For reference, the section you removed:

Hashing the message

Unlike some other signature schemes (e.g. RSA) the Lamport signature scheme does not require that the message m is hashed before it is signed. A system for signing long messages can use a collision resistant hash function h and sign h(m) instead of m.

The section was correct, but perhaps not clear enough. If your message is 256 bits or shorter then the Lamport method can sign the message directly, as is, without first hashing it. But if the message is longer than 256 bits, then you first have to hash it, to compress it down to the size that your Lamport signature can handle.

When adding that section we also had in mind that other signature schemes such as RSA have many more demands on how the "short message" should be shaped to avoid weak signatures. (Kind of like weak keys in encryption. But instead in this case "weak messages".) That is, certain "short messages" would give away the content of the RSA private key. So RSA first processes ("pads") the message in a way that avoids causing weak signatures. While Lamport signatures doesn't have such "weak messages", they can securely sign any message from 0000...0000 to FFFF...FFFF.

But I think signing without first hashing is only secure if the receiver in some secure way knows the size of the message. For instance, if the messages you use always have the same fixed size (that happen to be 256 bits or lower). Or, if you can send varying size messages: That the receiver knows when you hash and not, so the receiver knows if it is a signature of a short message, or a signature of the hash of a longer message.

Of course, if your messages are much smaller than 256 bits you have the problem of how to get long enough signatures. That is, you would need some kind of padding to get the full signature size. Otherwise the signature would be too short. And if you just pad with zeroes, then a length extension attack could be done on the message.

So in the end, the simplest and most useful way to avoid all those problems is to always hash the message first, no matter how short or long it is. Thus always getting a "short message" of the correct size to sign. (Of course, you need to use a secure hash function that internally uses the correct padding to avoid length extension attacks. But all modern cryptographic hash functions take care of that correctly.)

--David Göthberg (talk) 17:55, 2 April 2018 (UTC)

Incorrect citation for Winternitz signature compression

The Winternitz signature compression points to a Github page that implements a slightly different signature scheme. Winternitz is just cited in the comment section. It is mentioned there that one of the visitors finds it an interesting scheme and that he therefore edited it into Wikipedia. I don't think this single person review of a separate scheme is enough to act as a citation in an encyclopedia - a paper of Winternitz should be referenced instead. — Preceding unsigned comment added by Owlstead (talk • contribs) 11:09, 2 March 2020 (UTC)