Are there any digital signature algorithms that can be used to produce signatures valid for multiple pieces of data?

For example: Pick a private key $k_{private}$, which has public key $k_{public}$. Produce one signature $S$ which is valid for $h_1, h_2, \dots , h_N$, which are hashes of messages $m_1, m_2, \dots , m_N$.

Looking for a solution where the signature size is constant, or at least growing slowly as the # of messages increases. There may also be millions of messages, and they would typically be added one at a time.

I think you could do it with merkle signatures. I'm especially interested in solutions using elliptic curves.

  • $\begingroup$ Every signature algorithm which uses hash functions (ECDSA, for example) produces signatures which are valid signatures for different messages. $\endgroup$ – Student20 Jul 25 '16 at 23:23
  • 1
    $\begingroup$ @Student20, but you could never find one :P I assume you're talking about the message space being larger than the hash space that the messages are mapped into. In order to use that, I'd have to break the irreversibility of a hash function, and if that can be done, then the scheme isn't secure because you could find infinitely many messages that are all valid for the same signature. I am looking to create signatures that are only valid for any one element in a defined, although appendable, set of elements. Each time you'd append, you'd produce a new signature that is valid for the N+1 elements. $\endgroup$ – morsecoder Jul 25 '16 at 23:55
  • 2
    $\begingroup$ Another obvious solution is to use "composite" signature which consists of signatures of messages $h_1, \ldots, h_N$. Then you just check whether any of these signatures is valid signature of some message $h$. $\endgroup$ – Student20 Jul 26 '16 at 0:17
  • 1
    $\begingroup$ This is pretty much the opposite of what signature algorithms are meant to do. It would make the signature repudiable. (Symmetric MAC algorithms quite often allow this. Signatures not so much.) $\endgroup$ – otus Jul 26 '16 at 5:08
  • 2
    $\begingroup$ I don't see why hash trees would not work here. Just sign the root of the hash tree. If a hash tree doesn't suffice, could you list additional requirements that you are looking for? $\endgroup$ – Maarten Bodewes Jul 26 '16 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.