New Concrete Relation between Trace, Definition Field, and Embedding Degree

Shoujiro HIRASAWA; Atsuko MIYAJI

doi:10.1587/transfun.E94.A.1368

New Concrete Relation between Trace, Definition Field, and Embedding Degree

Shoujiro HIRASAWA, Atsuko MIYAJI

Full Text Views

0

Cite this

Summary :

A pairing over an elliptic curve E/F_p^m to an extension field of F_p^mk has begun to be attractive in cryptosystems, from the practical and theoretical point of view. From the practical point of view, many cryptosystems using a pairing, called the pairing-based cryptosystems, have been proposed and, thus, a pairing is a necessary tool for cryptosystems. From the theoretical point of view, the so-called embedding degree k is an indicator of a relationship between the elliptic curve Discrete Logarithm Problem (ECDLP) and the Discrete Logarithm Problem (DLP), where ECDLP over E(F_p^m) is reduced to DLP over F_p^mk by using the pairing. An elliptic curve is determined by mathematical parameters such as the j-invariant or order of an elliptic curve, however, explicit conditions between these mathematical parameters and an embedding degree have been described only in a few degrees. In this paper, we focus on the theoretical view of a pairing and investigate a new condition of the existence of elliptic curves with pre-determined embedding degrees. We also present some examples of elliptic curves over 160-bit, 192-bit and 224-bit F_p^m with embedding degrees k < (log p)² such as k=10, 12, 14, 20, 22, 24, 28.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E94-A No.6 pp.1368-1374

Publication Date: 2011/06/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E94.A.1368

Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)

Category

Cite this

Copy

Shoujiro HIRASAWA, Atsuko MIYAJI, "New Concrete Relation between Trace, Definition Field, and Embedding Degree" in IEICE TRANSACTIONS on Fundamentals, vol. E94-A, no. 6, pp. 1368-1374, June 2011, doi: 10.1587/transfun.E94.A.1368.
Abstract: A pairing over an elliptic curve E/F_p^m to an extension field of F_p^mk has begun to be attractive in cryptosystems, from the practical and theoretical point of view. From the practical point of view, many cryptosystems using a pairing, called the pairing-based cryptosystems, have been proposed and, thus, a pairing is a necessary tool for cryptosystems. From the theoretical point of view, the so-called embedding degree k is an indicator of a relationship between the elliptic curve Discrete Logarithm Problem (ECDLP) and the Discrete Logarithm Problem (DLP), where ECDLP over E(F_p^m) is reduced to DLP over F_p^mk by using the pairing. An elliptic curve is determined by mathematical parameters such as the j-invariant or order of an elliptic curve, however, explicit conditions between these mathematical parameters and an embedding degree have been described only in a few degrees. In this paper, we focus on the theoretical view of a pairing and investigate a new condition of the existence of elliptic curves with pre-determined embedding degrees. We also present some examples of elliptic curves over 160-bit, 192-bit and 224-bit F_p^m with embedding degrees k < (log p)² such as k=10, 12, 14, 20, 22, 24, 28.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E94.A.1368/_p

Copy

@ARTICLE{e94-a_6_1368,
author={Shoujiro HIRASAWA, Atsuko MIYAJI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={New Concrete Relation between Trace, Definition Field, and Embedding Degree},
year={2011},
volume={E94-A},
number={6},
pages={1368-1374},
abstract={A pairing over an elliptic curve E/F_p^m to an extension field of F_p^mk has begun to be attractive in cryptosystems, from the practical and theoretical point of view. From the practical point of view, many cryptosystems using a pairing, called the pairing-based cryptosystems, have been proposed and, thus, a pairing is a necessary tool for cryptosystems. From the theoretical point of view, the so-called embedding degree k is an indicator of a relationship between the elliptic curve Discrete Logarithm Problem (ECDLP) and the Discrete Logarithm Problem (DLP), where ECDLP over E(F_p^m) is reduced to DLP over F_p^mk by using the pairing. An elliptic curve is determined by mathematical parameters such as the j-invariant or order of an elliptic curve, however, explicit conditions between these mathematical parameters and an embedding degree have been described only in a few degrees. In this paper, we focus on the theoretical view of a pairing and investigate a new condition of the existence of elliptic curves with pre-determined embedding degrees. We also present some examples of elliptic curves over 160-bit, 192-bit and 224-bit F_p^m with embedding degrees k < (log p)² such as k=10, 12, 14, 20, 22, 24, 28.},
keywords={},
doi={10.1587/transfun.E94.A.1368},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - New Concrete Relation between Trace, Definition Field, and Embedding Degree
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1368
EP - 1374
AU - Shoujiro HIRASAWA
AU - Atsuko MIYAJI
PY - 2011
DO - 10.1587/transfun.E94.A.1368
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E94-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2011
AB - A pairing over an elliptic curve E/F_p^m to an extension field of F_p^mk has begun to be attractive in cryptosystems, from the practical and theoretical point of view. From the practical point of view, many cryptosystems using a pairing, called the pairing-based cryptosystems, have been proposed and, thus, a pairing is a necessary tool for cryptosystems. From the theoretical point of view, the so-called embedding degree k is an indicator of a relationship between the elliptic curve Discrete Logarithm Problem (ECDLP) and the Discrete Logarithm Problem (DLP), where ECDLP over E(F_p^m) is reduced to DLP over F_p^mk by using the pairing. An elliptic curve is determined by mathematical parameters such as the j-invariant or order of an elliptic curve, however, explicit conditions between these mathematical parameters and an embedding degree have been described only in a few degrees. In this paper, we focus on the theoretical view of a pairing and investigate a new condition of the existence of elliptic curves with pre-determined embedding degrees. We also present some examples of elliptic curves over 160-bit, 192-bit and 224-bit F_p^m with embedding degrees k < (log p)² such as k=10, 12, 14, 20, 22, 24, 28.
ER -