Does Ed25519 support cryptographic threshold signatures?

Question

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.

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.