Paper 2017/1174

Efficient Optimal Ate Pairing at 128-bit Security Level

Md. Al-Amin Khandaker, Yuki Nanjo, Loubna Ghammam, Sylvain Duquesne, Yasuyuki Nogami, and Yuta Kodera


Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and Kachisa-Schaefer-Scott (KSS-16) [19] curves at 128-bit security level (twist and sub-group attack secure). They have also concluded that in the context of Optimal-Ate pairing with their suggested parameters, BLS-12 and KSS-16 curves are more efficient choices than BN curves. Therefore, this paper selects the atypical and less studied pairing-friendly curve in literature, i.e., KSS-16 which offers quartic twist, while BN and BLS-12 curves have sextic twist. In this paper, the authors optimize Miller's algorithm of Optimal-Ate pairing for the KSS-16 curve by deriving efficient sparse multiplication and implement them. Furthermore, this paper concentrates on the Miller's algorithm to experimentally verify Barbulescu et al.'s estimation. The result shows that Miller's algorithm time with the derived pseudo 8-sparse multiplication is most efficient for KSS-16 than other two curves. Therefore, this paper defends Barbulescu and Duquesne's conclusion for 128-bit security.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. INDOCRYPT 2017
KSS-16 curveOptimal-Ate pairingsparse multiplication
Contact author(s)
khandaker @ s okayama-u ac jp
2017-12-06: received
Short URL
Creative Commons Attribution


      author = {Md.  Al-Amin Khandaker and Yuki Nanjo and Loubna Ghammam and Sylvain Duquesne and Yasuyuki Nogami and Yuta Kodera},
      title = {Efficient Optimal Ate Pairing at 128-bit Security Level},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1174},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.