Programming ECC

If $P$ lies in the ground field and the embedding degree $k$ is at least 2, then $$e(P,Q)=f_P(Q{)}^{(q^k-1)/r}$$ where $f_P$ is the function with divisor $r(P)-r(O)$.

Proof: Choose any point $R\in E({𝔽}_q)$ that is one of $O,-P,Q,-Q,Q-P$ and consider the function $f_P^{\prime }$ that satisfies $(f_P^{\prime })=r(P+R)-r(R)$, so that the Tate pairing is $$f_P^{\prime }((Q)-(O){)}^{(q^k-1)/r}$$ We have $f^{\prime }(O)\in {𝔽}_q^{*}$ since it does not have a zero or pole at $O$. Hence $f^{\prime }(O{)}^{(q^k-1)/r}=1$ by Fermat's Little Theorem (we know $q-1$ must divide $(q^k-1)/r$) so the pairing can be computed using $$e(P,Q)=f_P^{\prime }(Q{)}^{(q^k-1)/r}.$$

Let $g_P,g_R$ be equations for vertical lines through $P,R$ respectively. Let $h$ be the equation of the line through $P+R$ and $-R$ (and hence $-P$). Then $$(f_P^{\prime }{g}_R^r{g}_P^r/h^r)=r(P)-r(O)=(f_P)$$ By choice of $R$, $g_R(Q),g_P(Q),h(Q)$ are nonzero and finite, and as they are ultimately exponentiated by $q^k-1$, we have $f_P^{\prime }(Q)=f_P(Q)$ Hence $$e(P,Q)=f_P(Q{)}^{(q^k-1)/r}.$$ $\blacksquare$

Using Twist Curves

We use the same notation as before. Assume $k$ is even. Let $d=k/2$. Let $E^{\prime }$ be the twist of the curve $E({𝔽}_{q^d})$, so that if $v$ is a quadratic nonresidue in ${𝔽}_{q^d}$ and $E$ is given by $y^2=x^3+ax+b$ then $E^{\prime }$ is given by $y^2=x^3+v^{2}ax+v^{3}b$ (see notes on MNT curves). (We have ${𝔽}_{q^k}={𝔽}_{q^d}[\sqrt{v}]$.) Then the map $\Psi :E^{\prime }\to E({𝔽}_{q^k})$ given by $$\Psi (x,y)=(v^{-1}x,v^{-3/2}y)$$ is a homomorphism.

Now let $P$ be a point of order $r$ in $E({𝔽}_q)$ and $Q^{\prime }$ be any point in $E^{\prime }({𝔽}_{q^d})$. Setting $G=⟨P⟩$, $G^{\prime }=⟨\{\Psi (Q^{\prime })\}⟩$, where $\{Q\}$ denotes the coset containing $Q$, $f$ to be the Tate pairing, and $G_1$ to the subgroup of ${𝔽}_{q^k}$ of order $r$ yields a pairing suitable for cryptography.

Most operations occur in the fields ${𝔽}_q$ and ${𝔽}_{q^d}$. We only apply the map $\Psi$ and perform operations in ${𝔽}_{q^k}$ when a pairing is required.

The above map $\Psi$ is precisely the map $\varphi$ that was mentioned in the the first example on the page defining the pairing. We have essentially described a way for all pairing-based cryptosystems (that use an even embedding degree) to benefit from twist maps.

Note we have a dilemma for the second example on the page mentioned above. The twist of $y^2=x^3+1$ is $y^2=x^3-1$ (if we have chosen a field where $-1$ is a quadratic nonresidue). If the inputs to the pairing come from the same group, we cannot use twist curves. Although most operations still are performed in the base field, we cannot use the denominator elimination optimization described below. The alternative is to use the twist curve for the second input group, but now the inputs to the pairing come from different groups.

Denominator Elimination

To compute a Tate pairing, a quotient is iteratively calculated (Miller's algorithm) and then raised to power of $(q^k-1)/r$, the Tate exponent. Each factor of the denominator is the equation of a vertical line evaluated at a particular point, i.e. the equation $X-a$ evaluated at some point $(x,y)$, which gives the factor $(x-a)$.

Because of the way we have selected our groups, $x\in {𝔽}_{q^d}$ (note that the map $\Psi$ leaves the $x$-coordinate of its input in the same field), and $a\in {𝔽}_q$ hence $(x-a)\in {𝔽}_{q^d}$.

Any element $a\in {𝔽}_{q^d}$ satisfies $a^{q^d-1}$. Observe $q^d-1$ divides $(q^k-1)/r$, the Tate exponent, because $r$ cannot divide $q^d-1$ (otherwise $d$ would be the embedding degree, not $k$). Thus each factor $(x-a)$ raised to the Tate exponent is $1$, so it can be left out of the quotient. Hence there is no need to compute the denominator at any time in Miller's algorithm, which we rewrite below.

• set $f\leftarrow 1$ and $V\leftarrow P$
• for $i\leftarrow t-1$ to 0 do
  • set $f\leftarrow f^2{g}_{V,V}(Q)$ and $V\leftarrow 2V$
  • if $l_i=1$ then
    • set $f\leftarrow f{g}_{V,P}(Q)$ and $V\leftarrow V+P$
  • end
• end

For odd $r$, the calculation in last iteration is $$f\leftarrow f{g}_{(r-1)P,P}(Q).$$ Since $r-1P=-P$, $g$ is simply the vertical line at $P$ which by denominator elimination can be ignored. Hence $f_r=f_{r-1}$.