構造小嵌入次數(shù)的橢圓曲線參數(shù)化族

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

doi:10.11999/JEIT170261

構造小嵌入次數(shù)的橢圓曲線參數(shù)化族

doi: 10.11999/JEIT170261

1.
(北京大學數(shù)學科學學院北京 100871)
2.
(中南大學數(shù)學與統(tǒng)計學院長沙 410083)
3.
(清華大學計算機科學與技術系北京 100084)

基金項目:

國家自然科學基金(61272499, 61472016, 61672059, 61602526)，國家重點研發(fā)計劃資助(2017YFB0802000)

計量
- 文章訪問數(shù): 1222
- HTML全文瀏覽量: 152
- PDF下載量: 143
- 被引次數(shù): 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)

摘要

摘要: 配對友好橢圓曲線在基于配對的密碼系統(tǒng)中起關鍵作用。這類曲線的構造不僅極大影響實現(xiàn)效率，更關系到系統(tǒng)安全。雖然目前已提出很多構造方法，但幾乎都依賴窮盡搜索。該文提出一種構造該類曲線的系統(tǒng)方法，將尋找配對友好曲線問題轉(zhuǎn)化到解方程，從而避免了窮盡搜索，并設計出具體算法。最后，將該算法應用到尋找嵌入次數(shù)為5,8,10和12的配對友好曲線中，發(fā)現(xiàn)所有類型的橢圓曲線族都可由該方法統(tǒng)一得到，包括完全族、可變判別式的完全族和稀疏族。特別地，還找到了新的橢圓曲線族。
- 基于配對的密碼 /
- 橢圓曲線 /
- 配對友好曲線 /
- 參數(shù)化族
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)

訪問統(tǒng)計