Hash functions from superspecial genus-2 curves using Richelot isogenies (Q2023308)

This paper provides a hash function based on Richelot isogenies on Jacobians of genus 2 curves defined over a finite field, improving a previous proposal of K. Takashima. A first construction of hash function based on the isogeny graph of supersingular elliptic curves was given by \textit{D. X. Charles} et al. [J. Cryptology 22, No. 1, 93--113 (2009; Zbl 1166.94006)]. This was generalized by \textit{K. Takashima} et al. [Mathematical modelling for next-generation cryptography. CREST Crypto-Math project. Singapore: Springer (2018; Zbl 1383.94002)] in the context of Jacobians of supersingular genus 2 curves, using Richelot isogenies (isogenies with \(\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}\)\, kernel). But \textit{E. V. Flynn} and \textit{Y. B. Ti} [Lect. Notes Comput. Sci. 11505, 286--306 (2019; Zbl 07173869)] pointed out that the Takashima's construction was insecure due to small cycles in the isogeny graph.\par The present paper shows how to prevent the Flyn and Ti attack . Instead of taking the full supersingular graph the authors use the superspecial subgraph (the Jacobians of the curves are superspecial). This graph is defined over \(\mathbb{F}_{p^2}\) and therefore all the arithmetic can be carried out on \(\mathbb{F}_{p^2}\). Section 2 to 6 gather concepts and tools about genus two curves, Richelot isogenies, the superspecial (2,2)-isogeny graph \(\mathcal{G}_p\)\, and the composition of isogenies in \(\mathcal{G}_p\). Section 7 discusses details of the construction of the hash function from \(\mathcal{G}_p\)\, and how to avoid the small cycles that appear in the Takashima scheme. Section 8 and Appendix B show an implementation in Magma, see Algorithm 1 and Figure 3. Finally Section 9 gives a comparison of the computational cost of the Charles, Goren and Lauter construction and the proposed one.