Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Are there digital signatures for which, given two documents signed by the same key, one could derive the key?

With such one-time signatures, one may be able to design a cryptocurrency based on proof-of-stake instead of proof-of-work. To disincentivise miners from cheating by mining several blocks, one could impose that miners sign with a one-time digital signature the blocks they mine. That way, if a miner did mine two different blocks with the same key, the key would be exposed and they would lose the funds associated with that key.

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

Yes, there does happen to be such a scheme: the Lamport one-time digital signature.

The basic idea of a Lamport signature is that the private key consists of a large number (say, 256) of pairs of secret random numbers, while the public key consists of the cryptographic hashes of those numbers. To sign a message, you first hash it down to 256 bits, and then, for each of those bits, reveal one of the secret numbers in each pair depending on the corresponding bit. Thus, a Lamport signature is literally a (pseudo-randomly chosen) half of the private key.

Technically, publishing two Lamport signatures using the same key weakens the security of the scheme by half, such that the probability of an attacker being able to successfully forge a signature for a given message increases from, say, $1/2^{256}$ to $1/2^{128}$. A third signature using the same key would increase the probability of a successful forgery to $1/2^{64}$, a fourth to $1/2^{32}$, and so on.

Generally, this one-time nature of Lamport signatures is seen as a problem, and there are various signature schemes, such as Merkle signatures, that extend the Lamport scheme to work around it. If you wanted to make deliberate use of it, you'd have to deal with the fact that, as described above, the security collapse caused by a duplicate Lamport signature is not quite immediately, but somewhat gradual.

For example, if you wanted a duplicate signature to allow easy forgery with $2^{32}$ effort, you'd have to accept that even a single signature could be forged with $2^{64}$ effort, which might be a bit too low for comfort.

One possible solution to this problem would be to modify the Lamport scheme so that, instead of pairs of random numbers, your private key would consist of, say, groups of 16 random numbers, out of each of which you'd reveal all but one in the signature (with the one hidden number in each group chosen based on four bits of the message hash). Thus, a duplicate signature would have a $15/16$ chance of fully revealing each group in your private key (and thus rendering it trivially forgeable), increasing the forgery probability from, say, a negligible $1/16^{64} = 1/2^{256}$ to an easy $1/16^\frac{64}{16} = 1/16^{4} = 1/2^{16}$.

Of course, you'd also need to deal with all the other inconvenient features of the Lamport signature scheme, like the enormous size of the public and private keys and the signatures themselves, or the fact that, as one would expect of a one-time signature scheme, each key can indeed only be safely used once. As the Wikipedia articles I've linked to note, various tricks do exist to mitigate several of these issues (and sometimes even several of them at once), but turning the basic Lamport scheme into something practically usable is still not exactly a trivial task.

share|improve this answer
add comment

You might want to check the literature on (offline) schemes for electronic cash, where they have devised schemes where spending the same coin twice results in de-anonymizing the double-spender. I'm not immediately sure whether it will apply directly to your problem, but I think it might be possible to apply their techniques to your setting.

share|improve this answer
add comment

Your Answer

 
discard

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.