论文标题
扭曲的$ \boldsymbolμ_4$ - 正常形式的椭圆形曲线形式
Twisted $\boldsymbolμ_4$-normal form for elliptic curves
论文作者
论文摘要
我们介绍了椭圆曲线的扭曲$ \boldsymbolμ_4$ - 正常形式,特别是具有复杂性的添加算法$ 9 \ mathbf {M} + 2 \ Mathbf {s} $,并与复杂性$ 2 \ MATHBF {M} + 5 \ 5 \ MATHBF(MATHBF)加倍算法 + 2二进制场。特征2的有限领域上的每个普通椭圆曲线对这个家庭中的一个都是同构。适用于较大类曲线的添加算法的这种改进与$ 7 \ MathBf {M} + 2 \ MathBf {S} $相当适用于这些扭曲曲线。派生的加倍算法本质上是最佳的,而没有任何特殊情况的假设。此外,我们还表明,随着点恢复的蒙特哥马利标量乘积将延伸到扭曲的模型中,从而使对称标量乘法适应于防止侧向通道攻击,成本为$ 4 \ MathBf {M} + 4 \ MathBf {S} + 1 \ MathBf {M} + MathBf {M} {M} {M} _t + 2 \ 2 \ 2 \ Mathbf} $} $} $} $} $} M}。在与2不同的特征中,我们在基本场上建立了带有扭曲的爱德华兹模型的线性同构。这项工作补充了$ \boldsymbolμ_4$ - 正常形式,填充了二进制磁场上椭圆曲线上有效算术的工作中的空白,这是通过$ \boldsymbolμ_4$ - normal形式的椭圆曲线对任何特征的椭圆曲线进行了解释。这些改进类似于Edwards和Twisted Edwards模型在奇数特征有限磁场上实现的椭圆曲线,并扩展$ \boldsymbolμ_4$ - 正常形式以覆盖二进制NIST曲线。
We introduce the twisted $\boldsymbolμ_4$-normal form for elliptic curves, deriving in particular addition algorithms with complexity $9\mathbf{M} + 2\mathbf{S}$ and doubling algorithms with complexity $2\mathbf{M} + 5\mathbf{S} + 2\mathbf{m}$ over a binary field. Every ordinary elliptic curve over a finite field of characteristic 2 is isomorphic to one in this family. This improvement to the addition algorithm, applicable to a larger class of curves, is comparable to the $7\mathbf{M} + 2\mathbf{S}$ achieved for the $\boldsymbolμ_4$-normal form, and replaces the previously best known complexity of $13\mathbf{M} + 3\mathbf{S}$ on López-Dahab models applicable to these twisted curves. The derived doubling algorithm is essentially optimal, without any assumption of special cases. We show moreover that the Montgomery scalar multiplication with point recovery carries over to the twisted models, giving symmetric scalar multiplication adapted to protect against side channel attacks, with a cost of $4\mathbf{M} + 4\mathbf{S} + 1\mathbf{m}_t + 2\mathbf{m}_c$ per bit. In characteristic different from 2, we establish a linear isomorphism with the twisted Edwards model over the base field. This work, in complement to the introduction of $\boldsymbolμ_4$-normal form, fills the lacuna in the body of work on efficient arithmetic on elliptic curves over binary fields, explained by this common framework for elliptic curves in $\boldsymbolμ_4$-normal form over a field of any characteristic. The improvements are analogous to those which the Edwards and twisted Edwards models achieved for elliptic curves over finite fields of odd characteristic, and extend $\boldsymbolμ_4$-normal form to cover the binary NIST curves.