How use multiple keys to sign the same document?

Question

I’m thinking about create one software, that will need the user to sign each document, using Ed25519. I need to create something that is secure and simple. Requering use a HSM is not viable and hardware implementation of Ed25519 is closely to nonexistent, and common users not have it.

Considering it, the key will be stored (in the encrypted way) on the computer and the signature operation will occur in the same machine. I don’t think it is safe enough. To create something “more secure”, and still accessible: the user can add more devices, more keys, that need to sign the same document.

One user can have two keys, one it is stored on the computer and another key on the smartphone, for instance. The attacker, in this situation, need to steal two keys, which can increase the difficult, a little bit.

What is the best (the safest and easiest) way to create a multi-signature?

I can use something like S(M, K1), S(M, K2) ... S(M, Kn). I think it will work, because the Message will be Signed by multiple Key, and we only need to append all these signature at the end. To verify, only require to compare all signatures with the same text and check against the public key. I'm not a cryptographer, so I'm a little bit worried if something is wrong.

Have a more elegant solution? Have something that can be wrong in this previous approach?

---

The main goal is:

1. Stealing all keys, except one, we still safe. We are safe until the attacker gets access to all the keys.

2. Signature operation need to occur where the key are stored, we can’t share a private key between the devices, or trust in a single device to perform the operation.

3. Uncomplicated way to verify the signature. Everyone, including the software, can easily verify that was signed by all these keys.

Note:

1. Keys, already compromised or not, can't be removed/revoked. All keys will be trusted forever, or until the signature algorithm has been broken.

Answer 1

Teach the verifier what set of keys must sign a document for it to be valid. When the verifier receives a document, it must have a valid signature by every one of those keys affixed to it.

Then before a verifier will accept a signed document, the possessor of every one of the signing keys must sign it.

That's it. That's enough for the security properties you've described.

It's not the most efficient scheme. There are more efficient schemes, e.g. in an earlier answer I wrote to a related question, but this will satisfy the security properties you asked for and can be built out of any ordinary public-key signature scheme.