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.

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 can one 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 function 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 a function exist? Would it be possible to construct such a function?

share|improve this question
1  
If you can live with pairings then you can take a look at threshold or multisignatures from the BLS signatures scheme. –  DrLecter Jun 24 at 10:08
add comment

1 Answer 1

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.

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.