Note: A distributed signature scheme exists for RSA: Practical Threshold Signatures, Victor Shoup. Is it possible to adapt such scheme for ECC?
A centralized signing machine is vulnerable to attackers
In the situation where a private key has been distributed over R number of machines, which each hold a part of the secret, these R machines can send their share to the signing machine, which will recombine the private key, using the R parts received, in order to sign messages.
This is not satisfactory, because the attacker now only has to attack the signing machine, and wait until it has recombined the private key in order to steal it.
Partial signatures
If sig=sign(sk,m) is the elliptic curve cryptography function to sign a message m with private key sk, yielding signature sig, and if shamir(sk) = [shsk1, shsk2, shsk3, ..., shskR] the function that produces a vector of Shamir secret parts, then the partial signatures would be:
shsig1=sign(shsk1,m)
shsig2=sign(shsk2,m)
...
shsigR=sign(shskR,m)
Since it is not practically possible to retrieve the private key from a ECC signature, it is also not practically possible to retrieve the shamir secret from a partial ECC signature. Therefore, it would be safe to send on such partial signature to the signing machine.
How to recombine the partial signatures?
Now we need a function combineShamirPartialSigs, where:
sig=combineShamirPartialSigs(shsig1, shsig2, ... , shsigR)=sign(sk,m)
In other words, the combination of partial signatures should be equivalent to the signature of the combined private key sk.
Progressive signing
Preferably, such function would even be able to sign progressively:
shsigP1=sign(shsk1,m)
shsigP2=combinePartialSigsProgressively(shsig1,shsk2,m)
shsigP3=combinePartialSigsProgressively(shsigP2,shsk3,m)
shsigPR=combinePartialSigsProgressively(shsigP[R-1],shskR,m)
=sig
The last machine R to sign progressively would then automatically produce the final signature sig.
Security value of this function
This kind of functions would solve a serious security problem. The R machines would not send their secret parts to the signing machine, but produce partial signatures by themselves and send those instead, or even gradually combine the signature by themselves. It would be pointless for the attacker to attack any centralized signing machine, because at no point in time it would know the private key. This function would protect a distributed signing infrastructure from attackers, by keeping its core secrets distributed at all times.
Question
Does such function exist? Would it be possible to construct such function?
