Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3

Yuto KAWAHARA; Tetsutaro KOBAYASHI; Gen TAKAHASHI; Tsuyoshi TAKAGI

doi:10.1587/transfun.E94.A.150

Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3

Yuto KAWAHARA, Tetsutaro KOBAYASHI, Gen TAKAHASHI, Tsuyoshi TAKAGI

Full Text Views

0

Cite this

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 F_3^m, and the computational cost of this algorithm is O(log m) multiplications in F_3^m. The second is computed by using an (m-1)(m-1) matrix over F₃. It can be computed by O(1) multiplications in F_3^m. However, this algorithm needs the off-line memory to store about m F_3^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_3^m. We propose 1/3-trace over F_3^m, which can compute solution x of x³ -x = c by using no multiplication in F_3^m. The proposed algorithm is computed by O(1) multiplications in F_3^m, and it requires less than m F₃-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⁵⁰⁹, 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).

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.1 pp.150-155

Publication Date: 2011/01/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.150

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Mathematics

Cite this

Copy

Yuto KAWAHARA, Tetsutaro KOBAYASHI, Gen TAKAHASHI, Tsuyoshi TAKAGI, "Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 1, pp. 150-155, January 2011, doi: 10.1587/transfun.E94.A.150.
Abstract: 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 F_3^m, and the computational cost of this algorithm is O(log m) multiplications in F_3^m. The second is computed by using an (m-1)(m-1) matrix over F₃. It can be computed by O(1) multiplications in F_3^m. However, this algorithm needs the off-line memory to store about m F_3^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_3^m. We propose 1/3-trace over F_3^m, which can compute solution x of x³ -x = c by using no multiplication in F_3^m. The proposed algorithm is computed by O(1) multiplications in F_3^m, and it requires less than m F₃-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⁵⁰⁹, 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).
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.150/_p

Copy

@ARTICLE{e94-a_1_150,
author={Yuto KAWAHARA, Tetsutaro KOBAYASHI, Gen TAKAHASHI, Tsuyoshi TAKAGI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3},
year={2011},
volume={E94-A},
number={1},
pages={150-155},
abstract={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 F_3^m, and the computational cost of this algorithm is O(log m) multiplications in F_3^m. The second is computed by using an (m-1)(m-1) matrix over F₃. It can be computed by O(1) multiplications in F_3^m. However, this algorithm needs the off-line memory to store about m F_3^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_3^m. We propose 1/3-trace over F_3^m, which can compute solution x of x³ -x = c by using no multiplication in F_3^m. The proposed algorithm is computed by O(1) multiplications in F_3^m, and it requires less than m F₃-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⁵⁰⁹, 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).},
keywords={},
doi={10.1587/transfun.E94.A.150},
ISSN={1745-1337},
month={January},}

Copy

TY - JOUR
TI - Faster MapToPoint on Supersingular Elliptic Curves in Characteristic 3
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 150
EP - 155
AU - Yuto KAWAHARA
AU - Tetsutaro KOBAYASHI
AU - Gen TAKAHASHI
AU - Tsuyoshi TAKAGI
PY - 2011
DO - 10.1587/transfun.E94.A.150
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2011
AB - 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 F_3^m, and the computational cost of this algorithm is O(log m) multiplications in F_3^m. The second is computed by using an (m-1)(m-1) matrix over F₃. It can be computed by O(1) multiplications in F_3^m. However, this algorithm needs the off-line memory to store about m F_3^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_3^m. We propose 1/3-trace over F_3^m, which can compute solution x of x³ -x = c by using no multiplication in F_3^m. The proposed algorithm is computed by O(1) multiplications in F_3^m, and it requires less than m F₃-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⁵⁰⁹, 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).
ER -