Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
复制标题
DOI：
10.1587/transfun.e94.a.150
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Yuto Kawahara;Tetsutaro Kobayashi;Gen Takahashi;T. Takagi
中科院分区：
文献类型：
--
作者：
Yuto Kawahara;Tetsutaro Kobayashi;Gen Takahashi;T. Takagi
基于配对的密码系统通常使用许多函数来构建，例如配对计算、有限域算术和椭圆曲线算术。 MapToPoint 是一种椭圆曲线点上的哈希算法，是构建基于配对的密码系统的函数之一。特征三中有两种关于超奇异椭圆曲线的MapToPoint算法，都是通过ηT配对来使用的。第一个是在 F3m 中使用平方根计算来计算的，该算法的计算成本是 F3m 中的 O(log m) 次乘法。第二个是通过在 F3 上使用 (m-1)×(m-1) 矩阵来计算的。它可以通过 F3m 中的 O(1) 乘法来计算。然而，该算法需要离线存储器来存储大约m个F3m元素。在本文中，我们通过使用 F3m 上的 1/3-trace，提出了一种针对特征三的超奇异椭圆曲线的高效 MapToPoint 算法。我们提出了 F3m 上的 1/3-trace，它可以通过在 F3m 中不使用乘法来计算 x3-x=c 的解 x。所提出的算法是通过 F3m 中的 O(1) 乘法计算的，并且需要将少于 m 个 F3 元素存储在离线存储器中才能有效地计算 F3m 上的迹。此外，在我们的 F3509 软件实现中，所提出的 MapToPoint 算法比在 AMD Opteron 处理器 (2.2GHz) 上使用平方根计算的传统 MapToPoint 算法快大约 35%。
Pairing-based cryptosystems are generally constructed using many functions such as pairing computation, arithmetic in finite fields, and arithmetic on elliptic curves. MapToPoint, which is a hashing algorithm onto an elliptic curve point, is one of the functions for constructing pairing-based cryptosystems. There are two MapToPoint algorithms on supersingular elliptic curves in characteristic three, which is used by ηT pairing. The first is computed by using a square root computation in F3m, and the computational cost of this algorithm is O(log m) multiplications in F3m. The second is computed by using an (m-1)×(m-1) matrix over F3. It can be computed by O(1) multiplications in F3m. However, this algorithm needs the off-line memory to store about m F3m-elements. In this paper, we propose an efficient MapToPoint algorithm on the supersingular elliptic curves in characteristic three by using 1/3-trace over F3m. We propose 1/3-trace over F3m, which can compute solution x of x3-x=c by using no multiplication in F3m. The proposed algorithm is computed by O(1) multiplications in F3m, and it requires less than m F3-elements to be stored in the off-line memory to efficiently compute trace over F3m. Moreover, in our software implementation of F3509, the proposed MapToPoint algorithm is approximately 35% faster than the conventional MapToPoint algorithm using the square root computation on an AMD Opteron processor (2.2GHz).