Security of BLS batch verification

\kappa-bits will give you 2^{-\kappa} probability of accepting an invalid batch of signatures.

What k you use is an application-dependent choice. Like @vbuterin said in the article you cited, \kappa=64 may be enough in applications where the attacker doesn’t get too many attempts.

Clearly, after \approx 2^{64} attempts, an attacker will succeed. So applications where signatures are flying left & right should likely not use such a low \kappa.

My sense is a conservative one. Use \ge 128-bit security! Always. \kappa=128. Why? It might make up for problems that are hard to foresee, whether introduced by you or not. (e.g., what if your RNG has less entropy than you believed, and those 64-bit “uniform” scalars are not that uniform after all).

PS: Hard to tell whether the “In Vitalik we all trust so sure that number is correct” is a tongue-in-cheek comment. Still, all hats being off to Vitalik, it would be preferable for folks to also do their own analysis of what makes sense in their application setting. (This, of course, can be difficult.)

1 Like