# One-time digital signatures

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.

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.

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.

There is one such signature scheme designed specifically for cryptocurrencies:

https://bitcointalk.org/index.php?topic=1129388.0

It is based on ECDSA and works by committing to $k$ (a number used to create the signature, see https://en.wikipedia.org/wiki/ECDSA) in advance by making $k$ x $G$ part of public key. If this key is used for a second time, $k$ will be necessarily reused, and ECDSA private key is known to be exposed if the same $k$ was used to sign two different messages.

However you should be careful if you try to use such signature scheme in a cryptocurrency. As noted in the above linked discussion at bitcointalk, one-time signature makes the common practice of address re-use impossible, even for honest users. Also, it does not stop miners from signing two blocks on two competing chains, as by the time the miner publishes the second block, he would have already moved funds to another address on both chains, and he won't lose anything.