Paper 2019/385

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.

Metadata
Available format(s)
PDF
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
2019-04-16: received
See all versions
Short URL
https://ia.cr/2019/385
License
Creative Commons Attribution
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.