Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem

Isogeny-based cryptography has received attention as a candidate of post-quantum cryptography (PQC), and its security is based on the hardness of isogeny problems. The idea of meet-in-the-middle (MITM) is a bidirectional search for a collision, and it gives a powerful tool in cryptanalysis. In this paper, we propose hybrid approaches of MITM for solving the isogeny path-finding problem. Specifically, we first build part of trees of isogenies in a conventional way, and we then search a pair of isogenous curves of prime power degree by the algebraic approach using modular polynomials, proposed by Takahashi et al.¥! at MathCrypt 2019. Our hybrid approaches relax the requirements of sizes of search tables in MITM, and they also enable us to parallelize the part of algebraic search perfectly and easily. Here we show experimental results of our hybrid approaches to discuss a comparison with pure MITM approaches from a perspective of performance and sizes of search tables.