同源密码中Montgomery模型的w-坐标研究

On the w-coordinates of Montgomery Model in Isogeny-based Cryptography

椭圆曲线群律计算是传统椭圆曲线密码(ECC)的核心运算,同时也是基于同源的后量子密码计算中的重要组成部分。Montgomery曲线上的Montgomery ladder算法是一种高效(伪)群律计算方法,且经常用于预防侧信道攻击。Farashahi和Hosseini在ACISP 2017提出了Edwards曲线模型上的w-坐标可得到类似Montgomery ladder算法以进行群律计算,Kim等人在ASIACRYPT 2019将其用于优化奇数次同源计算。随后,不同曲线模型上的w-坐标陆续被提出用于优化同源计算。本质上,w-坐标是关于传统椭圆曲线有理点(x,y)-坐标的有理函数。与标准(x,y)-坐标相比,w-坐标不仅可以节约椭圆曲线群律和同源计算的计算量,还可以减少带宽。Hisil和Renes在ACM TOMS 2019提出可利用加2阶点得到更多的w-坐标。受此启发,本文提出利用Montgomery曲线上的2-同源构造出3类新的w-坐标,与x-坐标相同的是,均可应用于Montgomery ladder算法和奇数次同源计算的优化。同时,w-坐标在计算奇数次同源中,同源映射像曲线系数计算公式与像点公式类似,可利用SIMD指令集将两者并行化处理,从而得到相关计算的进一步加速。最后,由于Edwards,Huff,Jacobi等曲线模型在某些条件下可与Montgomery模型建立双有理等价,因此可由Montgomery曲线上新的w-坐标开发出其他曲线模型上更多的w-坐标,它们将有可能支持同源密码实现中更有效的算法。

Elliptic curve group law calculation is the core operation of traditional Elliptic Curve Cryptography(ECC),which is also an important part of isogeny-based post quantum cryptography.The Montgomery ladder algorithm on Montgomery curve is an efficient(pseudo)group law calculation method,which is commonly used to resist side channel attacks.Farashahi and Hosseini in ACISP 2017 proposed the w-coordinates on Edwards curve model which could induce Montgomery-like ladder algorithm for group law calculation.By adopting such w-coordinates,Kim et al.in Asiacrypt 2019 optimized odd order isogeny computation.After that,several works have been devoted to extensively exploiting w-coordinates on different elliptic curve models.Essentially,the w-coordinates are rational functions of the traditional(x,y)-coordinates for rational points.Compared with the standard elliptic curve rational point(x,y)-coordinate,the w-coordinate not only reduces the amount of intermediate calculation in group law calculation and isogeny calculation,but also saves half of the bandwidth.Hisil and Renes in ACM TOMS 2019 considered how to obtain more w-coordinates by adding some 2-torsion point.Inspired by their work,this paper proposes three new w-coordinates by using a 2-isogeny on Montgomery curve,which are similar to the x-coordinate.These w-coordinates can be applied to Montgomery ladder algorithm,as well as to the optimization of odd degree isogeny computation.Simultaneously,in the calculation of the odd-numbered homology of the w-coordinate,the calculation formula of the Montgomery curve coefficient is similar to the isogeny formula,so the SIMD instruction set can be used to parallelize the coordinate calculation and the coefficient calculation,so as to obtain the further acceleration of the isogeny calculation.Moreover,since curve models such as Edwards,Huff,and Jacobi can establish a rational equivalent mapping with the Montgomery curve model under certain conditions,more w-coordinates can be developed from the three new types of w-coordinates,which implies such curve models can possess more w-coordinates to design better algorithms for isogeny based cryptography.