International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Computing Pairings Using x-Coordinates Only

Authors:
Steven D. Galbraith
Xibin Lin
Download:
URL: http://eprint.iacr.org/2008/019
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2008-17696,
  title={Computing Pairings Using x-Coordinates Only},
  booktitle={IACR Eprint archive},
  keywords={elliptic curves, pairings, point compression.},
  url={http://eprint.iacr.org/2008/019},
  note={ linxibin@mail2.sysu.edu.cn 13899 received 14 Jan 2008, last revised 21 Jan 2008},
  author={Steven D. Galbraith and Xibin Lin},
  year=2008
}