
For FullText 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 3
Yuto KAWAHARA Tetsutaro KOBAYASHI Gen TAKAHASHI Tsuyoshi TAKAGI
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E94A
No.1
pp.150155 Publication Date: 2011/01/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E94.A.150 Print ISSN: 09168508 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)>>
Summary:
Pairingbased 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 pairingbased 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 F_{3m}, and the computational cost of this algorithm is O(log m) multiplications in F_{3m}. The second is computed by using an (m1)(m1) matrix over F_{3}. It can be computed by O(1) multiplications in F_{3m}. However, this algorithm needs the offline memory to store about m F_{3m}elements. In this paper, we propose an efficient MapToPoint algorithm on the supersingular elliptic curves in characteristic three by using 1/3trace over F_{3m}. We propose 1/3trace over F_{3m}, which can compute solution x of x^{3} x = c by using no multiplication in F_{3m}. The proposed algorithm is computed by O(1) multiplications in F_{3m}, and it requires less than m F_{3}elements to be stored in the offline memory to efficiently compute trace over F_{3m}. Moreover, in our software implementation of F_{3509}, 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).

