Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
Aggregate Signatures are more general than that, but might offer you what you want. –  Maeher Jun 24 at 9:17

2 Answers 2

up vote 4 down vote accepted

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

share|improve this answer
    
You may also take a look at this paper. –  DrLecter Jun 25 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? –  user127317 Jun 25 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 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. –  user127317 Jun 26 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.

share|improve this answer
    
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. –  user127317 Jun 25 at 15:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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