Paper 2022/037
Subgroup membership testing on elliptic curves via the Tate pairing
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
-
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}
}
