**Computing Pairings Using x-Coordinates Only**

*Steven D. Galbraith and Xibin Lin*

**Abstract: **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.

**Category / Keywords: **elliptic curves, pairings, point compression.

**Date: **received 14 Jan 2008, last revised 21 Jan 2008

**Contact author: **linxibin at mail2 sysu edu cn

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Version: **20080122:040127 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]