Analysis of the Gallant-Lambert-Vanstone Method Based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves
Analysis of the Gallant-Lambert-Vanstone Method Based on Efficient Endomorphisms: Elliptic and Hyperelliptic Curves
复制标题
DOI：
10.1007/3-540-36492-7_3
复制
发表时间：
2002-08
期刊：
影响因子：
--
通讯作者：
F. Sica;M. Ciet;J. Quisquater
中科院分区：
文献类型：
--
作者：
F. Sica;M. Ciet;J. Quisquater
在这项工作中，我们分析了Galant，Lambert和Vanstone(Crypto 2001)的GLV方法，它使用一个快速的自同态Φ和极小多项式X2+RX+st来计算位于椭圆曲线上的点P的任何倍数。首先，我们填补了归约映射f的核K向量的界的证明中的一个空白：(i，j)→i+λj(Modn)。特别地，我们证明了GLV分解具有显式常数kP=k1P+k2Φ(P)，其中max Rik1|，|k2|⪯√1+|r|+S√n.接下来，我们改进了这个界，并在给定的例子中给出了关于量supk，nmax|k1|，|k2|/√n的最佳常数.独立地，Park，Jeong，Kim，and Lim(PKC2002)也给出了类似但稍弱的界.最后，我们给出了推广到超椭圆曲线的GLV方法的第一个显界，如Park，Jeong和Lim(Eurocrypt 2002)所述。
In this work we analyse the GLV method of Gallant, Lambert and Vanstone (CRYPTO 2001) which uses a fast endomorphismΦwith minimal polynomialX2+rX+sto compute any multiplekPof a pointPof ordernlying on an elliptic curve. First we fill in a gap in the proof of the bound of the kernelKvectors of the reduction mapf : (i, j)→ i+λj(modn). In particular, we prove the GLV decomposition with explicit constantkP=k1P+k2Φ(P), with max Rik1∣, ∣k2∣ ⪯ √1 +∣r∣ +s√n. Next we improve on this bound and give the best constant in the given examples for the quantity supk,nmax ∣k1∣, ∣k2∣/√n. Independently Park, Jeong, Kim, and Lim (PKC 2002) have given similar but slightly weaker bounds. Finally we provide the first explicit bounds for the GLV method generalised to hyperelliptic curves as described in Park, Jeong and Lim (EUROCRYPT 2002).