My question might be quite beginner, so please pardon my ignorance :)

So, assume there are 10 parties, each with their own keypairs. There is a message $M$ that is passed from one party to the next. Each has to sign the message with their own private key, append the signature, and send it to the next guy.

As you can see, such a system will be quite expensive (for an RSA key with keysize 1024-bits, it'll be 128 characters per signature).

Is there a way to achieve the same goal (sending a message to multiple parties for them to sign it) while keeping the signature size cheap and small?

It'll be great if the answer is not an "all-or-nothing", meaning that if the signing parties were X, Y and Z, the "combined signature" wouldn't just either prove that parties X, Y and Z signed it or that no one signed it.

  • 1
    $\begingroup$ RSA 1024 is no considered secure. Use ECDSA? $\endgroup$
    – kelalaka
    Oct 1, 2020 at 17:14
  • 2
    $\begingroup$ Not really with RSA, however there may be with other signature systems, depending on the requirements. When the receiver (who only knows the public keys) verifies it, what does he verify? Does he need to check whether signer #5 signed it? Or, is it sufficient if he checks if all 10 parties signed it (and if they didn't, he doesn't care who didn't)? $\endgroup$
    – poncho
    Oct 1, 2020 at 17:14
  • $\begingroup$ Is this like $$RSASign(\ldots \big(RSASign(prvkey_2,hash(RSASign(prvkey_1, hash(m)\big)\ldots )$$ $\endgroup$
    – kelalaka
    Oct 1, 2020 at 17:20
  • $\begingroup$ @poncho: the verifier would get a list of people who signed message $M$. He needs to verify if every single one in that list has signed it (regardless of order). It's also important that the signature is not "poisoned" by having a party that is not in the list sign it. I edited my answer to reflect this. $\endgroup$
    – jimmytann
    Oct 2, 2020 at 6:20


Your Answer

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

Browse other questions tagged or ask your own question.