Secure multi-party computation for digital signature

Question

Is there any practical algorithm that will allow to use public key cryptography (RSA or ECC) in the following way

1. There are N parties. Up to M are malicious adversaries (were trusted, but got taken over silently). I will be happy with solution for any N and M = 1.
2. Parties can communicate securely. No eavesdropping.
3. Private key K is somehow split and shared between all N parties. Maybe something like Shamir's Secret Sharing. No party can recover K without other N-1 parties data.
4. All parties receive some data S.
5. Parties should be able to encrypt S (actually hash of S, I need digital signature) with K, but without revealing any useful information about K to malicious adversary; or should detect that there are too many malicious adversaries and abort.

Answer 1

Here's a fairly straight-forward method, using RSA:

Set-up phase (assuming a trusted dealer that participates only with the setup phase; such a setup without a dealer can be done, but is considerably more complicated):

• The dealer selects a random RSA public/private keypair $(n,e)$ and $(d)$

• The dealer then selects $N$ values $d_1, d_2, …, d_N$ with the constraint that $d_1 + d_2 + … + d_N \equiv d \pmod{ \lambda(n) }$

• The dealer privately sends $d_i$ to party $i$, and publishes the public key $(n, e)$

Signature generation phase:

• Each party gets a copy of the value to be signed $S$

• Each party $i$ deterministically pads $S$ (perhaps using PKCS #1.5 signature padding, perhaps using PSS using randomness seeded by $S$), and then raises that to the power of $d_i$ modulo $n$; that is, it computes $sig_i = \text{Pad}(S)^{d_i} \bmod n$

• Each party sends $sig_i$ to a collector, which computes $sig = sig_1 \cdot sig_2 \cdot … \cdot s_n \bmod n$, and broadcasts it

• Everyone checks if $sig$ is a valid signature to the value $s$; if not, then a malicious party is detected

Lets go through the requirements:

• No party can recover secret key $d$ without other $N-1$ parties data

Met; without all the $d_i$ values, you cannot reconstruct the $d$ value.

• 5.Parties should be able to encrypt $S$ (actually hash of $S$, I need digital signature) with secret key $d$, but without revealing any useful information about $d$ to malicious adversary

Met; each party acts as an Oracle that'll compute $f(x) = x^{d_i} \pmod n$, however if the Discrete Log problem is hard, you can't recover $d_i$ from that.

Now, a malicious party could perform a Denial of Service attack (by not computing his $sig_i$ value properly. On the other hand, I believe that this will always be true if you require that $N-1$ parties be unable to recover the key (or otherwise generate arbitrary signatures, which is effectively the same as recovering the key), and so I would claim that this meets your requirement.