Talk:Lamport signature/Archive 1

Security against quantum computers

The article currently contains the following statement, which needs to be discussed.

"When used in Merkle trees, Lamport signatures form a digital signature scheme that is secure against quantum computers, the only known digital signature scheme to do so."

Firstly, it is only believed that quantum computers can not solve general NP complete problems. Thus the statement should be changed to "Lamport signatures are believed to be secure against quantum computers". Secondly, there exist other digital signature schemes e.g. based on the difficulty of lattice basis reduction, which are not known to be breakable on quantum computers. Finally, it is unclear why there is the restriction "When used in Merkle trees ...". 67.84.116.166 17:58, 10 September 2006 (UTC)

Actually, I think it has been proven that quantum computers can not solve general NP problems. 216.254.71.63 19:34, 28 September

Hi. This article used to state this more correctly but has since then been destroyed by less knowledgeable editors. It used to say:

"Note: A Lamport signature can only be used to sign one message. However combined with hash trees it can be used for many messages and is then a fairly efficient digital signature scheme."

"Lamport signatures is the only digital signature scheme that is secure against quantum computers."

It is news to me that there are other such robust signatures (the lattice reduction) but good to hear. We might need them one day. It also means that the RSA labs article about this that this article used to link too as reference is wrong. Ah well, one can not trust any source, not even RSA labs...

It is on my todo list to clean up this article. And make it readable for the non-maths people. So much work to do...

--David Göthberg 22:00, 28 September 2006 (UTC)

If there is a proof that quantum computers can not solve general NP problems in polynomial time, then I'd like to see a reference for this claim. For example the wiki quantum computer page only claims that "BQP is suspected to be disjoint from NP-complete". There are some results that support such a "conjecture", e.g. that a quantum computer can not efficiently invert a black box function. But that is not a proof. Also, at least some assumption is necessary, because BCP != NP would imply that P != NP. 67.84.116.166 22:39, 28 September 2006 (UTC)

I fixed the statements about hash trees so they now are true. I do understand hash trees and hash lists well so I know that part is now correct. Note that a hash list is better than a hash tree to make one short Lamport key (one hash) out of the list of hashes that originally formed the key. While a hash tree is better than a hash list to handle MANY such short keys.

Regarding the quantum part I should mention I am not a maths guy so I don't know if that is true, but I have seen many sources mention that hashes are believed to be secure against quantum computers. And thus Lamport signatures should be secure too. I readded the reference to RSA labs where they state that. Note that the RSA labs article also has a simple explanation how Lamport signatures works so that means it is also a reference for how Lamport signatures work.

--David Göthberg 11:56, 7 November 2006 (UTC)

Article name

The full name of this method is as far as I get it the Lamport one-time signature scheme. I did the Google test and found all kinds of combinations of those words used as shorter names for it. But the long name is awkward as an article name. And I think the name we had (Lamport signature scheme) just represented one such short form and the word "scheme" could just as well be any number of other similar words such as method, algorithm, construct etc. So I moved the article to the shortest unambiguous name (Lamport signature) which I think is the name most would bother to type into a search field. --David Göthberg 11:56, 7 November 2006 (UTC)

Question

What are Y and Z in the "Keys" section? How are the subscripts defined for y_i,j ∈ Y? Y does not appear to be a priori a doubly-indexed set. - 74.112.174.10 20:59, 3 January 2007 (UTC)

See the new "plain English" section I added today. --David Göthberg 00:14, 22 August 2007 (UTC)

Unclear notation

The notation for the algorithm seems very unclear. What is the key and what is being hashed? -- Myria 19:49, 13 May 2007 (UTC)

See the new "plain English" section I added today. --David Göthberg 00:14, 22 August 2007 (UTC)

Updated Security Estimates

This is my second pass at the security estimates. I am reasonably confident with the first half of the results, up and till i begin to take into account attacks with a large number of preimages. At this point the conclusions are less certain. I'd appreciate people taking a close look at the results and double checking them for accuracy.

For your convenience, here are related papers I have found in this area that discuss:

• impact of long messages on preimages in hash functions ( J. Kelsy and B. Schneir, "Second preimages on n-bit hash functions for much less than 2^n work". [1] )

• impact of long messages on collisions in hash functions in conventional and quantum attacks ( S. Kutin, "Quantum lower bound for the collision problem", [2] )

• impact of collecting a large number of digests and other hazzards ( B Preneel, "Design Principles for Iterated Hash Functions Revised", [3] )

I have not found any publications that combine:

• Large number of digests and quantum attacks; or
• Large number of plaintext-ciphertext pairs and quantum attacks; or
• Long messages, large number of digests and quantum attacks.

CipherNord 12:58, 22 August 2007 (UTC)

