ηT配对的配对域F36m上的最优乘法算法

北京大学学报（自然科学版）

η_T配对的配对域F_3^6m上的最优乘法算法

亓延峰¹,贾大江²,唐春明¹,徐茂智^1,3

1. 北京大学数学科学学院,北京100871; 2.国家电网公司山西省电力公司, 太原030001;3. 网络与软件安全保障教育部重点实验室,北京100871;

收稿日期:2010-05-14 出版日期:2010-09-20 发布日期:2010-09-20

Optimal Multiplication Algorithm for the η_T Pairing over F_3^6m

QI Yanfeng¹, JIA Dajiang², TANG Chunming¹, XU Maozhi^1,3

1. School of Mathematical Sciences, Peking University, Beijing 100871; 2. Shanxi Electronic Power Corporation, National Grid Corporation, Taiyuan 030001; 3. Key Laboratory of Network and Software Security Assurance, Beijing 100871;

Received:2010-05-14 Online:2010-09-20 Published:2010-09-20

摘要/Abstract

摘要： 在基于配对的公钥密码学应用中, 配对的有效快速实现依赖于基域的扩域中乘法算法的有效快速的实现,特别是在η_T配对的实现中需要 F_3^6m中的快速乘法运算。作者提出了对偶插值算法, 其渐近复杂度为 11 次基域中的乘法运算, 这达到了F_3^6m中乘法运算的理论下界。

关键词: 基于配对的密码学, 有限域乘法, Vandermonde矩阵, 对偶多项式插值

Abstract: In the application of pairing based cryptosystems, especially the η_T pairing, the fast and effective implementation of the pairings depends on the effective multiplications in the extension fields. The authors propose the dual interpolation multiplication (DIM) algorithm in F_3^6m which takes asymptotically 11 multiplications in F3m ( m→∞) . This algorithm reaches the theoretical lower bound of the number multiplications in F_3^6m.

Key words: pairing based cryptosystems, multiplications in finite fields, Vandermonde matrix, interpolation of dual polynomials

中图分类号:

TN918

亓延峰,贾大江,唐春明,徐茂智. η_T配对的配对域F_3^6m上的最优乘法算法[J]. 北京大学学报（自然科学版）.

QI Yanfeng,JIA Dajiang,TANG Chunming,XU Maozhi. Optimal Multiplication Algorithm for the η_T Pairing over F_3^6m[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

导出引用管理器 EndNote|Ris|BibTeX

链接本文: https://xbna.pku.edu.cn/CN/

https://xbna.pku.edu.cn/CN/Y2010/V46/I5/749

[1]	殷勍, 王念平. Piccolo结构抵抗差分和线性密码分析能力的进一步评估[J]. 北京大学学报自然科学版, 2018, 54(6): 1173-1178.
[2]	张凯,关杰,张中亚,罗磊. 混合密码SCB算法的密钥恢复攻击[J]. 北京大学学报（自然科学版）, 2013, 49(3): 397-403.
[3]	尹华军,张习勇. 一类二次函数指数和的简化计算[J]. 北京大学学报（自然科学版）, 2012, 48(5): 695-700.
[4]	张中亚,关杰,丁林. 一个改进的 Salsa20 流密码算法[J]. 北京大学学报（自然科学版）, 2011, 47(2): 201-207.
[5]	胡志,周正华,徐茂智. 用有效可计算自同态来计算Tate配对[J]. 北京大学学报（自然科学版）, 2010, 46(5): 685-690.
[6]	曹浩,魏仕民,卓泽鹏,王会歌. 具有最大代数免疫阶的布尔函数的新构造[J]. 北京大学学报（自然科学版）, 2010, 46(5): 704-708.
[7]	谭林,戚文峰. l-序列的采样元素分布及k-错线性复杂度[J]. 北京大学学报（自然科学版）, 2010, 46(5): 715-719.
[8]	程庆丰,魏福山,马传贵. 一种抗DoS攻击的密钥交换协议[J]. 北京大学学报（自然科学版）, 2010, 46(5): 720-724.
[9]	熊晓雯,付绍静,屈龙江. 具有最大代数免疫度的偶数元布尔函数的计数[J]. 北京大学学报（自然科学版）, 2010, 46(5): 725-730.
[10]	徐茂智,喻洪辉,唐春明,亓延峰. 二元域上Edwards型椭圆曲线的配对计算[J]. 北京大学学报（自然科学版）, 2010, 46(5): 736-742.
[11]	唐春明,亓延峰,徐茂智. 实现k=18的Brezing-Weng曲线的最优配对[J]. 北京大学学报（自然科学版）, 2010, 46(5): 743-748.
[12]	游建雄,李瑞林,李超. 轻量级分组密码KeeLoq的故障攻击[J]. 北京大学学报（自然科学版）, 2010, 46(5): 756-762.