Cryptology ePrint Archive: Report 2016/472

Adequate Elliptic Curve for Computing the Product of n Pairings

Loubna Ghammam and Emmanuel Fouotsa

Abstract: Many pairing-based protocols require the computation of the product and/or of a quotient of n pairings where n > 1 is a natural integer. Zhang et al.[1] recently showed that the Kachisa-Schafer and Scott family of elliptic curves with embedding degree 16 denoted KSS16 at the 192-bit security level is suitable for such protocols comparatively to the Baretto- Lynn and Scott family of elliptic curves of embedding degree 12 (BLS12). In this work, we provide important corrections and improvements to their work based on the computation of the optimal Ate pairing. We focus on the computation of the nal exponentiation which represent an important part of the overall computation of this pairing. Our results improve by 864 multiplications in Fp the computations of Zhang et al.[1]. We prove that for computing the product or the quotient of 2 pairings, BLS12 curves are the best solution. In other cases, specially when n > 2 as mentioned in [1], KSS16 curves are recommended for computing product of n pairings. Furthermore, we prove that the curve presented by Zhang et al.[1] is not resistant against small subgroup attacks. We provide an example of KSS16 curve protected against such attacks.

Category / Keywords: foundations / BN curves, KSS16 curves, BLS curves, optimal Ate pair- ing, product of n pairings, subgroup attacks.

Date: received 17 May 2016

Contact author: ghammam loubna at yahoo fr

Available format(s): PDF | BibTeX Citation

Version: 20160517:151719 (All versions of this report)

Short URL: ia.cr/2016/472

Discussion forum: Show discussion | Start new discussion