构造小嵌入次数的椭圆曲线参数化族

张猛; 徐茂智; 胡志; 侯英

doi:10.11999/JEIT170261

构造小嵌入次数的椭圆曲线参数化族

doi: 10.11999/JEIT170261

1.
(北京大学数学科学学院北京 100871)
2.
(中南大学数学与统计学院长沙 410083)
3.
(清华大学计算机科学与技术系北京 100084)

基金项目:

国家自然科学基金(61272499, 61472016, 61672059, 61602526)，国家重点研发计划资助(2017YFB0802000)

计量
- 文章访问数: 1157
- HTML全文浏览量: 142
- PDF下载量: 143
- 被引次数: 0
出版历程
- 收稿日期: 2017-03-29
- 修回日期: 2017-10-20
- 刊出日期: 2018-01-19

On Parameterized Families of Elliptic Curves with Low Embedding Degrees

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)

摘要

摘要: 配对友好椭圆曲线在基于配对的密码系统中起关键作用。这类曲线的构造不仅极大影响实现效率，更关系到系统安全。虽然目前已提出很多构造方法，但几乎都依赖穷尽搜索。该文提出一种构造该类曲线的系统方法，将寻找配对友好曲线问题转化到解方程，从而避免了穷尽搜索，并设计出具体算法。最后，将该算法应用到寻找嵌入次数为5,8,10和12的配对友好曲线中，发现所有类型的椭圆曲线族都可由该方法统一得到，包括完全族、可变判别式的完全族和稀疏族。特别地，还找到了新的椭圆曲线族。
- 基于配对的密码 /
- 椭圆曲线 /
- 配对友好曲线 /
- 参数化族
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

HTML全文

参考文献(19)

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.

施引文献

资源附件(0)

访问统计