The search functionality is under construction.

The search functionality is under construction.

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**_{3m}, and the computational cost of this algorithm is *O*(log *m*) multiplications in **F**_{3m}. The second is computed by using an (*m*-1)*m*-1) matrix over **F**_{3}. It can be computed by *O*(1) multiplications in **F**_{3m}. However, this algorithm needs the off-line 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/3-trace* over **F**_{3m}. We propose *1/3-trace* 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 off-line 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).

- 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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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**_{3m}, and the computational cost of this algorithm is *O*(log *m*) multiplications in **F**_{3m}. The second is computed by using an (*m*-1)*m*-1) matrix over **F**_{3}. It can be computed by *O*(1) multiplications in **F**_{3m}. However, this algorithm needs the off-line 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/3-trace* over **F**_{3m}. We propose *1/3-trace* 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 off-line 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).

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**_{3m}, and the computational cost of this algorithm is *O*(log *m*) multiplications in **F**_{3m}. The second is computed by using an (*m*-1)*m*-1) matrix over **F**_{3}. It can be computed by *O*(1) multiplications in **F**_{3m}. However, this algorithm needs the off-line 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/3-trace* over **F**_{3m}. We propose *1/3-trace* 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 off-line 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).

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**_{3m}, and the computational cost of this algorithm is *O*(log *m*) multiplications in **F**_{3m}. The second is computed by using an (*m*-1)*m*-1) matrix over **F**_{3}. It can be computed by *O*(1) multiplications in **F**_{3m}. However, this algorithm needs the off-line 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/3-trace* over **F**_{3m}. We propose *1/3-trace* 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 off-line 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).

ER -