# Usage of twists at pairing-based cryptography

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.
• 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.. Aug 24 '17 at 11:07
• That seems odd, the largest twist possible is sextic. This paper, for example, states that KSS16 works with $E'(\mathbb{F}_{p^4})$. Aug 24 '17 at 11:23
• 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. Aug 24 '17 at 12:41
• 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$. Aug 25 '17 at 11:21