To reduce bandwidth in elliptic curve cryptography one can transmit only $x$-coordinates of points (or $x$-coordinates together with an extra bit). For further computation using the points one can either recover the $y$-coordinates by taking square roots or one can use point multiplication formulae which use $x$-coordinates only. We consider how to efficiently use point compression in pairing-based cryptography. We give a method to compute compressed Weil pairings using $x$-coordinates only. We also show how to compute the compressed Tate and ate pairings using only one $y$-coordinate. Our methods are more efficient than taking square roots when the embedding degree is small. We implemented the algorithms in the case of embedding degree 2 curves over $\F_p$ where $p \equiv 3 \pmod{4}$ and found that our methods are $10-15\%$ faster than the analogous methods using square roots.

Efficiently computable homomorphisms allow elliptic curve point multiplication to be accelerated using the Gallant-Lambert-Vanstone (GLV) method. We extend results of Iijima, Matsuo, Chao and Tsujii which give such homomorphisms for a large class of elliptic curves by working over quadratic extensions and demonstrate that these results can be applied to the GLV method. Our implementation runs in between 0.70 and 0.84 the time of the previous best methods for elliptic curve point multiplication on curves without small class number complex multiplication. Further speedups are possible when using more special curves.

We analyse the efficiency of pairing computations on hyperelliptic curves given by a real model using a balanced divisor at infinity. Several optimisations are proposed and analysed. Genus two curves given by a real model arise when considering pairing friendly groups of order dividing $p^{2}-p+1$. We compare the performance of pairings on such groups in both elliptic and hyperelliptic versions. We conclude that pairings can be efficiently computable in real models of hyperelliptic curves.

For AES 128 security level there are several natural choices for pairing-friendly elliptic curves. In particular, as we will explain, one might choose curves with $k=9$ or curves with $k=12$. The case $k=9$ has not been studied in the literature, and so it is not clear how efficiently pairings can be computed in that case. In this paper, we present efficient methods for the $k=9$ case, including generation of elliptic curves with the shorter Miller loop, the denominator elimination and speed up of the final exponentiation. Then we compare the performance of these choices. From the analysis, we conclude that for pairing-based cryptography at the AES 128 security level, the Barreto-Naehrig curves are the most efficient choice, and the performance of the case $k=9$ is comparable to the Barreto-Naehrig curves.