Efficient and Generalized Pairing Computation on Abelian Varieties

In this paper, we propose a new method for constructing a bilinear pairing over (hyper)elliptic curves, which we call the R-ate pairing. This pairing is a generalization of the Ate and Ate_i pairing, and can be computed more efficiently. Using the R-ate pairing, the loop length in Miller´s algorithm can be as small as log (r^1/phi(k)) some pairing-friendly elliptic curves which have not reached this lower bound. Therefore, we obtain savings of between 29% and 69% in overall costs compared to the Ate_i pairing. On supersingular hyperelliptic curves of genus 2, we show that this approach makes the loop length in Miller´s algorithm shorter than that of the Ate pairing.