Paper 2019/385
Miller Inversion is Easy for the Reduced Tate Pairing of Embedding Degree Greater than one
Abstract
We present algorithms for Miller inversion for the reduced Tate pairing with embedding degree k>1. Let q be a number of elements of field of definition of an elliptic curve. For even k, our algorithm run deterministically with O((k log q)^3) bit operations. For odd k, out algorithm run probabilistically with O(k^6 (log q)^3) bit operations in average.
Note: Major revision(Dec. 2024): it turned out that our key idea is applicable to any embedding degree greater than one.
Minor revision(Jan. 2025): some changes including (but not limited to)
Section 1, Footnote[1]: "square computations" -> "square root computations"
Section 5:
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- elliptic curve cryptosystempairing inversionTate pairing
- Contact author(s)
- satoh df603 @ gmail com
- History
- 2025-01-30: last of 4 revisions
- 2019-04-16: received
- See all versions
- Short URL
- https://ia.cr/2019/385
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/385,
author = {Takakazu Satoh},
title = {Miller Inversion is Easy for the Reduced Tate Pairing of Embedding Degree Greater than one},
howpublished = {Cryptology {ePrint} Archive, Paper 2019/385},
year = {2019},
url = {https://eprint.iacr.org/2019/385}
}
