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


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.

  • $\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 Aug 24 '17 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 Aug 24 '17 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 Aug 24 '17 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 Aug 24 '17 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 Aug 25 '17 at 11:21

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.