双线性对快速计算中的多项式选取

苏志图，李 晖，马建峰

(西安电子科技大学计算机网络与信息安全教育部重点实验室 西安 710071)

如何高效地实现密码算法是公钥密码体制中的重要问题。在基于身份的密码体制中，双线性对的计算效率是影响整个密码算法性能的关键[1-4]。目前，所有的双线性对快速计算方法都建立在M iller算法[5]的基础上。因此优化M iller算法一直是基于身份的密码体制中的重要研究课题[6-7]。双线性对快速计算的当前研究就如何减少M iller算法中的循环次数以提高计算效率，提出了一些新的双线性对，如eta对[1]、ate对[2]、 Atei对[8]。

1 一些背景知识

2 多项式选取

3 结 论

[1] BARRETO P, GALBRAITH S, HIGEARTAIGH C, et al.Efficient pairing computation on supersingular abelian varieties[J]. Designs, Codes and Cryptography, 2007, 42:239-271.

[2] HESS F, SMART N, VERCAUTEREN F. The eta pairing revisited[J]. IEEE Transactions on Information Theory,2006, 52: 4595-4602.

[3] MATSUDA S, KANAYAMA N, HESS F, et al. Optimised versions of the ate and tw isted ate pairings[C]//Cryptography and Coding 2007: Lecture Notes in Computer Science 4887. Berlin: Springer-verlag, 2007:302-312.

[4] DUURSMA I, LEE H S. Tate pairing implementation for hyperelliptic curves[C]//Advances in Cryptology-ASIACRYPT 2003: Lecture Notes in Computer Science 2894. Berlin: Springer-verlag, 2003: 111-123.

[5] M ILLER V. The Weil pairing and its efficient calculation[J]. Journal of Cryptology, 2004, 17: 235-261.

[6] 赵昌安，张方国. 双线性对有效计算研究进展[J]. 软件学报, 2009, 20(11): 3001-3009.

ZHAO Chang-an, ZHANG Fang-guo. Research and development on efficient pairing computations[J]. Journal of Software, 2009, 20(11): 3001-3009.

[7] 胡磊. 椭圆曲线Tate对的压缩[J]. 软件学报, 2007, 18(7):1799-1805.

HU Lei. Compression of tate pairings on elliptic curves[J].Journal of Software, 2007, 18(7): 1799-1805.

[8] ZHAO C A, ZHANG F G, HUANG J W. A note on the ate pairing[J]. International Journal of Information Security,2008, 7: 379-382.

[9] BLAKE I, SEROUSSI G, SMART N. Advances in elliptic curve cryptography[M]. New York: Cambridge University Press, 2005: 183-213.

[10] FREEMAN D. Constructing abelian varieties for pairing-based cryptography[D]. Berkeley: University of California, 2008.

[11] BARRETO P, KIM H, LYNN B, et al. Efficient algorithms for pairing-based cryptosystems[C]//Advances in Cryptology CRYPTO 2002: Lecture Notes in Computer Science 2442. Berlin: Springer-verlag, 2002: 354-369.

[12] SILVERMAN J. The arithmetic of elliptic curves[M]. New York : Springer-Verlag, 2009: 137-157.

编 辑 张 俊