Paper 2008/019

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.

Metadata
Available format(s)
PDF PS
Publication info
Published elsewhere. Unknown where it was published
Keywords
elliptic curvespairingspoint compression.
Contact author(s)
linxibin @ mail2 sysu edu cn
History
2008-01-22: received
Short URL
https://ia.cr/2008/019
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/019,
      author = {Steven D.  Galbraith and Xibin Lin},
      title = {Computing Pairings Using x-Coordinates Only},
      howpublished = {Cryptology ePrint Archive, Paper 2008/019},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/019}},
      url = {https://eprint.iacr.org/2008/019}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.