Cryptology ePrint Archive: Report 2019/485

A taxonomy of pairings, their security, their complexity

Razvan Barbulescu and Nadia El Mrabet and Loubna Ghammam

Abstract: The Kim-Barbulescu attack against pairings made it necessary to increase the key sizes of the most popular families of pairings : BN, BLS-12, KSS-16, KSS-18 and BLS-24. The computation of new key sizes was a slow process because it was done in two waves : first a series of theoretical estimations, then a wave of precise estimations based on practical models. In this paper, we propose an up-to-date security evaluation for more then hundred pairing friendly elliptic curves. We evaluate the complexity of a complete pairing execution taking into account the Miller algorithm for different degree of twist and the Final exponentiation for the most promising curves. At 128 bits of security we find that the best pairings in the BD model are BLS-24 and BLS-12. The best pairings are not affected by the new polynomial selection method. At 192 bits of security, we find that the new champions are the less known BLS-24, KSS-16 and KSS-18. At 256 bits of security we conclude that the best pairing is BLS-27.

Category / Keywords: public-key cryptography / Discrete Logarithm Problem; Number Field Sieve; Elliptic Curves; Pairings

Date: received 12 May 2019, last revised 29 Sep 2020

Contact author: ghammam loubna at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200929:121755 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]