Optimal Pairings
Fréderik Vercauteren · IEEE Transactions on Information Theory · 2010
In this paper, we introduce the concept of an optimal pairing, which by definition can be computed using onlylog2r/¿(k) basic Miller iterations, withrthe order of the groups involved andkthe embedding degree. We describe an algorithm to construct optimal ate pairings on all parametrized families of pairing friendly elliptic curves. Finally, we conjecture that any nondegenerate pairing on an elliptic curve without efficiently computable endomorphisms different from powers of Frobenius requires at leastlog2r/¿(k) basic Miller iterations.