Generating pairing-friendly elliptic curve parameters using sparse families (Q1640702)

Let \(E/\mathbb{F}_q\) be an ordinary elliptic curve with Frobenius trace \(t = q+1 - \# E(\mathbb{F}_q)\) such that \(\# E(\mathbb{F}_q) = hr\) for some large prime \(r\). \(E\) is said to be pairing friendly if \(\log q \approx \log r\) (measured by the \(\rho\) value \(\rho = \log q / \log r\)) and there exists a bilinear pairing \(\hat{e}: G_1 \times G_2 \mapsto G_T\) where \(G_1, G_2 \leq E(\mathbb{F}_q)\), \(G_T \leq \mathbb{F}^\ast_{q^k}\) and \(\# G_1 = \# G_2 = \# G_T = r\) such that the discrete logarithm problem in all three groups is believed to be hard. The integer \(k\), called the embedding degree, should also be sufficiently small that arithmetic in \(G_T\) is efficient. One method to construct pairing-friendly curves involves parameterizing the values of \(q\), \(t\), \(r\) via polynomial families, triples of polynomials \((q(x),t(x),r(x))\) in \(\mathbb{Q}[x].\) Sparse polynomial families are those satisfying \(4 q(x) - t(x)^2 = g(x) y(x)^2\) with \(g(x)\) quadratic with positive leading coefficient; these are attractive because the resulting curves have large CM discriminants, providing some resistance against certain attacks on the discrete logarithm problem. In this paper, the authors propose a novel method for constructing sparse polynomial families that combines methods of \textit{H.-S. Lee} and \textit{C.-M. Park} [Lect. Notes Comput. Sci. 5671, 66--77 (2009; Zbl 1250.14017)] and \textit{R. Dryło} [ibid. 7107, 310--319 (2011; Zbl 1291.94075)]. The construction is used to produce new sparse families with \(\rho \leq 2\) and the same embedding degrees as those appearing in the literature, as well as first examples for several other embedding degrees. These families were used to produce numerical examples of pairing-friendly curves with parameters of cryptographically-relevant size, considering recent progress on the tower number field sieve algorithm for solving the discrete logarithm problem in \(G_T\).