Constructing pairing-friendly hyperelliptic curves using Weil restriction (Q2430992)

A pairing-friendly curve is a curve over a finite field \(\mathbb{F}_q\) whose Jacobian has small embedding degree \(k = [\mathbb{F}_{q}(\zeta_r) ~|~ \mathbb{F}_{q}]\) with respect to a large subgroup of prime order \(r\). Such curves, particularly elliptic curves and, to a lesser extent, genus \(2\) hyperelliptic curves, have a variety of applications in public-key cryptosystems. Supersingular curves are pairing-friendly, but the possible embedding degrees are limited to at most \(12\) for genus \(\leq 2.\) Thus, methods for constructing ordinary curves with small embedding degree have been of particular interest. The goal is to find such curves for which the finite field size is small compared to the \(r,\) measured by the \(\rho\)-value. In this paper, the authors describe a new method for constructing pairing-friendly genus \(2\) hyperelliptic curves over finite fields \(\mathbb{F}_q\) whose Jacobians are ordinary and simple. The main idea is to use existing methods to construct an elliptic curve over \(\mathbb{F}_q\) that becomes pairing friendly over \(\mathbb{F}_q^d,\) and to use the Weil restriction of scalars to find a pairing friendly genus 2 curve over \(\mathbb{F}_q.\) This construction yields curves defined over smaller fields relative to the subgroup size than previous constructions, and hence smaller \(\rho\) values. Using constructions due to Cocks and Pinch [Identity-based cryptosystems based on the Weil pairing (unpublished manuscript) (2001)] and \textit{F. Brezing} and \textit{A. Weng} [``Elliptic curves suitable for pairing based cryptography'', Des. Codes Cryptography 37, No. 1, 133--141 (2005; Zbl 1100.14517)] yields curves with generically smaller \(\rho\) values than those obtained from other constructions (\(4\) as opposed to \(8\)), as well as a record value of about \(2.2\) (compared with \(4\)).