Construction of Hyperelliptic Curves with CM and Its Application to Cryptosystems
Construction of Hyperelliptic Curves with CM and Its Application to Cryptosystems
复制标题
CM构造超椭圆曲线及其在密码系统中的应用
DOI：
10.1007/3-540-44448-3_20
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Tsujii
中科院分区：
文献类型：
--
作者：
J. Chao;Kazuto Matsuo;Hiroto Kawashiro;S. Tsujii
在基于超椭圆曲线上离散对数问题的密码系统设计中，安全超椭圆曲线的构造是最重要也是最困难的问题。目前唯一可行的方法是使用CM曲线。然而，找到CM曲线的模型是不平凡的。流行的方法使用theta函数来导出Jacobian簇的投影嵌入，这需要非常高的精度来计算theta函数。正如我们在本文中所示，它的成本计算时间的一个指数函数的判别式的CM字段。本文提出了一种新的算法来寻找超椭圆曲线的显式模型与CM。给出了代数曲线雅可比簇的CM检验算法和从小域提升CM曲线的模型和不变量的算法。我们还表明，所提出的不变量提升算法的CM字段的判别式的多项式时间的复杂性。
Construction of secure hyperelliptic curves is of most important yet most difficult problem in design of cryptosystems based on the discrete logarithm problems on hyperelliptic curves. Presently the only accessible approach is to use CM curves. However, to find models of the CM curves is nontrivial. The popular approach uses theta functions to derive a projective embedding of the Jacobian varieties, which needs to calculate the theta functions to very high precision. As we show in this paper, it costs computation time of an exponential function in the discriminant of the CM field. This paper presents new algorithms to find explicit models of hyperelliptic curves with CM. Algorithms for CM test of Jacobian varieties of algebraic curves and to lift from small finite fields both the models and the invariants of CM curves are presented. We also show that the proposed algorithm for invariants lifting has complexity of a polynomial time in the discriminant of the CM field.