双基数链算法计算Tate对的一种改进

doi:10.3969/j.issn.0372-2112.2012.09.012

电子学报 ›› 2012, Vol. 40 ›› Issue (9): 1775-1782.DOI: 10.3969/j.issn.0372-2112.2012.09.012

双基数链算法计算Tate对的一种改进

翁江, 豆允旗, 马传贵

信息工程大学信息工程学院, 河南郑州 450002

收稿日期:2011-09-20 修回日期:2012-02-15 出版日期:2012-09-25
- 作者简介:
- 翁江 男,1986年3月出生于陕西省西安市.现为信息工程大学信息工程学院博士研究生.主要研究方向为椭圆曲线双线性对快速计算及其侧信道攻击. E-mail:wengjiang858@163.com 豆允旗 男,1987年9月出生于河南省商丘市.现为信息工程大学信息工程学院硕士研究生.主要研究方向为椭圆曲线侧信道攻击. E-mail:douyunqi@126.com 马传贵 男,1962年4月出生于山东省菏泽市.现为信息工程大学信息工程学院教授、博士生导师.主要研究方向为密码学和无线网络安全. E-mail:chuanguima@sina.com
- 基金资助:
- 国家高技术研究发展计划 (863计划)课题 (No.2009AA01Z417)

Refinements of Double-Base Chains Algorithm for Computing Tate Pairing

WENG Jiang, DOU Yun-qi, MA Chuan-gui

Institute of Information Engineering, Information Engineering University, Zhengzhou, Henan 450002, China

Received:2011-09-20 Revised:2012-02-15 Online:2012-09-25 Published:2012-09-25
- Supported by:
- Subject of National High-tech R&D Program of China (863 Program) (No.2009AA01Z417)

摘要/Abstract

摘要： 双线性对在基于身份的密码体制中有着广泛的应用.Miller算法是计算双线性对的核心算法.本文在双基数链计算Tate对的基础上给出了一种高效的Miller算法.通过范函数和共轭技巧的应用,减少了Miller算法中有理函数直线和垂线的数量并用共轭代替了求逆运算.结果表明新算法与已有算法相比效率提高了10%以上.

关键词: 双基数链, Miller算法, Tate对, 椭圆曲线

Abstract: Pairings have been widely used in the study of identity-based cryptosystems (IBC).Miller algorithm is the key of computing pairings.We propose an efficient Miller algorithm computing Tate pairing based on the double-base chain.Through the application of norm function and conjugate technique,our refinements reduce the total number of lines and vertical lines in the rational function,and replace the inverse by its conjugate in Miller algorithm.Results show that the efficiency of our algorithm can be improved by more than 10% compared with the previous method.

Key words: double-base chains, Miller algorithm, Tate pairing, elliptic curve

中图分类号:

TP309

翁江, 豆允旗, 马传贵. 双基数链算法计算Tate对的一种改进[J]. 电子学报, 2012, 40(9): 1775-1782.

WENG Jiang, DOU Yun-qi, MA Chuan-gui. Refinements of Double-Base Chains Algorithm for Computing Tate Pairing[J]. Acta Electronica Sinica, 2012, 40(9): 1775-1782.

参考文献

