This is a loaded question so I'll list the concerns, not all of which need to be satisfied.

Does there exist a threshold-signature scheme for Ed25519 that...

  1. Does not require a trusted dealer to set up the key shares (required)
  2. Does not require interaction to set up the key shares (optional: ideally users can independently generate key pairs, but if all n users need to interact to compute the key shares, that's acceptable)
  3. Supports arbitrary m-of-n composition, as opposed to having restrictions on m (required)
  4. Does not require interaction to reconstruct the threshold signature from signature shares (optional: same as 2, non-interative schemes are preferred)

Some sources claim that this is possible (e.g. https://ripple.com/curves-with-a-twist/) but I haven't seen an implementation yet.

  • $\begingroup$ There is always the generic solution: A public key is the concatenation of n individual public keys and the threshold m, a signature is the concatenation of m individual signatures. $\endgroup$ Dec 2, 2014 at 13:04

1 Answer 1


Threshold (robust) m-of-n variant of Schnorr signature scheme is known:

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could be solved with Shamir scheme (interpolation) for Schnorr signature, namely re-construct response s from shares of k and x (wikipedia notations). No trusted dealer is straightforward for Schnorr scheme while choosing x and k, to meet points 1 and 2.

Schnorr scheme admits efficient verifiable threshold variant without any trusted dealer (like while signing key generation). Efficient means combining partial signatures needs just a single interpolation for a known linear combination of secrets (that is, signing key and k) and another interpolation for random group element gk. Verifiable means any error (like misbehaving participant) will be detected. Threshold means any m honest participants will produce a signature. At last, "threshold" signature is verifiable as usual one, the same equation.

Let me refer to "High-speed high-security signatures", section "The signature system", subsection "EdDSA keys and signatures". Verification equation is similar to Schnorr scheme, with multiplier 8; signature is response S, initial random r, random group element R, actual secret a. It fits well. Ok, we have "-" sign while calculating response with original Schnorr scheme.

  • $\begingroup$ Ed25519 includes $R$ in the message hash. Does that cause problems for the threshold scheme? $\endgroup$ May 18, 2015 at 13:21
  • 1
    $\begingroup$ @CodesInChaos A new fresh $R$ can be calculated by the subset of key-share-holders willing to issue a signature. Care to state a problem? $\endgroup$ May 21, 2015 at 16:54

Your Answer

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

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