[BLS-wg] New algorithm for aggregating BLS signatures

[Sean Bowe]

Thanks for posting, looks cool!

I noticed that the batch verification technique proposed in Dan's note
encourages you to perform the random exponentiations on the pairing
products, but in practice it's probably more efficient for you to
apply them as scalar multiplications to the aggregated public keys
prior to the pairings. That is,

e(g_1, sigma) = e(apk_1 * rho_1, H_0(m_1)) *** e(apk_b * rho_b, H_0(m_b))

Or, you could also apply it to the G2 element by combining it with the
G2 cofactor multiplication you have to do anyway as a result of
hashing to the group. (The G2 cofactor is quite large, so it may pay
off if you're doing windowed exponentiation.)

Sean

On Sat, Mar 24, 2018 at 9:40 PM, Bram Cohen via bls-wg
<bls-wg at lists.z.cash.foundation> wrote:
> Dan Boneh came up with a new approach for aggregating BLS signatures which
> allows keys to be aggregated as well as signatures. We're going to be
> implementing this:
>
> https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html