Hashing to elliptic curves of \(j\)-invariant 1728 (Q2120982)

The author proposes to use a simplified Shallue-van de Woestijn-Ulas (SWU) method [\textit{A. Shallue} and \textit{C. E. van de Woestijne}, Lect. Notes Comput. Sci. 4076, 510--524 (2006; Zbl 1143.11331); \textit{M. Ulas}, Bull. Pol. Acad. Sci., Math. 55, No. 2, 97--104 (2007; Zbl 1131.11039)] to develop a deterministic hashing \(h: \mathbb F_q \to E(\mathbb F_q)\) to the \(\mathbb F_q\)-rational points of an elliptic curve \(E:y^2=x^3-ax\) (which has a \(j\)-invariant 1728). The case when the (finite) ground field is of characteristic \(p\equiv 1 \bmod 4\) and when \(\sqrt a \not\in \mathbb F_q\) is of particular interest in applications. The method requires us to find a rational curve \(D\) (denoted \(D_8\) in the paper), defined over \(\mathbb F_q\), on the Kummer surface \(K\) associated to the product \(E\times E'\), where \(E'\) is a quadratic \(\mathbb F_q\)-twist of \(E\). If we can explicitly compute a parametrization of \(D\) we can (via projections) construct a hash function \(h\) on the rational points of \(E\). The author explicitly gives a procedure to obtain \(D\) and a parametrization of \(D\). The procedure starts with a given conic \(C_1\) in \(\mathbb P^1\times \mathbb P^1\) invariant under the Frobenius map (i.e. taking \(q\)-th power of the coordinates). The curve \(C_1\) is the projection of curve \(D_1\), defined over \(\mathbb F_{q^2}\), of a singular Kummer surface. The curve \(D_1\) is in turn birationally mapped to \(D\). The procedure is intricate and needs an intermediate map to another curve \(D_2\) on a Kummer surface. To prove the rationality of these curves, one uses a criteria proven in [\textit{P. Satgé}, Prog. Math. 199, 313--334 (2001; Zbl 1075.14513)] which needs us to compute intersection multiplicities with exceptional curves on the surface. Finally, a parametrization is explicitly computed for \(D\) and via composition with natural maps we obtain \(h\). It turns out that the proposed hashing \(h\) is at most \(8:1\). In the final section of the paper, the author proves the algebraic complexity of \(h\) and states a problem relating to a generalization of the simplified SWU method when the \(j\)-invariant is \(0\).