Further Optimizations of CSIDH: A Systematic Approach to Efficient Strategies, Permutations, and Bound Vectors
Further Optimizations of CSIDH: A Systematic Approach to Efficient Strategies, Permutations, and Bound Vectors
复制标题
CSIDH 的进一步优化：高效策略、排列和绑定向量的系统方法
DOI：
10.1007/978-3-030-57808-4_24
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Azarderakhsh, Reza
中科院分区：
文献类型：
--
作者：
Hutchinson, Aaron;LeGrow, Jason;Koziel, Brian;Azarderakhsh, Reza
CSIDH是最近提出的一种基于构造超奇异椭圆曲线之间同构的后量子密钥建立协议。最近的几项工作给出了CSIDH的恒定时间实现以及对理想类群动作评估算法的一些优化，包括Meyeret等人的Simba技术和Onukiet等人的两点方法。Cervantes-Vázquezet等人最近的一项工作详细说明了对Meyeret等人和Onukiet等人的工作的一些改进。这些优化中的几个--特别是素数的排序的选择、SIMBA划分和策略的选择以及定义秘密密钥空间的界限向量的选择--已经以Anad hoc式的方式进行了，因此，尽管它们产生了性能改进，但这些选择是否可以被改进还不清楚或者如何做到这一点。在这项工作中，我们提出了一个框架，分别使用线性规划、动态规划和凸规划技术来改进这些优化。我们的框架适用于任何CSIDH安全级别，适用于所有当前提出的计算类群操作的范例，以及适用于底层曲线的任何模型选择。在Meyeret等人的实现中，我们获得了13.04%的加速比，而对于Cervantes-Vázquez等人提出的进一步优化，在两点方法下，我们获得了5.23%的加速比，给出了迄今为止CSIDH最快的恒定时间实现。
CSIDH is a recent post-quantum key establishment protocol based on constructing isogenies between supersingular elliptic curves. Several recent works give constant-time implementations of CSIDH along with some optimizations of the ideal class group action evaluation algorithm, including the SIMBA technique of Meyeret al.and the “two-point method” of Onukiet al.A recent work of Cervantes-Vázquezet al.details a number of improvements to the works of Meyeret al.and Onukiet al.Several of these optimizations—in particular, the choice of ordering of the primes, the choice of SIMBA partition and strategies, and the choice of bound vector which defines the secret keyspace—have been made in anad hocfashion, and so while they yield performance improvements it has not been clear whether these choices could be improved upon, or how to do so. In this work we present a framework for improving these optimizations using (respectively) linear programming, dynamic programming, and convex programming techniques. Our framework is applicable to any CSIDH security level, to all currently-proposed paradigms for computing the class group action, and to any choice of model for the underlying curves. Using our framework we find improved parameter sets for the two major methods of computing the group action: in the case of the implementation of Meyeret al.we obtain a 13.04% speedupwithoutapplying the further optimizations proposed by Cervantes-Vázquez et al., while for that of Cervantes-Vázquezet al.under the two-point method we obtain a speedup of 5.23%, giving the fastest constant-time implementation of CSIDH to date.
登录
查看更多内容
为 CSIDH 提供更强、更快的侧通道保护
DOI：
10.1007/978-3-030-30530-7_9
发表时间：
2019
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Daniel Cervantes;Mathilde Chenu;Jesús;L. D. Feo;F. Rodríguez;Benjamin A. Smith
通讯作者：
Benjamin A. Smith
关于狮子和鳄鱼：CSIDH 的高效恒定时间实现
DOI：
10.1007/978-3-030-25510-7_17
发表时间：
2019
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
Michael Meyer;Fabio Campos;S. Reith
通讯作者：
S. Reith
构建基于同源密码学并行实现的规范策略
DOI：
10.1007/978-3-030-05378-9_10
发表时间：
2018
期刊：
IACR Cryptol. ePrint Arch.
影响因子：
--
作者：
A. Hutchinson;Koray Karabina
通讯作者：
Koray Karabina
如何在爱德华兹曲线上构造CSIDH
DOI：
--
发表时间：
2020
期刊：
IACR Cryptology ePrint Archive
影响因子：
--
作者：
Tomoki Moriya;Hiroshi Onuki;T. Takagi
通讯作者：
T. Takagi
NEOS 服务器 4.0 管理指南
DOI：
10.2172/822567
发表时间：
2001
期刊：
ArXiv
影响因子：
--
作者：
E. Dolan
通讯作者：
E. Dolan