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

Takakazu Satoh

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 cryptosystem pairing inversion Tate pairing supersingular 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: 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}
}