[1] A J Menezes,T Okamoto,S A Vanstone.Reducing elliptic curve logarithms to logarithms in a finite field [J].IEEE Transaction on Information Theory,1993,39(5):1639-1646.
[2] G Frey,H G Ruck.A remark concerning m-divisibility and the discrete logarithm in divisor class group of curves [J].Mathematics of Computation,1994,62 (206):865-874.
[3] A Shamir.Identity-based cryptosystems and signature schemes. Advances in Cryptology-Crypto’84. Berlin Heidelberg:Springer-Verlag,1984.47-53.
[4] R Sakai,K Ohgishi,M Kasahara.Cryptosystems based on pairing. Symposium on Cryptography and Information Security. Japan:Okinawa,2000.26-28.
[5] A Joux.A one round protocol for tripartite Diffie-Hellman. ANTS-4:Proceedings of the 4^th International Symposium on Algorithmic Number Theory. Berlin Heidelberg:Springer-Verlag,2000.385-394.
[6] D Boneh,M Franklin.Identity-based encryption from the Weil pairing. Advances in Cryptology-Crypto’2001. Berlin Heidelberg:Springer-Verlag,2001.213-229.
[7] F Zhang,R Safavi-Naini,W Susilo.An efficient signature scheme from bilinear pairings and its applications. Public Key Cryptography-PKC’2004. Berlin Heidelberg:Springer-Verlag,2004.277-290.
[8] 祁明,L Harn.基于离散对数的若干新型代理签名方案 [J].电子学报,2000,28(11):114-118. Qi Ming,L Harn.Some new proxy signature schemes based on discrete logarithms. Acta Electrionica Sinica,2000,28(11):114-118.(in Chinese)
[9] V S Miller.The Weil pairing and its efficient calculation [J].Journal of Cryptology,2004,17(04):235-261.
[10] K E Stange.The Tate pairing via elliptic nets. Pairing-Based Cryptography Pairing 2007. Berlin Heidelberg:Springer-Verlag,2007.329-348.
[11] C A Zhao,F G Zhang,J W Huang.Efficient Tate paring computation using double-base chains [J].Science in China series F-Information sciences,2008,51(08):1096-1105.
[12] 陈厚友,马传贵.基于双基数链的Tate对快速算法 [J].电子学报,2011,39(2):408-413. Chen Hou-you,Ma Chuan-gui.Fast Tate pairing algorithm using double-base chains [J].Acta Electrionica Sinica,2011,39 (2):408-413.(in Chinese)
[13] P S L M Barreto,S D Galbraith,C Eigeartaig,M Scott.Efficient pairing computation on supersingular abelian varieties [J].Designs,Codes Cryptography,2007,42(3):239-271.
[14] F Hess,N P Smart,F Vercauteren.The Eta pairing revisited [J].IEEE Transactions on Information Theory,2006,52(10):4595-4602.
[15] F Vercauteren.Optimal pairings [J].IEEE Transactions on Information Theory,2010,56(1):455-461.
[16] V Dimitrov,G Jullien.Loading the bases:A new number representation with applications [J].IEEE Circuits and Systems Magazine,2003,3(2):6-23.
[17] V S Dimitrov,L Imbert,P K Mishra.Efficient and secure elliptic curve point multiplication using double-base chains. ASIACRYPT 2005. Berlin Heidelberg:Springer-Verlag,2005.59-78.
[18] M Scott.Implementing cryptographic pairings. Pairing 2007. Tokyo:LCNS,2007.177-196.
[19] P S L M Barreto,H Y Kim,B Lynn,M Scott.Efficient algorithms for pairing based cryptosystems. Cryptology-Cryto’2002. Berlin Heidelberg:Springer-Verlag,2002.354-368.
[20] I F Blake,V K Murty,G W Xu.Refinements of Miller’s algorithm for computing the Weil/Tate pairing [J].Journal of Algorithms,2006,58(2):34-149.
[21] D E Knuth.The Art of Computer Programming [M].Massachusetts:Addison-Wesley,1988.
[22] IEEE P1363,Standard Specifications For Public Key Cryptography [S].
[23] M Ciet,M Joye,K Lauter,P L Montgomery.Trading inversions for multiplications in elliptic curve cryptography [J].Designs,Codes and Cryptography,2006,39(2):189-206.
[24] T Kobayashi,K Aoki,H Imai.Efficient algorithms for tate pairing [J].IEICE Trans on Fundamentals,2006,E89-A(1):134-143.

双基数链算法计算Tate对的一种改进

Refinements of Double-Base Chains Algorithm for Computing Tate Pairing

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	翁江, 姬伟峰, 吴玄, 李映岐, 张林锋, 孟浩. Jacobi Quartic曲线上GLV/GLS标量乘算法[J]. 电子学报, 2021, 49(9): 1783-1789.
[2]	李森森, 黄一才, 郁滨, 鲍博武. 基于PUF的低开销物联网安全通信方案[J]. 电子学报, 2019, 47(4): 812-817.
[3]	翁江, 康晓春, 豆允旗, 马传贵. 一类j=0超奇异椭圆曲线的性质及其标量乘算法[J]. 电子学报, 2018, 46(9): 2131-2138.
[4]	陈昕, 宋亚鹏, 刘志强. 一种新型的LTE-A网络切换认证协议[J]. 电子学报, 2017, 45(2): 485-491.
[5]	张文芳, 王小敏, 郭伟, 何大可. 基于椭圆曲线密码体制的高效虚拟企业跨域认证方案[J]. 电子学报, 2014, 42(6): 1095-1102.
[6]	陈琳;孙万忠;陈性元;戴紫彬. 基于有符号数字系统的Montgomery模逆算法及其硬件实现[J]. 电子学报, 2012, 40(3): 489-494.
[7]	张李军;王鲲鹏. 环Z_n上椭圆曲线的群法则及其在Paillier系统中的应用[J]. 电子学报, 2011, 39(8): 1733-1738.
[8]	黎明;吴丹;戴葵;邹雪城. 高性能可扩展公钥密码协处理器研究与设计[J]. 电子学报, 2011, 39(3): 665-670.
[9]	邵春雨;苏锦海;魏有国;周晶晶. 一种双矩阵组合公钥算法[J]. 电子学报, 2011, 39(3): 671-674.
[10]	陈厚友;马传贵. 基于双基数链的Tate对快速算法[J]. 电子学报, 2011, 39(2): 408-413.
[11]	王念平. 一种新的五元联合稀疏形式表示算法及其应用[J]. 电子学报, 2011, 39(1): 114-118.
[12]	冯涛;王毅琳;马建峰. 一种新的基于椭圆曲线密码体制的 Ad hoc组密钥管理方案[J]. 电子学报, 2009, 37(5): 918-924.
[13]	鲍皖苏;陈辉. 基于双基表示的并列点乘算法[J]. 电子学报, 2009, 37(4): 873-876.
[14]	代战锋;温巧燕;李小标. 基于分布式PKI的P2P网络认证技术[J]. 电子学报, 2009, 37(11): 2561-2564.
[15]	曹天杰, 雷红. 基于椭圆曲线的隐私增强认证密钥协商协议[J]. 电子学报, 2008, 36(2): 397-401.