Optimal pairing computation over families of pairing-friendly elliptic curves (Q429764)

Bilinear, non-degenerate pairings on elliptic curves over finite fields have many applications in cryptography. The efficient computation of those pairings with variants of Miller's algorithm is part of this research area. \textit{F. Vercauteren} [``Optimal pairings'', IEEE Trans. Inf. Theory 56, No. 1, 455--461 (2010; \url{doi:10.1109/TIT.2009.2034881})] introduced the concept of an optimal pairing, which is by definition a pairing for which Miller's basic algorithm performs an expected minimal number of iterations. A summary of recent constructions of pairing-friendly elliptic curves is given in [\textit{D. Freeman} et al., J. Cryptology 23, No. 2, 224--280 (2010; Zbl 1181.94094)]. There are several approaches to achieve optimal pairings, in particular, variants of the so-called Ate or R-ate pairing. In this article, the authors provide several families of pairing-friendly curves. For each family, they explain how to obtain an optimal pairing by following the Ate or R-ate pairing approach.