8
$\begingroup$

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.

$\endgroup$
  • $\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$ – CodesInChaos Dec 2 '14 at 13:04
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Ed25519 includes $R$ in the message hash. Does that cause problems for the threshold scheme? $\endgroup$ – CodesInChaos May 18 '15 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$ – Vadym Fedyukovych May 21 '15 at 16:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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