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 given approach is 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. In particular, we deal with two Legendre symbols for the curve Bandersnatch proposed by the Ethereum Foundation team. Due to recent improvements of Euclidean type constant-time algorithms for the Legendre symbol computation, the new subgroup check is almost free for that curve.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- 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