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.
  • 3
    $\begingroup$ 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. $\endgroup$
    – Natanael
    Commented Feb 23, 2019 at 10:49
  • 1
    $\begingroup$ FYI: signature is not ‘encryption with the private key’. It's a separate concept, with different computations. $\endgroup$ Commented Feb 23, 2019 at 15:01
  • $\begingroup$ @Natanael No, because I have to integrate this solution with existing PKI, so completely different type of signature will not do. $\endgroup$
    – adontz
    Commented Feb 23, 2019 at 15:03
  • 2
    $\begingroup$ Some references on Schnorr-type threshold signatures, particularly with EdDSA: crypto.stackexchange.com/a/50450 $\endgroup$ Commented Feb 23, 2019 at 15:16
  • $\begingroup$ @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) $\endgroup$
    – Natanael
    Commented Feb 23, 2019 at 17:05

1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.