4
$\begingroup$

I'm new to cryptography and I am working on R-ate Pairings on a BN Curve:

$y^2=x^3+b$ with $b$=5

with its M-type twist:

$y^2=x^3+b\beta$, and $\beta^2 = -2$.

The base finite field characteristic is P

Now, according to the paper, there is a Frobenius endomorphism

$\pi^p:(x,y)\longmapsto(x^p,y^p)$

So, for a given point:

$Q(x,y)$ on $y^2=x^3+5\beta$,

Its Frobenius map $Q`(x^p,y^p)$ should also have $(y^p)^2=(x^p)^3+5\beta$.

My calculation shows the results is $(y^p)^2=(x^p)^3-5\beta$

enter image description here

So where am I going wrong?
Thanks for your help.

Reference of the paper (in Chinese): enter image description here

Translation of algorithm image:

$\pi_q$ as Frobenius endomorphism, $\pi_q: E \rightarrow E$, $\pi_q(x,y) = (x^q,y^q)$

$\pi_{q^2}: E \rightarrow E$, $\pi_{q^2}(x,y) = (x^{q^2},y^{q^2})$

R-ate pairing ("pair's calculation"):

Input: $P \in \mathbb{E(\mathbb{F_p}})[r], Q \in \mathbb{E'(\mathbb{F_{p^2}})}[r]$, $a = 6t+2$

Output: $R_a(Q,P)$

a) Let $a = \sum_{i=0}^{L-1}a_i 2^i, a_{L-1}=1$

b) Set $T=Q, f=1$

c) With $i$ from $L-2$ down until 0, execute:

  • c.1) calculate $f = f^2 \cdot g_{T,T}(P), T=[2]T$

  • c.2) if $a_i = 1$, compute $f = f\cdot g_{T,Q}(P), T = T+Q$

d) Compute $Q_1 = \pi_q(Q), Q_2=\pi_{q^2}(Q)$

e) compute $f = f\cdot g_{T,Q_1}(P), T = T+Q_1$

f) compute $f = f\cdot g_{T,-Q_2}(P), T = T-Q_2$

g) compute $f = f^{(q^{12}-1)/r}$;

h) output $f$.

Edit:

In step d) $Q_1$ is a point after applying the Frobenius map on $Q$. Then in step e) there is $T=T+Q_1$ Confusion: According my calculation above, $Q_1$ should not be on the same curve where $T$ is. Is it correct to calculate $T=T+Q_1$? Or is my calculation wrong?

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Dec 13 '17 at 7:46
1
$\begingroup$

In step d) $Q_1$ is a point after applying the Frobenius map on $Q$. Then in step e) there is $T=T+Q_1$. Confusion: According to my calculation above, $Q_1$ should not be on the same curve where $T$ is. Is it correct to calculate $T=T+Q_1$? Or is my calculation wrong?

It looks like CurveEnthusiast verified your calculation in comments, so this is strictly for your final question:

The Frobenius map $\pi$ is a mapping from $\mathbb{E}′(\mathbb{F}_q)$ to itself. $T$ is a point on this curve, and since $\pi:\mathbb{E}′(\mathbb{F}_q) \rightarrow \mathbb{E}′(\mathbb{F}_q)$, $Q_1$ is also on the curve and so the sum is defined.

$\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.