Paper 2022/037

Subgroup membership testing on elliptic curves via the Tate pairing

Dmitrii Koshelev
Abstract

This note explains how to guarantee the membership of a point in the prime-order subgroup of an elliptic curve (over a finite field) satisfying some moderate conditions. For this purpose, we apply the Tate pairing on the curve, however it is not required to be pairing-friendly. Whenever the cofactor is small, the new subgroup test is much more efficient than other known ones, because it needs to compute at most two $n$-th power residue symbols (with small $n$) in the basic field. More precisely, the running time of the test is (sub-)quadratic in the bit length of the field size, which is comparable with the Decaf-style technique. The test is relevant, e.g., for the zk-SNARK friendly curves Bandersnatch and Jubjub proposed by the Ethereum and Zcash research teams respectively.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
non-prime-order elliptic curvespower residue symbolsubgroup membership testingTate pairing
Contact author(s)
dimitri koshelev @ gmail com
History
2023-02-05: last of 6 revisions
2022-01-14: received
See all versions
Short URL
https://ia.cr/2022/037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/037,
      author = {Dmitrii Koshelev},
      title = {Subgroup membership testing on elliptic curves via the Tate pairing},
      howpublished = {Cryptology ePrint Archive, Paper 2022/037},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/037}},
      url = {https://eprint.iacr.org/2022/037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.