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

Contact author: dimitri koshelev at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20220114:072630 (All versions of this report)

Short URL: ia.cr/2022/037