0
$\begingroup$

Let $E(\mathbb F_{q^k})$ be an elliptic curve on finite field $\mathbb F_{q^k}$, where $\mathbb F_{q^k}$ is an extension of $\mathbb F_q$ with $k>1$. Let $e: G_1 \times G_2 \rightarrow G_t$ be a bilinear pairing, and $G_1$, $G_2$ are some subgroup of $E(\mathbb F_{q^k})$ of order $r$, where $r| \# E(\mathbb F_q)$ and $r^2 | \# E(\mathbb F_{q^k})$, and $G_t$ is subgroup of order of $\mathbb F^*_{q^k}$.

Is it possible to modify (Weil or Tate) pairing such that the order of $G_t$ be $r^2$? In other word, is it possible to map (with keeping bilinearity property) two $r$-torsion points to a $r^2$-root of unity?

$\endgroup$
5
$\begingroup$

No, it is not possible.

By the definition of bilinearity, we have $e( kG, H ) = k \cdot e( G, H )$. If the order of $G$ is $r$ (that is, $rG = 0$, we have $e( rG, H ) = e( 0, H ) = r \cdot e(G, H)$. We know $e(0, H) = 0$ (as bilinear functions maps the identity to the identity), and hence we have $r \cdot e(G, H) = 0$; that is, the order of $e(G, H)$ must be either $r$, or some divisor of $r$.

$\endgroup$
  • $\begingroup$ A point of order $r$ is $r^2$-torsion. $\endgroup$ – fkraiem Jan 2 '17 at 6:57
  • $\begingroup$ @fkraiem: while this is true, it is misleading. An elliptic curve point $G$ is an $n$-torsion point iff $nG = 0$. Now, if $G$ is order $r$, then $rG = 0$, and so $r^2 G = r(rG) = 0$, and so $G$ is pedantically an $r^2$-torsion point, however it is also an $r$-torsion point. In any case, the question specifically asked "... that the order of $G_t$ be $r^2$" $\endgroup$ – poncho Jan 2 '17 at 15:28
  • 2
    $\begingroup$ Well the question also specifically asks that the result be "a $r^2$-torsion point", I guess this just shows that OP has no idea what he's talking about, but that was already evident from his previous questions... $\endgroup$ – fkraiem Jan 2 '17 at 15:45
  • 1
    $\begingroup$ If only we were in a place where we can help those out that don't understand what's going on :-) $\endgroup$ – CurveEnthusiast Jan 3 '17 at 13:01
0
$\begingroup$

We can simply obtain a pairing $G_1 \times G_2 \rightarrow G_t$, where the order of $G_1$ and $G_t$ is $r^2$, and the order of $G_2$ is $r$, just by using the Tate pairing.

Definition of Tate pairing is: $t_r: E(\mathbb F_{q^k})[r^2] \times E(\mathbb F_{q^k})/r^2E(\mathbb F_{q^k}) \rightarrow \mathbb F^*_{q^k}/(\mathbb F^*_{q^k})^{r^2}$

by exponentiation the result by $(q^k-1)/{r^2}$, elements of $\mathbb F^*_{q^k}/(\mathbb F^*_{q^k})^{r^2}$ will sends to exact $r^2$-roots of unity.

where $E( \mathbb F_{q^k})[r^2]$ is a group of $r^2$-tortion points, and $r^2E(\mathbb F_{q^k})$ is a coset of points in $E(\mathbb F_{q^k})$ defined by

$r^2E(\mathbb F_{q^k})=\{ [r^2]P : P \in E(\mathbb F_{q^k})\}$

Just by adding $r^2$-tortion points to the element of this coset we can obtain another $r^4-1$ cosets in which the order of elements of them is not equal, but the elements of these cosets is equivalent in $E(\mathbb F_{q^k})/rE(\mathbb F_{q^k})$.

The Idea is that we can choose a $r$-tortion point $Q$ from the equivalence cosets of $E(\mathbb F_{q^k})/rE(\mathbb F_{q^k})$. Then simply simulate a pairing $ e: G_1 \times G_2 \rightarrow G_t$, where the order of $G_1$ and $G_t$ is equal to $r^2$ and the order of $G_2$ is equal to $r$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.