Parallel Algorithms on Hyperelliptic Pairings Using Hyperelliptic Nets

Pairings are useful tools in cryptography and efficient implementations play a critical role in their usage, where Miller’s algorithms are the main method for all pairings. As an alternative approach, elliptic nets were first employed to evaluate Tate pairings and generalized to the hyperelliptic nets for Tate pairings on hyperelliptic curves. In this work, for hyperelliptic pairings derived from rational functions, we establish the unitary formulae in terms of hyperelliptic nets. Afterwards, for genus-2 hyperelliptic pairings, we construct a parallel Double-and-Add algorithm on the minimal block. In particular, all terms in new blocks, having irrelevant formulae on current blocks, can be evaluated with 12 processors in parallel, thus the explicit loop cost reduces to \(4\textsf{M}'\) (multiplications in extension fields) with 276 parallel processors. As an additional merit, Double and Double-Add algorithms invoke analogous operations such that our method avoids extra additions in Miller’s algorithms.