Choosing and generating parameters for low level pairing implementation on BN curves.
Sylvain Duquesne, Nadia El Mrabet, Safia Haloui, Franck Rondepierre · 2015
Many hardware and software pairing implementations can be found in the literature and some pairing friendly parameters are given. How-ever, depending on the situation, it could be useful to generate other nice parameters (e.g. resistance to subgroup attacks, larger security levels, database of pairing friendly curves). The main purpose of this paper is to describe explicitly and exhaustively what should be done to generate the best possible parameters and to make the best choices depending on the implementation context (in terms of pairing algorithm, ways to build the tower field, Fp12 arithmetic, groups involved and their generators, system of coordinates). We focus on low level implementations, assuming that Fp additions have a significant cost compared to other Fp operations. However, the results obtained are still valid in the case where Fp additions can be ne-glected. We also explain why the best choice for the polynomials defining the tower field Fp12 is only depending on the value of the BN parameter u modulo small integers like 12 as a nice application of old elementary arithmetic results. Moreover, we use this opportunity to give some new improvements on Fp12 arithmetic (in a pairing context) in terms of Fp-addition allowing to save around 10 % of them depending on the context. 1