The BLS signature scheme [1] promised $b$-bit security for signature with a $2b$-bit appendix, under classical hypothesis leaving aside the possibility of Quantum Computers usable for cryptanalysis. Hovav Shacham's 2005 thesis proposed to use Barreto-Naehrig curves to achieve security comparable to RSA-1024 ($b\approx80$-bit security) with a $2b=160$-bit appendix.

However, per this summary of 2016 attacks, BLS signature using BN curves turned out to require larger appendix; like perhaps $8b/3$-bit appendix for $b$-bit security with $b\approx128$ (with Barreto? and Menezes-Palash-Singh considering $3b$-bit for something conservative).

Is BLS signature still conjectured to achieve $b$-bit security for $2b$-bit appendix using some concrete construction, and which? If not, what comes closest?

If that's not too much a different question, what would be a concrete parametrization for $b\approx128$-bit security?

[1] : Dan Boneh, Ben Lynn, Hovav Shacham, Short Signatures from the Weil Pairing, in Journal of Cryptology, 2004, originally in proceedings of Asiacrypt 2001.

  • 1
    $\begingroup$ According to my reading of BLS, the way to do this would be to increase the "security multiplier" beyond 6. I'm not competely sure but I think the multiplier is half the embedding degree (BN curves have $d = 12$), in which case eprint 2011/465 might be your answer as it suggests curves with $d = 24$. $\endgroup$ – Bristol Apr 27 '18 at 9:44

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.