TY - GEN
T1 - Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem
AU - Ikematsu, Yasuhiko
AU - Fukasaku, Ryoya
AU - Kudo, Momonari
AU - Yasuda, Masaya
AU - Takashima, Katsuyuki
AU - Yokoyama, Kazuhiro
N1 - Funding Information:
This work was supported by JSPS KAKENHI Grant Number JP19K 20266, JP19K22847.
Publisher Copyright:
© 2020 ACM.
PY - 2020/10/5
Y1 - 2020/10/5
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85095573371&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85095573371&partnerID=8YFLogxK
U2 - 10.1145/3384940.3388956
DO - 10.1145/3384940.3388956
M3 - Conference contribution
AN - SCOPUS:85095573371
T3 - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020
SP - 36
EP - 44
BT - APKC 2020 - Proceedings of the 7th ACM Workshop on ASIA Public-Key Cryptography, Co-located with AsiaCCS 2020
PB - Association for Computing Machinery, Inc
T2 - 7th ACM Workshop on Asia Public-Key Cryptography, APKC 2020, held in conjunction with the 15th ACM ASIA Conference on Computer and Communications Security, ACM ASIACCS 2020
Y2 - 6 October 2020
ER -