# Secure multi-party computation for digital signature

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.
• Maybe what you want is a threshold signature scheme, or group signatures? It works approximately the same, at least M of N parties agree on a single message and communicate in order to sign it. – Natanael Feb 23 at 10:49
• FYI: signature is not ‘encryption with the private key’. It's a separate concept, with different computations. – Squeamish Ossifrage Feb 23 at 15:01
• @Natanael No, because I have to integrate this solution with existing PKI, so completely different type of signature will not do. – adontz Feb 23 at 15:03
• Some references on Schnorr-type threshold signatures, particularly with EdDSA: crypto.stackexchange.com/a/50450 – Squeamish Ossifrage Feb 23 at 15:16
• @adontz there exists some transparent threshold schemes that can work with existing keys in existing ECC curves. Also, encryption can work too (technically key exchange, then encryption) – Natanael Feb 23 at 17:05

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, 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 private 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

ets go through the requirements:

• No party can recover $$K$$ 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 $$K$$, but without revealing any useful information about $$K$$ 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.