双线性对的快速计算研究
|
摘要
基于身份的密码体制是现代密码学的一个研究热点，它降低了公钥密码系统中可信第三方管理公钥证书的复杂度。目前许多基于身份的密码方案都使用了椭圆曲线上的双线性对。为了使这些方案能够在工程实践中应用，对选取的椭圆曲线提出了一些限制：(1)为了保证系统的安全性，要求选取的椭圆曲线具有一个大素数阶的子群并且双线性对所映射到的有限域扩域应足够大，一般不能小于960比特；(2)从系统的计算效率考虑，要求双线性对所映射到的有限域扩域的阶应足够小。为了满足前述的两个条件，要求椭圆曲线具有适宜的嵌入次数。
超奇异椭圆曲线的嵌入次数≤6，但它们的群结构比较简单，存在易受攻击的风险。为了提高系统的安全级别，通常会采用非超奇异椭圆曲线。但具有较小嵌入次数的非超奇异椭圆曲线很稀少，很难通过随机选取的方式寻找到，需要设计专门的方法来构造。目前在能有效构造具有较小嵌入次数的非超奇异椭圆曲线的方法中，分圆多项式与有理多项式的合成多项式的可约分性起着重要的作用。但可约分的合成多项式的分布很稀疏。
在基于身份的密码体制中，双线性对的计算决定着整个系统的效率。通常采用Miller算法来计算双线性对。在Miller算法中许多运算在有限域的扩域中进行，为了提高计算效率，应尽量减少扩域中的乘法运算和求逆运算的次数。
论文对分圆多项式与有理多项式的合成多项式的可约分性，双线性对的快速计算以及多核处理器环境下双线性对的并行计算进行了研究，取得以下主要结果。
(1)给出了分圆多项式与有理多项式的合成多项式可约分的充分必要条件。根据这个充要条件，提出了一种通过构造分圆域的单代数扩域，然后利用本原元定理来构造可约分的分圆多项式与有理多项式的合成多项式的方法。该方法可以构造出所有使满足条件的有理多项式。
(2)分析了双线性对计算中所利用的循环控制多项式的性质。在这个结论的基础上，给出了构造适合于双线性对计算的非超奇异椭圆曲线时，选取适宜的椭圆曲线参数的方法。还给出了利用分圆多项式与有理多项式的合成多项式的不可约分因子来生成适合于双线性对计算的非超奇异椭圆曲线，并运用Miller算法来计算Atei对时，循环次数达到理论下限的充要条件。
(3)通过利用新Miller公式，改进了基于双重基链的Tate对计算方法，大大减少了二倍乘运算和三倍乘运算的计算量。改进的方法与原方法比效率提高了约23%。
(4)提出一种通过构造具有一个阶为Proth型素数的子群的椭圆曲线来优化双线性对计算的方法。该方法减少了运用Miller算法计算双线性对时所需的加法运算的次数，而同时未降低子群阶的汉明重量，保证了系统的安全性。
(5)将从右至左重复加倍和加方法推广到双线性对的计算中。在Miller算法中采用从右至左的计算结构，使得在同一轮循环中加法运算和二倍乘算不相关，从而可以利用处理器的两个核来并行计算Tate对。
(6)提出对Miller算法中的循环控制参数进行分解，从而将Miller公式分解为三个不相关的部分，然后利用多核处理器的三个不同的核来并行计算不相关的三个分量。为了平衡各个核的计算量，提出了两种方法：一种利用椭圆曲线上的有效自同态；另一种利用预计算。
Identity-based cryptography is an active research area in modern cryptography. It has re-duced the complexity of certificate management of the certificate authority in public-key cryp-tosystem. Currently, many identity-based protocols use the bilinear pairing on elliptic curves.To make these protocols practical, the elliptic curves which are suitable for pairing applicationmust have some specially properties.(1) For the security of the cryptosystem, it requires thatthe elliptic curve has a subgroup of large prime order and the extension field which the bilinearpairing maps to is large enough;(2) For the efciency of the cryptosystem, it requires the ex-tension field which the bilinear pairing maps to must be small enough. In order to meet theserequirements, it requires the selected elliptic curves must have suitable embedding degree.
The embedding degree of supersingular elliptic curves is≤6. Because of the simplicityof the group structure of supersingular elliptic curve, it may be vulnerable. To improve thesecurity level, we turn to ordinary elliptic curve. However, ordinary elliptic curves with smallembedding degree are very rare. They are hard to be found by randomly selection. So it needsto design special method to construct these curves. The composition of rational polynomialand cyclotomic polynomial which is factorable plays an important role in constructing ordinaryelliptic curve with small embedding degree. But these rational polynomials distribute sparsely.
In identity-based cryptosystem, the computation of bilinear pairing plays a key role inthe performance of the cryptosystem. Usually, it uses Miller’s algorithm to compute bilinearpairing. In Miller’s algorithm many operations are done in extension field. To improve theefciency, it must reduce the number of multiply operation and inversion operation in extensionfield.
This paper discusses constructing the composition of rational polynomial and cyclotomicpolynomial which is factorable, fast computation of Tate pairing and parallel computation ofTate pairing. The main results of this paper are as follows.
(1) We give the sufcient and necessary condition for the reducibility of the composition ofrational polynomial and cyclotomic polynomial. Based on this sufcient and necessarycondition, we present a method to construct composition of rational polynomial and cyclo-tomic polynomial which is reduceable. It constructed a simple extension of the cyclotomicfield and used the primitive element theorem to generate the polynomial with desired prop-erty. This method can construct all polynomials which satisfy the special condition.
(2) We analysis the property of loop control polynomial in Miller’s algorithm. Based on thisresult, we give a method to select elliptic curve parameters when constructing pairing-friendly elliptic curves.
(3) In order to improve the performance of the Tate pairing computation method which isbased double-base chain, we use new Miller formula. It reduced the number of doublingoperation and tripling operation evidently. Compared with the original method, it has again about23%.
(4) We present a method to speed up the computation of Tate pairing by constructing ellipticcurve with a subgroup whose order is a proth form prime. It reduced the number of additionoperation in Miller’s algorithm. By the same time, it has not lower the hamming weight ofthe subgroup order which guarantees the security level.
(5) We extend the right-to-left binary method to pairing computation. Using the right-to-leftstructure in Miller’s algorithm, the addition operation and the doubling operation in thesame loop are uncorrelated. Thus it can use two cores of the multi-core processor to com-pute Tate pairing parallelly.
(6) By decomposing the loop controlling parameter in Miller’s algorithm, we split the Millerformula into three uncorrelated parts. Then these parts can be computed by three diferentcores of multi-core processor. To balance the computational load between cores, we taketwo approaches: one is using the efciently computable endomorphism on elliptic curve,the other is using precomputation.
超奇异椭圆曲线的嵌入次数≤6，但它们的群结构比较简单，存在易受攻击的风险。为了提高系统的安全级别，通常会采用非超奇异椭圆曲线。但具有较小嵌入次数的非超奇异椭圆曲线很稀少，很难通过随机选取的方式寻找到，需要设计专门的方法来构造。目前在能有效构造具有较小嵌入次数的非超奇异椭圆曲线的方法中，分圆多项式与有理多项式的合成多项式的可约分性起着重要的作用。但可约分的合成多项式的分布很稀疏。
在基于身份的密码体制中，双线性对的计算决定着整个系统的效率。通常采用Miller算法来计算双线性对。在Miller算法中许多运算在有限域的扩域中进行，为了提高计算效率，应尽量减少扩域中的乘法运算和求逆运算的次数。
论文对分圆多项式与有理多项式的合成多项式的可约分性，双线性对的快速计算以及多核处理器环境下双线性对的并行计算进行了研究，取得以下主要结果。
(1)给出了分圆多项式与有理多项式的合成多项式可约分的充分必要条件。根据这个充要条件，提出了一种通过构造分圆域的单代数扩域，然后利用本原元定理来构造可约分的分圆多项式与有理多项式的合成多项式的方法。该方法可以构造出所有使满足条件的有理多项式。
(2)分析了双线性对计算中所利用的循环控制多项式的性质。在这个结论的基础上，给出了构造适合于双线性对计算的非超奇异椭圆曲线时，选取适宜的椭圆曲线参数的方法。还给出了利用分圆多项式与有理多项式的合成多项式的不可约分因子来生成适合于双线性对计算的非超奇异椭圆曲线，并运用Miller算法来计算Atei对时，循环次数达到理论下限的充要条件。
(3)通过利用新Miller公式，改进了基于双重基链的Tate对计算方法，大大减少了二倍乘运算和三倍乘运算的计算量。改进的方法与原方法比效率提高了约23%。
(4)提出一种通过构造具有一个阶为Proth型素数的子群的椭圆曲线来优化双线性对计算的方法。该方法减少了运用Miller算法计算双线性对时所需的加法运算的次数，而同时未降低子群阶的汉明重量，保证了系统的安全性。
(5)将从右至左重复加倍和加方法推广到双线性对的计算中。在Miller算法中采用从右至左的计算结构，使得在同一轮循环中加法运算和二倍乘算不相关，从而可以利用处理器的两个核来并行计算Tate对。
(6)提出对Miller算法中的循环控制参数进行分解，从而将Miller公式分解为三个不相关的部分，然后利用多核处理器的三个不同的核来并行计算不相关的三个分量。为了平衡各个核的计算量，提出了两种方法：一种利用椭圆曲线上的有效自同态；另一种利用预计算。
Identity-based cryptography is an active research area in modern cryptography. It has re-duced the complexity of certificate management of the certificate authority in public-key cryp-tosystem. Currently, many identity-based protocols use the bilinear pairing on elliptic curves.To make these protocols practical, the elliptic curves which are suitable for pairing applicationmust have some specially properties.(1) For the security of the cryptosystem, it requires thatthe elliptic curve has a subgroup of large prime order and the extension field which the bilinearpairing maps to is large enough;(2) For the efciency of the cryptosystem, it requires the ex-tension field which the bilinear pairing maps to must be small enough. In order to meet theserequirements, it requires the selected elliptic curves must have suitable embedding degree.
The embedding degree of supersingular elliptic curves is≤6. Because of the simplicityof the group structure of supersingular elliptic curve, it may be vulnerable. To improve thesecurity level, we turn to ordinary elliptic curve. However, ordinary elliptic curves with smallembedding degree are very rare. They are hard to be found by randomly selection. So it needsto design special method to construct these curves. The composition of rational polynomialand cyclotomic polynomial which is factorable plays an important role in constructing ordinaryelliptic curve with small embedding degree. But these rational polynomials distribute sparsely.
In identity-based cryptosystem, the computation of bilinear pairing plays a key role inthe performance of the cryptosystem. Usually, it uses Miller’s algorithm to compute bilinearpairing. In Miller’s algorithm many operations are done in extension field. To improve theefciency, it must reduce the number of multiply operation and inversion operation in extensionfield.
This paper discusses constructing the composition of rational polynomial and cyclotomicpolynomial which is factorable, fast computation of Tate pairing and parallel computation ofTate pairing. The main results of this paper are as follows.
(1) We give the sufcient and necessary condition for the reducibility of the composition ofrational polynomial and cyclotomic polynomial. Based on this sufcient and necessarycondition, we present a method to construct composition of rational polynomial and cyclo-tomic polynomial which is reduceable. It constructed a simple extension of the cyclotomicfield and used the primitive element theorem to generate the polynomial with desired prop-erty. This method can construct all polynomials which satisfy the special condition.
(2) We analysis the property of loop control polynomial in Miller’s algorithm. Based on thisresult, we give a method to select elliptic curve parameters when constructing pairing-friendly elliptic curves.
(3) In order to improve the performance of the Tate pairing computation method which isbased double-base chain, we use new Miller formula. It reduced the number of doublingoperation and tripling operation evidently. Compared with the original method, it has again about23%.
(4) We present a method to speed up the computation of Tate pairing by constructing ellipticcurve with a subgroup whose order is a proth form prime. It reduced the number of additionoperation in Miller’s algorithm. By the same time, it has not lower the hamming weight ofthe subgroup order which guarantees the security level.
(5) We extend the right-to-left binary method to pairing computation. Using the right-to-leftstructure in Miller’s algorithm, the addition operation and the doubling operation in thesame loop are uncorrelated. Thus it can use two cores of the multi-core processor to com-pute Tate pairing parallelly.
(6) By decomposing the loop controlling parameter in Miller’s algorithm, we split the Millerformula into three uncorrelated parts. Then these parts can be computed by three diferentcores of multi-core processor. To balance the computational load between cores, we taketwo approaches: one is using the efciently computable endomorphism on elliptic curve,the other is using precomputation.
引文
[1] Brezing F, Weng A. Elliptic Curves Suitable for Pairing Based Cryptography. Designs,Codes and Cryptography.2005,37(1).133-141.
[2] Boxall J, Mrabet N E, Laguillaumie F, Le D P. A Variant of Miller’s Formula and Algo-rithm. Pairing-Based Cryptography-Pairing2010, LNCS6487. Berlin: Springer-Verlag,2010.417-434.
[3] Hankerson D, Menezes A J and Vanstone S. Guide to Elliptic Curve Cryptography.Springer-Verlag,2004.
[4] Goldreich O. Foundations of Cryptography-Volume I (Basic Tools). Cambridge Univer-sity Press,2001.
[5] Goldreich O. Foundations of Cryptography-Volume II (Basic Applications). CambridgeUniversity Press,2004.
[6]冯登国译.密码学原理与实践.第三版.北京:电子工业出版社,2009.
[7] Dife W, Hellman M E. New directions in cryptography. IEEE Transactions on Informa-tion Theory,1976,22(6):644-654.
[8] Shannon C. Communication Theory of Secrecy Systems. Bell System Technical Journal.1949,28(4).656–715.
[9] RSA Laboratories. Block Ciphers. RSA Laboratories Technical Report TR-601Version2.0,1995.
[10]杨波.现代密码学.第一版.北京:清华大学出版社,2003.
[11]李毅超，蔡洪斌，谭浩，秦志光，杨义先译.信息安全原理与应用.第四版.北京:电子工业出版社,2007.
[12]卢开澄.计算机密码学―计算机网络中的数据保密与安全.第三版.北京:清华大学出版社,2003.
[13]孟庆树，王丽娜，傅建明，张焕国译.密码编码学与网络安全―原理与实践.第四版.北京:电子工业出版社,2006.
[14] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.1978,21(2).120-126.
[15] El Gamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Log-arithms. Advances in Cryptology-CRYPTO1984, LNCS196. Berlin: Springer-Verlag,1984.10-18.
[16] Miller V S. Use of Elliptic Curves in Cryptography. Advances in Cryptology-CRYPTO1985, LNCS218. Berlin: Springer-Verlag,1985.417-426.
[17] Koblitz N. Elliptic Curve Cryptosystems. Mathematics of Computation.1987,48.203-209.
[18] Koblitz N. Hyperelliptic cryptosystems. Journal of Cryptology.1989,1(3).139-150.
[19] Hofstein J, Pipher J, Silverman J H. NTRU: A Ring-Based Public Key Cryptosystem. Al-gorithmic number theory Symposium-ANTS-III, LNCS1423. Berlin: Springer-Verlag,1998.267-288.
[20] Hofstein J, Pipher J, Silverman J H. An Introduction to Mathematical Cryptography.Springer-Verlag,2008.
[21] Koblitz N. A Course In Number Theory And Cryptography. Second edition. Springer-Verlag,1994.
[22] Koblitz N, Menezes A, Wu Y H, Zuccherato R J. Algebraic aspects of cryptography.Springer-Verlag,1999.
[23] Garrett P. Making, Breaking Codes: An Introduction to Cryptology. Prentice-Hall,2001.
[24] Mao W B. Modem Cryptography: Theory and Practice. Prentice-Hall,2003.
[25] Schneier B. Applied Cryptography. Second edition. John Wiley&Sons,1996.
[26] Denis T S, Rose G. BigNum Math: Implementing Cryptographic Multiple PrecisionArithmetic. Syngress Publishing,2006.
[27] Denis T S, Johnson S. Cryptography for Developers. Syngress Publishing,2007.
[28] Welschenbach M. Cryptography in C and C++. Second edition. Apress,2005.
[29]张方国，陈晓峰.基于身份的密码体制的研究综述.中国密码学发展报告2008.北京:电子工业出版社,2009.1-31.
[30] Shamir A. Identity-Based Cryptosystems and Signature Schemes. Advances inCryptology-CRYPTO1984, LNCS196. Berlin: Springer-Verlag,1984.47-53.
[31] Boneh D, Franklin M. Identity-based encryption from the weil pairing. SIAM Journal ofComputing.2003,32(206).586-615.
[32] Sakai R, Ohgishi K, Kasahara M. Cryptosystems based on pairing over elliptic curve.Symposium on Cryptography and Information Security,2001.
[33] Cocks C. An Identity Based Encryption Scheme Based on Quadratic Residues. Proceed-ings of the8th IMA International Conference on Cryptography and Coding, LNCS2260.Berlin: Springer-Verlag,2001.360-363.
[34] Freeman D, Scott M and Teske E. A Taxonomy of Pairing-Friendly Elliptic Curves. Jour-nal of Cryptology.2010,23(2).224-280.
[35] Galbraith S D. Pairings. Advances in Elliptic Curve Cryptography. Cambridge UniversityPress,2005.
[36] Menezes A, Okamoto T and Vanstone S A. Reducing Elliptic Curve Logarithms to Log-arithms in a Finite Field. IEEE Transactions on Information Theory.1993,39(5).1639-1646.
[37] Frey G, Ru¨ck H-G. A remark concerning m-divisibility and the discrete logarithm in thedivisor class group of curves. Mathematics of Computation.1994,62(206).865-874.
[38] Odlyzko A. Discrete Logarithms: The Past and the Future. Designs, Codes and Cryptog-raphy.2000,19(2-3).129-145.
[39] Husemo¨ler D. Elliptic Curves. Second edition. Springer-Verlag,2004.
[40] Schoof R. Nonsingular plane cubic curves over finite fields. Journal of CombinatorialTheory.1987,46(2).183-211.
[41] Waterhouse W. Abelian varieties over finite fields. Annales Scientifiques de l’écoleNormale Supérieure.1969,2(4).521-560.
[42] Balasubramanian R, Koblitz N. The Improbability That an Elliptic Curve Has Subexpo-nential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm. Journalof Cryptology.1998,11(2).141-145.
[43] Luca F, Shparlinski I. Elliptic curves with low embedding degree. Journal of cryptology.2006,19(4).553-562.
[44] Pohlig S, Hellman M. An improved algorithm for computing logarithms over GF(p) andits cryptographic significance. IEEE Transactions on Information Theory.1978,24(1).106-110.
[45] Silverman J H. The Arithmetic of Elliptic Curves. Second edition. Springer-Verlag,2009.
[46] Atkin A O L, Morain F. Elliptic curves and primality proving. Mathematics of Computa-tion.1993,61(203).39-68.
[47] Boneh D, Lynn B and Shacham H. Short signatures from the weil pairing. Advances inCryptology-ASIACRYPT2001, LNCS2248. Berlin: Springer-Verlag,2002.514-532.
[48] Joux A. A one round protocol for tripartite dife-hellman. Journal of Cryptology.2004,17(4).263-276.
[49] Paterson K G. Id-based signatures from pairings on elliptic curves. Electronics Let-ters.2002,38(18).1025-1026.
[50] Miller V S. The Weil Pairing and its Efcient Calculation. Journal of Cryptology.2004,17(4).235-261.
[51] Stange K. The Tate Pairing Via Elliptic Nets. Pairing-Based Cryptography-Pairing2007,LNCS4575. Berlin: Springer-Verlag,2007.329-384.
[52]赵昌安，张方国.双线性对有效计算研究进展述.软件学报.2009,20(11).3001-3009.
[53] Shipsey R. Elliptic Divibility Sequences. Ph.D dissertation, University of London,2001.
[54] Ward M. Memoir on elliptic divisibility sequences. American Journal of Mathematics.1948,70(1).31-74.
[55] Barreto P S L M, Galbraith S D,O′hE′igeartaigh C O, Scott M. Efcient pairing compu-tation onsupersingular abelian varieties. Designs, Codes and Cryptography.2007,42(3).239-271.
[56] Hess F, Smart N P, Vercauteren F. The Eta Pairing Revisited. IEEE Transactions on In-formation Theory.2006,52(10).4595-4602.
[57] Lee E, Lee H S, Park C M. Efcient and generalized pairing computation on abelianvarieties. IEEE Transactions on Information Theory.2009,55(4).1793-1803.
[58] Freeman D. Constructing Abelian Varieties for Pairing-Based Cryptography. Ph.D dis-sertation, Harvard University,2008.
[59] Lynn B. On the Implementation of Pairing-Based Cryptosystems. Ph.D. Dissertation,Stanford University,2007.
[60] Sto¨gbauer M. Efcient Algorithms for Pairing-Based Cryptosystems. Ph.D. Dissertation,Darmstadt University of Technology,2004.
[61]崔巍.基于双线性对的数字签名体制研究和设计.北京邮电大学博士论文，2009.
[62]林惜斌.椭圆曲线密码中标量乘与双线性对的快速算法研究.中山大学博士论文，2009.
[63]吴宏锋.椭圆曲线密码中的点乘与双线性对的计算.北京大学博士论文，2008.
[64]辛向军.几种具有附加性质的数字签名体制的研究.西安电子科技大学博士论文，2008.
[65]杨晨.基于双线性对的密码协议的设计与分析.西安电子科技大学博士论文，2008.
[66]赵昌安.双线性对的有效计算.中山大学博士论文，2008.
[67] Miyaji A, Nakabayashi M, Takano S. New explicit conditions of elliptic curve traces forFR-reduction. IEICE transactions on fundamentals of electronics, communications andcomputer sciences.2001, E84-A(5).1234-1243.
[68]柯召，孙琦.数论讲义.第二版.北京:高等教育出版社,2003.
[69] Page D, Smart N P, Vercauteren F. A comparison of MNT curves and supersingu-lar curves. Applicable Algebra in Engineering, Communication and Computing.2006,17(5).1025-1026.
[70] Scott M, Barreto P S L M. Generating More MNT Elliptic Curves. Designs, Codes andCryptography.2006,38(2).209-217.
[71] Galbraith S D, McKee J F, Valenc a P C. Ordinary abelian varieties having small embed-ding degree. Finite Fields and Their Applications.2007,13(4).800-814.
[72] Freeman D. Constructing Pairing-Friendly Elliptic Curves with Embedding Degree10.Algorithmic Number Theory Symposium-ANTS-VII, LNCS4076. Berlin: Springer-Verlag,2006.452-465.
[73] Barreto P S L M, Naehrig M. Pairing-Friendly Elliptic Curves of Prime Order. SelectedAreas in Cryptography-SAC2005, LNCS3897. Berlin: Springer-Verlag,2006.319-331.
[74] Beuchat J L, Diaz J E G, Mitsunari S, Okamoto E, Rodriguez-Henriquez F, Teruya T.High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-NaehrigCurves. Pairing-Based Cryptography-Pairing2010, LNCS6487. Berlin: Springer-Verlag,2010.21-39.
[75] Devegili A J, Scott M, Dahab R. Implementing Cryptographic Pairings over Barreto-Naehrig Curves. Pairing-Based Cryptography-Pairing2007, LNCS4575. Berlin:Springer-Verlag,2007.197-207.
[76] Fan J F, Vercauteren F, Verbauwhede I. Faster Fp-arithmetic for Cryptographic Pairingson Barreto-Naehrig Curves. Cryptographic Hardware and Embedded Systems-CHES2009, LNCS5747. Berlin: Springer-Verlag,2009.240-253.
[77] Masataka A, Yasuyuki N, Yoshitaka M. Fast Ate Pairing Computation of EmbeddingDegree12Using Subfield-Twisted Elliptic Curve. IEICE Transactions on Fundamentalsof Electronics, Communications and Computer Sciences.2009. E92-A(2).508-516.
[78] Sakemi Y, Nogami Y, Kato H, Morikawa Y. Cross twisted Xate pairing with Barreto-Naehrig curve for multi-pairing technique. Proceedings of the2009IEEE internationalconference on Symposium on Information Theory-ISIT’09,2009.2386-2390.
[79] Sakemi Y, Kato H, Takeuchi S, Nogami Y, Morikawa Y. Two Improvements of TwistedAte Pairing with Barreto-Naehrig Curve by Dividing Miller’s Algorithm. Advances inInformation Sciences and Service Sciences.2010,2(4).1-13.
[80] Dupont R, Enge A, Morain F. Building Curves with Arbitrary Small MOV Degree overFinite Prime Fields. Journal of Cryptology.2005,18(2).79-89.
[81]张禾瑞，郝鈵新.高等代数.第四版.北京:高等教育出版社，1999.
[82] Barreto P S L M, Lynn B, Scott M. Constructing Elliptic Curves with Prescribed Embed-ding Degrees. Proceedings of the3rd international conference on Security in communi-cation networks-SCN2002, LNCS2576. Berlin: Springer-Verlag,2002.263-273.
[83] Duursma I, Lee H S. Tate pairing implementation for hyperelliptic curves y2=xp x+d. Advances in Cryptology-ASIACRYPT2003, LNCS2894. Berlin: Springer-Verlag,2003.111-123.
[84] Matsuda S, Kanayama N, Hess F, Okamoto E. Optimised Versions of the Ate and TwistedAte Pairings. The11th IMA International Conference on Cryptography and Coding,LNCS4887. Berlin: Springer-Verlag,2007.302-312.
[85] Zhao C A, Zhang F G, Huang J W. A note on the Ate pairing. International Journal ofInformation Security.2008,7(6).379-382.
[86] Vercauteren F. Optimal pairings. IEEE Transactions on Information Theory.2010,56(1).455-461.
[87] Galbraith S D, Harrison K, Soldera D. Implementing the tate pairing. Algorithmic Num-ber Theory Symposium-ANTS-V, LNCS2369. Berlin: Springer-Verlag,2002.69-86.
[88] Eisentra¨ger K, Lauter K, Montgomery P L. Fast elliptic curve arithmetic and improvedWeil pairing evaluation. CT-RSA2003, LNCS2612. Berlin: Springer-Verlag,2003.343-354.
[89] Blake I, Murty K, Xu G. Refinements of miller’s algorithm for computing weil/tate pair-ing. Journal of Algorithms.2006,58(2).134-149.
[90] Eisentra¨ger K, Lauter K, Montgomery P L. Improved Weil and Tate Pairings for Ellipticand Hyperelliptic Curves. Algorithmic Number Theory Symposium-ANTS-VI, LNCS3076. Berlin: Springer-Verlag,2004.169-183.
[91] Kobayashi T, Aoki K, Imai H. Efcient algorithms for Tate pairing. IEICE Transactionson Fundamentals of Electronics, Communications and Computer Sciences.2006, E89-A(1).134-143.
[92] Zhao C A, Zhang F G, Huang J W. Efcient Tate pairing computation using double-basechains. Science in China Series F: Information Sciences.2008,51(8).1096-1105.
[93] Scott M. Faster pairings using an elliptic curve with an efcient endomorphism. Progressin Cryptology-INDOCRYPT2005, LNCS3797. Berlin: Springer-Verlag,2005.258-269.
[94] Ionica S, Joux A. Pairing computation on elliptic curves with efciently computable en-domorphism and small embedding degree. Pairing-Based Cryptography-Pairing2010,LNCS6487. Berlin: Springer-Verlag,2010.435-449.
[95] Scott M, Benger N, Charlemagne M, Perez L J D, Kachisa E J. On the Final Exponenti-ation for Calculating Pairings on Ordinary Elliptic Curves. Pairing-Based Cryptography-Pairing2009, LNCS5671. Berlin: Springer-Verlag,2009.78-88.
[96] Lin X B, Zhao C A, Zhang F G, Wang Y M. Computing the Ate Pairing on Elliptic Curveswith Embedding Degree k=9. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences.2008. E91-A(9).2387-2393.
[97] Barreto P S L M, Lynn B, Scott M. On the selection of pairing-friendly groups. SelectedAreas in Cryptography-SAC’2003, LNCS3006. Berlin: Springer-Verlag,2003.17-25.
[98] Galbraith S D, Paterson K, Smart N. Pairings for cryptographers. Discrete Applied Math-ematics.2008,156(16).3113-3121.
[99] Granger R, Paterson K, Smart N. High security pairing-based cryptography revisited.Algorithmic Number Theory Symposium-ANTS-VII, LNCS4076. Berlin: Springer-Verlag,2006.480-494.
[100] Hitt L. On the minimal embedding field. Pairing-Based Cryptography-Pairing2007,LNCS4575. Berlin: Springer-Verlag,2007.294-301.
[101] Koblitz N, Menezes A. Pairing-based cryptography at high security levels. Cryptographyand Coding:10th IMA International Conference, LNCS3796. Berlin: Springer-Verlag,2005.13-36.
[102] Scott M. Computing the Tate pairing. The Cryptographer’s Track at RSA Conference-CT-RSA2005, LNCS3376. Berlin: Springer-Verlag,2005.293-304.
[103] Harrison K, Page D, Smart N P. Software implementation of finite fields of characteristicthree, for use in pairing-based cryptosystems. LMS Journal of Computation and Mathe-matics.2002,5.181-193.
[104] Naehrig M, Niederhagen R, Schwabe P. New software speed records for cryptographicpairings. Progress in cryptology: cryptology and information security in Latin America-LATINCRYPT’10, LNCS6212. Berlin: Springer-Verlag,2010.109-123.
[105] Perez L J D, Kachisa E J, Scott M. Implementing cryptographic pairings: a magmatutorial. IACR Cryptology ePrint Archive, Report2009/072,2009. Available fromhttp://eprint.iacr.org/2009/072.
[106] Scott M, Costigan N, Abdulwahab W. Implementing Cryptographic Pairings on Smart-cards. Cryptographic Hardware and Embedded Systems-CHES2006, LNCS4249.Berlin: Springer-Verlag,2006.134-147.
[107] Kocher P C. Timing Attacks on Implementations of Dife-Hellman, RSA, DSS, andOther Systems. Advances in Cryptology-CRYPTO1996, LNCS1109. Berlin: Springer-Verlag,1996.104-113.
[108] Kocher P C, Jafe J, Jun B. Diferential Power Analysis. Advances in Cryptology-CRYPTO1999, LNCS2139. Berlin: Springer-Verlag,1996.388-397.
[109] El Mrabet N, Flottes M L, Di Natale G. A practical Diferential Power Analysis attackagainst the Miller algorithm. The5th International Conference on Ph.D. Research inMicroelectronics&Electronics-PRIME2009,2009.308-311.
[110] Ghosh S, Mukhopadhyay D, Chowdhury D R. Fault Attack and Countermeasures onPairing Based Cryptography. International Journal of Network Security.2011,12(1).21-28.
[111] Kim T H, Takagi T, Han D-G, Kim H W, Lim J. Side Channel Attacks and Counter-measures on Pairing Based Cryptosystems over Binary Fields. Cryptology and NetworkSecurity-CANS2006, LNCS4301. Berlin: Springer-Verlag,2006.168-181.
[112] Ozturk E. Efcient and Tamper-Resilient Architectures for Pairing Based Cryptography.Ph.D dissertation, Worcester Polytechnic Institute,2009.
[113] Page D. Vercauteren F. A Fault Attack on Pairing-Based Cryptography. IEEE Transac-tions on Computers.2006,55(9).1075-1080.
[114] PBC. The Pairing-Based Cryptography Library. Available fromhttp://crypto.stanford.edu/pbc/.
[115] MIRACL. Multiprecision Integer and Rational Arithmetic C/C++Library. Availablefrom http://www.shamus.ie/.
[116] Ash R B. Abstract Algebra: The Basic Graduate Year. Available fromhttp://www.math.uiuc.edu/r-ash/Algebra.html.
[117]范德瓦尔登.代数学I.北京:科学出版社,1978.
[118]聂灵沼，丁石孙.代数学引论.第二版.北京:高等教育出版社,2000.
[119]万哲先.代数和编码.第三版.北京:高等教育出版社,2007.
[120]张禾瑞.近世代数基础.修订本.北京:高等教育出版社，2005.
[121] Blake I F, Seroussi G, Smart N P. Elliptic Curves in Cryptography. Cambridge UniversityPress,1999.
[122]裴定一，祝跃飞.算法数论.第一版.北京：科学出版社,2002.
[123]吴铤，董军武，王明强译.椭圆曲线及其在密码学中的应用―导引.北京：科学出版社,2007.
[124]周玉洁，冯登国.公开密钥密码算法及其快速实现.第一版.北京:国防工业出版社,2002.
[125]祝跃飞，张亚娟.椭圆曲线公钥密码导引.第一版.北京:科学出版社,2006.
[126] Washington L C. Elliptic Curves: Number Theory and Cryptography. Second edition.Chapman&Hall/CRC,2008.
[127] Lay G-J, Zimmer H G. Constructing elliptic curves with given group order over largefinite fields. Algorithmic Number Theory Symposium-ANTS-I, LNCS877. Berlin:Springer-Verlag,1994.452-465.
[128] Savas E, Schmidt T A, Koc C K. Generating Elliptic Curves of Prime Order. Third In-ternational Workshop on Cryptographic Hardware and Embedded Systems-CHES01,LNCS2162. Berlin: Springer-Verlag,2001.145-161.
[129] Cox D A. Primes of the Form x2+ny2: Fermat, Class Field Theory, and ComplexMultiplication. John Wiley&Sons,1989.
[130] Cohen H, Frey G (Editors). Handbook of Elliptic and Hyperelliptic Curve Cryptography.Chapman&Hall/CRC,2006.
[131] Martin L. Introduction to Identity-Based Encryption. Artech House,2008.
[132] Barreto P S L M, Kim H Y, Lynn B and Scott M. Efcient algorithms for pairing-basedcryptosystems. Advances in Cryptology-CRYPTO2002, LNCS2442. Berlin: Springer-Verlag,2002.354-369.
[133] Pollard J. Monte-Carlo methods for index computation mod p. Mathematics of Compu-tation.1978,32(143).918-924.
[134] Silverman J H. The Xedni Calculus and the Elliptic Curve Discrete Logarithm Problem.Designs, Codes and Cryptography.2000,20(1).5-40.
[135] Baier H. Efcient Algorithms for Generating Elliptic Curves over Finite Fields Suitablefor Use in Cryptography. Ph.D dissertation, Darmstadt University of Teetmology,2002．
[136] Bro¨ker R. Constructing elliptic curves of prescribed order. Ph.D dissertation, Leiden Uni-versity,2006.
[137] Lang S. Algebra. Revised Third edition. Springer-Verlag,2002.
[138] Lidl R, Niederreiter H. Finite Fields. Second edition. Cambridge University Press,1997.
[139] McEliece R J. Finite Fields for Computer Scientists and Engineers. Springer-Verlag,1987.
[140] Washington L C. Introduction to Cyclotomic Fields. Second edition. Springer-Verlag,1997.
[141]华罗庚.数论导引.第一版.北京:科学出版社,1957.
[142] Comuta A, Kawazoe M, Takaharashi T. Pairing-friendly elliptic curves with small se-curity loss by Cheon’s algorithm. Proceedings of the10th international conference onInformation security and cryptology-ICISC’07, LNCS4817. Berlin: Springer-Verlag,2007.297-308.
[143] Duan P, Cui S, Chan C W. Special polynomial families for generating more suitablepairing-friendly elliptic curves. Proceedings of the5th WSEAS International Conferenceon Electronics, Hardware, Wireless and Optical Communications. Wisconsin: WorldScientific and Engineering Academy and Society (WSEAS),2006.187-192.
[144] Karabina K, Teske E. On prime-order elliptic curves with embedding degrees3,4and6. Algorithmic Number Theory Symposium-ANTS-VIII, LNCS5011. Berlin: Springer-Verlag,2008.102-117.
[145]冯克勤.代数数论.第一版.北京:科学出版社,2000.
[146]张贤科.代数数论导引.第二版.北京:高等教育出版社，2006.
[147] Gaa′l I, Robertson L. Power integral bases in prime-power cyclotomic fields. Journal ofNumber Theory.2006,120(2).372-384.
[148] Robertson L. Power Bases for Cyclotomic Integer Rings. Journal of Number Theory.1998,69(1).98-118.
[149] Gyo¨ry K. Sur les polyno mes a`coefcients entiers et de discriminant donne′, III, Publ.Math. Debrecen.1976,23.141-165.
[150] Robertson L. Power Bases for2-Power Cyclotomic Fields. Journal of Number Theory.2001,88(1).196-209.
[151] Kachisa E J, Schaefer E F and Scott M. Constructing Brezing-Weng pairing friendlyelliptic curves using elements in the cyclotomic field. Proceedings of Pairing-BasedCryptography-Pairing2008, LNCS5209. Berlin: Springer-Verlag,2008.126-135.
[152] Satoru T, Ken N. More constructing pairing-friendly elliptic curves forcryptography.Pairing-Based Cryptography-Pairing2008, LNCS5209. Berlin: Springer-Verlag,2008.136-145.
[153] Crandall R, Pomerance C. Prime Numbers: A Computational Perspective. Springer-Verlag,2005.
[154] Chang C C, Lou D C. Fast parallel computation of multi-exponentiation for public keycryptosystems. Proceedings of the Fourth IEEE International Conference on Parallel andDistributed Computing, Applications and Technologies (PDCAT),2003.955-958.
[155] Chiou C W. Parallel implementation of the RSA public-key cryptosystem. InternationalJournal of Computer Mathematics.1993,48(3).153-155.
[156] Gallant R P, Lambert R J and Vanstone S A. Faster point multiplication on elliptic curveswith efcient endomorphisms. Advances in Cryptology-CRYPTO2002, LNCS5209.Berlin: Springer-Verlag,2001.190-200.
[157] Cohen H. A course in computational algebraic number theory. Springer-Verlag,1993.
[158] Dimitrov V S, Imbert L, Mishra P K. Efcient and Secure Elliptic Curve Point Multipli-cation Using Double-Base Chains. Advances in Cryptology-ASIACRYPT2005, LNCS3788. Berlin: Springer-Verlag,2005.59-78.
[2] Boxall J, Mrabet N E, Laguillaumie F, Le D P. A Variant of Miller’s Formula and Algo-rithm. Pairing-Based Cryptography-Pairing2010, LNCS6487. Berlin: Springer-Verlag,2010.417-434.
[3] Hankerson D, Menezes A J and Vanstone S. Guide to Elliptic Curve Cryptography.Springer-Verlag,2004.
[4] Goldreich O. Foundations of Cryptography-Volume I (Basic Tools). Cambridge Univer-sity Press,2001.
[5] Goldreich O. Foundations of Cryptography-Volume II (Basic Applications). CambridgeUniversity Press,2004.
[6]冯登国译.密码学原理与实践.第三版.北京:电子工业出版社,2009.
[7] Dife W, Hellman M E. New directions in cryptography. IEEE Transactions on Informa-tion Theory,1976,22(6):644-654.
[8] Shannon C. Communication Theory of Secrecy Systems. Bell System Technical Journal.1949,28(4).656–715.
[9] RSA Laboratories. Block Ciphers. RSA Laboratories Technical Report TR-601Version2.0,1995.
[10]杨波.现代密码学.第一版.北京:清华大学出版社,2003.
[11]李毅超，蔡洪斌，谭浩，秦志光，杨义先译.信息安全原理与应用.第四版.北京:电子工业出版社,2007.
[12]卢开澄.计算机密码学―计算机网络中的数据保密与安全.第三版.北京:清华大学出版社,2003.
[13]孟庆树，王丽娜，傅建明，张焕国译.密码编码学与网络安全―原理与实践.第四版.北京:电子工业出版社,2006.
[14] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM.1978,21(2).120-126.
[15] El Gamal T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Log-arithms. Advances in Cryptology-CRYPTO1984, LNCS196. Berlin: Springer-Verlag,1984.10-18.
[16] Miller V S. Use of Elliptic Curves in Cryptography. Advances in Cryptology-CRYPTO1985, LNCS218. Berlin: Springer-Verlag,1985.417-426.
[17] Koblitz N. Elliptic Curve Cryptosystems. Mathematics of Computation.1987,48.203-209.
[18] Koblitz N. Hyperelliptic cryptosystems. Journal of Cryptology.1989,1(3).139-150.
[19] Hofstein J, Pipher J, Silverman J H. NTRU: A Ring-Based Public Key Cryptosystem. Al-gorithmic number theory Symposium-ANTS-III, LNCS1423. Berlin: Springer-Verlag,1998.267-288.
[20] Hofstein J, Pipher J, Silverman J H. An Introduction to Mathematical Cryptography.Springer-Verlag,2008.
[21] Koblitz N. A Course In Number Theory And Cryptography. Second edition. Springer-Verlag,1994.
[22] Koblitz N, Menezes A, Wu Y H, Zuccherato R J. Algebraic aspects of cryptography.Springer-Verlag,1999.
[23] Garrett P. Making, Breaking Codes: An Introduction to Cryptology. Prentice-Hall,2001.
[24] Mao W B. Modem Cryptography: Theory and Practice. Prentice-Hall,2003.
[25] Schneier B. Applied Cryptography. Second edition. John Wiley&Sons,1996.
[26] Denis T S, Rose G. BigNum Math: Implementing Cryptographic Multiple PrecisionArithmetic. Syngress Publishing,2006.
[27] Denis T S, Johnson S. Cryptography for Developers. Syngress Publishing,2007.
[28] Welschenbach M. Cryptography in C and C++. Second edition. Apress,2005.
[29]张方国，陈晓峰.基于身份的密码体制的研究综述.中国密码学发展报告2008.北京:电子工业出版社,2009.1-31.
[30] Shamir A. Identity-Based Cryptosystems and Signature Schemes. Advances inCryptology-CRYPTO1984, LNCS196. Berlin: Springer-Verlag,1984.47-53.
[31] Boneh D, Franklin M. Identity-based encryption from the weil pairing. SIAM Journal ofComputing.2003,32(206).586-615.
[32] Sakai R, Ohgishi K, Kasahara M. Cryptosystems based on pairing over elliptic curve.Symposium on Cryptography and Information Security,2001.
[33] Cocks C. An Identity Based Encryption Scheme Based on Quadratic Residues. Proceed-ings of the8th IMA International Conference on Cryptography and Coding, LNCS2260.Berlin: Springer-Verlag,2001.360-363.
[34] Freeman D, Scott M and Teske E. A Taxonomy of Pairing-Friendly Elliptic Curves. Jour-nal of Cryptology.2010,23(2).224-280.
[35] Galbraith S D. Pairings. Advances in Elliptic Curve Cryptography. Cambridge UniversityPress,2005.
[36] Menezes A, Okamoto T and Vanstone S A. Reducing Elliptic Curve Logarithms to Log-arithms in a Finite Field. IEEE Transactions on Information Theory.1993,39(5).1639-1646.
[37] Frey G, Ru¨ck H-G. A remark concerning m-divisibility and the discrete logarithm in thedivisor class group of curves. Mathematics of Computation.1994,62(206).865-874.
[38] Odlyzko A. Discrete Logarithms: The Past and the Future. Designs, Codes and Cryptog-raphy.2000,19(2-3).129-145.
[39] Husemo¨ler D. Elliptic Curves. Second edition. Springer-Verlag,2004.
[40] Schoof R. Nonsingular plane cubic curves over finite fields. Journal of CombinatorialTheory.1987,46(2).183-211.
[41] Waterhouse W. Abelian varieties over finite fields. Annales Scientifiques de l’écoleNormale Supérieure.1969,2(4).521-560.
[42] Balasubramanian R, Koblitz N. The Improbability That an Elliptic Curve Has Subexpo-nential Discrete Log Problem under the Menezes-Okamoto-Vanstone Algorithm. Journalof Cryptology.1998,11(2).141-145.
[43] Luca F, Shparlinski I. Elliptic curves with low embedding degree. Journal of cryptology.2006,19(4).553-562.
[44] Pohlig S, Hellman M. An improved algorithm for computing logarithms over GF(p) andits cryptographic significance. IEEE Transactions on Information Theory.1978,24(1).106-110.
[45] Silverman J H. The Arithmetic of Elliptic Curves. Second edition. Springer-Verlag,2009.
[46] Atkin A O L, Morain F. Elliptic curves and primality proving. Mathematics of Computa-tion.1993,61(203).39-68.
[47] Boneh D, Lynn B and Shacham H. Short signatures from the weil pairing. Advances inCryptology-ASIACRYPT2001, LNCS2248. Berlin: Springer-Verlag,2002.514-532.
[48] Joux A. A one round protocol for tripartite dife-hellman. Journal of Cryptology.2004,17(4).263-276.
[49] Paterson K G. Id-based signatures from pairings on elliptic curves. Electronics Let-ters.2002,38(18).1025-1026.
[50] Miller V S. The Weil Pairing and its Efcient Calculation. Journal of Cryptology.2004,17(4).235-261.
[51] Stange K. The Tate Pairing Via Elliptic Nets. Pairing-Based Cryptography-Pairing2007,LNCS4575. Berlin: Springer-Verlag,2007.329-384.
[52]赵昌安，张方国.双线性对有效计算研究进展述.软件学报.2009,20(11).3001-3009.
[53] Shipsey R. Elliptic Divibility Sequences. Ph.D dissertation, University of London,2001.
[54] Ward M. Memoir on elliptic divisibility sequences. American Journal of Mathematics.1948,70(1).31-74.
[55] Barreto P S L M, Galbraith S D,O′hE′igeartaigh C O, Scott M. Efcient pairing compu-tation onsupersingular abelian varieties. Designs, Codes and Cryptography.2007,42(3).239-271.
[56] Hess F, Smart N P, Vercauteren F. The Eta Pairing Revisited. IEEE Transactions on In-formation Theory.2006,52(10).4595-4602.
[57] Lee E, Lee H S, Park C M. Efcient and generalized pairing computation on abelianvarieties. IEEE Transactions on Information Theory.2009,55(4).1793-1803.
[58] Freeman D. Constructing Abelian Varieties for Pairing-Based Cryptography. Ph.D dis-sertation, Harvard University,2008.
[59] Lynn B. On the Implementation of Pairing-Based Cryptosystems. Ph.D. Dissertation,Stanford University,2007.
[60] Sto¨gbauer M. Efcient Algorithms for Pairing-Based Cryptosystems. Ph.D. Dissertation,Darmstadt University of Technology,2004.
[61]崔巍.基于双线性对的数字签名体制研究和设计.北京邮电大学博士论文，2009.
[62]林惜斌.椭圆曲线密码中标量乘与双线性对的快速算法研究.中山大学博士论文，2009.
[63]吴宏锋.椭圆曲线密码中的点乘与双线性对的计算.北京大学博士论文，2008.
[64]辛向军.几种具有附加性质的数字签名体制的研究.西安电子科技大学博士论文，2008.
[65]杨晨.基于双线性对的密码协议的设计与分析.西安电子科技大学博士论文，2008.
[66]赵昌安.双线性对的有效计算.中山大学博士论文，2008.
[67] Miyaji A, Nakabayashi M, Takano S. New explicit conditions of elliptic curve traces forFR-reduction. IEICE transactions on fundamentals of electronics, communications andcomputer sciences.2001, E84-A(5).1234-1243.
[68]柯召，孙琦.数论讲义.第二版.北京:高等教育出版社,2003.
[69] Page D, Smart N P, Vercauteren F. A comparison of MNT curves and supersingu-lar curves. Applicable Algebra in Engineering, Communication and Computing.2006,17(5).1025-1026.
[70] Scott M, Barreto P S L M. Generating More MNT Elliptic Curves. Designs, Codes andCryptography.2006,38(2).209-217.
[71] Galbraith S D, McKee J F, Valenc a P C. Ordinary abelian varieties having small embed-ding degree. Finite Fields and Their Applications.2007,13(4).800-814.
[72] Freeman D. Constructing Pairing-Friendly Elliptic Curves with Embedding Degree10.Algorithmic Number Theory Symposium-ANTS-VII, LNCS4076. Berlin: Springer-Verlag,2006.452-465.
[73] Barreto P S L M, Naehrig M. Pairing-Friendly Elliptic Curves of Prime Order. SelectedAreas in Cryptography-SAC2005, LNCS3897. Berlin: Springer-Verlag,2006.319-331.
[74] Beuchat J L, Diaz J E G, Mitsunari S, Okamoto E, Rodriguez-Henriquez F, Teruya T.High-Speed Software Implementation of the Optimal Ate Pairing over Barreto-NaehrigCurves. Pairing-Based Cryptography-Pairing2010, LNCS6487. Berlin: Springer-Verlag,2010.21-39.
[75] Devegili A J, Scott M, Dahab R. Implementing Cryptographic Pairings over Barreto-Naehrig Curves. Pairing-Based Cryptography-Pairing2007, LNCS4575. Berlin:Springer-Verlag,2007.197-207.
[76] Fan J F, Vercauteren F, Verbauwhede I. Faster Fp-arithmetic for Cryptographic Pairingson Barreto-Naehrig Curves. Cryptographic Hardware and Embedded Systems-CHES2009, LNCS5747. Berlin: Springer-Verlag,2009.240-253.
[77] Masataka A, Yasuyuki N, Yoshitaka M. Fast Ate Pairing Computation of EmbeddingDegree12Using Subfield-Twisted Elliptic Curve. IEICE Transactions on Fundamentalsof Electronics, Communications and Computer Sciences.2009. E92-A(2).508-516.
[78] Sakemi Y, Nogami Y, Kato H, Morikawa Y. Cross twisted Xate pairing with Barreto-Naehrig curve for multi-pairing technique. Proceedings of the2009IEEE internationalconference on Symposium on Information Theory-ISIT’09,2009.2386-2390.
[79] Sakemi Y, Kato H, Takeuchi S, Nogami Y, Morikawa Y. Two Improvements of TwistedAte Pairing with Barreto-Naehrig Curve by Dividing Miller’s Algorithm. Advances inInformation Sciences and Service Sciences.2010,2(4).1-13.
[80] Dupont R, Enge A, Morain F. Building Curves with Arbitrary Small MOV Degree overFinite Prime Fields. Journal of Cryptology.2005,18(2).79-89.
[81]张禾瑞，郝鈵新.高等代数.第四版.北京:高等教育出版社，1999.
[82] Barreto P S L M, Lynn B, Scott M. Constructing Elliptic Curves with Prescribed Embed-ding Degrees. Proceedings of the3rd international conference on Security in communi-cation networks-SCN2002, LNCS2576. Berlin: Springer-Verlag,2002.263-273.
[83] Duursma I, Lee H S. Tate pairing implementation for hyperelliptic curves y2=xp x+d. Advances in Cryptology-ASIACRYPT2003, LNCS2894. Berlin: Springer-Verlag,2003.111-123.
[84] Matsuda S, Kanayama N, Hess F, Okamoto E. Optimised Versions of the Ate and TwistedAte Pairings. The11th IMA International Conference on Cryptography and Coding,LNCS4887. Berlin: Springer-Verlag,2007.302-312.
[85] Zhao C A, Zhang F G, Huang J W. A note on the Ate pairing. International Journal ofInformation Security.2008,7(6).379-382.
[86] Vercauteren F. Optimal pairings. IEEE Transactions on Information Theory.2010,56(1).455-461.
[87] Galbraith S D, Harrison K, Soldera D. Implementing the tate pairing. Algorithmic Num-ber Theory Symposium-ANTS-V, LNCS2369. Berlin: Springer-Verlag,2002.69-86.
[88] Eisentra¨ger K, Lauter K, Montgomery P L. Fast elliptic curve arithmetic and improvedWeil pairing evaluation. CT-RSA2003, LNCS2612. Berlin: Springer-Verlag,2003.343-354.
[89] Blake I, Murty K, Xu G. Refinements of miller’s algorithm for computing weil/tate pair-ing. Journal of Algorithms.2006,58(2).134-149.
[90] Eisentra¨ger K, Lauter K, Montgomery P L. Improved Weil and Tate Pairings for Ellipticand Hyperelliptic Curves. Algorithmic Number Theory Symposium-ANTS-VI, LNCS3076. Berlin: Springer-Verlag,2004.169-183.
[91] Kobayashi T, Aoki K, Imai H. Efcient algorithms for Tate pairing. IEICE Transactionson Fundamentals of Electronics, Communications and Computer Sciences.2006, E89-A(1).134-143.
[92] Zhao C A, Zhang F G, Huang J W. Efcient Tate pairing computation using double-basechains. Science in China Series F: Information Sciences.2008,51(8).1096-1105.
[93] Scott M. Faster pairings using an elliptic curve with an efcient endomorphism. Progressin Cryptology-INDOCRYPT2005, LNCS3797. Berlin: Springer-Verlag,2005.258-269.
[94] Ionica S, Joux A. Pairing computation on elliptic curves with efciently computable en-domorphism and small embedding degree. Pairing-Based Cryptography-Pairing2010,LNCS6487. Berlin: Springer-Verlag,2010.435-449.
[95] Scott M, Benger N, Charlemagne M, Perez L J D, Kachisa E J. On the Final Exponenti-ation for Calculating Pairings on Ordinary Elliptic Curves. Pairing-Based Cryptography-Pairing2009, LNCS5671. Berlin: Springer-Verlag,2009.78-88.
[96] Lin X B, Zhao C A, Zhang F G, Wang Y M. Computing the Ate Pairing on Elliptic Curveswith Embedding Degree k=9. IEICE Transactions on Fundamentals of Electronics,Communications and Computer Sciences.2008. E91-A(9).2387-2393.
[97] Barreto P S L M, Lynn B, Scott M. On the selection of pairing-friendly groups. SelectedAreas in Cryptography-SAC’2003, LNCS3006. Berlin: Springer-Verlag,2003.17-25.
[98] Galbraith S D, Paterson K, Smart N. Pairings for cryptographers. Discrete Applied Math-ematics.2008,156(16).3113-3121.
[99] Granger R, Paterson K, Smart N. High security pairing-based cryptography revisited.Algorithmic Number Theory Symposium-ANTS-VII, LNCS4076. Berlin: Springer-Verlag,2006.480-494.
[100] Hitt L. On the minimal embedding field. Pairing-Based Cryptography-Pairing2007,LNCS4575. Berlin: Springer-Verlag,2007.294-301.
[101] Koblitz N, Menezes A. Pairing-based cryptography at high security levels. Cryptographyand Coding:10th IMA International Conference, LNCS3796. Berlin: Springer-Verlag,2005.13-36.
[102] Scott M. Computing the Tate pairing. The Cryptographer’s Track at RSA Conference-CT-RSA2005, LNCS3376. Berlin: Springer-Verlag,2005.293-304.
[103] Harrison K, Page D, Smart N P. Software implementation of finite fields of characteristicthree, for use in pairing-based cryptosystems. LMS Journal of Computation and Mathe-matics.2002,5.181-193.
[104] Naehrig M, Niederhagen R, Schwabe P. New software speed records for cryptographicpairings. Progress in cryptology: cryptology and information security in Latin America-LATINCRYPT’10, LNCS6212. Berlin: Springer-Verlag,2010.109-123.
[105] Perez L J D, Kachisa E J, Scott M. Implementing cryptographic pairings: a magmatutorial. IACR Cryptology ePrint Archive, Report2009/072,2009. Available fromhttp://eprint.iacr.org/2009/072.
[106] Scott M, Costigan N, Abdulwahab W. Implementing Cryptographic Pairings on Smart-cards. Cryptographic Hardware and Embedded Systems-CHES2006, LNCS4249.Berlin: Springer-Verlag,2006.134-147.
[107] Kocher P C. Timing Attacks on Implementations of Dife-Hellman, RSA, DSS, andOther Systems. Advances in Cryptology-CRYPTO1996, LNCS1109. Berlin: Springer-Verlag,1996.104-113.
[108] Kocher P C, Jafe J, Jun B. Diferential Power Analysis. Advances in Cryptology-CRYPTO1999, LNCS2139. Berlin: Springer-Verlag,1996.388-397.
[109] El Mrabet N, Flottes M L, Di Natale G. A practical Diferential Power Analysis attackagainst the Miller algorithm. The5th International Conference on Ph.D. Research inMicroelectronics&Electronics-PRIME2009,2009.308-311.
[110] Ghosh S, Mukhopadhyay D, Chowdhury D R. Fault Attack and Countermeasures onPairing Based Cryptography. International Journal of Network Security.2011,12(1).21-28.
[111] Kim T H, Takagi T, Han D-G, Kim H W, Lim J. Side Channel Attacks and Counter-measures on Pairing Based Cryptosystems over Binary Fields. Cryptology and NetworkSecurity-CANS2006, LNCS4301. Berlin: Springer-Verlag,2006.168-181.
[112] Ozturk E. Efcient and Tamper-Resilient Architectures for Pairing Based Cryptography.Ph.D dissertation, Worcester Polytechnic Institute,2009.
[113] Page D. Vercauteren F. A Fault Attack on Pairing-Based Cryptography. IEEE Transac-tions on Computers.2006,55(9).1075-1080.
[114] PBC. The Pairing-Based Cryptography Library. Available fromhttp://crypto.stanford.edu/pbc/.
[115] MIRACL. Multiprecision Integer and Rational Arithmetic C/C++Library. Availablefrom http://www.shamus.ie/.
[116] Ash R B. Abstract Algebra: The Basic Graduate Year. Available fromhttp://www.math.uiuc.edu/r-ash/Algebra.html.
[117]范德瓦尔登.代数学I.北京:科学出版社,1978.
[118]聂灵沼，丁石孙.代数学引论.第二版.北京:高等教育出版社,2000.
[119]万哲先.代数和编码.第三版.北京:高等教育出版社,2007.
[120]张禾瑞.近世代数基础.修订本.北京:高等教育出版社，2005.
[121] Blake I F, Seroussi G, Smart N P. Elliptic Curves in Cryptography. Cambridge UniversityPress,1999.
[122]裴定一，祝跃飞.算法数论.第一版.北京：科学出版社,2002.
[123]吴铤，董军武，王明强译.椭圆曲线及其在密码学中的应用―导引.北京：科学出版社,2007.
[124]周玉洁，冯登国.公开密钥密码算法及其快速实现.第一版.北京:国防工业出版社,2002.
[125]祝跃飞，张亚娟.椭圆曲线公钥密码导引.第一版.北京:科学出版社,2006.
[126] Washington L C. Elliptic Curves: Number Theory and Cryptography. Second edition.Chapman&Hall/CRC,2008.
[127] Lay G-J, Zimmer H G. Constructing elliptic curves with given group order over largefinite fields. Algorithmic Number Theory Symposium-ANTS-I, LNCS877. Berlin:Springer-Verlag,1994.452-465.
[128] Savas E, Schmidt T A, Koc C K. Generating Elliptic Curves of Prime Order. Third In-ternational Workshop on Cryptographic Hardware and Embedded Systems-CHES01,LNCS2162. Berlin: Springer-Verlag,2001.145-161.
[129] Cox D A. Primes of the Form x2+ny2: Fermat, Class Field Theory, and ComplexMultiplication. John Wiley&Sons,1989.
[130] Cohen H, Frey G (Editors). Handbook of Elliptic and Hyperelliptic Curve Cryptography.Chapman&Hall/CRC,2006.
[131] Martin L. Introduction to Identity-Based Encryption. Artech House,2008.
[132] Barreto P S L M, Kim H Y, Lynn B and Scott M. Efcient algorithms for pairing-basedcryptosystems. Advances in Cryptology-CRYPTO2002, LNCS2442. Berlin: Springer-Verlag,2002.354-369.
[133] Pollard J. Monte-Carlo methods for index computation mod p. Mathematics of Compu-tation.1978,32(143).918-924.
[134] Silverman J H. The Xedni Calculus and the Elliptic Curve Discrete Logarithm Problem.Designs, Codes and Cryptography.2000,20(1).5-40.
[135] Baier H. Efcient Algorithms for Generating Elliptic Curves over Finite Fields Suitablefor Use in Cryptography. Ph.D dissertation, Darmstadt University of Teetmology,2002．
[136] Bro¨ker R. Constructing elliptic curves of prescribed order. Ph.D dissertation, Leiden Uni-versity,2006.
[137] Lang S. Algebra. Revised Third edition. Springer-Verlag,2002.
[138] Lidl R, Niederreiter H. Finite Fields. Second edition. Cambridge University Press,1997.
[139] McEliece R J. Finite Fields for Computer Scientists and Engineers. Springer-Verlag,1987.
[140] Washington L C. Introduction to Cyclotomic Fields. Second edition. Springer-Verlag,1997.
[141]华罗庚.数论导引.第一版.北京:科学出版社,1957.
[142] Comuta A, Kawazoe M, Takaharashi T. Pairing-friendly elliptic curves with small se-curity loss by Cheon’s algorithm. Proceedings of the10th international conference onInformation security and cryptology-ICISC’07, LNCS4817. Berlin: Springer-Verlag,2007.297-308.
[143] Duan P, Cui S, Chan C W. Special polynomial families for generating more suitablepairing-friendly elliptic curves. Proceedings of the5th WSEAS International Conferenceon Electronics, Hardware, Wireless and Optical Communications. Wisconsin: WorldScientific and Engineering Academy and Society (WSEAS),2006.187-192.
[144] Karabina K, Teske E. On prime-order elliptic curves with embedding degrees3,4and6. Algorithmic Number Theory Symposium-ANTS-VIII, LNCS5011. Berlin: Springer-Verlag,2008.102-117.
[145]冯克勤.代数数论.第一版.北京:科学出版社,2000.
[146]张贤科.代数数论导引.第二版.北京:高等教育出版社，2006.
[147] Gaa′l I, Robertson L. Power integral bases in prime-power cyclotomic fields. Journal ofNumber Theory.2006,120(2).372-384.
[148] Robertson L. Power Bases for Cyclotomic Integer Rings. Journal of Number Theory.1998,69(1).98-118.
[149] Gyo¨ry K. Sur les polyno mes a`coefcients entiers et de discriminant donne′, III, Publ.Math. Debrecen.1976,23.141-165.
[150] Robertson L. Power Bases for2-Power Cyclotomic Fields. Journal of Number Theory.2001,88(1).196-209.
[151] Kachisa E J, Schaefer E F and Scott M. Constructing Brezing-Weng pairing friendlyelliptic curves using elements in the cyclotomic field. Proceedings of Pairing-BasedCryptography-Pairing2008, LNCS5209. Berlin: Springer-Verlag,2008.126-135.
[152] Satoru T, Ken N. More constructing pairing-friendly elliptic curves forcryptography.Pairing-Based Cryptography-Pairing2008, LNCS5209. Berlin: Springer-Verlag,2008.136-145.
[153] Crandall R, Pomerance C. Prime Numbers: A Computational Perspective. Springer-Verlag,2005.
[154] Chang C C, Lou D C. Fast parallel computation of multi-exponentiation for public keycryptosystems. Proceedings of the Fourth IEEE International Conference on Parallel andDistributed Computing, Applications and Technologies (PDCAT),2003.955-958.
[155] Chiou C W. Parallel implementation of the RSA public-key cryptosystem. InternationalJournal of Computer Mathematics.1993,48(3).153-155.
[156] Gallant R P, Lambert R J and Vanstone S A. Faster point multiplication on elliptic curveswith efcient endomorphisms. Advances in Cryptology-CRYPTO2002, LNCS5209.Berlin: Springer-Verlag,2001.190-200.
[157] Cohen H. A course in computational algebraic number theory. Springer-Verlag,1993.
[158] Dimitrov V S, Imbert L, Mishra P K. Efcient and Secure Elliptic Curve Point Multipli-cation Using Double-Base Chains. Advances in Cryptology-ASIACRYPT2005, LNCS3788. Berlin: Springer-Verlag,2005.59-78.