Closed formulae for the Weil pairing inversion

AbstractUsing the Miller algorithm, we can efficiently compute the Weil pairing for two given points on an elliptic curve. On the other hand, security of pairing based cryptographic protocols depends on the converse problem: find a point on an elliptic curve whose Weil pairing with a given (fixed) point is equal to a given root of unity, which we call the Weil pairing inversion problem. In this article, we give closed formulae which give a solution to the problem. For supersingular elliptic curves over fields of characteristic two or three, these formulae take more simpler forms than those for other elliptic curves