TNFS resistant families of pairing-friendly elliptic curves (Q2333827)

In recent years there has been progress on index calculus algorithms for computing discrete logarithms in various classes of non-prime finite fields. These affect the security of cryptographic schemes involving pairings of elliptic curves \(E\) defined over a finite field \(\mathbb F_q\). Such a pairing maps a direct product of cyclic subgroups of \(E(\mathbb F_q)\) of prime order \(r\) into a multiplicative order \(r\) subgroup of the field \(\mathbb F_{q^k}\), and one requires the discrete logarithm in both kinds of subgroups to be infeasible. This paper considers the case of asymmetric pairings, which are defined on ordinary elliptic curves over a prime field \(\mathbb F_p\) that are constructed by the so-called Complex Multiplication (CM) method. In the literature there has been a considerable amount of work for constructing such pairings with moderate extension degree \(k\) of about 6 to 36 and a small ratio \(\rho := \log p / \log r\). In this way, the efficiency of computing the pairing and the hardness of the discrete logarithm problems can be balanced for various security levels (e.g., 128 bits) in an optimal way. However, the Tower Number Field Sieve (TNFS) has now weakened the security for discrete logarithms in finite fields \(\mathbb F_{p^k}\) with composite exponent \(k\). Therefore, in the present paper the common algorithms for generating pairing-friendly families of curves are adapted in order to account for this fact. For the security levels of 128 bits, 192 bits and 256 bits the authors present versions of the Brezing-Weng method for so-called complete families and Complete with Variable Discriminant (CVD) families. They suggest comprehensive tables for various extension degrees \(k\), both prime and composite. It is argued that given the current state-of-the-art, it is beneficial to also consider larger \(\rho\)-values (up to 2) in order to optimally balance the parameters.