Closed formulae for the Weil pairing inversion (Q938771)

Pairings are bilinear maps \(\beta:\mathbb{G}_0\times\mathbb{G}_1\to\mathbb{G}_2\), with \(\mathbb{G}_0\), \(\mathbb{G}_1\), \(\mathbb{G}_2\) cyclic groups of the same order. Weil and Tate pairings are computed by the famous Miller's algorithm and some variants of it. In this paper, the following inversion problem is considered: \textit{Fixed pairing inversion} (FPI) Fixed \(x\in\mathbb{G}_0\), for any \(z\in\mathbb{G}_2\) find \(y\in\mathbb{G}_1\) such that \(\beta(x,y)=z\). Let \(E\) be an elliptic curve and let \(x\in E\) be an element of order \(m\in\mathbb{G}^+\). Let \(G=\langle x\rangle\) be the group generated by \(x\) in \(E\). Then, there is an elliptic curve, written commonly as \(E/G\), and an isogeny \(\phi:E\to E/G\) such that \(\text{ker}(\phi)=G\). The author is able to determine a map \(V_x:U_m\to (E/G)[m]\), where \(U_m\) is the multiplicative group of the \(m\)-th roots of unity, such that \(V_x\) is a monomorphism and whenever \(x\in (E/G)[m]\) but \(x\not\in\text{ker}(\widehat{\phi})\), where \(\widehat{\phi}\) is the dual isogeny, then for the Weil map \(W:E[m]\times E[m]\to U_m\)the following holds: \(\forall u\in U_m\;\left[W(x,V_{\widehat{\phi}(x)}(u)) = u\right].\) Thus \(V_{\widehat{\phi}(x)}\) is giving the solution to FPI. In section 4 the author provides some conditions restricting the values of \(V_a\) for general elliptic curves. But for the special cases of supersingular curves and field characteristic 2 and 3, the author gives explicit expressions for \(V_x\). Nevertheless, for practical purposes the full evaluation of these expressions is highly complex and the formal reduction obtained from the paper results remains hard.