Parametrization of KSS-16 curves, choosing a prime and understand the Ate pairing field size.

44 Views Asked by At

I'm actually really confused. I just looked it up in different sources [1,2,3a] [1] states

$q=1/980(u^{10} + 2u^9 + 5u^8 + 48u^6 + 152u^5 + 240u^4 + 625u^2 + 2398u + 3125)$

where $q=p^d$ for any prime $p$ and integer $d$. The other both sources states this with $p$ and names it the field size.

There is the first part I cannot follow directly. But the next thing is also weird: in [3b] there is a new key size recommendation for 128 bit of equivalent security. It is a 34-bit "prime":

$u = -2^{34} +2^{27} -2^{23} +2^{20} - 2^{11} +1$ or a 35-bit $u=2^{35} - 2^{32} -2^{18} + 2^{8} +1$

but, if I let Sage check, it turnes out, that none of them is a prime.

If I, furthermore, consider the optimal Ate pairing, it will get into $\mathbb F_{p^k}$, and if I plug in that 34-bit "prime" it leads to a field size of 545 5441 bits, what is quite to low?

Could someone help me get light in that fog?

References

[1] Mrabet etal. Guide to Pairing-Based Cryptography. 2017. Page 4-14. Example 4.5

[2] https://eprint.iacr.org/2016/472 , page 3 section 2.1

[3] https://eprint.iacr.org/2017/334 ,

  • (a) page 4 section 2.3

  • (b) page 13 section 6.3