4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ In the first link, there are formulas provided for how to add points on a twisted Edwards curve, and equation (26) outlines the steps required to compute the $g_{P,Q}$ that Miller's algorithm needs to compute $f$, and then you can compute the Tate pairing as in equation (1). What questions do you have on the implementation? (I don't know about any libraries that do this.) $\endgroup$ – user47922 Jun 13 '17 at 11:58
  • $\begingroup$ I will convert those information in a git-project and writing some C-Stuff, that can be easily verified. I will add a link, if I'm done. I guess, that I will need help by converting information into code. I'll add some more question especially for those required steps to compute $g_{P,Q}$. But now I have to take my way to work :( $\endgroup$ – Shalec Jun 13 '17 at 13:21
  • $\begingroup$ You need both curves, defined over base and extension fields, to have subgroups of the same order for some small $k$. One should generate a curve for this condition to hold. $\endgroup$ – Vadym Fedyukovych Jun 13 '17 at 21:44
  • $\begingroup$ Oh well.. I just computed $k=36923497843531950071291768178790786942399037929900048730647048166798214771$. Its odd, so it is not compliant to that suggested calculation. $\endgroup$ – Shalec Jun 14 '17 at 16:21
12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Could you recommend any other fast curve, instead of FourQ and BN? Are Goldilocks nice to use? $\endgroup$ – Shalec Jun 14 '17 at 16:23
  • $\begingroup$ I see your point. On the right side of the Tate-pairing, I have to compute with Elements around $q^{2^{245}}$. This cannot be stored, or am I wrong? $\endgroup$ – Shalec Jun 14 '17 at 16:36
  • $\begingroup$ Are Goldilocks an option? $\endgroup$ – Shalec Jun 14 '17 at 16:55
  • 1
    $\begingroup$ "Are Goldilocks an option?" -> no, for the same reason as FourQ. You need a pairing-friendly curve, which is not what those curves (Goldilocks, Curve25519, FourQ, etc.) are designed for. $\endgroup$ – Mehdi Tibouchi Jun 15 '17 at 2:45
  • 1
    $\begingroup$ This book should contain all you need to write a pairing implementation: crcpress.com/Guide-to-Pairing-Based-Cryptography/Mrabet-Joye/p/… (Unfortunately, despite being quite new, it doesn't reflect the recent improved attacks on the target group, so for revised security estimates, you might want to refer to a paper like the one you mention by Barbulescu and Duquesne). $\endgroup$ – Mehdi Tibouchi Jun 15 '17 at 8:43

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.