Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem
Hybrid Meet-in-the-Middle Attacks for the Isogeny Path-Finding Problem
复制标题
针对同源路径查找问题的混合中间相遇攻击
DOI：
10.1145/3384940.3388956
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Yokoyama Kazuhiro
中科院分区：
文献类型：
--
作者：
Ikematsu Yasuhiko;Fukasaku Ryoya;Kudo Momonari;Yasuda Masaya;Takashima Katsuyuki;Yokoyama Kazuhiro
基于同构的密码学作为后量子密码学（PQC）的候选密码学而受到关注，其安全性是基于同构问题的困难性。中间相遇（Meet-in-the-middle，MITM）的思想是一种双向的冲突搜索，它为密码分析提供了一个强有力的工具。在本文中，我们提出了混合方法的MITM解决孤立路径查找问题。具体来说，我们首先建立一个传统的方法的同源树的一部分，然后我们搜索一对同源曲线的素数幂次代数方法使用的模多项式，提出了Takahashi等人。在MathCrypt 2019。我们的混合方法放宽了MITM中搜索表的大小要求，它们也使我们能够完美而容易地并行化代数搜索的一部分。在这里，我们展示了我们的混合方法的实验结果，从搜索表的性能和大小的角度讨论与纯MITM方法的比较。
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.