A note on implementing subgroup membership using the Tate pairing

Oct 6, 2025 3 min read

The paper “Subgroup membership testing on elliptic curves via the Tate pairing” by Dmitrii Koshelev (https://eprint.iacr.org/2022/037.pdf) is a cute result. Let $E/F_p$ be an elliptic curve of order $N = c\cdot r$, with prime integer $r$. To check that a point $P \in E$ is of order $r$, the naive method is to check that $[r]P = \mathcal{O}$. The paper shows that, given the group structure $E \cong Z_{e_1} \bigoplus Z_{e_2 \cdot r}$ and $e_2 \mid p-1$ ($c$ being $e_1\cdot e_2$), it is sufficient to check that the Tate pairings:

$$ f_{e_1,P_1}(P)^{(p-1)/e_1} = 1 \quad \text{and}\quad f_{e_2,P_2}(P)^{(p-1)/e_2} = 1 $$

where $P_1$ and $P_2$ are points on $E$ of orders $e_1$ and $e_2$ respectively.

$E$ is not necessarily pairing-friendly. Pairing-friendliness just means that the embedding degree $k$ is small enough to have fast arithmetic and big enough to have good security (e.g. $k=12$ for BLS12 and BN curves). Here $k=1$ and we only care about performance. To compute these pairings, we need to compute:

  1. the Miller functions $f_{e_i,P_i}$
  2. the final exponentiations by $(p-1)/e_i$

The whole idea of the paper is that when $e_i$ are small, these two steps become very efficient to implement.

Step 2

Let us start with step 2. Given $f\in F_p$, checking that $f^{(p-1)/e_i} =_? 1$ is equivalent to checking if $f$ is an $e_i$-th residue in $F_p$, i.e. $\exists z \in F_p$ s.t. $z^{e_i} = f \pmod p$. This is known as Euler criterion. For small $e_i$, this can be performed more efficiently than exponentiation, by using Euclidean algorithms. The power residue symbol satisfy similar relations to the GCD and hence one can adapt GCD algorithms to compute power residue symbols. For $e_i = 2$, this is known as the Legendre symbol and can be computed efficiently using the binary GCD algorithm (see Pornin’s algorithm and gnark-crypto implementation by Arya). For bigger $e_i \leq 16$, there are similar algorithms — although less “CPU-friendly” than the binary-GCD. However, one can always resolve to exponentiations.

Step 1

Computing Miller functions is done through Miller loops. For small $e_i$, we can explicitly give the formulas. For example when $e_i=2$, the paper states that $f_{e_i,P_i} = X - X_{P_i}$ which is true when the curve is given in short Weierstrass form $E_{sw}: Y^2=X^3+AX+B$. When $e_i=1$, $f_i=1$ trivially. When $e_i=2^m$, the paper gives the formula in page 5.

Discussion

I believe that the result is significantly performant only when $e_1=e_2=2$, in which case we can compute the Legendre symbol efficiently using the binary-GCD algorithm. For other cases it is still moderately fast using exponentiations, or someone has to implement efficient Euclidean-type higher power residue symbols.

Now let us focus on the case $e_1=e_2=2$. This happens for the curve Bandersnatch used in Verkle trie. It is mostly efficient when given in twisted Edwards form $E_{ed}: ax^2+y^2=1+dx^2y^2$. So to implement this test with input points $(x,y)\in E_{ed}$, we need to map $(x,y)$ to $(X,Y) \in E_{sw}$. The formula is:

$$ X = (\frac{a-d}{4})\cdot(\frac{1+y}{1-y}) + \frac{a+d}{6} $$

and we don’t need the $Y$ coordinate.

To avoid inverses we use the fact that $(\frac{1/x}{p})2 = (\frac{x}{p})2$. Thus, $f{2,P_i} = X - X{P_i}$ becomes:

$$ 12(a-d)^2(1-y)[(5a - d - 12X_{P_i}) + (a - 5d + 12X_{P_i})y] $$

or equivalently

$$ t_2 (1-y)(t_1 + t_0y) $$

with $t_2=12(a-d)^2$, $t_1=5a - d - 12X_{P_i}$ and $t_0=a - 5d + 12X_{P_i}$ some pre-computed constants.

For Bandersnatch implementers, they just need to take this last formula with:

  • $X_{P_1} = \texttt{0x23e93c143a3aa62dfef158aabe40ed250530ac9369509c984891a87e04178ed3}$
  • $X_{P_2} = \texttt{0x5de00fbdcf0964d2188e44aec311d927af0f7e94e94fca97c891a87d84178ed1}$

which leads, for the first point, to:

  • $t_0=1$
  • $t_1=1$
  • $t_2=\texttt{0x384d1c153c878eea316b96e5c340cf6abd025b636bd74122926c66eb6fa86d15}$

and, for the second, to:

  • $t_0=\texttt{0x636b1e56f54c03e873dd6068f2f238776f43b4a3d72a357835d2fc15ba90cdea}$
  • $t_1=\texttt{0x108288fc3451795fbf5c779f16af9f8de479ef5f28d42686ca2d03e9456f321d}$
  • $t_2=\texttt{0x34f9acec8bf92f766108eca94020963ae3496e2743876768b74534c34ef9473e}$

A full implementation in gnark-crypto can be found here: https://github.com/Consensys/gnark-crypto/pull/708