Cryptology ePrint Archive: Report 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.
Category / Keywords: implementation / non-prime order elliptic curves, power residue symbol, subgroup membership testing, Tate pairing
Date: received 11 Jan 2022, last revised 9 Apr 2022
Contact author: dimitri koshelev at gmail com
Available format(s): PDF | BibTeX Citation
Version: 20220409:092501 (All versions of this report)
Short URL: ia.cr/2022/037
[ Cryptology ePrint archive ]