[Cryptography] Fast bulk signature verification followed by fast non-interactive multisignature aggregation

[Jae Kwon]

Is there an efficient way to batch-verify signatures (e.g. some may be
incorrect) and then non-interactively aggregate the correct ones into a
multisignature (they are of the same message) such that all operations are
fast (e.g. don't require linear pairing operations)?

I've been looking around (BLS, EdDSA, Schnorr) but it appears that there's
a tradeoff... I'm not aware of any scheme that allows me to do both, as
stated in the question.

Since I'll be dealing with many signers on the order of tens of thousands,
the signatures must be relatively short on the order of less than 100
bytes.  And since they must be verified before aggregation and any number
of them may fail, I don't see how I can use pairing schemes.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140923/d79c95c5/attachment.html>