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.
No takes yet. Share an insight, caveat, or question.
Fréderik Vercauteren (2010) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: