Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
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 eta(T) pairing. The first is computed by using a square root computation in F3., and the computational cost of this algorithm is 0(log m) multiplications in F3(m). The second is computed by using an (m-1)x(m-1) matrix over F(3). It can be computed by 0(1) multiplications in F(3)m.. However, this algorithm needs the off-line memory to store about in F3(m)-elements. In this paper, we propose an efficient MapToPoint algorithm on the supersingular elliptic curves in characteristic three by using 1/3-trace over F(3m). We propose 1/3-trace over F(3)m, which can compute solution x of x(3) - x = c by using no multiplication in F(3)m.. The proposed algorithm is computed by 0(1) multiplications in F3., and it requires less than in F(3)-elements to be stored in the off-line memory to efficiently compute trace over F(3)m. Moreover, in our software implementation of F(3)509, the proposed MapToPoint algorithm is approximately 35% faster than the conventional MapToPoint algorithm using the square root computation on an AMD Opteron processor (2.2 GHz).
maptopoint supersingular elliptic curves characteristic 3 eta(t) pairing trace