Special TNFS-Secure Pairings on Ordinary Genus 2 Hyperelliptic Curves

Pairings on genus 2 hyperelliptic curves are believed to be far less efficient compared to elliptic curve ones. The main reason is the structure of their Jacobian which leads to slower doubling and addition operations. However, genus 2 curves have attractive features that, when properly exploited, can counter the computationally expensive Jacobian operations. One of these features is that they admit twists of higher degrees than elliptic curves, allowing to map Jacobian operations to smaller extension fields. In this paper, we apply generalizations of elliptic curve constructions based on the Cocks–Pinch and Brezing–Weng methods to derive instances of efficient genus 2 pairings, focusing on curves with embedding degrees 8, 16, and 24 that admit degree 8 twists. We present a theoretical comparison with their elliptic curve counterparts, based on the number of prime field multiplications. Our examples target 128- and 192-bit security, considering the progress of STNFS attacks on the DLP in extension fields of composite degree. We propose the first STNFS-secure genus 2 pairings at 128-bit security, as well as more promising candidates for 192-bit security compared to previous works. Finally, we present a proof-of-concept implementation in SageMath that can serve as a baseline for future benchmarks and efficient implementations.