Are there any hash-based signature schemes which would let two (or more) people sign the same message without increasing the size of the signature linearly?

For my purposes, it is fine if the scheme supports only one-time signatures.

I think PORS scheme can probably be adjusted to support a small (i.e. < 16) number of signers without growing the size of the signature linearly - but not sure if there are other schemes that can do that.

  • 1
    $\begingroup$ Do you count using generic multiparty computation protocols to implement the signing scheme? $\endgroup$ – Natanael Apr 10 '19 at 21:19
  • $\begingroup$ Probably not in this instance. $\endgroup$ – irakliy Apr 10 '19 at 22:38
  • $\begingroup$ for many schemes (especially a simple one like lamport) I believe you simply can split the seed / pre-image commitments, but then you reduce the security margin against malicious signers. $\endgroup$ – Natanael Apr 10 '19 at 22:52
  • $\begingroup$ That was kind of my thinking for PORS. For example, in case of 2 signers, you can probably get away with 1.5x size of a single signature if you can tolerate 100-bit security against malicious signer. $\endgroup$ – irakliy Apr 10 '19 at 23:00

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.