I don't agree with the security estimates. Some of it is original reasearch. Some conclusions do not follow and look rather speculative. I.e. Grover's algorithm says it takes $O(2^{n/2})$ work on a quantum computer to invert an n bit function. It does not say that every algorithm can be performed in time approximate to the square root of the best classical algorithm. E.g., the best result for finding a hash collision (that I'm aware of) takes $O(2^{n/3})$ on a quantum computer compared to $O(2^{n/2})$ for classical computers.

The paper by Schneier and Kelsey (rsp. Dean et al.) is not relevant here, because it assumes that the attacker can produce long messages as a result for the attack. Kutin proves lower bounds for black box functions. Preneel's work is somewhat relevant, but the number of necessary hash targets is large and would have to be taken into account for an estimate.

To conclude, wikipedia is not the place for guesses. If a problem has not been discussed in the literature it should be described as an open problem. 169.231.5.121 14:17, 22 August 2007 (UTC)

I think that using IVs/nonces in the right way can mitigate or even nullify several of the concerns still stated in the "Security parameters" section. For instance, if every key pair used its own IV and each random number in the secret key is hashed like this to create the hashes for the public key:

public hash = hash( key IV + position in key + secret key value )

"+" here meaning concatenation.

Then an attacker has to run a full new brute force search for each value in the key, and also do it again for every new key he wants to attack. Then he can not reuse any stored results or similar.

--David Göthberg 15:50, 23 August 2007 (UTC)

Yes, this might help. I can't find any references though. Also, I haven't been unable to find the paper [Wiener02] cited in Preneel's talk, currently discussed in the security section. 169.231.5.121 16:07, 23 August 2007 (UTC)

169.231.5.121

169.231.5.121: I noticed you have done many changes to the article. I agree with most of the changes. However, there are some things I want to point out:

• Before you edit/delete/re-delete stuff from the article do click the history tab of the page and see the edit comments that the previous editors have written. Then you might understand WHY they did the changes they did.
• Then you would have learnt that the reason I reverted you and put back the "see also" link to Hash tree was not that it necessarily needed a link since as you pointed out in your edit comment that link already exists in the article, but that that link did have a relevant comment that first should be worked into the article before removing it. (And I was not in the mood to do that at that time, so I just reverted your deletion.)
• You really should log in to Wikipedia and not continue edit from a IP. Editing from a IP will cause you all kinds of problems. See, most vandalism and incompetent edits comes from not logged in users so seeing just an IP number in the edit history makes the rest of us expect your edits to be bad. Secondly, if you choose a user name and log in the rest of us can "get to know" your edits and know what to expect and thus be more relaxed about your edits which will benefit both you and us.

--David Göthberg 10:53, 23 August 2007 (UTC)

The statement that hash trees were proposed by Merkle is clearly a statement about hash trees and hence belongs in the article hash tree. There it already is prominently featured in the section uses. Generally statements in wikipedia should be clear enough so that they can be verified. The statement in this article does neither state the name of the inventor nor give any reference to where it was proposed and hence is kind of worthless. Rather than indiscriminatly spreading information in several articles, I prefer to put information at the right place as well as citing them properly.

I don't agree with you implicit claim that users with an accout are somehow more competent than anonymous users. I for example choose to stay anonymous, just so that I'm forced to give proper references and explanations to claims, rather than pretending authority and using this to intimidate others. 169.231.5.121 14:50, 23 August 2007 (UTC)

Well, if you log in you will save me and others a lot of work. See, when I in my watchlist see edits done by editors that I know mostly do good correct edits then I don't bother to check those edits, saving me lots of work. I tend to get back to those articles later anyway, when some anonymous user has edited them. Then I often also do check the older edits from editors I know. But still, that means just checking the article every now and then in one batch operation.

Also, if you log in we can leave you messages on your talk page and see your edit history etc. Sure, we can see that for your IP too, but we don't know if you have the same IP everyday and we don't know for how long you have had that IP and how long you will keep it. And have you even noticed that I left a message on your talkpage? I heard that nowadays IP users don't get a notice about that any more. If I get a message on my talk page then I get a orange box informing about it on top of all Wikipedia pages I enter, until I view my talkpage.

I should perhaps mention that I think you do good work here, so I would like to be able to skip checking your edits.

--David Göthberg 15:20, 23 August 2007 (UTC)

Oh, I saw you just added "Main article: hash tree" to the "Public key for multiple messages" section. Good solution, since it kind of indicates there are more stuff in the hash tree article that might be relevant to Lamport signatures. Although I still think we should perhaps add a statement that hash trees were specifically invented by Ralph Merkle in 1979 to handle many Lamport signatures. --David Göthberg 16:10, 23 August 2007 (UTC)

Difference between mathematical description and English description

The two sections describing the signature scheme differ in a small respect. The English form incorporates the 'Hashing the Message' optimization, while the math form states the algorithm in its unmodified form. —Preceding unsigned comment added by 98.212.137.224 (talk) 13:14, 29 October 2008 (UTC)

Yes, you understood it right. When I wrote the "Plain English description" I preferred to describe how this method would usually be used. And I wouldn't call first hashing the message an "optimisation", since it would be silly to directly sign large files of many megabytes and similar.

--David Göthberg (talk) 17:52, 29 October 2008 (UTC)