Reducing Pairing Inversion to Exponentiation Inversion using Non-degenerate Auxiliary Pairing
The security of pairing-based cryptosystems is closely related to the difficulty of the pairing inversion problem. Building on previous works, the authors provide further contributions on the difficulty of pairing inversion. In particular, they revisit the approach of Kanayama-Okamoto who modified exponentiation inversion and Miller inversion by considering an "Auxiliary" pairing. First, by generalizing and simplifying Kanayama-Okamoto's approach, they provide a simpler approach for inverting generalized ate pairings of Vercauteren. Then they provide a complexity of the modified Miller inversion, showing that the complexity depends on the sum-norm of the integer vector defining the auxiliary pairing.