|
|
|
| On Parameterized Families of Elliptic Curves with Low Embedding Degrees |
| Zhang Meng① Xu Maozhi① Hu Zhi② Hou Ying③ |
①(School of Mathematical Sciences, Peking University, Beijing 100871, China)
②(School of Mathematics and Statistics, Central South University, Changsha 410083, China)
③(Department of Compute Science and Technology, Tsinghua University, Beijing 100084, China) |
|
|
|
|
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.
|
|
Received: 29 March 2017
Published: 08 November 2017
|
|
|
| Fund:The National Natural Science Foundation of China (61272499, 61472016, 61672059, 61602526), The National Key R&D Program of China (2017YFB0802000) |
|
Corresponding Authors:
Xu Maozhi
E-mail: mzxu@pku.edu.cn
|
|
|
|
| [1] |
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.
|
| [2] |
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.
|
| [3] |
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.
|
| [4] |
PATERSON K G. ID-based signatures from pairings on elliptic curves[J]. Electronics Letters, 2002, 38(18): 1025-1026.
|
| [5] |
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.
|
| [6] |
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.
|
| [7] |
FOTIADIS G and KONSTANTINOU E. More sparse families of pairing-friendly elliptic curves[C]. Cryptology and Network Security, Springer International Publishing, 2014: 384-399.
|
| [8] |
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.
|
| [9] |
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.
|
| [11] |
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.
|
| [12] |
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.
|
| [13] |
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.
|
| [14] |
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.
|
| [15] |
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.
|
| [16] |
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.
|
| [17] |
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.
|
| [18] |
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.
|
| [19] |
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.
|
| [20] |
FOTIADIS G and KONSTANTINOU E. On the efficient generation of generalized MNT elliptic curves[C]. Algebraic Informatics, Springer Berlin Heidelberg, 2013: 147-159.
|
|
|
|
