On Parameterized Families of Elliptic Curves with Low Embedding Degrees

Zhang Meng; Xu Maozhi; Hu Zhi; Hou Ying

doi:10.11999/JEIT170261

Volume 40 Issue 1

Jan. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(1): 35-41

Zhang Meng, Xu Maozhi, Hu Zhi, Hou Ying. On Parameterized Families of Elliptic Curves with Low Embedding Degrees[J]. Journal of Electronics & Information Technology, 2018, 40(1): 35-41. doi: 10.11999/JEIT170261

Citation:

Zhang Meng, Xu Maozhi, Hu Zhi, Hou Ying. On Parameterized Families of Elliptic Curves with Low Embedding Degrees[J]. Journal of Electronics & Information Technology, 2018, 40(1): 35-41. doi: 10.11999/JEIT170261

Citation:

PDF( 250 KB)

On Parameterized Families of Elliptic Curves with Low Embedding Degrees

doi: 10.11999/JEIT170261

1.
(School of Mathematical Sciences, Peking University, Beijing 100871, China)
2.
(School of Mathematics and Statistics, Central South University, Changsha 410083, China)
3.
(Department of Compute Science and Technology, Tsinghua University, Beijing 100084, China)

Funds:

The National Natural Science Foundation of China (61272499, 61472016, 61672059, 61602526), The National Key RD Program of China (2017YFB0802000)

Received Date: 2017-03-29
Rev Recd Date: 2017-10-20
Publish Date: 2018-01-19

Abstract

Abstract

Pairing-friendly elliptic curves play a vital role in pairing-based cryptography. The constructionof such curves not only influences the implementation efficiency, but concerns the security of system. Though many methods for constructing such curves are introduced, most of which rely on exhaustive search. In this paper, a new systematic method is proposed for constructing such curves which converts the problem to solving equation systems, instead of exhaustive searching. The utility of the method is demonstrated by surveying such elliptic curves with embedding degree 5, 8, 10 and 12, and all kinds of families can be explained via the proposed method including complete families, complete families with variable discriminant and sparse families. Specifically, a new family of elliptic curves is found.
- Pairing-based cryptography,
- Elliptic curves,
- Pairing-friendly curves,
- Parameterized families

FullText(HTML)

References(19)

References

JOUX A. A one round protocol for tripartite Diffie- Hellman[J]. Journal of Cryptology, 2004, 17(4): 385-393. doi: 10.1007/s00145-004-0312-y.

MENEZES A J, OKAMOTO T, and VANSTONE S A. Reducing elliptic curve logarithms to logarithms in a finite field[J]. IEEE Transactions on Information Theory, 1993, 39(5): 1639-1646. doi: 10.1109/18.259647.

BONEH D and FRANKLIN M K. Identity-based encryption from the Weil pairing[C]. International Cryptology Conference on Advances in Cryptology, Springer-Verlag, 2001: 213-229.

PATERSON K G. ID-based signatures from pairings on elliptic curves[J]. Electronics Letters, 2002, 38(18): 1025-1026.

GOPAL P V S S N and Reddy P V. Efficient ID-based key-insulated signature scheme with batch verifications using bilinear pairings over elliptic curves[J]. Journal of Discrete Mathematical Sciences Cryptography, 2015, 18(4): 385-402. doi: 10.1080/09720529.2014.1001586.

ROBERT O. On Constructing families of pairing-friendly elliptic curves with variable discriminant[C]. Progress in Cryptology-Indocrypt 2011, International Conference on Cryptology in India, Chennai, India, 2011: 310-319.

FOTIADIS G and KONSTANTINOU E. More sparse families of pairing-friendly elliptic curves[C]. Cryptology and Network Security, Springer International Publishing, 2014: 384-399.

FREEMAN D, SCOTT M, and TESKE E. A taxonomy of pairing-friendly elliptic curves[J]. Journal of Cryptology, 2010, 23(2): 224-280. doi: 10.1007/s00145-009-9048-z.

LE D P, MRABET N E, and TAN C H. On near prime-order elliptic curves with small embedding degrees[C]. Algebraic Informatics. Springer International Publishing, 2015: 140-151. [10] LEE H S and PARK C M. Constructing pairing-friendly curves with variable CM discriminant[J]. Bulletin of the Korean Mathematical Society, 2012, 49(1): 75-88. doi: 10.4134/BKMS.2012.49.1.075.

TANAKA S and NAKAMULA K. Constructing pairing- friendly elliptic curves using factorization of cyclotomic polynomials[C]. Pairing-Based Cryptography-Pairing 2008, Second International Conference, Egham, UK, 2008: 136-145.

YOON K. A new method of choosing primitive elements for Brezing-Weng families of pairing- friendly elliptic curves[J]. Journal of Mathematical Cryptology, 2015, 9(1):1-9.

LEE H S and LEE P R. Families of pairing-friendly elliptic curves from a polynomial modification of the Dupont- Enge-Morain method[J]. Applied Mathematics Information Sciences, 2016, 10(2): 571-580. doi: 10.18576/amis/100218.

YASUDA T, TAKAGI T, and SAKURAI K. Constructing pairing-friendly elliptic curves using global number fields[C]. Third International Symposium on Computing and Networking, 2015: 477-483.

OKANO K. Note on families of pairing-friendly elliptic curves with small embedding degree[J]. JSIAM Letters, 2016: 61-64. doi: 10.14495/jsiaml.8.61.

LI L. Generating pairing-friendly elliptic curves with fixed embedding degrees[J]. Science China Information Sciences, 2017, 60(11): 119101. doi: 10.1007/s11432-016-0412-0.

ATKIN A O L and MORAIN F. Elliptic curves and primality proving[J]. Mathematics of Computation, 1997, 61(203): 29-68. doi: 10.1090/S0025-5718-1993-1199989-X.

GALBRAITH S D, MCKEE J F, and VALENCA P C. Ordinary abelian varieties having small embedding degree[J]. Finite Fields Their Applications, 2007, 13(4): 800-814. doi: 10.1016/j.ffa.2007.02.003.

ZHANG M, HU Z, and XU M. On constructing parameterized families of pairing-friendly elliptic curves with\rho=1[C]. International Conference on Information Security and Cryptology, Springer, Cham, 2016: 403-415.

FOTIADIS G and KONSTANTINOU E. On the efficient generation of generalized MNT elliptic curves[C]. Algebraic Informatics, Springer Berlin Heidelberg, 2013: 147-159.

Relative Articles

Supplements(0)

Cited By

Proportional views