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.


  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.
  • $\begingroup$ 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? $\endgroup$
    – SEJPM
    Commented Nov 5, 2017 at 13:37
  • $\begingroup$ 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. $\endgroup$
    – Inkeliz
    Commented Nov 5, 2017 at 14:42

1 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.

  • $\begingroup$ Note that it is possible to hash just once. So the size of the message is not a huge issue. $\endgroup$
    – Maarten Bodewes
    Commented Nov 6, 2017 at 22:12
  • $\begingroup$ True, but sensible protocols put small bounds on the sizes of documents signed, in order to limit the damage of a DoS against a verifier and to eliminate the temptation to operate on unauthenticated data as it streams in. $\endgroup$ Commented Nov 6, 2017 at 22:27

Your Answer

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

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