2
$\begingroup$

First of all I would like to understand how twists are used in pairings. The 2nd step is, how to use them to improve the calculation speed?

Say $E'(\mathbb F_{p^2})$ is a twist of $E(\mathbb F_p)$.

I just thought about choosing $m_1,m_2\in (0,\lfloor \sqrt{\operatorname{ord}(E)} \rfloor)$ randomly, define $m=m_1+m_2\cdot \lambda$ and performing $mP=m_1P+ m_2\psi(P)$, where $P\in E$ and $\psi:\ E\to E'$. My main thought about this technique is, to reduce the size of the integers $m$ and performing two scalar multiplications in different groups, if this might be a speed-up. But then we should have $\psi(P)=\lambda P$ for any, maybe large $\lambda$. If this idea was already mentioned before, could someone link me a paper or any other source?

Feel free to edit this post, if necessary, and add tags. :)

Edit1: To make the explanation (maybe) a bit easier, consider $E:\ y^2=x^3+x$ and the twist $E':\ y^2=x^3+2^{1/4}x$ over $\mathbb F_p$ and $\mathbb F_{p^2}$ with the embedding degree $k=16$.

Edit2: If I remember well, we should consider a type-2 pairing, where $G_1\neq G_2$ and $\psi:\ G_1\to G_2$ is efficient, but $G_2\to G_1$ is not efficient. I guess this holds in our situation, since $\newcommand\F{\mathbb F}\F_{p^2}=\F_p[x]/(X^2-2)$ for $p\equiv \pm3\pmod 8$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

I'm not sure I understood your question, but... twists are used to improve performance. In your example, without twists, $G_2$ is $E(\mathbb{F}_{p^{16}})$. With a quartic twist, you can use $E'(\mathbb{F}_{p^{4}})$, which is much more efficient (the reason for this is that the homomorphism $\Psi$ maps the point coordinates to sparse elements of $\mathbb{F}_{p^{16}}$, i.e. with a lot of zero coefficients, which can be multiplied much faster by ignoring the internal multiplications by zero).

The splitting of the scalar $m$ into $m_1, m_2$ is known as "GLV method". While it is used to speed up point multiplications, as far as I know it can't be applied directly to the pairing computation. But it can be used for pairing-based schemes that use point multiplication along with the pairing computation.

Improve this answer
$\endgroup$
5
  • $\begingroup$ You understood my question. Actually I only read pairings defined as a mapping $E(\mathbb F_p)\times E(\mathbb F_{p^2}) \to \mu_r\subset \mathbb F_{p^{16}}$. Therefore I don't get it in which part, this improvement is added. In another paper about KSS16 curves, they defined the twist $E'(\mathbb F_{p^2})$ which would be an octic twist, but for such twists I cannot find anything. I hope you see, why I'm confused.. $\endgroup$
    – Shalec
    Commented Aug 24, 2017 at 11:07
  • $\begingroup$ That seems odd, the largest twist possible is sextic. This paper, for example, states that KSS16 works with $E'(\mathbb{F}_{p^4})$. $\endgroup$
    – Conrado
    Commented Aug 24, 2017 at 11:23
  • $\begingroup$ Take a look at [1] on page 13 section 6.3, please. Is this a typo? [1] eprint.iacr.org/2017/334.pdf $\endgroup$
    – Shalec
    Commented Aug 24, 2017 at 12:05
  • $\begingroup$ Ok, lets assume that they done a type (which would clear some other things, I cannot recognize). The only part, where $E'$ arithmetics could be used, is while the Miller-loop. But on which part? Lets consider your paper section 2.2. $\endgroup$
    – Shalec
    Commented Aug 24, 2017 at 12:41
  • $\begingroup$ Yep, seems like an typo in the paper, notice how they talk about $\mathbb{F}_{p^{12}}$ even though it isn't used in KSS16. In the Miller loop, $P$ is in $E'$, and $P$ is the input to the "line function" $\ell$. $\endgroup$
    – Conrado
    Commented Aug 25, 2017 at 11:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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