# Is there a way to compress multiple signatures of the same data?

So, I'm working with a system that allows individual users to each have their own private-public key pair.

I would like to allow multiple users to use their private key to sign the same piece of information to confirm they agree with something. By signature, I mean the public key can be used to check the signature is valid.

However, space is at a premium. So is there a way to compress those multiple signatures of the same data?

Using Curve25519, but other algorithms might be acceptable.

-
Aggregate Signatures are more general than that, but might offer you what you want. –  Maeher Jun 24 '14 at 9:17

You can use multi-signatures.

One example is the BN06 scheme described in the paper:
Bellare, Neven - Multi-signatures in the plain public-Key model and a general forking lemma

-
You may also take a look at this paper. –  DrLecter Jun 25 '14 at 16:00
Actually, I think that multiple signatures work the wrong way. I would like for anyone on the network to prove that it was signed by someone with a given public key. This is more anonymous and allows them to use their private key to prove they are a signer but not allow others to look at a multisignature and say that it was signed by public key x,y, and z, right? –  mczarnek Jun 25 '14 at 21:34
@user127317 : $\;\;\;$ Do you need showings of ownership? $\:$ That does not necessarily disallow the latter. $\:$ You might be interested in some sort of undeniable multi-signature. $\;\;\;\;\;\;\;$ –  Ricky Demer Jun 26 '14 at 1:16
Yes, I need to from a signature, be able to say that account A,B,C,... verify that this information is correct. –  mczarnek Jun 26 '14 at 15:41

I don't think a reduction based on repeated messages with possible with normal ECC signatures (ECDSA, ElGamal, EdDSA, etc.).

A few alternative approaches:

• public key recovery

This doesn't reduce the size of the signature itself, but you don't need to transmit the public key alongside the signature. If applicable, this gains you 2 times the security level in size.

• Hashed Schnorr signatures.

This reduces the signature size to 3 times the security level (instead of 4 times the security level)

Not sure how this interacts with multi target attacks.

• BLS signatures

Signature size is only 2 times the security level.

-
Not having to transmit the public key alongside the signature would be a very nice speed up as our public keys are 32B or 64B each on their own. –  mczarnek Jun 25 '14 at 15:35