Pairing on FourQ

Question

How would you define a pairing on the - so called - curve "Four$\mathbb Q$?

Since FourQ is a twisted Edwards curve, given by $E/\mathbb F_{q}:\ -x^2+y^2 = 1+dx^2y^2$, where $d\in\mathbb F_p(i), q=p^2, p=2^{127}-1$, we could check [1] and try to define such a pairing for values given by [2, section 2.1].

FourQ itself was frist presented in 2015 [2] and one can see the ongoing research in [3] and [4]. The provided lib contains all necessary group operations for a successful ECC and some tests on different devices. I'm targeting a 32-bit microcontroller (ARM Cortex-M4) where you can find a working lib in [4]. But I guess, there is no formulae for computing intersection or tangent lines. (Which might not be that difficult to define) They provide a full $\mathbb F_q$ and $EC$ arithmetic.

Summarizing the facts, given by [2], we get an embedding degree $k=(N-1)/2$, where N is a 246-bit prime, deviding the curve order. Therefore $N=(q+1-t_E)/(2^3\cdot7^2)$, where $t_e$ is the trace of Frobenius. [2, page 4] So we have the crypto subgroup $E(\mathbb F_q)[N]$ with embedding degree $k=(N-1)/2$. Therefore we have to define the Tate-Pairing, as suggested in [1, section 2.1], $T_N:\ E(\mathbb F_q)[N] \times E(\mathbb F_{q^k}(=\mathbb F_{p^{N-1}})) \to \mu_N$ with $(P,Q)\mapsto f_P(Q)^{(q^k-1)/N}$ computed by Miller's algorithm, where $\mu_N$ denotes the Nth-root of unity in $\mathbb F_{q^k}$.

So my question is: How do I define such a pairing? What kind of arithmetic do I need? I guess, that I don't need the whole $E(\mathbb F_{q^k})$ arithmetic, but to deside, if a randomly chosen point lies on that curve. I will need the whole $\mu_N$ multiplication and doubling arithmetics.

Does someone knows any currently released Tate-Pairings on twisted Edwards curves written in Java or C? Or any pre-print paper, that deal with FourQ and some kind of pairing? I do not want to invent something again, if it is allready done.

If someone can add some tags, to reach more people that could help, feel free to add those.

[1] http://dx.doi.org/10.1155/2013/136767

[2] http://eprint.iacr.org/2015/565

[3] https://www.microsoft.com/en-us/research/project/fourqlib/

[4] https://github.com/Microsoft/FourQlib

Answer 1

The facts you mention regarding the embedding degree show that FourQ is not a pairing-friendly curve, and hence you cannot compute a pairing on it efficiently. Indeed, the representation of group elements both in the source group on the “other side” and in the target group involve something like $2^{246}$ coefficients over $\mathbb{F}_q$, so you cannot even manipulate elements in those groups to begin with.

In most settings, the fact that FourQ is not pairing-friendly is actually a feature. But since it is a very special and isolated curve by design, there is no way of tweaking it somehow to make it pairing-friendly while retaining its other nice properties.

---

Replying to the more general question of recommending a "fast" curve for pairings: one should keep in mind that "fast" for pairings and "fast" for usual elliptic curve arithmetic are mostly unrelated properties. For example, you can find pairing-friendly Edwards curves, but because of the cofactor, this will not work with BN curves, so one would need to use a different pairing-friendly family, such as KSS, typically with a different embedding degree, so there's a somewhat complicated security trade-off.

Until recently, BN curves were believed to be the fastest you could do at the 128-bit security level. Due to recent improvements of discrete log algorithms on the target groups of pairings, the security of the traditional BN254 curve has been reduced, so people are in the process of reevaluating previous recommendations. This is still somewhat up in the air at this point.