# Are commutative digital signature possible?

Say we have a message $$m$$. Signer $$S^1$$ will sign this message using his digital signature to produce:

$$\operatorname{Sign}_{S^1}(m)$$

Now, say another signer $$S^2$$ wants to sign the output of the previous stage to generate:

$$\operatorname{Sign}_{S^2}(\operatorname{Sign}_{S^1}(m))$$

Is there a way to verify that $$m$$ has been signed by either signer without having to remove the signature of signer $$S^2$$?

Also, can I verify that $$m$$ was signed by signer $$S^1$$, even if I am not interested in verifying that it was signed by signer $$S^2$$?

• It's not quite clear to me what you would want to verify. Do you want to verify that both parties signed the message? Do you want to verify that at least one of the parties signed the message or do you want to verify that one specific party signed the message? (In the last case, do you know the other signers' public keys or not? – Maeher Mar 20 '19 at 16:53
• If we are willing to restrict the original $m$ in some way (like, having a certain size, or not starting with a certain bitstring, or ending with some encoding of its length) then what's asked is easy for any signature scheme with appendix. Basically we parse a signed message to find the appendixes for the various signatures, and verify the signatures that we care about. – fgrieu Mar 20 '19 at 17:26
• @Maeher yes i want to verify that the message was signed by Signer 1, assuming we know the signer's public key. – user101 Mar 20 '19 at 22:35
• I think Maeher asked for the other signers public key, and I think you mention the org. signer's public key in your comment. Note that there is some difference between knowing the value of a public key that was probably used for signing and trusting a public key. – Maarten Bodewes Mar 21 '19 at 13:14
• I didn't say that you would use the signer's public key to sign something. The signer's public key is just the public key that belongs to the private key that can sign something. You need it to verify signatures, but to do that you must first trust that it is the right key, otherwise an adversary could send you his key, and let you trust his signature rather than the intended one. – Maarten Bodewes Mar 22 '19 at 23:40

Let a signed message consist of a bit string $$m$$ and a set of signatures $$\Sigma$$. A ‘signed message’ of a bit string $$m$$ with no signatures is $$(m, \{\})$$. When the $$i^{\mathit{th}}$$ user signs $$(m, \Sigma)$$, they return $$(m, \Sigma \cup \{\sigma\})$$ where $$\sigma = \operatorname{Sign}_{S^i}(m)$$. The verifier confirms that there are signatures by all the signers they care about on the message.
This works with any base signature scheme, like Ed25519. If a signature appendix in the base signature scheme adds $$s$$ bytes, and there are $$n$$ signatures, a signature appendix in this composite signature scheme adds $$s\cdot n$$ bytes, and the cost of verification is at most $$s$$ times the cost of verification of the base signature scheme.