Talk:Lamport signature

From Wikipedia, the free encyclopedia

[edit] 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)

[edit] 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)

[edit] 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)