This study reports on an implementation of cryptographic pairings in a general purpose computer algebra system. For security levels equivalent to the different AES flavours, we exhibit suitable curves in parametric families and show that optimal ate
and twisted ate pairings exist and can be efficiently evaluated. We provide a correct description of Millers algorithm for signed binary expansions such as the NAF and extend a recent variant due to Boxall et al. to addition-subtraction chains. We analyse and compare several algorithms proposed in the literature for the final exponentiation. Finally, we ive recommendations on which curve and pairing to choose at each security level.
We determine the conditions under which singular values of multiple $eta$-quotients of square-free level, not necessarily prime to~6, yield class invariants, that is, algebraic numbers in ring class fields of imaginary-quadratic number fields. We sho
w that the singular values lie in subfields of the ring class fields of index $2^{k - 1}$ when $k geq 2$ primes dividing the level are ramified in the imaginary-quadratic field, which leads to faster computations of elliptic curves with prescribed complex multiplication. The result is generalised to singular values of modular functions on $X_0^+ (p)$ for $p$ prime and ramified.
We give an elementary and self-contained introduction to pairings on elliptic curves over finite fields. For the first time in the literature, the three different definitions of the Weil pairing are stated correctly and proved to be equivalent using
Weil reciprocity. Pairings with shorter loops, such as the ate, ate$_i$, R-ate and optimal pairings, together with their twisted variants, are presented with proofs of their bilinearity and non-degeneracy. Finally, we review different types of pairings in a cryptographic context. This article can be seen as an update chapter to A. Enge, Elliptic Curves and Their Applications to Cryptography - An Introduction, Kluwer Academic Publishers 1999.
A generalised Weber function is given by $w_N(z) = eta(z/N)/eta(z)$, where $eta(z)$ is the Dedekind function and $N$ is any integer; the original function corresponds to $N=2$. We classify the cases where some power $w_N^e$ evaluated at some quadrati
c integer generates the ring class field associated to an order of an imaginary quadratic field. We compare the heights of our invariants by giving a general formula for the degree of the modular equation relating $w_N(z)$ and $j(z)$. Our ultimate goal is the use of these invariants in constructing reductions of elliptic curves over finite fields suitable for cryptographic use.
We analyse and compare the complexity of several algorithms for computing modular polynomials. We show that an algorithm relying on floating point evaluation of modular functions and on interpolation, which has received little attention in the litera
ture, has a complexity that is essentially (up to logarithmic factors) linear in the size of the computed polynomials. In particular, it obtains the classical modular polynomials $Phi_ell$ of prime level $ell$ in time O (ell^3 log^4 ell log log ell). Besides treating modular polynomials for $Gamma^0 (ell)$, which are an important ingredient in many algorithms dealing with isogenies of elliptic curves, the algorithm is easily adapted to more general situations. Composite levels are handled just as easily as prime levels, as well as polynomials between a modular function and its transform of prime level, such as the Schlafli polynomials and their generalisations. Our distributed implementation of the algorithm confirms the theoretical analysis by computing modular equations of record level around 10000 in less than two weeks on ten processors.
