6
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Aggregate Signatures are more general than that, but might offer you what you want. $\endgroup$
    – Maeher
    Commented Jun 24, 2014 at 9:17

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ You may also take a look at this paper. $\endgroup$
    – DrLecter
    Commented Jun 25, 2014 at 16:00
  • $\begingroup$ 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? $\endgroup$
    – mczarnek
    Commented Jun 25, 2014 at 21:34
  • $\begingroup$ @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. $\;\;\;\;\;\;\;$ $\endgroup$
    – user991
    Commented Jun 26, 2014 at 1:16
  • $\begingroup$ Yes, I need to from a signature, be able to say that account A,B,C,... verify that this information is correct. $\endgroup$
    – mczarnek
    Commented Jun 26, 2014 at 15:41
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – mczarnek
    Commented Jun 25, 2014 at 15:35

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.