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
    Commented Apr 10, 2019 at 21:19
  • $\begingroup$ Probably not in this instance. $\endgroup$
    – irakliy
    Commented Apr 10, 2019 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
    Commented Apr 10, 2019 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
    Commented Apr 10, 2019 at 23:00


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.