Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3

Yuto KAWAHARA  Tetsutaro KOBAYASHI  Gen TAKAHASHI  Tsuyoshi TAKAGI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.1   pp.150-155
Publication Date: 2011/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.150
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
Category: Mathematics
Keyword: 
MapToPoint,  characteristic 3,  supersingular elliptic curves,  trace,  ηT pairing,  

Full Text: PDF(588.1KB)>>
Buy this Article




Summary: 
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.2 GHz).