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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. INDOCRYPT 2017
Keywords
KSS-16 curveOptimal-Ate pairingsparse multiplication
Contact author(s)
khandaker @ s okayama-u ac jp
History
2017-12-06: received
Short URL
https://ia.cr/2017/1174
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/1174,
      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{https://eprint.iacr.org/2017/1174}},
      url = {https://eprint.iacr.org/2017/1174}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.