Elliptic Curve Crypto, is a distributed signing method possible using Shamir's Secret Sharing? 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?
You can do it with two machines. https://www.iacr.org/archive/crypto2001/21390136.pdf (this paper is for DSA; it's easy to adapt for ECDSA).

Here's an open-source JavaScript implementation of two-party ECDSA signing, using Bitcoin parameters: http://www.jpaulgossip.com/demo/split-key.html

Unfortunately the protocol requires at least three rounds of interactive communication so it is probably not suitable for what you call progressive signing.

I believe splitting a key among more than two machines remains an open problem. ECDSA is not well suited for split signatures. I assume your application is something like Bitcoin which requires ECDSA. If only Bitcoin had used BLS signatures, then it would be easy to implement multiparty signing.

Update (4/5/15): A group of researchers at Princeton have solved the problem of multiparty (more than two parties) Bitcoin signatures: https://freedom-to-tinker.com/blog/stevenag/threshold-signatures-for-bitcoin-wallets-are-finally-here/