For Full-Text PDF, please login, if you are a member of IEICE, or go to Pay Per View on menu list, if you are a nonmember of IEICE.
 Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3Yuto 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-155Publication Date: 2011/01/01Online ISSN: 1745-1337 DOI: 10.1587/transfun.E94.A.150Print ISSN: 0916-8508Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)Category: MathematicsKeyword: MapToPoint,  characteristic 3,  supersingular elliptic curves,  trace,  ηT pairing,  Full Text: PDF>> 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).