### Miller Inversion is Easy for the Reduced Tate Pairing on Supersingular Curves of Embedding Degree Two and Three

Takakazu Satoh

##### Abstract

We present a simple algorithm for Miller inversion for the reduced Tate pairing on supersingular elliptic curve of trace zero defined over the finite fields with q elements. Our algorithm runs with O((log q)^3) bit operations.

Note: Major revision: our method is extended to the embedding degree three case. It turned out Akagi and Nogami[1] obtained similar results for some ordinary curves. The article is referred. Bug fix: Algorithm 4.1(2.1 in previous version), Step 6: check order of candidates of output to ensure correctness Fix several typos.

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
elliptic curve cryptosystempairing inversionTate pairingsupersingular curve
Contact author(s)
satoh df603 @ gmail com
History
2019-09-16: last of 2 revisions
See all versions
Short URL
https://ia.cr/2019/385

CC BY

BibTeX

@misc{cryptoeprint:2019/385,
author = {Takakazu Satoh},
title = {Miller Inversion is Easy for the Reduced Tate Pairing on Supersingular Curves of Embedding Degree Two and Three},
howpublished = {Cryptology ePrint Archive, Paper 2019/385},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/385}},
url = {https://eprint.iacr.org/2019/385}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.