# How use multiple keys to sign the same document?

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.
• 1) Can an attacker strip signatures off, ie remove signatures? 2) Is there an out-of-band method to fetch how many signatures would be expected from a given person? If not, an attacker can "just compromise" one device and change the per-message setting to use one signature? – SEJPM Nov 5 '17 at 13:37
• 1) It’s a good point, I already noticed that situation. But it can occur with just one signature too. If I sign M, you can remove the signature, making it to be invalid. Removing one or more signatures will make it invalid, in this case. 2) Well, the receiver will only trust in the "first key" forever. The first "bundle of key" you got from the sender is the correct one, no revocation or new key is possible. If an attacker compromises the receiver: he can forge the signature. But, considering the receiver have multiples devices, all need to be compromised, or it can be noticeable. – Inkeliz Nov 5 '17 at 14:42